リロケータブルなメモリを作ってみた
コンシューマとかのゲーム開発で画像（というよりは大きいリソース）を扱っていると、メモリの断片化が起こって悲しいことになることがよくあります。
対策としてメモリアロケータを変えたり、一括でメモリを確保したりといった方法で何とかすることがありますが、ここでは、メモリのデータを移動させる（リロケートする）ことで何とかするライブラリを作ってみました*1。これで断片化ともおさらばです。
リソースデータは基本的にでかいので、リロケートの際に出来る限り移動する量が少なくなるようにしてみました。
使い方
登場人物は reloc_pool, reloc_ptr, pinned_ptr のみなので、使い方は簡単です。
unsigned char* p = new unsigned char[100]; reloc::reloc_pool<1> pool(p, 100); reloc::reloc_ptr p1 = pool.allocate(30); // この時点でのメモリの状態 // |30| | assert(p1.pin().get() == p); reloc::reloc_ptr p2 = pool.allocate(30); // この時点でのメモリの状態 // |30|30| | assert(p2.pin().get() == p + 30); reloc::reloc_ptr p3 = pool.allocate(30); // この時点でのメモリの状態 // |30|30|30| | assert(p3.pin().get() == p + 60); pool.deallocate(p2); // この時点でのメモリの状態 // |30| |30| | // 断片化発生 // 連続した40バイトの領域が無いのでリロケーションが発生する reloc::reloc_ptr p4 = pool.allocate(40); // この時点でのメモリの状態 // |30|30| 40 | assert(p1.pin().get() == p); assert(p3.pin().get() == p + 30); assert(p4.pin().get() == p + 60); // 後片付け pool.deallocate(p1); pool.deallocate(p3); pool.deallocate(p4); delete[] p;
reloc_ptr の指す領域は移動可能なデータなので、pin() でポインタの位置を固定しないと使えません。
reloc::reloc_ptr rp = pool.allocate(10); { reloc::pinned_ptr pp = rp.pin(); // ここから pp の寿命が切れるまでは、リロケーションが発生しても // pp.get() のポインタは移動しない { reloc::pinned_ptr pp2 = pp; // 参照カウンタで管理しているので共有可能 } // この時点ではまだメモリはピンされている状態 } // ここでピンが解除され、リロケーション可能になる
reloc_pool には Alignment と Traits をテンプレート引数で指定することができます。
メモリを移動するときに Traits::copy（もしくは Traits::move）が呼び出されるので、Alignment をバースト転送可能なアライメントにしておいて、Traits::copy でその処理を行えばいい感じに移動できると思います。
あとはコンストラクトするときやデストラクトするときに Traits::construct, Traits::destroy が呼ばれるので、デフォルトコンストラクタとコピーコンストラクタで例外を投げないクラスなら構築できるはずです。
リロケーションのアルゴリズム
それぞれの n 個の隣接した空き領域を合計したときに、要求したサイズを満たす空き領域の範囲の中から、データの移動量が最小となるような範囲を移動させるようになっています。
図にするとこんな感じ。
Reloc
ただし、順序が決して入れ替わらないような移動しか行わないので、ほんとに最小の移動量で済むわけではないし、ピンが打たれている場合にはフリーリストの合計サイズより少ないメモリを確保しようとしても失敗する可能性があります。 View more presentations from melpon
単にこれはリロケーションのアルゴリズムが思いつかなかったからなのですが、何かいい方法があれば教えて下さい。
注意点
管理用の領域はプール用に渡されたメモリではなく、普通に動的にメモリ確保とかしてるので、reloc_pool::allocate は例外を投げる可能性があります*2。
deallocate は例外を投げないように作ったはずなので多分大丈夫です。
