FC2ブログ

スポンサーサイト

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

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では少し賢い(?)線形検索を採用していた。大量に確保されチャンクが増えた状態でのランダムな確保/開放には滅茶苦茶弱かった。
スポンサーサイト

コメントの投稿

非公開コメント

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

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

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