malloc の旅 (glibc 編) - iwiwi 備忘録

すごい分かりやすかった

次の空き領域へのポインタを空き領域の先頭に置いておく
freeしたあと，した場所へのポインタを先頭にしておくのが重要らしい
良い
- コードが簡単
- フラグメンテーションしなければ速い
悪い
- 小さい malloc 多発 → フラグメンテーション
- free が O(n)
- （小さい malloc は多発している：例えば Linux ではマウスポインタが 1px 動くだけでイベントの構造体が malloc）
フラグメンテーションさえ解決すればよい？

アドレス順じゃなくて，サイズ順でソートしてもっとく？ → free で併合できない，フラグメンテーションが進む
仕方ないので構造体メンバを増やす：サイズを覚える（＝今までと同じリスト），前のサイズも覚える（→前に戻れる），サイズ順リストも覚える
- free が O(1) になった（前がわかるから）
- malloc が O(n)，ヘッダサイズ大
ヘッダサイズ：細かいテクで改善してゆく
- アドレスの下３ビットが０になることを利用し，そこにつめる
malloc：リストを，サイズごとに分けて作っておく
- 512 バイト以下まで全部作る，それから上は指数的にする
それでも超でかいのは困る
- anonymous mmap．/dev/zero を渡すとメモリ確保 API．
- でかいブロックは heap からでなく mmap で直接カーネルから取得