FC2ブログ

スポンサーサイト

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

双方向リスト/単方向リスト/xor linked list 比較

種類/項目 ノードの追加 ノードの削除 ノードの走査 ノード当りの
メモリ
速度
先頭 最後尾 任意ノードの前 任意ノードの後 先頭 最後尾 任意ノード 順番 逆順
双方向リスト ポインタ2個 速い
単方向リスト ×(*1) × × × × ポインタ1個 すごく速い
xor linked list ポインタ1個 速い?

◎ … O(1)で特に条件も無く可能
× … O(n)覚悟で先頭からリンク辿らない限り無理
△ … O(n)覚悟で先頭からリンク辿るか、前後のノードのうちいずれかのポインタがあれば可能

*1 最後尾ノードへのリンクがあれば可能

xor linked list に何か日の目が当てられないかと表にしてみたが、やっぱり微妙。
△を×扱いにすると、単方向リストと比較しての優位は、最後尾ノードへの操作が可能なことだけになる。
ありえないが、前後のノードのうちどっちかが判明している状況でなら、△を◎扱いにすることで速度が遅くなる代わりにメモリが減る双方向リストになる。

・最後尾への操作(追加だけなら単方向リストでも可能)
・最後尾からの逆順走査
のどちらかあるいは両方に加え、更に
・ポインタ1個分のメモリ
に価値を見出し
・xor演算による速度低下
を許容できる状況なら xor linked list を使えるかもしれない。
書いてて思ったが、そんなことは多分無い。
あとデバッガが使える環境だと、追いにくくなるということに難色を示されると思う。
スポンサーサイト

xor linked list

前後のポインタを持つ代わりに、前後のポインタのxor値をもつ双方向リスト。
・ポインタ2個分のメモリが1個になる
・要素を操作するときには、操作する要素のポインタに加え、前後どちらかの要素がわかっていなければならない。
・ポインタ操作にxor演算がはいるので通常の双方向リストと比べて遅くなる。
という特徴をもつ。面白いけど使い所がわからない・・・

前後どちらかのポインタがわからない限りは、リストの先頭要素か最終要素しか操作できない。
前後のどちらかの要素が判明しているなら、その分のメモリを使って双方向リスト使えよという話になるので、(外部から前後の要素が判明するようなパターンを除いて)要素単体単体へ操作可能なシーンは期待できない。

・リストを前向きにも後ろ向きにも辿りたい
・メモリをポインタ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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。