OreOreAllocator

ssacontents

アロケーターについて †

汎用アロケーターの要件 †

1. メモリの使用効率が良いこと
2. フラグメントを最小限にすること
3. スレッドセーフ
4. そこそこの速度

速度よりも、安定性、フラグメント対策が優先

ゲームで使うアロケーターの要件 †

1. 速いこと
2. 使用効率がいいこと
3. フラグメントを起こしにくいこと
4. 必要に応じてスレッドセーフ

速度が最優先。フラグメント対策は、定期的にパージすることである程度無視できる。
メモリ要件の厳しいゲームコンソールでは効率も大事

汎用アロケーターの基本的なアルゴリズム †

1. 空きメモリブロックを検索し、必要とするサイズに最も近いものを選ぶ(good fit)
   1. フラグメント化の抑止
   2. 使用効率の最適化
2. 空きメモリブロックの検索方法で様々なアルゴリズムがある
   1. ハッシュ系
      • TLSF, DLMalloc
   2. 二分木系
      • スラブアロケータ(Linux,SunOS)

• いずれも、アルゴリズムの基本は、Good Fitと効率(無駄の排除)にある。
• 必要とする領域に最も近い空きエリアを如何にして効率よく検索するかというテーマ。

OreOreアロケター †

• 総合的な性能で既存のアロケーターと競う気はない
• 何かを犠牲にすれば、既存のアロケーターより性能がでるはず
• 犠牲にするもの
  1. 広大な範囲で使われた場合(アロケーション数が数千のオーダー)での効率とフラグメント
  2. Goot Fit
  3. 使用効率
  4. スレッドセーフは後回し

基本アルゴリズム †

参考資料 †

• DLMalloc http://g.oswego.edu/dl/html/malloc.html