9-Laboratory –

たまには、プログラム的話題を。メモリアロケータについて。
･･･
未使用メモリチャンクにタグを埋め込むアイデアを目にした。
今回のお題は、コレを応用してオレオレメモリアロケータを作ること。
仕様は
･線形時間(何が悲しくて線形時間。定数時間の間違い)でアロケートできる。
･普通のnewよりは速く。
･アロケートする型は事前に決めておいてよい。
実装は、

typedef unsigned int uint;
/*オレオレアロケータ*/
template＜typename T＞
class FastAlloc
{
　　　/*uintを下回るサイズのものは扱えません。*/
	char nunamed[ !(sizeof(T) < sizeof(uint)) ]; 
 
	const int MAX_NUM;
	T*buf_;/*全体のバッファ*/
	T*base_;/*フリーリストの現在の先頭*/
public:
	FastAlloc(int size)
		:MAX_NUM(size)
	{	
		/*メモリ割り当て*/
		buf_ = new T[MAX_NUM];
		/*空きメモリチャンクはその先頭に次の空きメモリへのポインタを格納している*/
		for(int i=0;i<max_num -1;i++)
			*(uint*)&buf_[i] = (uintptr_t)&buf_[i+1]; 
		/*一番最後の次は、NULL*/
		*(uint*)&buf_[MAX_NUM-1] = NULL; 
		/*最初のメモリをBaseに設定*/
		base_ = buf;
	}
	~FastAlloc()
	{
		delete []buf_;
	}
	T*New()
	{
		_ASSERT_EXPR(base_, L"格納限界を超えました");
 
		T*p = base_;
		uintptr_t nextPoint = *((uint*)base_);
		base_ = (T*)nextPoint;
		return p;
	}
	void Delete(T*p)
	{
		/*解放されたメモリの次ポイントに、現在のFreePointの先頭を割り当てる*/
		*(uint*)p = (uintptr_t)base_;
		base_ = p;
	}
};

最初に、指定した型の配列をもっさり確保しておく。
すべて未アロケートメモリなので、勝手に書き込む。
書き込む内容は、その要素の次の未アロケートメモリアドレス。
すると、単方向リストになります。
(※アドレスをその未アロケート部分に書き込めないといけないので、
unsinged intより小さいサイズのshort,charは使えません。)
返すときは、未アロケートリストの先頭に配置して、その次の未アロケート
要素を直前の未アロケートリストの先頭に設定します。
個人的な萌えポイントは、コンストラクタとデストラクタ以外に
“buf_”の文字が出てこないところ。
･･･
で速度の検証。
単純に、アロケートする時間を計測する。
一番いい結果だけ出すと、

new&delete[1447]
local [13]
FastAlloc[47]
続行するには何かキーを押してください . . .

とか。[]内がかかった時間。
速えええ。
ローカル変数の約1/4倍、普通のallocate
に比べてなんと、30倍も速く確保できます。
素晴らしい。
静的領域でやった方がこの手の処理は早いみたいな話を聞いたことが
ありますが、今回は｢全く｣結果が変わりませんでした。
なんでだろう。
※081003追記:直上の文は、static char buf_[0xff]とかしたほうがしたほうが速いですよ
という噂を聞いたということです。そしてそうしたけれども、結果が変わらなかったという
ことです。
※081003追記2:このパフォーマンスの向上率はアロケートするチャンクサイズで変わったりします。
でかいとあんまりオレオレアロケータの恩恵は受けにくいみたいです。C++Style内でも書いてありますが、
ただのnewは、元々でかいサイズを確保するようにできているようです。(小さいのは思ったような速度がでない。)