とある愚直のアロケータ

前置き。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のアロケータに向いています。

とある愚直のリニアサーチ

前のエントリで線形探索のメモリアロケータは駄目だ駄目だ、と言いました。

で、まず線形探索の何が駄目って、メモリは以下のようになっています。
最初は「未使用領域（青）」しかありません。ここからどう領域をとっても良いです。
ただ、使っていくうちに「使用領域（赤）」と「未使用領域（青）」の数珠つなぎになりがちです。
new/deleteの順番を意識すればこういったメモリの配置問題が解決できることもありますが、
実際には「クラスがメモリの状態に束縛される」とすると非常に面倒です。
なので、効率的なアロケータは必須なのです。

あなたが下のような断片化した領域をつなぐ双方向リストを持っていると仮定してください。

ここから効率よくメモリを探すことは絶対にできません。
ソートしておくといったことも考えられますが、ソートすると解放された領域のマージが困難です。
（freeされた隣接した領域はより大きなメモリに備えるため結合されなければならないので）

対してdlmallocではこんなアルゴリズムを用いています。
領域サイズごとにツリーをもっているので探索は高速に行え、また領域の再利用も非常に容易です。
加えて領域のマージが可能なように隣接した領域に対するアクセス方法も備えています。

dlmallocはこう述べます。
「よいアロケータは幾つもの目標をバランス良く必要とする」

A good memory allocator needs to balance a number of goals:

dlmallocが目指した目標は以下の８つです。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

・最大限の互換性を持つこと

Maximizing Compatibility

dlmallocは互換性（plug-compatible）を重視し、
ANSI/POSIXとの規格に従います。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

・最大限のポータビリティを持つこと

Maximizing Portability

複数のプラットフォームに順応するように作られています。
場合によってはシステムコールを呼び出して効率化を図りますが、
システム依存部分はきちんと切り離されています。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

・最小のスペースにすること

Minimizing Space

アロケータはスペースを浪費してはいけません。
よって出来うる限り最大効率でメモリ領域を確保します。
そして、断片化を最小にする形でメモリを維持します。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

・最小の時間にすること

Minimizing Time

malloc,free,reallocは平均した時間ができるだけ速くなるべきです。
メモリ状態に依存して極度に遅くなるのならばプログラマは気軽にメモリを確保できまえん。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

・最大限のチューニングを可能にすること

Maximizing Tunability

様々な#defineが静的なチューニングを可能にします。
これによって
「速度を犠牲にして安全なアロケータにする」
「できうる限りアーキテクチャにあわせてアライメントを揃える」
「安全性は犠牲にしてできるだけ最小のスペースで最速にメモリを確保する」
なんていうことを「選択」できます。
動的なチューニングに関してもmalloptでサポートしています。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

・メモリ領域のローカル性を最大限にすること

Maximizing Locality

通常一緒に使われるようなメモリ領域を近くに確保するように努めます。
これはプログラムの実行時にページとキャッシュミスを最小限にする為にうまく働くことが期待できます。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

・最大限のエラー検出を可能にすること

Maximizing Error Detection

abort関数を定義したりすることでメモリ破壊の検出を容易にします。
メモリ破壊検出ツールの変わりにはなりませんが、
多重freeなどのような不正を検出するための仕組みは必要な筈でこれらを備えています。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

・例外を最小にすること

Minimizing Anomalies

デフォルトの設定で構成されたアロケータは様々な負荷に耐え、よく振る舞うように考えられています。
WindowToolKitやGUI、コンパイラ、インタプリタ、開発ツール、ネットワークプログラム、グラフィック処理、
ウェブブラウザ、文字列処理、など例外なくよく機能する筈です。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

と、こんな感じでdlmallocの高い目標を紹介しました。
「愚直な」単なる線形アロケータと比べてdlmallocがよく働くための仕組みを備えていることが解ってもらえたでしょうか。
大事なことなのでもう一度いいます。

「線形探索のアロケータを書いてはいけない！　使ってもいけない！」

次は使い方を書きたいと思います。

dlmallocはC++があったから生まれたといっても過言ではないのだ

