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

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

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

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

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


1.はじめに

YLUG の 「第67回カーネル読書会 (glibc malloc について)」の ビデオで, 「mmap()/munmap() を使って 1MB アラインされたメモリ領域を得る方法」 が紹介されていた.発表者の kosaki さんは, その方法を知って「腰を抜かした」と言っていたが, 私は1985年頃に同じようなことを考えたことがあるので, 出しゃばってここで整理・解説しておこう.

「同じようなこと」といっても,当時 mmap()/munmap() を使ったわけではないので, 以下の説明は mmap()/munmap() に依存する話ではなく, 一般のメモリ割り当て関数 (malloc() など) でも通用する話である. また,mmap()/munmap() はいまだに使ったことがないので,以下の説明で mmap()/munmap() に関する部分は間違っているかもしれない. もしそうであれば遠慮なく指摘してください.


2.問題

多くの32ビット CPU 用の malloc() は, 8バイト境界にアラインされたアドレスを返します (詳しくは「malloc() が返すアドレスの下位数ビットは常に0って知ってます?」を参照). また mmap() はページ境界 (普通は 4KB?) にアラインされたアドレスを返します.

さて,ここで問題です. 上記のメモリ割り当て関数が保証しているアラインメントよりも大きいアラインメントを持つメモリ領域を確保するにはどうしたらよいでしょうか? ただしメモリ領域のアラインメント (2の冪乗) とサイズは, その都度指定されるものとします.

具体例を挙げると,


3.解答

ここでは,要求されたアラインメントおよびサイズをそれぞれ alignment1 および size,メモリ割り当て関数が保証するアラインメントを alignment2 とする.

基本的な考え方は,「size よりいくらか大きい領域を確保し, その中で alignment1 を満たす部分を使用する」ということである. では,どれだけ余分な領域を確保する必要があるのか. また,どうやって alignment1 を満たす部分を見つけるのか.

話を簡単にするため,alignment1=8,alignment2=1 の (つまり全くアラインしていない) 場合をまず考えよう. 必要としている領域の先頭アドレスは,malloc() が返したアドレスを alignment1 の倍数に切り上げることで得られる. つまり malloc() が返したアドレスが,

この場合,アドレスの切り上げ量の最大値は7 (=alignment1−1) である. 確保した領域の先頭アドレスが最大これだけ切り上げられる可能性があるから, それだけ余分に確保しておく必要がある.

もし alignment2=2 ならば, 上記の8つの場合のうちの奇数行目しかあり得ないから, 最大切り上げ量は6になる.同様に alignment2=4 ならば1行目と5行目しかあり得ないから,最大切り上げ量は4になる. これを一般化すると,最大切り上げ量は alignment1−alignment2 になる. ただし alignment1≦alignment2 ならば,そもそも切り上げる必要はない. したがってメモリ割り当て関数を使って確保すべきサイズは,

size + ((alignment1 <= alignment2) ? 0 : (alignment1 - alignment2))
である.

次に,先頭アドレスを alignment1 の倍数に切り上げる方法を説明する. 「倍数に切り上げ」というと,普通は乗除算を使用するが,alignment1 は2の冪乗なのでビット演算を用いて高速に計算できる. 以下の説明では,メモリ割り当て関数が返したアドレスを allocatedAddress, 所望の領域のアドレスを alignedAddress とする.

仮に alignment1=8 とする. allocatedAddress の下位3ビットをリセットすれば,それは確かに8の倍数になるが, これでは8バイト未満切り上げではなく切り下げである. そこで下位3ビットをリセットする前に allocatedAddress に7を足しておけば, めでたく切り上げとなる.また,下位3ビットをリセットするには ~7 と AND を取ればよい.つまり,

alignedAddress = (allocatedAddress + 7) & ~7.

一般の alignment1 の場合には次のようになる.

alignedAddress = (allocatedAddress + (alignment1 - 1)) & ~(alignment1 - 1).

以上をまとめると, 任意の境界にアラインされた領域を割り当てる関数は次のようになる. ただし,一般的なメモリ割り当て関数を Allocate(size) とする. 実際にコンパイルしたわけではないので,正しさは保証しません.:)

