FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

FixedAllocator メモ

・std::vector<> を使っている実装がある
良いことが何も無い。
 確保に失敗したら例外がでる&リカバリー不可。
 std::vectorのバッファは寿命がかなり長くなったりするので(コンソールだと)メモリ断片化の原因になる。
 OSのメモリ確保関数の呼び出し回数が増える

・ブロックにチャンクの情報をつける
ブロックの手前か後ろにチャンクのポインタをつけてやるとFreeでのチャンク検索が不要になる。
その代わりメモリ使用量がかなり増える。例えば 8byte のブロックにポインタを1個つけると50%の増加になる。
ほかにもブロックのサイズとアライメントを 16byte にしたい場合、余計なポインタを1個つけるとアライメントを保つためにパティングを入れる羽目になりメモリ消費量が倍になる。

・チャンクの初期化
最初にフリーリストでブロックを繋いでしまうという方法以外にも、確保時にチャンクからブロックを1個ずつ切り崩していくという方法がある。初期化のコストが減る代わりに、何処まで切り崩したかを保持しておかなければならない、切崩しが可能かどうかを判定しなければならないなど、少しだけ煩雑になる。doom3のidHeapの小さいブロックの確保がこの方法だった。
スポンサーサイト

FixedAllocator その3

固定サイズアロケータその3
その2の「OSのメモリが開放されずピーク時のメモリ使用量で常に使用する」という仕様が微妙な環境のためにOSにメモリを戻すようにしたバージョン。通常のアロケータに近づけた感じ。
動的にメモリを確保/開放することで、若干遅くなるがピーク時と通常時のメモリ使用量に差がある場合に通常時のメモリ使用量が抑えられるというメリットがある。

■チャンク
チャンクという固まりでメモリを確保している。OSから(大量の)メモリを確保してそれを自前で管理するという仕組みでmalloc()/free()の呼び出し頻度を減らしている。これはユーザサイドで動作するアロケータに共通する。

■チャンクサイズの増減による影響
チャンクサイズの増減は次のような影響がある。

・malloc()/free()の呼び出し頻度
サイズが増えると呼び出し頻度が減り速度が向上する。

・チャンクへの操作頻度
サイズが増えるとチャンクの切り替わりが少なくなり、サイズが減るとチャンクの切り替わりが多くなる。切り替えのための操作はFixedAllocatorの中では割と高いコストになる。

・メモリ使用効率
チャンク内のメモリの使用効率(使用中のブロックが占める割合)は、多くの場合チャンクサイズと反比例する。完全にランダムにメモリを確保/開放していれば使用効率とチャンクサイズの相関関係はなくなる。また微々たるものだがチャンクの管理用メモリのオーバヘッドがある。

■Freeする際にチャンクに戻すメリット
Freeするポインタのアドレスが、OSから確保したメモリの範囲内に入っているかどうかをチェックすることで誤ったポインタのFreeを検出することができる。

ここから上は現在の実装に関する覚書、ここから下は他の選択肢に関する覚書

■Freeでの選択肢
・テンポラリなフリーリストを設けるか?(テンポラリなリストに一定個数のブロックが溜まればチャンクに戻す)
・OSにメモリを戻すか戻さないか?

現在の実装では、Freeするブロックはそれが属するチャンクに必ず戻している。これをチャンクに戻さずにをテンポラリなフリーリストに戻すと
・チャンクの検索が省けるためFreeが高速化する
・テンポラリなフリーリストから確保すれば高速化&キャッシュヒット率の向上を見込める
というメリットと
・誤ったポインタをFreeした場合に厄介なバグ(&検出不可)を引き起こす
というデメリットがある。
直に影響するメリットと誤った使い方をしたときのデメリットを同列に考えるべきかどうかというのはポリシーによるのでさて置く。あとテンポラリなリストは確保/開放されるチャンクの偏りを軽減するので(微々たるものだが)メモリの使用率に多くの場合マイナスの影響が出ると思う。

OSにメモリを戻すためには、ブロックをそれが属しているチャンクに戻す必要がある。(チャンク内で使用しているブロックが0でなければいけないので)戻さないという選択をしたのが、その2になる。全体で使用中ブロック数をカウントし、それが0になったときだけチャンクを全部開放するという手もあるがこれは現実的ではない。

デバッグ限定でFreeするポインタを検証するというのもいいかもしれない。
そうすれば誤ったポインタをFreeした場合の検出だけは可能になる。

■どうやってポインタからチャンクを検索するか?
・赤黒木
・チャンクのアライメントを大きくしてアドレスからチャンクのアドレスを計算する(例: チャンクのアライメントが0x10000の場合、開放対象のポインタが 0x12345678 ならチャンクのアドレスは 0x12340000 になる)
たぶんこの2択?前者はO(logN)、後者はO(1)。後者はOSからメモリをとる場合(アライメントが大きい確保がどのように処理されるか不明な場合)に採用し難いかもしれない。前者はチャンクサイズを大きくすればチャンクの絶対数が減る為高速化する。後者はチャンクの数に影響を受けない。
「Modern C++」のFixedAllocatorでは少し賢い(?)線形検索を採用していた。大量に確保されチャンクが増えた状態でのランダムな確保/開放には滅茶苦茶弱かった。 続きを展開する

循環型双方向リスト

循環型双方向リスト
続きを展開する

FixedAllocator その2

固定サイズアロケータその2。
その1の最大の制限である「初期化時に指定した個数以上の確保ができない」を、動的なメモリ確保によって克服したバージョン。

その1並に速く、OSからのメモリ確保に失敗しない限りは確保し続けられるというメリットがある反面、常にピーク時のメモリを使用し続けるという嬉しくない仕様になっている。
この仕様はメモリが無尽蔵にあるPC環境では、対したデメリットにはならないがメモリが少なく使いまわしが前提となる環境では大きいデメリットになる。

Effecient C++ の MemoryPool と同じ。

FixedAllocator その1

固定サイズアロケータその1。
一番単純。速い代わりに初期化時に指定した個数以上の確保ができない。
確保するブロック数が判明しているなら、使えるかもしれない。


検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。