FC2ブログ

スポンサーサイト

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

idHeap

githubで公開されたdoom3のソースコードのメモリ周りの実装のメモ。

CPU/メモリどちらのパフォーマンスも追及してる感じがなかったのと、メモリをお大尽に使ってるのはPCゲーだから?
マルチスレッドセーフでない。メモリの確保がひとつのスレッドからしか行われないのか、それとも別のガードを入れているのかは知らないが、どっちにしてもすごい。
おそらくヒープの性能が問題になるようなコードが少ない(あるいは無い)のだと思う。ある意味理想的。

ソースは
TTimo-doom3.gpl-1559777\neo\idlib\Heap.h
TTimo-doom3.gpl-1559777\neo\idlib\Heap.cpp
の2つ。

中核になっているのはHeap.cppに定義されている idHeap クラス。
これのAllocate()とFree()についてメモ。

1~255byteをsmall、256~32767byteをmidium、32KB以上をlargeとして、別々に管理している。
各ブロックのポインタの-1byteの場所にはsmall,midium,largeのどれかであるかを示す定数が入っている。

smallのブロックの構造:
|a|b| c |
a ... フリーリストのインデックス, 1byte, 0~32
b ... smallであることを示す定数, 1byte,SMALL_ALLOC)
c ... ユーザにされる渡データ部, 8byte align, 8の倍数サイズ

middleのブロックの構造:
|a   |b |c|   d   |
a ... mediumHeapEntry_s, 28byte
b ... dを8byte alignにするためのパティング,3byte
c ... middleであることを示す定数値, 1byte, MEDIUM_ALLOC
d ... ユーザに渡されるデータ部, 8byte align, 8の倍数のサイズ


middleは、複数のブロックを管理しているページという要素があり、1つ目のポインタはそれへのポインタ。
前後のブロックで双方向リストを構築するのがprev,next。
フリーブロック同士で双方向リストを構築するのがprevFreeとnextFree。
そのブロックがフリーかどうかを示すフラグがfreeBlock、1だとそのブロックがフリーブロックであることを示す。
計28byte。やばい。

largeのブロック構造:
| a |b |c|   d   |
a ... ページへのポインタ, 4byte
b ... アライメント調整用のパティング, 3byte
c ... largeからの確保であることを示す定数, 1byte, LARGE_ALLOC

ヘッダのサイズは8byte。
ページと1対1に対応するので、実際にはaの手前にpage_sがある。
なのでそれも含めると、ヘッダは32byteになる。

ページ:
利用形態は違えどsmall,middle,large全部で使われている要素。
small,middleでは、それぞれのブロックの上位構造として64KB固定サイズのページが
largeでは、ブロックそのものが1ページになる。
確保解放関係の関数で::malloc()、::free()を最終的に呼び出しているのはAllocatePage()/FreePage()の2つだけ。
::malloc()により確保した領域の先頭に下記の構造体が配置される。



smallで使用されるページは、単方向リストにより idHeap::smallFirstUsedPage に繋がれる。
middleで使用されるページは、双方向リストにより idHeap::mediumFirstFreePage,mediumFirstUsedPage に繋がれる。
largeで使用されるページは、双方向リストにより idHeap::largeFirstUsedPage に繋がれる
prevはmiddleとlargeでしか使われない。
largestFreeとfirstFreeはmiddleでしか使われない。
largestFreeは、そのページの中で一番大きいブロックのサイズではなく、フリーなブロックが格納されている双方向リスト(firstFree)の先頭のブロックのサイズ。

smallのアルゴリズム:
ページをスタックアロケータのバッファとして利用している。
解放のときは、ページから切り出したブロックを、フリーリストに戻している。
ページの解放は行われない。
64KBごとに::malloc()が呼ばれることを除けば、確保、解放ともに O(1)。

middleの確保アルゴリズム:
1)要求サイズが入るページをページの双方向リストから(idHeap::mediumFirstFreePage)線形検索
2)ページが無ければ新規に作成
3)ページからブロックを切り出す。
1がO(n)。

middleの解放アルゴリズム:
largestFreeの意味を字のままに捉えるとはまる。largestFreeはfirstFreeの先頭ブロックのサイズ。最大のフリーブロックのサイズではない。
前後にフリーブロックがあればブロックをマージし、フリーリストを管理している双方向リスト(page_s::firstFree)にブロックを戻す。
このとき、解放しようとしているブロックの手前にフリーブロックが無かった場合(816行目)、解放しようとしているブロックを、双方向リストの先頭に持ってくるという、とんでもないことをやっている。これによってブロックを2つ確保して、そのうちの先に確保したほうを解放した場合、(たとえページにどれだけ空きがあろうが)largestFreeがそのブロックのサイズになってしまう。
firstFreeは多分サイズ順にブロックを入れておくつもりだったんじゃなかろうかと邪推。
Heap.hのラッパークラスのひとつidDynamicBlockAllocだと、サイズ別にバランス木を構築しているのに、なぜこれはこんなアルゴリズムなのか不明。
速度が速くなっても::malloc()を呼び出す回数が増えれば逆に遅くなるだろうし、なによりメモリ効率が悪くなる。
意図が不明すぎ。

largeのアルゴリズム:
::malloc()/::free()をほぼそのまま呼んでいるのに近い。
スポンサーサイト
検索フォーム
ユーザータグ

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

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