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

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

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


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

f:id:Isoparametric:20091221084143p:image

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


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

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

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

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

                                                                                  • -

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

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がよく働くための仕組みを備えていることが解ってもらえたでしょうか。
大事なことなのでもう一度いいます。


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


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