#define ALLOCATE_ALIGNMENT  8   // Allocate() が保証するアラインメント

void *AlignedAllocate(size_t size, size_t alignment)
{
  if(alignment <= ALLOCATE_ALIGNMENT) {
    // Allocate() が保証するアラインメントで充分な場合
    return Allocate(size);
  } else {
    // Allocate() が保証するアラインメントでは不十分な場合
    char *allocatedAddress, *alignedAddress;
    size_t allocatedSize;

    // 先頭アドレスの最大切り上げ量だけ余分に確保する.
    allocatedSize = size + alignment - ALLOCATE_ALIGNMENT;
    if((allocatedAddress = Allocate(allocatedSize)) == NULL)
      return NULL;

    // allocatedAddress を alignment の倍数に切り上げる.
    alignment--;
    alignedAddress = (char*)(((uintptr_t)allocatedAddress + alignment) & ~(uintptr_t)alignment);

    if(/* mmap()/munmap() のように,Allocate() で確保した領域の
        * 一部を Deallocate(address, size) で解放できる場合
        */) {
      // 先頭アドレスの切り上げ量
      size_t roundup = (size_t)(alignedAddress - allocatedAddress);
      size_t unused;

      if(roundup > 0) {
        // 所望の領域の前に未使用部分がある場合:それを解放する.
        Deallocate(allocatedAddress, roundup);
      }

      // unused ← 所望の領域の後ろの未使用部分のサイズ
      alignment++;  // 元の値に戻す.
      unused = alignment - ALLOCATE_ALIGNMENT - roundup;
      if(unused > 0)
        Deallocate(alignedAddress + size, unused);
    } else {
      // 本当は,ここで確保した領域を後で解放するため,allocatedAddress も返すべき.
    }
    return alignedAddress;
  }
}

4.そもそも,なぜメモリ割り当て関数が保証するより
  大きいアラインメントが必要なの?

思いつくまま書いてみる.

以上はハードウェア (CPU,デバイス) 側の事情によるものだが, その一方でソフトウェア側の事情によるものもある. glibc malloc() の 1MB アラインメントの話はこちらに該当する. その目的を一般的に表現すると,次のようになる.


5.アラインメントを指定できるメモリ割り当て関数 (OS・処理系依存)


6.参考図書

省メモリプログラミング

楽天で買う

価格: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 をそのまま使用する場合に比べて数十倍以上速くなることもある.

■参考

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

ところで,省メモリが高速化につながる場合も多い.昔からメモリと速度のトレードオフ (高速でメモリを大量に使用するアルゴリズム (例えばテーブル参照) を使うか, それとも低速でメモリを少ししか使用しないアルゴリズムを使うか) がよく問題になるので,省メモリと高速化は両立しないと思い込んでいる人もいるだろう. しかし最近の 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];



珠玉のプログラミング

楽天で買う

価格: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 良いプログラマになりたいあなたに



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

楽天で買う

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

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



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

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

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




BINARY HACKS

楽天で買う

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

Binary Hacks ―ハッカー秘伝のテクニック100選
高林 哲 鵜飼 文敏 佐藤 祐介 浜地 慎一郎 首藤 一幸
オライリー・ジャパン
売り上げランキング: 35295
おすすめ度の平均: 5.0
5 組み込み系の開発者は必携です
5 ハードコア?なソフトウエア
5 大工さんにおける電動工具の紹介本
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 パッケージソフト開発者の必読書



実践デバッグ技法

楽天で買う

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

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



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



【送料無料】いかにして問題をとくか第11版

楽天で買う
価格:1,575円(税込、送料別)

いかにして問題をとくか
G. ポリア
丸善
売り上げランキング: 41

7.サイト内関連ページ


8.更新履歴

  1. 2006/10/08(日) 公開
  2. 2006/10/31(火) アラインメントを指定できるメモリ割り当て関数 (OS・処理系依存)を追加.
  3. 2007/02/03(土) 『「アラインメント」で検索してここにいらした方へ』を追記.
  4. 2007/07/29(日) アドレス (値) のアラインメントを返すマクロへのリンクを追加.
  5. 2010/06/12(土) 参考図書追加.
  6. 2016/06/30(木) uintptr_t を使用するように修正.


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