malloc() が返すアドレスの下位数ビットは常に０って知ってます？

●「アラインメント」で検索してここにいらした方へ

↓こちらのページの方が適当かもしれません．

本当は「malloc() が返すアドレスは８の倍数って知ってます？」にしたかったんだけど，「８」というのは CPU 依存の数字だし，一般には２の冪乗なのでこういうタイトルにした．

そもそもこの記事を書くきっかけは， YLUG の「第67回カーネル読書会 (glibc malloc について)」のビデオと資料を見たこと． 20年以上前に Lisp の処理系を作ろうとして (結局作らなかったけど(^^;)) メモリ管理方法について色々考えたアイディアと同じものもいくつか出てきて，懐かしくもあり，またとても面白かったが，私にとって目新しいアイディアは少なかった．

malloc() の内部実装に興味を持つ人であっても，意外と上記タイトルに書いた事実を知らない人が多いようなので，「ビデオと資料」のページに色々とコメントした．この記事はそれを整理してまとめたものである．

それを説明する前に，「アラインメント」という言葉の意味をご存知ですか？もしそうでなければ，こちらを先にお読みください．

さて，本題．

UNIX 用であれ，Windows 用であれ，また組込用であれ，すべての malloc() の仕様書には次のような一文が必ず書かれているはずである．

malloc() が返すアドレスは，あらゆるデータ型に適合するようにアラインされている．

多くの32ビット CPU では，(標準的なＣ言語がサポートする型の中で) 最もアラインメントの厳しいデータ型は double 型 (８バイト・アラインメント) である (たぶん)．malloc() が返すアドレスは，当然 double 型にも適合しなければならない．したがって malloc() が返すアドレスは８の倍数である．言い換えると，malloc() が返すアドレスの下位３ビットは常に０である．

もちろん，ここでいう「８バイト (３ビット)」という数字は CPU 依存であるし，場合によっては malloc() の実装依存でもあるだろう． 16ビット CPU では「２バイト (１ビット)」かもしれないし， 128ビット CPU ではおそらく「16バイト (４ビット)」以上になるだろう．

面倒なので，以下の説明では「８バイト (３ビット)」とする．

それを確かめたかったら，malloc() が返すアドレスを printf() で表示させてみてください．(笑)

いちいち printf() の出力を見るのが面倒なら，次のようにするといいでしょう．

#include <assert.h>

void *p = malloc(…);
if(p == NULL) goto NoMemory;
assert(((size_t)p & 7) == 0);

2007/07/29(日) 追記

あるいは次のようにすれば，malloc() が返したアドレスのアラインメントを表示させることができます．

size_t alignment;
void *p = malloc(…);
if(p == NULL) goto NoMemory;
alignment = AddressAlignmentOf(p);

#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)
// C99 以後
printf("Address:%p Alignment:%zu\n", p, alignemnt);
#else /* defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) */
// C99 より前
printf("Address:%p Alignment:%lu\n", p, (unsigned long)alignment);
#endif /* defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) */

assert(alignment >= 8);

例えば double 型の配列を確保するコードは，次のようにせなあかんようになります．
(このコードの根拠の詳しい説明はこちら．)

void *p; /* unaligned_malloc() が返すアドレス */
double *array; /* double 型の配列を指す．*/
unsigned nElements = 256; /* 配列の要素数 */
size_t size = sizeof(double) * nElements; /* 確保すべき配列のバイト数 */

/* unaligned_malloc() がアラインされていないアドレスを返すので，
 * (確保すべき配列のアラインメント－１バイト) 余分に確保する必要がある．
 * (AlignmentOf(type) は type 型のアラインメントを返すマクロ．)
 */
size += AlignmentOf(double) - 1;

/* アラインされていないアドレスを返す，malloc() のダメダメ版．*/
p = unaligned_malloc(size);
if(p == NULL) goto NoMemory;

/* p が double 境界にアラインされている保証はないので，
 * p を AlignmentOf(double) の倍数に切り上げた値を array とする．
 * (実際にコンパイルしたわけではないので，
 * 下の式はキャストに問題があるかもしれん．(^^;))
 */
array = (double*)(((size_t)p + (AlignmentOf(double) - 1)) & ~(AlignmentOf(double) - 1));

{ /* フツーに array[] を読み書きする．*/
  unsigned i;

  for(i = 0; i < nElements; i++)
    array[i] = …;
  :
  :
}

/* 配列を解放する．*/
free(p);    /* free(array) ではない．*/

あんたが使うてる CPU，アラインメントに寛大なヤツか？ x86 とか．
もしそうやったら，上のコードのようなことせんでも動くこた動くよ．
ただし配列にアクセスするのがちょっと遅うなるけどな．
それで性能上問題ないんやったら，上のコードみたいにせんでもええわな．

けどな，あんたが使うてる CPU がアラインメントに厳しいヤツ (RISC とか) やったら，そうはいかんで．
上のようなコードにせんかったら，配列にアクセスした途端にアラインメント割込みが発生するで．
OS が UNIX やったら SIGBUS が発生してコアダンプするのがオチや (実例)．

