noocyte のプログラミング研究室 〜プログラムは楽しげに走らねばならない♪〜

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

公開:2006/10/08(日)
最終更新:2016/05/06(金)

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

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


1.はじめに

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

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

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


2016/02/25(木)
slideshare で資料が公開されていたので今更だけど追記.


2.「malloc() が返すアドレスの下位数ビットが常に0」
  って何を意味するの?

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

さて,本題.

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

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

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

もちろん,ここでいう「8バイト (3ビット)」という数字は CPU 依存であるし, 場合によっては malloc() の実装依存でもあるだろう. 16ビット CPU では「2バイト (1ビット)」かもしれないし, 128ビット CPU ではおそらく「16バイト (4ビット)」以上になるだろう.

面倒なので,以下の説明では「8バイト (3ビット)」とする.


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

Visual C/C++ では,SSE のためのデータ型 (__m128 (16バイト・アラインメント厳守) など) をサポートしているが,32bit Windows 用の malloc,new,Win32 アロケータ等は8バイト・アラインメントしか保証していないので, これらを用いて 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バイト.


3.本当に malloc() が返すアドレスって8の倍数になってるの?

それを確かめたかったら,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);

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

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

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

/* unaligned_malloc() がアラインされていないアドレスを返すので,
 * (確保すべき配列のアラインメント−1バイト) 余分に確保する必要がある.
 * (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) ではない.*/

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

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

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

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


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


7.参考図書

省メモリプログラミング

楽天で買う

価格:4,410円(税込、送料別)

省メモリプログラミング―メモリ制限のあるシステムのためのソフトウェアパターン集 (Software patterns series)
ジェイムズ ノーブル チャールズ ウィアー
ピアソンエデュケーション
売り上げランキング: 80302
おすすめ度の平均: 5.0
5 メモリ制限のあるシステム
5 分類が上手い
5 組み込み向けのデザインパターンとしてはまともです。
5 すべての設計者・プログラマに必須

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

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

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

■参考

メモリー管理の内側  動的アロケーションの選択肢とトレードオフ、そして実装 (原文)
  • 単純な malloc() / free() のサンプルコード
    (原理を理解するためのものであって実用的ではない.)
  • 各種メモリ割り当て戦略の比較表
  • 参考文献・論文へのリンク集

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

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

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



ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
ジュニア,ヘンリー・S. ウォーレン
エスアイビーアクセス
売り上げランキング: 27265
おすすめ度の平均: 5.0
5 ビットの楽しみ
5 たのしみ? たしなみ?
5 ちゃんと読むと得した気分になれます
5 最後の頑張りに効きます
5 Hackっていうのは、こういうコトさ

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

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




ガベージコレクションのアルゴリズムと実装

楽天で買う

価格:3,360円(税込、送料別)

ガベージコレクションのアルゴリズムと実装
中村 成洋 相川 光
秀和システム
売り上げランキング: 4312
おすすめ度の平均: 3.5
2 擬似コードのバグは見て見ぬふり
5 GCの入門書として今のところ最強!



珠玉のプログラミング

楽天で買う

価格:3,570円(税込、送料別)

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造
ジョン ベントリー
ピアソンエデュケーション
売り上げランキング: 7857
おすすめ度の平均: 4.5
5 アルゴリズムについて勉強したい人には必読の本です
5 楽しく読めるプログラミングの本
5 「プログラミング」と言う作業を見つめなおすのに最適。「設計する」と言う概念がよく分からない初級プログラマにも
5 納得!アルゴリズムは重要
5 プログラマなら読むべき本



プログラミング作法

楽天で買う

価格:2,940円(税込、送料別)

プログラミング作法
プログラミング作法
posted with amazlet at 10.06.20
ブライアン カーニハン ロブ パイク
アスキー
売り上げランキング: 20088
おすすめ度の平均: 4.5
5 良著です。
5 入門書の次の次の次くらいに!
3 繰り返し読む必要あり
5 絶対にお勧めの本です
5 良いプログラマになりたいあなたに



【送料無料】リンカ・ローダ実践開発テクニック

楽天で買う

価格:2,940円(税込、送料別)

著者サポートページ




Linkers & loaders

楽天で買う

価格:3,360円(税込、送料別)

Linkers & Loaders
Linkers & Loaders
posted with amazlet at 10.06.17
John R. Levine
オーム社
売り上げランキング: 139529
おすすめ度の平均: 3.0
4 プログラムが実行される仕組みが良く分かる
1 概要が書かれた本
1 ひどい訳
5 dllのしくみがわかる!
5 パッケージソフト開発者の必読書



BINARY HACKS

楽天で買う

価格:3,360円(税込、送料別)

Binary Hacks ―ハッカー秘伝のテクニック100選
高林 哲 鵜飼 文敏 佐藤 祐介 浜地 慎一郎 首藤 一幸
オライリー・ジャパン
売り上げランキング: 35295
おすすめ度の平均: 5.0
5 組み込み系の開発者は必携です
5 ハードコア?なソフトウエア
5 大工さんにおける電動工具の紹介本
5 当然教科書ではない。でも、とても参考になります。
5 バイナリアンの基本



実践デバッグ技法

楽天で買う

価格:2,940円(税込、送料別)

実践 デバッグ技法 ―GDB、DDD、Eclipseによるデバッギング
Norman Matloff Peter Salzman
オライリージャパン
売り上げランキング: 79214



デバッガの理論と実装 (ASCII SOFTWARE SCIENCE Language)
ジョナサン・B. ローゼンバーグ
アスキー
売り上げランキング: 295384
おすすめ度の平均: 5.0
5 デバッグできないとき
5 普通に読んでいくだけでも面白い
5 デバッカの理論には必読

8.サイト内関連ページ


9.外部へのリンク

malloc() や new() が返すアドレスのアラインメントに関する話題.


10.更新履歴

  1. 2006/10/08(日) 公開
  2. 2007/01/14(日) わずかに修正.
  3. 2007/02/12(月) 下記を追加.
  4. 2007/07/29(日) 下記を追記.
  5. 2010/06/12(土) 参考図書追加.
  6. 2013/01/27(日)
  7. 2014/04/30(水)「Visual C/C++ 32bit malloc のアラインメントは8バイト」を追記.


Copyright © 2006-2016 noocyte
E-mail: relipmoced (a) yahoo.co.jp
  (" (a) " を半角のアットマークに書き替えてください.)
リンクはご自由に.
「noocyte のプログラミング研究室」トップページに戻る.