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

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

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

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

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

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

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

具体例を挙げると，

malloc() を使って，256バイト境界にアラインされた100バイトの領域が欲しい．
mmap() を使って，1MB 境界にアラインされた 1MB の領域が欲しい．(glibc malloc() さんからのリクエスト)

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

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

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

８の倍数ならば，そのまま使用できる．
８の倍数＋１ならば，＋７すればよい．
８の倍数＋２ならば，＋６すればよい．
８の倍数＋３ならば，＋５すればよい．
８の倍数＋４ならば，＋４すればよい．
８の倍数＋５ならば，＋３すればよい．
８の倍数＋６ならば，＋２すればよい．
８の倍数＋７ならば，＋１すればよい．

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

もし alignment2＝2 ならば，上記の８つの場合のうちの奇数行目しかあり得ないから，最大切り上げ量は６になる．同様に alignment2＝4 ならば１行目と５行目しかあり得ないから，最大切り上げ量は４になる．これを一般化すると，最大切り上げ量は alignment1－alignment2 になる．ただし alignment1≦alignment2 ならば，そもそも切り上げる必要はない．したがってメモリ割り当て関数を使って確保すべきサイズは，

size + ((alignment1 <= alignment2) ? 0 : (alignment1 - alignment2))

である．

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

仮に alignment1＝8 とする． allocatedAddress の下位３ビットをリセットすれば，それは確かに８の倍数になるが，これでは８バイト未満切り上げではなく切り下げである．そこで下位３ビットをリセットする前に allocatedAddress に７を足しておけば，めでたく切り上げとなる．また，下位３ビットをリセットするには ~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;
  }
}

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

CPU がサポートするデータ型であっても，Ｃ言語で通常サポートされないものは， malloc() でも考慮外の可能性がある．そのようなデータ型の中に，malloc() よりも厳しいアラインメントを要求するものがあるかもしれない．
アラインメントに寛容な CPU では，アラインされていないデータにも問題なくアクセスできるが，その代わりアクセス時間は余分にかかる．このような CPU のための malloc() が保証するアラインメントは，速度とメモリ利用効率のトレードオフで決められていると考えられる．アラインメントを小さくすれば，メモリの利用効率は向上するが，アラインメントの厳しいデータへのアクセスは遅くなる．それを高速化したい場合， malloc() よりも厳しいアラインメントが必要になる．
メモリに直接アクセスするデバイスによっては，特殊なアラインメントを要求するものがあるかもしれない．

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

アラインメントの大きなメモリ領域を用いて，高速かつメモリ効率の良い多数の集合を実現するため．

UNIX
- posix_memalign()
- memalign()
Windows (VC)

楽天で買う

価格：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];

楽天で買う

価格：3,570円（税込、送料別）

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

posted with amazlet at 10.06.20

ジョンベントリー
ピアソンエデュケーション
売り上げランキング: 7857

おすすめ度の平均:

アルゴリズムについて勉強したい人には必読の本です

楽しく読めるプログラミングの本

「プログラミング」と言う作業を見つめなおすのに最適。「設計する」と言う概念がよく分からない初級プログラマにも

納得！アルゴリズムは重要

プログラマなら読むべき本

Amazon.co.jp で詳細を見る

楽天で買う

価格：2,940円（税込、送料別）

プログラミング作法

posted with amazlet at 10.06.20

ブライアンカーニハンロブパイク
アスキー
売り上げランキング: 20088

おすすめ度の平均:

良著です。

入門書の次の次の次くらいに！

繰り返し読む必要あり

絶対にお勧めの本です

良いプログラマになりたいあなたに

Amazon.co.jp で詳細を見る

楽天で買う

価格：3,360円（税込、送料別）

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

posted with amazlet at 10.06.17

中村成洋相川光
秀和システム
売り上げランキング: 4312

おすすめ度の平均:

擬似コードのバグは見て見ぬふり

GCの入門書として今のところ最強!

Amazon.co.jp で詳細を見る

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

posted with amazlet at 10.06.12

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

おすすめ度の平均:

ビットの楽しみ

たのしみ？　たしなみ？

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

最後の頑張りに効きます

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

Amazon.co.jp で詳細を見る

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

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