… いや，上のようなコード書くより，そんなアカンタレ malloc() 捨てた方がええな．
そや，そうすべきなんや．
それともあんた，そんな malloc() 使いたいんか？

上記のコードもその一例ですが … 詳しくは↓こちらへどうぞ．

アラインメントの大きなメモリ領域を確保する方法

楽天で買う

価格：4,410円（税込、送料別）

省メモリプログラミング―メモリ制限のあるシステムのためのソフトウェアパターン集 (Software patterns series)

posted with amazlet at 10.06.12

ジェイムズノーブルチャールズウィアー
ピアソンエデュケーション
売り上げランキング: 80302

おすすめ度の平均:

メモリ制限のあるシステム

分類が上手い

組み込み向けのデザインパターンとしてはまともです。

すべての設計者・プログラマに必須

Amazon.co.jp で詳細を見る

「省メモリ」とあるが，メモリ管理の高速化についても参考になる技法が解説されている．時々「malloc 高速(化)」などで検索して来る人がいるが， malloc の速度をこれ以上大きく改善する余地はあまりないと思う (あるとしても非常に難しいだろう)．その理由は，

(プロセス内での) 動的メモリ管理なんて，1958 年に Lisp が登場して以来，半世紀以上にもわたって散々研究され尽くしている．簡単に高速化できるのならば，とっくの昔に (前世紀のうちに) できていたはず．メモリ関連のハードウェア・アーキテクチャが根本的に変わらない限り， malloc の大幅な高速化は期待できそうにない．
そもそも malloc の仕様は，引数がサイズだけなので初心者にも簡単に使える反面， 高速化にも省メモリにも全く向いていない． malloc は「与えられた情報 (引数) はサイズだけなのに，どうやって最適化しろと？(怒)」と文句を言いたくなるだろう．

それでもなお malloc の高速化それ自体を目指したい人には「(悲愴な顔で) 頑張ってください」としか言えないが，「アプリケーションのメモリ管理を高速化したいから高速な malloc が欲しい」というのならあまりにも芸がなさすぎる．そういう人はこの本の「第５章 Memory Allocation：メモリ割当て」を読んで反省してください．(笑)

アプリを高速化したいなら，できるだけ malloc/free を呼び出す頻度を減らすこと．そのためには１回の malloc で確保した大きな領域 (メモリプール) に多数のオブジェクトを詰め込む必要がある (これは省メモリにもなる) が，どのオブジェクトを同じ領域に入れるべきかはオブジェクトの寿命 (extent)，サイズ，アラインメントなどを考慮して決める必要がある．特に，寿命を知っているのはアプリケーションだけだ．

ところで，省メモリが高速化につながる場合も多い．昔からメモリと速度のトレードオフ (高速でメモリを大量に使用するアルゴリズム (例えばテーブル参照) を使うか，それとも低速でメモリを少ししか使用しないアルゴリズムを使うか) がよく問題になるので，省メモリと高速化は両立しないと思い込んでいる人もいるだろう．しかし最近の CPU は命令実行速度に比べてメモリアクセス速度がはるかに遅いので，無駄なメモリを削減したり，メモリ上のデータ配置を変える (同時期に頻繁に使用するデータをなるべく少数のキャッシュラインに集中させる) と高速化されることも多い． (1970年代以前の CPU は命令実行とメモリアクセスが同期していたので同程度の速度だった．)

さて，ここで問題．次のコードで大きな２次元配列 (例えば画像データ) をコピーする場合，(1) と (2) のどちらが速いか．またその理由を述べよ． (理由を書かなければ０点)

int src[M][N], dest[M][N];
unsigned i, j;

// (1)
for(i = 0;  i < M;  i++)
  for(j = 0;  j < N;  j++)
    dest[i][j] = src[i][j];

// (2)
for(j = 0;  j < N;  j++)
  for(i = 0;  i < M;  i++)
    dest[i][j] = src[i][j];

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

posted with amazlet at 10.06.12

ジュニア,ヘンリー・S. ウォーレン
エスアイビーアクセス
売り上げランキング: 27265

おすすめ度の平均:

ビットの楽しみ

たのしみ？　たしなみ？

ちゃんと読むと得した気分になれます

最後の頑張りに効きます

Hackっていうのは、こういうコトさ

Amazon.co.jp で詳細を見る

主に２進整数やビットパターンのさまざまな演算技法について解説している．基本的には (特定のプログラミング言語に依存しない) 数学的な解説が中心だが，Ｃ言語によるサンプルコードも示している．

アラインメントやオフセットの計算に使える「２の冪乗の倍数への切り上げ／切り下げ」や，メモリブロックの管理に使える「次の２の冪乗への切り上げ／切り下げ」， (ビット／バイト) エンディアン変換や FFT (高速フーリエ変換) で使われるビットリバース (ビット逆順) などを含む「ビットやバイト単位の並べ替え」など．