高速固定長アロケータ - ゲーム作ろうよ

概要

newとかdeleteってもの凄く重いですよね。
何故かって割り当てられる領域を探すのに時間がかかっているんです。

OS側でメモリを管理しているわけですが、色んなシステムが割り当て要求をしてきます。
さらに大きさがバラバラなので、割り当て取り消しを繰り返しているうちに虫食い状態になります。
そこでOSさんはメモリから要求サイズより大きい場所を探します。
デフラグするということもありますが、そんな時間ももったいない。

弾幕系のSTGなんか弾の生成削除でnew/deleteしていたらfpsなんて激減ですよ。

そこで

ある程度大きいサイズをあらかじめ確保しておいて、固定された大きさで大雑把に割り当てを行いましょう。

制作方針

今回のポイントはメモリプールとplacement newです。
また、空きのインデックスを持つことで、空きを探すための線形検索が発生しないので高速です。

templateを用いていますが汎用性を持たすためなのでそんなに気にしなくても大丈夫です。

ダウンロード

サンプルソース

allocate.h

#ifndef _ALLOCATER_
#define _ALLOCATER_

//-------------------------------------------
//              Allocater 
//
// allocate from memory pool
//
// ## MAX_SIZE -- the most large object size
// ## LENGTH   -- the number of object
// ## TYPE     -- unique number 
//
//-------------------------------------------
template<int MAX_SIZE,int LENGTH=1,int TYPE=-1>　class Allocater
{
private:
	Allocater(); // singleton

public:
	virtual ~Allocater(){}
	
	void init();

	void* New();
	void  Delete(void* p);

	template<typename T>
	void  DeleteDest(T* p)
	{
		p->~T();	
		Delete(p);
	}

	int getType(){ return TYPE; }
	
	static Allocater<MAX_SIZE,LENGTH,TYPE>& getInstance();

protected:
private:
	char mMemoryPool[MAX_SIZE*LENGTH];
	int  mMemoryIndex[LENGTH];
	int  mLastIndex;
};

とりあえず前半部分です。
Singletonで構成されていてどこからでもアクセスできます。

template引数	役割
MAX_SIZE	割り当ての大きさの最大値
LENGTH	アロケータの扱える割り当て数
TYPE	ユニーク値(MAX_SIZEとLENGTHが衝突する時)

例えばMAX_SIZEとLENGTHが等しかった場合は同じアロケータとして認知されます。
そこで、TYPEに適当な値を入れることで衝突を避けることができます。

「あれ？なんでDeleteが２つあるの？」
Deleteはデストラクタを呼びませんが、DeleteDestはデストラクタを呼びます。

「じゃあ、なんでNewはひとつなの？」
デストラクタには引数が発生しませんが、コンストラクタには引数が発生するため
ユーザー側で対処させるためです。
[

allocate.h

//-------------------------------------------
// Constructor
//-------------------------------------------
template<int MAX_SIZE,int LENGTH,int TYPE>
Allocater<MAX_SIZE,LENGTH,TYPE>::Allocater()
{
	init();
}

template<int MAX_SIZE,int LENGTH,int TYPE>
void Allocater<MAX_SIZE,LENGTH,TYPE>::init()
{
	for(int i=0;i<LENGTH;i++) mMemoryIndex[i] = i+1; // next
	mLastIndex = 0; // free index
}

mMemoryIndexは次に空なメモリを指します。(初期状態では1番めの次は2番目が空きです）
mLastIndexでは空である最初の場所を示しています。

このシステムは簡易リストといったところでしょうか。

//-------------------------------------------
// New
//-------------------------------------------
template<int MAX_SIZE,int LENGTH,int TYPE>
void* Allocater<MAX_SIZE,LENGTH,TYPE>::New()
{
	if( mLastIndex == LENGTH ) return 0; // Overflow

	int last = mLastIndex;            // prev
	mLastIndex = mMemoryIndex[last];  // next (update)

	return &mMemoryPool[last*MAX_SIZE];
}

次の場所をmLastIndexにセットして
空いている最初の場所のポインタを返しています。

//-------------------------------------------
// Delete
//-------------------------------------------
template<int MAX_SIZE,int LENGTH,int TYPE>
void Allocater<MAX_SIZE,LENGTH,TYPE>::Delete(void* p)
{
	int pos = (((char*)p)-mMemoryPool)/MAX_SIZE;

	if( !(0<=pos&&pos<LENGTH) ) return; // error

	mMemoryIndex[pos] = mLastIndex;
	mLastIndex = pos;
}

メモリの位置を確認しています。
開放すべき場所は最初に確保した場所のどこかであり
MAX_SIZEごとに区切られた場所でもあるので割り算で簡単に求められます。

開放するのは簡単です。
自分が最初の空き場所であることを示せばいいのです。（mLastIndex = pos）

//------------------------------------------
// Instance
//------------------------------------------
template<int MAX_SIZE,int LENGTH,int TYPE>
Allocater<MAX_SIZE,LENGTH,TYPE>&
Allocater<MAX_SIZE,LENGTH,TYPE>::getInstance()
{
	static Allocater<MAX_SIZE,LENGTH,TYPE> a;
	return a;
}

#endif // _ALLCOATER_

さて、こんな簡単に実装できてしまいました。早速テストしてみましょう。

テストコード

main.cpp

#include "allocate.h"
#include <iostream>
using namespace std;

//-----------------------------------------------------------------
// target1
//-----------------------------------------------------------------
class Object
{
public:
	int mNum;
	Object(int num):mNum(num) { cout << "object constructor " << mNum << endl; }
	virtual ~Object() { cout << "object destructor " << mNum << endl; }
};

//-----------------------------------------------------------------
// target2
//-----------------------------------------------------------------
class LargeObject : public Object
{
public:
	LargeObject(int num):Object(num) { cout << "large object constructor " << mNum << endl; }
	virtual ~LargeObject() { cout << "large object destructor " << mNum << endl; }
};

#define ALLOCATE Allocater<sizeof(LargeObject),3>::getInstance()

//-----------------------------------------------------------------
// main
//-----------------------------------------------------------------
int main()
{
	Object* obj1 = ( new(ALLOCATE.New()) LargeObject(0) );
	Object* obj2 = ( new(ALLOCATE.New()) LargeObject(1) );
	Object* obj3 = ( new(ALLOCATE.New()) Object(2) );
	
	ALLOCATE.DeleteDest<Object>(obj1);
	ALLOCATE.DeleteDest<Object>(obj2);
	ALLOCATE.DeleteDest<Object>(obj3);
	return 0;
}

ここでようやくplacement newの登場です。
new(初期化するメモリ) 初期化方法(コンストラクタ)

この方法で先ほど確保したメモリ領域を初期化します。さっきは確保しただけだったんですね。
これを行わないとコンストラクタが呼ばれなくて大変なことになります。

結果

object constructor 0
large object constructor 0
object constructor 1
large object constructor 1
object constructor 2
large object destructor 0
object destructor 0
large object destructor 1
object destructor 1
object destructor 2

ちゃんと動きました。
アクセス方法に違和感を感じるような気もしますが今日はこれでおしまいです。

次はスマートポインタを拡張してアロケータと対応できるようにする予定です。