メモリ断片化を防ぐ「双頭スタックアロケータ」
The Double Headed Stack Allocator
ゲーム開発で使われる高速なメモリ確保手法「スタックアロケータ」を発展させ、1つのメモリ領域の両端から2つのスタックを伸ばす「双頭スタックアロケータ」を解説。レベルデータとキャラクタデータのように独立して増減するシステムでも断片化を防げる仕組みを、StarCraft 2での実例を交えて紹介する。
レベルデータのtosは0から上方向に、キャラクタデータのtosはメモリの終端から下方向に伸びる。両者が交差し、レベル側のtosがキャラクタ側のtosを超えたときがメモリ不足だ。
HNでの議論
33- Panzerschrek
プレイヤーが世界を走り回るにつれて、古いレベルジオメトリが解放され、新しいレベルジオメトリがディスクからストリーミングされて割り当てられる、というストリーミング型のオープンワールドゲームを想像してみてほしい。
そんなケースでは、スタックライクなアロケータは最良の戦略ではない。代わりに何らかの循環型アロケータを使うことができる。知る限り、Quake はサーフェスキャッシュでこれをやっていた。
- tom_
これは普通のアロケータでもうまく機能する。以前働いていた職場では、通常のメモリマネージャに「高位アドレス割り当て」オプションがあり、最低アドレスではなく可能な限り最高アドレスを見つけるようになっていた。永続的なデータを作りながら一時的なデータを割り当てる必要がある状況で、不必要な断片化を招かずに済むので、かなり良かった。
- windenntw
そしてだからこそ AmigaOS はメモリアロケータの呼び出しで MEMF_REVERSE オプションを許していたのだ（ http://amigadev.elowar.com/read/ADCD_2.1/Includes_and_Autodo... ）。95年か96年頃だったか、X サイズ（1KB とかそのくらい）を超えるすべての割り当てに MEMF_REVERSE を強制する、ごくごく単純な OS パッチを作った記憶があるが、これがメモリ断片化の削減に驚くほど効果があった :)
- saagarjha
この種のパターンは、何らかのパイプライン処理を扱うときにはかなり一般的だ。GPU に重みをストリーミングする際に以前実装した別の解決策は、その領域を2回ミラーマップして、最初の領域から順にポインタを渡しつつ、仮想アドレスを使って先頭にラップアラウンドできるようにするものだった。これは「割り当てる側」を使い果たすことがないので、複数ステージ先まで割り当てられる分、少しだけ強力だと思っている。残念ながら両面アロケータでは、パイプライン用に本当に1ステージ分しか余分に確保できない。
- kevin_thibedeau
二分割バッファは、可変サイズのオブジェクトの列を格納するのに向いている。循環バッファのように動作し、バンプアロケータのメモリ枯渇で行き詰まることもない。これには逐次的な反復が必要だが、こういうものではランダムアクセスが必要になることはめったにない。