メモリ管理
最近、ある事情からメモリ管理の手法を調べることになり、ウェブ上の資料を漁っていました。
§
まず最初にあたったのは、「The Memory Management Reference」。このサイトは、メモリ管理が抱える問題点やその解決手法を傍観するのに便利でした。
一般にメモリ管理では、対象とするレイヤーをアプリケーションに限定した場合、まず覚えておくべき３つの制約があります。すなわち、
- CPUオーバーヘッド
- インタラクティブな停止時間（(1)との違いがよく分かりませんが）
- メモリオーバーヘッド
これらの制約は互いにトレードオフの関係にあって、例えば実行速度を要求すると、反対にメモリ管理自体に要するメモリ消費量が大きくなってしまいます。極論でいうと、メモリの浪費（外部断片化）を気にせずに済むならば、空いている領域にどんどん要求されたメモリを割り当てていけば速いというわけです。このトレードオフの関係については、「メモリ管理の内側」と題された developerWorks の記事に実装方法別の分かりやすい説明を見つけました。同時に、dlmalloc を含む様々なアロケータを紹介していて、各アロケータを比較検討したい時にも役立ちそうです。
ところで、メモリ管理プログラムを自作することはそもそも有効な手段なのでしょうか？。結論から先に言うと、メモリ管理を熟知した専門家でない限り、自作するのは現実的ではないようです。メモリプールのようなサブアロケータにしても、ポインタと絡んだやっかいなバグの混入は避けにくく、中途半端な実装では返って性能低下を招く可能性があります。
しかしながら、あらゆる場合においてアロケーターを自作するのは無駄というわけではありません。特定の状況下においては、アロケータの自作は十分検討する価値があります。例えば、組み込みシステムなど、リソースの制約が大きい環境下では、既存の実装では性能要件を満たせない事が多々あると推測されます。また、組み込み以外の分野においても、メモリの割り当てと解放（又はこれに付随する処理）がボトルネックと判明しているならば、独自の割り当てアルゴリズムを用意するのは一つの手だと思われます。例えば、現在Linuxカーネルで採用されているスラブアロケータは、この典型例と言えるでしょう。スラブアロケータでは、カーネルが、プロセス記述子やファイル記述子など一定サイズのオブジェクトを頻繁に生成・破棄する事実に着目し、一度生成したオブジェクトをキャッシュする事で高速化を実現しています。また、割り当て手法が Buddy System であるにも関わらず、メモリの内部断片化が発生しにくい設計になっていて高い空間効率を維持しています。
メモリ管理の制約により万能なアロケータを作るのは到底無理ですが、このようにシステムの挙動をつぶさに観察し、その特性に合わせてアロケータを設計すれば、処理速度の高速化が望めそうです。
あとがき
実は、今回のエントリーを書くきっかけとなったのは、先日ある会社に選考課題の回答として提出したメモリ管理プログラムです*1。課題の内容は、malloc/free の自作ではなく、あくまでサブアロケータを実装するというものでした。残念ながら、結果は不合格。「仕事のコードじゃないんだし、こんなものでいいだろう」と途中で性能を妥協してしまったのが敗因かもしれません。とほほっ。そこで、どなたか面倒見のいい方からの添削を期待してソースコードを公開しておきます*2。メモリ管理の手法を調査する前に作ったので、アルゴリズムに稚拙なところがありますが、そこは大目に見て頂ければと思います。
http://homepage.mac.com/radio_nights/files/memory-pool.tar.gz