なんだってー！！！！(；ﾟдﾟ） (ﾟдﾟ；（ﾟдﾟ；）
いや、過言かもしれませんが、C++の存在がdlmallocを書く切っ掛けになったのは確かです。
dlmallocは現在はLinuxなどのデフォルトのmalloc実装ではありませんが、
dlmallocは本当に優れたアルゴリズムを持っています。
まずは「はじめに」の日本語訳を引用として載せておきます。（この記事自体は非常に古いもので現在のmallocの実装の詳細を反映してはいませんが、今なお使うに値するアロケータだと俺は信じますし、使っています）
http://g.oswego.edu/dl/html/malloc.html

はじめに

メモリアロケータはソフトウェア工学のインフラにおける興味深いケーススタディを形成します。

私はそれを1987年に書き始めて以来、維持と発展に努めてきました。（これは多くのボランティアの方々の助けがあってこそです)

このアロケータはいくつかの助けとなるユーティリティ関数と共に標準Cの関数であるmalloc(), free(), realloc()の実装を提供します。

このアロケータに名前を与えたことは一度もありません。

ただ、多くの人がこれを「Doug Lea's Malloc」もしくは略名で「dlmalloc」と呼びます。

このアロケータのコードはパブリックドメインに位置しています。

（それは
ftp://g.oswego.edu/pub/misc/malloc.cから利用可能です）

そして、とても広く使われています。



mallocのデフォルトバージョンとして幾つかのLinuxのバージョンで用いられたり、

幾つかの一般的に使われているソフトウェアパッケージの中で（ネイティブのmallocと置き換えられて）使われています。

他にも様々なPCの環境や組み込みシステム、私の知らないとても多くの場所で使用されました。

私はこのアロケータの最初のバージョンを何らかのC++プログラムを書いた後に書きました。

それはメモリの動的割り当てがうまく働く事を期待されたプログラムでした。


私は見つけてしまったのです。その環境でのアロケータが私の予想より遙かにゆっくりと動き、かつ（あるいは）、遙かに多くのメモリ領域を消費していることを。

これは私がそのプログラムを動かしていたシステム(主にSunOsとBSDの最新版)上のメモリアロケータの特性故でした。

私はこの挙動を打ち崩すためにまず多くのC++の上で動作する専用のアロケータを書きました。

様々なクラスでoperator newをオーバーロードするためです。


これらの幾つかはC++Report(1989)の記事の中で、コンテナクラスの為の領域割り当てテクニックとして紹介されているものです。

しかし、私はすぐに当時書いていた汎用的なプログラムに対して新しいクラスを追加する際に気付いたのです。

動的に割り当てられ、よく使われるような様々なクラスにとって、

それぞれに特別なアロケータを記述することが優れた戦略ではないと。

（1986年から1991年にかけて私はGNU C++ library.のlibg++における第一線に立つ作者でした）

より広い解決策を求められていたので、

非常に特別な場合を除いて、プログラマが専用のアロケータを記述する誘惑にとらわれないように

通常のC++/Cの負荷の下でよく働くアロケータを書く必要がありました。

この記事ではアロケータの為に必要になる主な設計目標と、アルゴリズム、および幾つかの実現に対する問題を記載します。

コードの方に目を通して頂ければより詳細なドキュメントを見つけることができるでしょう。

コンテナやクラスごとに専用のアロケータを書いてしまう誘惑というのは確かに存在すると思います。
ですが、

非常に特別な場合を除いて、プログラマが専用のアロケータを記述する誘惑にとらわれないように

書かれたのがdlmallocなのです。

これは想像に過ぎませんが、小さなクラスなどを頻繁に作ろうとするC++だからこそ、既存のアロケータでは駄目だという結論になったのではないかと自分は考えます。
通常C++はCよりも細かく、そして頻繁にnew/deleteをするでしょうから。

その戦略に対する答えの一つが「各個クラスやコンテナ別にアロケータを書く」ということではありますが、
賢く働くアロケータがあればプログラマは専用のアロケータを用意する必要はなくなるのです。
そして、これが1989年当時に行われたということは驚くべきことではないでしょうか？
2009年になっても多くのプログラマはこのdlmallocより劣ったプログラムを便利だと思って使っているのですから。
（意訳的なものも含めた翻訳なので、間違いなどあればお気兼ねなくお寄せください）