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

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

さて，本題．

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

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

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

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

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

■例外 (2013/01/27(日) 追記 … ここに追記するよりページ全体の構成を見直すべきだけど面倒なので放置．)

Visual C/C++ では，SSE のためのデータ型 (__m128 (16バイト・アラインメント厳守) など) をサポートしているが，32bit Windows 用の malloc，new，Win32 アロケータ等は８バイト・アラインメントしか保証していないので，これらを用いて SSE 用のデータ型を含む構造体などを確保すると， アラインメント違反 (一般保護例外 #GP) が発生する場合がある． DirectXMath / XNA Math / D3DX 等，SSE 対応のライブラリを使用する場合は _aligned_malloc() などを使用する必要がある．

Windows 7 (SP1) で確認したところ，どうやら DispatchMessage() がこっそり catch して握りつぶしているらしく，例外が発生してもエラーダイアログが出ないままメッセージループが継続するので気づかない．

align (Visual C++ Language Reference)

To create an array whose base is properly aligned, use _aligned_malloc, or write your own allocator. Note that normal allocators, such as malloc, C++ operator new, and the Win32 allocators return memory that will most likely not be sufficiently aligned for __declspec(align(#)) structures or arrays of structures.

2014/04/30(水) 追記

Visual C/C++ では，32bit 版 malloc のアラインメントは8バイト，64bit 版では16バイト．

３．本当に malloc() が返すアドレスって８の倍数になってるの？

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

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

#include <assert.h>

void *p = malloc(…);
if(p == NULL) goto NoMemory;
assert(((uintptr_t)p & 7) == 0); // Windows では uintptr_t の代わりに UINT_PTR を使用する．

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);

４．もし malloc() が返すアドレスがアラインされてなかったらどうなるの？

例えば 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*)(((uintptr_t)p + (AlignmentOf(double) - 1)) & ~(AlignmentOf(double) - 1));

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

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

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

５．なんで↑こんなわけわからんことせなあかんの？
　　どえれゃーめんどくせゃーてかんわ．
　　フツーに malloc() が返したアドレスに
　　そのまま配列書いたらあかんの？

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

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

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

６．malloc() が保証するより大きいアラインメントが
　　必要な場合はどーすりゃいーの？

必要なアラインメントが OS のメモリ管理単位のサイズより小さい場合
- UNIX/Linux 系ならば memalign() や posix_memalign() を使う．
- Windows ならば _aligned_malloc() など．
必要なアラインメントが OS のメモリ管理単位の場合
- UNIX/Linux 系ならば mmap() (ページ境界にアラインされる)．
- Windows ならばファイルマッピング関数を使用する．
上記のサンプルのようなコードを自分で書く．
参考：アラインメントの大きなメモリ領域を確保する方法

７．参考図書

楽天で買う

価格：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)，サイズ，アラインメントなどを考慮して決める必要がある．特に，寿命を知っているのはアプリケーションだけだ．目的に合ったメモリプールならば，malloc/free をそのまま使用する場合に比べて数十倍以上速くなることもある．

■参考

メモリー管理の内側動的アロケーションの選択肢とトレードオフ、そして実装 (原文)

単純な malloc() / free() のサンプルコード
(原理を理解するためのものであって実用的ではない．)
各種メモリ割り当て戦略の比較表
参考文献・論文へのリンク集

ところで，省メモリが高速化につながる場合も多い．昔からメモリと速度のトレードオフ (高速でメモリを大量に使用するアルゴリズム (例えばテーブル参照) を使うか，それとも低速でメモリを少ししか使用しないアルゴリズムを使うか) がよく問題になるので，省メモリと高速化は両立しないと思い込んでいる人もいるだろう．しかし最近の 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 (高速フーリエ変換) で使われるビットリバース (ビット逆順) などを含む「ビットやバイト単位の並べ替え」など．