* KMemPoolのアルゴリズムについて
-(by [[K]], 2019.12.26)
** (0)
-KMemPoolは、[[K]]が2019年の夏ごろから使っている、malloc/free相当の機能を持つライブラリです。
** (1)
//-基本インタフェース
//--KMemPool *KMemPool_init(KMemPool *w, KMemPool *p);
//--void *KMemPool_dest(KMemPool *w, KInt force);
//--void *KMemPool_alloc(KMemPool *w, KInt siz);
//--KMemPool *KMemPool_free(KMemPool *w, KInt siz, void *p);
//--void *KMemPool_realloc(KMemPool *w, KInt s0, KInt s1, void *p);
-基本的な考え方として、KMemPoolでは、mallocと同じことをするのではなく、mallocよりもちょっとだけ情報を与える代わりに、mallocよりもずっと高速にしてやろうという考えのもとで作られています。
-mallocの処理で時間がかかっているのは、チェーンでつながった空き領域を走査して、適切なサイズを見つけてくるところです。
-またfreeの処理で時間がかかっているのは、前後の空き領域と結合させる処理です。これをやるために空き領域をアドレス順でソートして、頑張っているわけです。
-KMemPoolでは、このどちらのループも原則としてやりません。だから当然速くなります。
-まずサイズを適当に量子化します（量子化＝飛び飛びの値に正規化すること）。
--8, 16, 24, 32, 40, 48, 56, 64 (ここまで8バイト刻み), 80, 96, 112, 128 (ここまで16バイト刻み), 160, 192, 224, 256 (ここまで32バイト刻み), ...
-これに適合しないサイズを要求されたら、適合サイズまで切り上げて計算します。
-そして、この量子化されたサイズには小さい順に番号を付けておきます。
-任意のサイズを渡されたときに、何番目のサイズのグループに属しているのかを計算するのは、ビット演算を使うことでO(1)のオーダーで演算できます。
--厳密にはサイズ情報がNビット幅で渡されるのならO(logN)にはなっていますので、まあ最大サイズをMとしたら、O(log(logM))ってことでしょうか。
-番号が決まったら、その番号の線形リストの先頭から一つとってくるのがmallocで、その番号の線形リストの先頭に一つ付け足すのがfreeです。これらはどちらも当然O(1)なので、すごく速いです。
--当然のことながら、線形リストの要素はその空きメモリ自身を兼ねるので、線形リストを伸ばしたりちぢめたりするために、別途のmallocやfreeは必要になりません。
-唯一の例外は、malloc時にリストが空だった場合です。この場合は仕方ないので別の方法で量子化されたサイズの空き領域を確保してきて、それを渡すことになります。
-[Q]なぜサイズを量子化するのですか？
-サイズを量子化しなければ、線形リストがたくさん必要になってしまいます。また似たようなサイズでも別々のリストで管理することになると、free済みのものを割り当てるという「リサイクル」がしにくくなります。そうなるとメモリが枯渇しやすくなります。
-量子化によって、たとえは本当は129バイトしか必要ではないのに、160バイトが割り当てられることになります。このときメモリの19%は無駄になります。このムダ率は最大でも20%にしかなりません。これを小さくしたければ量子化の刻みをもっと小さくすることで改善できますが、リサイクル問題も考えると、単に小さくすればいいというものでもなさそうです。もしかしたらもっと荒い刻みの方がいいかもしれません。
-[Q]これでは再結合ができませんよね？メモリが断片化してしまって使い物にならなくなるのではないですか？
-それは実によい指摘です。そう、基本的にはその通りです、もし話がここまでであれば。
** (2)
-KMemPoolは、malloc時にどのプールからメモリを取ってくるかを指定しなければいけません（これが純粋なmallocとは違う、追加の情報に該当します）。freeの時は、取ってきたプールへメモリを返すことになります。
--プールは必要に応じていくつでも作れます。
-このプールという考え方は、メモリオブジェクトの寿命を反映しています。たとえばあるメモリ構造（たとえば二分木）があった時に、そのメモリ構造を構成するメモリは全て一つのプールから取ってくることにします。こうすれば、そのメモリ構造全体を解放した時には、そのプールに属するメモリは全て返されるということになります。
-一方、プールは結構大きな単位（たとえば1MBとか）でメモリを確保して（デフォルトのmallocなどを使って）、それを切り分けて線形リストに充てんしていきます。大きな単位で確保した記録も取っておきます。
-プールに属するメモリをすべて返した時点で（＝オブジェクト構造を解放した時点で）、アプリはKMemPoolをデストラクトするので、KMemPoolは大きな単位で取ってきていたメモリを全部システムへ返します（デフォルトのfreeなどを使って）。
-こうして、断片化したメモリはきれいにつながってシステムに返されることになるのです。
-[Q]プールごとに、量子化された空きメモリを管理するための線形リストがある（＝線形リストが100個以上ある）のですか？
-はいそうです。
-[Q]なんかそれはちょっと無駄っぽくないですか？
-無駄かもしれませんが、仮に100個だとしても、800バイトですよね（ポインタが64bitだとして）。それでアルゴリズムがシンプルになり、高速化もできるのなら、私は許容できます。
-[Q]たとえば二分木をプログラムで扱っているとき、ノードやリーフを増やしたくなったら、メモリ確保が必要になりますよね？その時にどのプールから取ってくればいいのかなんて、どうやって知るんですか？
-二分木の中に、どのプールを使うかの情報も含めておくのです。そうすれば間違いはないです。
** (3)
-デバッグ効率などを考えると、プールにすべてのメモリが返されたわけでもないのに、間違ってデストラクタを呼び出してしまった場合にエラー終了できるとより良いかもしれません。
-そのためには、プールごとに割り当て済みのメモリブロック数をカウントしておくといいでしょう。これが0になっていないときにデストラクタが呼ばれたら、エラー終了すればいいわけです。
** (4)
-私が使っているKMemPoolは、メモリ利用効率を徹底して追及するために、メモリブロックのサイズやどこのメモリプールに属しているかなどの情報を、メモリオブジェクトのヘッダに含めていません。だからfree時に指定しなければいけません。これは便利ではないので、もしそれらをメモリオブジェクトのヘッダに含めるのなら、それも有意義だと思います。
-さらに、freeした際にメモリブロックのサイズを-1などのあり得ない値に改変するようにしておくと、double-freeのバグを容易に検出できるようになるでしょう。
-ちなみになぜメモリブロックのサイズやメモリプールへのポインタをメモリブロックに格納しなかったのかですが、結局のところfreeするプログラムはmallocするプログラムと同じレイヤに属している場合がほとんどで、これらの情報をすべて持っていることがとても多いのです。だから困ることは時々しかなく、困った場合は、自前でメモリオブジェクトの中にsizeフィールドやmempoolフィールドを持たせるだけで簡単に解決できています。
** (5)
-アイデアのきっかけについて。
-もともとは、メモリのフラグメンテーションをどうするかを考えていました。たとえば、
for (i = 0; i < 10000000; i++)
p[i] = malloc(100);
-みたいなループを回した後に、p[i]の偶数番号だけfreeしたらどうなるでしょうか。そりゃ断片化しまくりですよね。
-これを救済するには、使っている番号だけq[i]にmallocし直して、その後にp[i]を全部freeとかすれば良さそうなものですが、それでもq[i]がp[i]の中に混ざりそうで、結局アプリ側ではほとんど何も解決できないなと思ったのです。
-これを救済するには、使っている番号だけq[i]にmallocし直してコピーして、その後にp[i]を全部freeとかすれば良さそうなものですが、それでもq[i]がp[i]の中に混ざりそうで、結局アプリ側ではほとんど何も解決できないなと思ったのです。
-この状況は標準のmallocとfreeだけではどうしようもないのです。これ以降のmallocでは別のところから取ってくれとか、何かそういう伝達手段がなければだめだと思いました（註1）。
-もちろん、そもそも断片化なんか気にするまでもないという態度をとることも可能です。でも断片化が進むと、空きメモリは十分にあるのに、メモリ不足やスワップファイルの巨大化やメモリ空間不足に陥る危険があるのです。
-しかもメモリは連続しているほうがキャッシュ利用効率が良くなります。
-別のケースとしては、この「清書作業」をやる前に、別の作業をしてしまって、freeした偶数番のp[i]の中が違うオブジェクトの一部として使われてしまったというのはどうでしょうか。そうなったら、もはやその後でp[i]の清書作業をしても、まとまった領域を解放することができません。本来はまとめられたかもしれないのに。
-この辺りの思考実験を出発点として、KMemPoolのアルゴリズムを作るに至りました。
-（註1）もちろん、t = malloc(100 * 5000000)して、ここに奇数番号の内容をコピーしておいて、p[i]を全部freeしたのちに、q[i]を必要なだけmallocして、そしてtからq[i]にコピーして、最後にtをfreeすれば、とりあえず目的は達成できます。しかしこれはメモリコピーの回数が倍増して時間がかかるうえに、本来は連続した領域が必ずしも必要ではないのに、100*5000000の連続領域を（一時的にとはいえ）必要としてしまっているのです。・・・やりたかったことはこれなのだろうかと、私は思うわけです。
* こめんと欄
#comment
![[K Wiki]](k.jpg "[K Wiki]")
