データ構造のサイズが通常2 ^ nであるのはなぜですか？

StackOverflow https://stackoverflow.com/questions/1816727

質問

歴史的な理由などはありますか？ char foo[256];や#define BUF_SIZE 1024のようなものを見たことがあります。私はほとんどが2 n サイズのバッファしか使用していません。これは主に、よりエレガントに見えると思うからであり、そのように特定の数を考える必要はありません。しかし、それがほとんどの人がそれらを使用する理由であるかどうかはよくわかりませんが、より多くの情報が評価されるでしょう。

役に立ちましたか？

解決

多くの人があなたが言うように習慣からそれをするが、多くの人がそうするけれども、いくつかの理由があるかもしれません。

非常に有用な場所の1つは、特に％演算子が高価なアーキテクチャ（ハードウェア分割なし-主に8ビットのマイクロコントローラー）での循環バッファの効率的な実装です。この場合、2 ^ nバッファーを使用するモジュロは、単に上位ビットをビットマスクする場合、または256バイトバッファーの場合は、8ビットインデックスを使用してラップアラウンドさせることです。 / p>

他の場合では、ページ境界、キャッシュなどとの整合により、一部のアーキテクチャで最適化の機会が提供される場合がありますが、これはアーキテクチャ固有のものです。しかし、そのようなバッファーはコンパイラーに最適化の可能性を提供しているだけかもしれません。そのため、他のすべての条件は同じです。なぜですか？

他のヒント

キャッシュ行は通常2の倍数です（多くの場合32または64）。その数の整数倍のデータは、対応する数のキャッシュラインに収まる（そして完全に利用する）ことができます。キャッシュにパックできるデータが多いほど、パフォーマンスが向上します。したがって、そのように構造を設計する人々は、そのために最適化すると思います。

他の誰もが言及したことに加えて、SSE命令は複数の要素を取り、要素の入力数は常に2の累乗であるという別の理由があります。バッファを2のべき乗にすることで、未割り当てメモリを読み取らないことが保証されます。ただし、これは実際にSSE命令を使用している場合にのみ適用されます。

最終的には、ほとんどの場合の圧倒的な理由は、プログラマが2のべき乗を好むからだと思います。

ハッシュテーブル、ページごとの割り当て

これは、サイズを法とするインデックスを計算し、そのサイズが2の累乗である場合、単純な bitwise-and または＆amp; は、％演算子を実装するはるかに低速な除算クラス命令を使用するのではなく、

古いIntel i386の本を見ると、 and は2サイクル、 div は40サイクルです。全体のサイクル時間は1000倍高速であるため、最も遅いマシン操作の影響も隠される傾向がありますが、分割の根本的な複雑さがはるかに大きいため、現在も不均衡が続いています。

また、mallocのオーバーヘッドが非常に長く回避される場合もありました。オペレーティングシステムから直接利用可能な割り当ては、特定のページ数（まだ）であるため、2の累乗が割り当ての粒度を最大限に活用する可能性があります。

そして、他の人が指摘したように、プログラマは2のべき乗が好きです。

頭の上のいくつかの理由を考えることができます：

  1. 2 ^ nは、すべてのコンピューターサイズで非常に一般的な値です。これは、ビットがコンピューターで表現される方法（2つの可能な値）に直接関係しています。つまり、変数は、境界が2 ^ nの値の範囲を持つ傾向があります。
  2. 上記の点により、バッファのサイズとして値256を見つけることがよくあります。これは、1バイトに格納できる最大数だからです。したがって、文字列のサイズとともに文字列を保存する場合、 SIZE_BYTE + ARRAY として保存すると最も効率的です。ここで、サイズバイトはサイズを示します配列。つまり、配列は1〜256の任意のサイズにできます。
  3. 他の多くの場合、サイズは物理的なものに基づいて選択されます（たとえば、オペレーティングシステムが選択できるメモリのサイズはCPUのレジスタのサイズなどに関連しています）。特定のビット数。つまり、使用できるメモリの量は通常2 ^ nの値になります（32ビットシステムの場合は2 ^ 32）。
  4. このような値には、パフォーマンス上の利点/調整の問題がある可能性があります。ほとんどのプロセッサは一度に一定量のバイトにアクセスできるため、サイズが20ビットの変数がある場合でも、32ビットプロセッサは32ビットを読み取ります。したがって、多くの場合、変数を32ビットにするだけの方が効率的です。また、一部のプロセッサでは、変数が特定のバイト数に揃えられるように必要にします（たとえば、メモリ内の奇数のアドレスからメモリを読み取れないため）。もちろん、奇妙なメモリの場所ではなく、4の倍数、8の6などの場所である場合があります。したがって、これらの場合、単に常に整列するバッファを作成する方が効率的です。 。

そうですね、これらの点は少し混乱しています。さらに説明が必要かどうか、特にIMOが最も重要なポイント4をお知らせください。

電子工学の基数2演算の単純さ（コストも参照）のため、左にシフト（2で乗算）、右にシフト（2で除算）。

CPUドメインでは、多くの構成体が基数2算術を中心に展開します。メモリ構造にアクセスするためのバス（制御およびデータ）は、多くの場合、電源2に揃えられます。

もちろん、アナログコンピューターを使用している場合、ストーリーは異なります。

FYI：レイヤーXにあるシステムの属性は、下にあるシステムの server レイヤー属性の直接の結果です。つまり、レイヤー＆lt;バツ。私がこれを述べている理由は、私の投稿に関して受け取ったいくつかのコメントに由来します。

E.g。 「コンパイラ」で操作できるプロパティ。レベルは継承＆amp;その下のシステムのプロパティ、つまりCPUの電子機器から派生します。

shift引数を使用するつもりでしたが、それを正当化する正当な理由を考えることができました。

2のべき乗であるバッファーの良い点の1つは、循環バッファー処理では、分割ではなく単純なandsを使用できることです：

#define BUFSIZE 1024

++index;                // increment the index.
index &= BUFSIZE;       // Make sure it stays in the buffer.

2のべき乗でない場合、除算が必要になります。昔は（そして現在は小さなチップで）重要だった。

ページサイズが2の累乗になることも一般的です。

Linuxでは、バッファーをチャンクしてソケットまたはファイル記述子に書き込むなどの操作を行うときにgetpagesize（）を使用します。

2を基数に丸めた数値を作成します。10、100、または1000000が10を基数に丸めた数値を作成します。

2の累乗（または96 = 64 + 32や192 = 128 + 64などの近似値）でない場合、なぜ精度が追加されているのか疑問に思うかもしれません。ベース2の丸められたサイズは、外部の制約またはプログラマーの無知から生じることはありません。あなたはそれがどれであるかを知りたいでしょう。

その他の回答では、特別な場合に有効な多くの技術的理由も指摘されています。ここでは繰り返しません。

ハッシュテーブルでは、2 ^ nを使用すると、特定の方法でキーの衝突を簡単に処理できます。一般に、キー衝突が発生した場合、サブ構造を作成します。同じハッシュ値を持つすべてのエントリのリスト。または、別の空きスロットを見つけます。空きスロットが見つかるまで、スロットインデックスに1を追加するだけです。しかし、この戦略はブロックされた場所のクラスターを作成するため、最適ではありません。より良い戦略は、gcd（n、h2）= 1となるように2番目のハッシュ番号h2を計算することです。次に、空きスロットが見つかるまで（ラップアラウンドで）h2をスロットインデックスに追加します。 nが2のべき乗である場合、gcd（n、h2）= 1を満たすh2を見つけるのは簡単です。すべての奇数が実行されます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top