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

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

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

「アラインメントの大きなメモリ領域を確保する方法」では， glibc malloc() がアラインメントの大きなメモリ領域を確保するために使用している方法について解説したが，ここではその領域を使って何をしているかということを，問題を一般化した形で解説する．

非常に多数の要素 (子) を持つ集合 (親) を実現するデータ構造を考えよう．例えば次のようなものである．

集合を連結リストで実装する場合，親はリストヘッダ (またはそれを含む構造体) で，子はリストの要素．
配列で実装する場合，親は配列全体 (を含む構造体)，子は配列要素．
木構造の場合，親は根節点へのポインタ (を含む構造体)，子は木のすべての節点 (根節点を含む)．

使用するデータ構造はどれでも (これら以外でも) よい．同じデータ構造で実現された集合が多数あるとして， 一つの子 child のアドレスを知っているときに，その親 parent のアドレスをすぐに得られるようにしたい，としよう．もちろん，できるだけメモリ効率が良く，高速でなければならない．

glibc malloc() の場合，その動機は次のとおりである．

glibc malloc() は複数のヒープ (親) を管理しており，そのうちの一つからブロック (子) を切り出してアプリケーションに提供する．アプリケーションがそれを free() した時， glibc free() が知っているのは (free() の引数として渡される) 子のアドレスだけで，親のアドレスはわからない．したがって free() は，そのブロックが属するヒープを特定し，そこにブロックを返さなければならない．

誰でもすぐに思いつくのは，親へのポインタを子に持たせる方法である．連結リストによる実装の場合，子のデータ構造は次のようになる．

typedef struct Parent Parent_t;
typedef struct Child Child_t;

struct Child {
  Child_t *next;        /* 連結リスト内の次の子   */
  Child_t *previous;    /* 連結リスト内の直前の子 */
  Parent_t *parent;     /* 親 */

  /* 以下，子自身のデータ */
  :
  :
};

ポインタ１個 (４バイト) 増やすだけなので最も簡単だし，速度も申し分ないが，子の数が非常に多いときは増やしたポインタ分のメモリがもったいない．子自身のデータのサイズがほんの数バイトしかないときは論外である．しかも，同じ親を持つ子は多数存在し，それらはすべて同じ親へのポインタを持つことになる．非常に多数の子が皆同じデータを持つなんて，一層もったいない感が強い．もっとなんとかならんのか！

次に思いつく方法は，データ構造はそのままで，すべての親のすべての子を列挙し， child と一致するものを探す方法である．親と子のメモリアドレスについて何の仮定もしない場合，最悪すべての親のすべての子と child を比較する必要がある．これは余分なメモリを必要としない反面，現存する子の総数に比例する手間がかかる．極端にのんびりしたアプリケーションでない限り，即却下である．

glibc free() のような場合はもっとマシで，あるブロックがあるヒープに含まれているかどうかはアドレスを２回大小比較するだけで判定できるから，最悪ヒープの総数 NHeaps に比例する手間で済む．さらに，ヒープのアドレスをソートした配列を用意して二分探索すれば log(NHeaps) まで改善できるが，ヒープを追加/削除した場合に配列を作り直す必要がある．できればもっと高速化したいよね～．

さて，いよいよ真打ち登場である．この方法では，次の前提条件をおく．

１つの親は１つの連続したメモリ領域を使用する (ここでは領域の先頭アドレスを「親のアドレス」という)．その親の子はすべて，この領域内に存在する．領域の先頭部分には，親のデータ構造 (またはそのポインタ) を置いてもよい．
すべての親が使用するメモリ領域のサイズは同じで，かつ２の冪乗バイトである．先頭アドレスはサイズの倍数にアラインされている．

話をわかりやすくするため，ここではサイズを glibc malloc() のヒープと同じ 1MB (0x00100000 バイト) としよう．親のアドレスは 1MB 境界にアラインされているので， 0xPPP00000 ('P' は任意の16進数字) になる．そしてその子が存在するアドレス範囲は 0xPPP00000 ～ 0xPPPFFFFF である．したがって子のアドレス 0xPPPQQQQQ ('Q' は任意の16進数字) が与えられたとき，下位20ビットを０にすれば，親のアドレスが瞬時に得られる．しかも余分なメモリは全く必要ない．めでたしめでたし．

楽天で買う

価格：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 (高速フーリエ変換) で使われるビットリバース (ビット逆順) などを含む「ビットやバイト単位の並べ替え」など．