スポンサーサイト

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

SmallObj覚書

SmallObjというかFixedAllocator?

・確保/開放がLIFOになってる分には速いが、ランダムな確保/開放は遅い
 FixedAllocator::VicinityFind や FixedAllocator::Allocate にはチャンクの線形検索が入っている。最後に使用されたチャンクがキャッシュとして保持されているため、そのキャッシュに引っかかった場合(オブジェクトの確保/解放がLIFOになっている場合)は検索が入らないけど、そうでない場合(ランダムな場合)には検索が入りまくる。この検索が(特にパラメータ指定をミスってチャンクの数がすごく多いような場合には)遅い。

・チャンクの検索が遅いことに対する改善案
 フリーブロックを持ったチャンクとそうでないチャンクを別々のリストで管理する
 O(1)でブロックからチャンクを求められる仕組みを導入する

改善案を施すとパラメータ指定(チャンクサイズとか)をミスったようなケースでも大抵高速に動くようになった。無論代償はある。というか無いわけが無い。

・他
 インデックスで管理しているやつをポインタに差し替えることで、インデックスにまつわる幾つかの演算を省くことができ、わずかだけど高速化できる。変わりに最小確保サイズが1byteから4byteになるが、そもそも1~3byteの要求がそんなにあるのか?という話になる。


スポンサーサイト

コメントの投稿

非公開コメント

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

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

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