C言語、配列の要素数を2の冪乗にする理由

Question

char buf[10];

配列の宣言についてなのですが・・・

配列の要素数を２のべき乗にする人がよくいますよね。
この理由は何でしょう？

2, 4, 8, 16, 32, 64, 128 などとやる理由はなんです？

アライメント関係があるのかと思ったのですが、ないような気がしてきました。
分かる方は理由を教えてください。
どのようなメリットがあるのでしょう？？

「追記」
asmさんの回答を見て確かに、２，４は見かけないですね。
小さすぎて特に使わないという理由もあるかもしれませんが、もしかしてアセンブリ言語のスタックが32bit(4B)が関係しているんでしょうか？？

8, 16, 32, 64, 128　２のべき乗と言うより、４の倍数ですか？

Answer 1

他回答者の方が仰るように、メモリなど、
パフォーマンス上のメリットは実際には少ないでしょう。

しかし、C言語に限らず、配列に限らず、
何かのデフォルトの数値に、2のべき乗を設定することが、
私はわりとよくあります。デフォルトのデフォルトです。

---

なぜそうするかというと、1に到達するまで、余りを出さずに、
どこまでも半分半分に分割できることが保証されているから、
多くしたり少なくしたりする操作が容易です。

普通のキリ番、たとえば300だと何が起こるかというと、
300→150→75→？　で、もう半分に割りきれません。
とりあえず、37にしましょうか。

しかし、反対に倍に増やしたとき、74になります。
74→148→296となって、単純な操作では元に戻りません。

もちろん、人間が判断するならそれくらい分かりますが、
機械に自動的に増減させるときに、処理が多少面倒です。

---

「100とか定数を増減させれば？」と思うかもしれませんが、
べき乗は圧倒的にスケールを変える足が速いです。

たとえば、2の20乗でもう約100万まで行きますが、
100を足すのでは1万回掛かります。

「桁数に応じて増減する値を変えて……」
ということもできますが、やっぱり処理が多少面倒です。

---

話は飛躍しますが、遺伝的アルゴリズムのような探索的な手法を取るときに、
100世代とか1万世代とか反復するので、
こういう細かいところで、意外と結果に差が付く場合があります。
カオスで誤差が増幅するみたいな話です。

結論として、2のべき乗を好むのは、
アルゴリズムによくある、再帰的な発想のひとつです。

Comments

[strike1217]

ふむふむ・・・

アライメントとは全く関係がないようですね。
アルゴリズムの１つとして考えればよいんですかね。

Answer 2

こんにちは。

アライメントでパディングが発生するくらいならその領域を使う時と、単なるキリ番の両方があると思いますよ。

Comments

[strike1217]

アライメントと関係があるという事ですよね？
２のべき乗にするとパディングが発生しないんですか？

[Chironian]

アライメントは２のべき乗になりますから、２のべき乗に足りない分がパディングで埋められます。そのパディングをなくそうとすると２のべき乗になります。

例えば、double型は通常8バイトのアライメントです。double型の直前にchar[11]の領域を確保していると5バイトのパディングが発生します。パディングで使わないより使ったほうが好ましい時はchar[16]にすることでパディングがなくなります。

[strike1217]

ああ、なるほど！
アライメントが２のべき乗になるのですね。

だから、２のべき乗にした方が効率よくメモリを扱えるというわけですね！

[strike1217]

例えがとても分かりやすいです。

直前の配列の要素数は、次の変数と直前の変数の隙間に影響を与えると考えれば良いのですね！！

Answer 3

昔のアセンブラー上がりのCプログラマーはバッファサイズなどを2のべき乗にする習慣があったのかもしれません。限られたメモリ領域を無駄なく隙間なく埋めるには2のべき乗サイズであると都合が良いですし、メモリレイアウトを考える際もきりの良い数字だと設計しやすいし（昔は方眼紙に書いていた！）、なによりも配列などのアドレス計算がビット演算でできるので少ない命令で高速に処理できます。あるいは、ハード(OS)寄りのCプログラマーも2のべき乗サイズにする習慣があるかもしれません。デバイスとやりとりするバッファサイズが2のべき乗であることが多いからです。
そして、そのような先輩プログラマーを見習った新人プログラマーが、あまり深く考えずになんとなくまねしているうちに2のべき乗サイズにする習慣が付いた、ということもあるかもしれません。

メモリもクロックもメガを通り越してギガに突入している今となっては2のべき乗にこだわるべき理由はないでしょう。ただ、リソースが乏しい小規模な組み込み系（搭載メモリの単位がキロバイトとか）などでは、メモリの効率利用やパフォーマンスのために考慮する価値はあると思います。

Comments

[strike1217]

「限られたメモリ領域を無駄なく隙間なく埋めるには2のべき乗サイズであると都合が良いです」
この理由はなぜでしょうか？？

[strike1217]

なぜ、２のべき乗にすると、無駄なく隙間なく埋めることができるんですか？

[catsforepaw]

搭載メモリのサイズが大抵2のべき乗だからです。8キロバイトとか32キロバイトとか。無駄なく使うには綺麗に分割できるサイズにするのが自然だと思います。

[strike1217]

ああ。なるほど！
確かに、それもありますね。

Answer 4

現実にはあまりメリットはなく、単にキリが良いからというイメージからではないでしょうか。
とくにヒープの場合ですと、割当するバイト数以外の管理用の領域が必要だったりするので、アライメント上はかえって不利になる可能性さえあります。

Comments

[strike1217]

そうなんですか！
特別なものではないんですかね。
ずっとアライメントと関係があるものかと思っていました。

[catsforepaw]

> アライメント上はかえって不利になる可能性さえあります。

一応、念のため指摘しておきますが、ヒープ領域を取得する際に2のべき乗にすることで不利になる可能性はありませんよ。私の知る限りでは（といってもVC++とgccぐらいしか知りませんが）mallocが返すヒープ領域の先頭アドレスは、サポートするすべてのデータ型のサイズ（少なくともdoubleの8バイト）にアラインメントが合うことが「保証」されています。ですので、特殊な事情（SSEやAVXの利用等）がない限りはアラインメントを気にする必要はありません。

Answer 5

2,4はあまり見ないような？

割となんとなくですが大体の規模を考える時に考えやすい
データ数が30～70多くても100いかないくらい => ちょい余分に128にしとこう
100～150 => 256もあればいいだろう
とか

ただ、自分でメモリ管理ライブラリ組むとしたら256 or 1KByte単位で管理するので
ライブラリやコンパイラも同様の仕様になってる可能性もあるかなーとか

Answer 6

私も気になったので検索してみました。かなり古い回答ですが、「mallocやfreeでのヒープ領域でのフラグメンテーションの発生を抑えるため」という回答があります。自動変数などが割り当てられるスタック領域にはとくにこの2の冪乗の意味はないようですが、おそらくmalloc等で確保したヒープ領域とサイズを合わせる風習があったのではないでしょうか。
http://thesmithfam.org/blog/2005/09/18/power-of-2-array-sizes/

Comments

[strike1217]

ヒープ領域で使われていた・・・という事でしょうか？

Answer 7

char buf[255]等とすることはあります。
サイズを1バイトで表現できる0xffとしているためです。

0x100や0x200がきりよく感じられるということもあるかもしれません。