とある愚直のアロケータ

前置き。dlmallocについて書くぞ！と言っておいて書いてなかったので。orz...すみません。

あろけーたをじぶんでかいてはいけません！！
なぜ、って大抵糞だからです。
例えば、こんな管理構造を持ったアロケータをよく見るんですが、

typedef struct _Allocator {
	unsigned char* pPool;					//	メモリプール
	int nPoolSize;					//	メモリプールのサイズ
	struct _SMemChain* pHead;		//	番兵
	struct _SMemChain* pTail;		//	番兵
	struct _SMemChain* pLast;		//	最後に追加されたチェインタグ
} Allocator;

typedef struct _SMemChain {
	struct _SMemChain* pPrev;	// 前のチェインタグ
	struct _SMemChain* pNext;	// 次のチェインタグ
	long nAllocArea;					// 確保したarea 数
	long nFreeArea;					// 空き area 数
} SMemChain;

この構造を持ったアロケータはほぼ必ず線形探索アロケータです。
線形探索アロケータというのは愚直に空きメモリを線形で探索するアロケータのことです。

Allocator allocator;
...
void* mem = MemAlloc(&allocator/* 管理構造体 */,32 /* 要求サイズ */);

のように使うわけですが、この方式はメモリ探索に大きな問題を抱えています。
要するに
「メモリを確保するとき、どこから調べたら効率的ですか？」
ということです。

メモリ領域を得るために与えられた全メモリ領域の先端から調べる場合、
メモリ領域が増えれば増えるほどMemAllocは線形コストを要求するので重くなります。
かといって、メモリの終端から調べれば断片化したメモリがあった場合に非常に非効率な結果を生み出します。

・メモリの先端から調べてはいけない。なぜなら領域が幾つもの領域に分かれているならばnew/mallocのコストは最初の何倍にもなってしまうだろうから
・メモリの終端から調べてはいけない。なぜなら領域の先端に既に解放され再利用可能な領域があろうとも見逃してしまうだろうから

で、どこから調べれば良いんでしょう？
単純な答えは線形のアロケータを使わない、ということです。

このアロケータのやっかいなところは、「ちょっと触っただけではやっかいな事が無く問題無く動いてしまうだろう」ということです。

・メモリの先端から調べるアロケータはメモリが断片化しないとnew/mallocが遅くなったことに気付きません。先頭から終端まで満遍なく確保して解放するようなテストでは問題が見えません。
・メモリの終端から調べるアロケータはメモリが断片化しないと領域が効率よく利用されていない事に気付きません。同じように先頭から終端まで満遍なく確保して解放するようなテストでは問題が見えません。

これらは、
「速度」と「空間」のどちらか、いや寧ろどちらも犠牲にしてしまういわば「糞アロケータ」です。

では、どうしたら良いのでしょう？

で、dlmalloc!!!!です。
（組み込み環境かつシングルスレッドの場合に推奨。マルチスレッドの場合はもっと良いアロケータの候補があるでしょう）

dlmallocは非常に優れたアロケータですが、
「速度」と「空間」を両立したアルゴリズムを持っています。（解説はまた以後
以下、意訳つき解説。

dlmalloc は空間を最小限にします。アロケータは無駄な領域を確保すべきではありません。小さなメモリに対して有効に働くように、プログラムで使用されないメモリの穴によって生じる断片化を最小限に維持します。（dlmallocは管理領域さえ最小限に確保します）

Minimizing Space
The allocator should not waste space: It should obtain as little memory from the system as possible, and should maintain memory in ways that minimize fragmentation -- ``holes''in contiguous chunks of memory that are not used by the program.

dlmalloc は時間を最小限にします。mallocやfree、realloc（もしくはnew/delete）の速度は平均的に速くあるべきで、メモリの状態に依存して極度に遅くなったりすべきではありません。

Minimizing Time
The malloc(), free() and realloc routines should be as fast as possible in the average case.

では、dlmallocはいかにして「速度」と「空間」を両立させるのでしょう？
それは優れた探索アルゴリズムにあります。
（この話は長いので続きます）

dlmallocは小さなブロックに対して非常に効果的に動くので、
小さなメモリをよく生成するC++のアロケータや、
Luaのアロケータに向いています。