[WitchTech 00415] Re: 手抜き malloc

[narunaru@123mail.net]

なるなると申します。

# 実は同じころに K&R の malloc をデバッグ用にちょっといじっていたので、ヘッ
ダが大きいのが気になっただけなのです。(malloc を直接使わないのであればあま
り問題にならないですが ...)

 > <200009010541.AA00400@episode1.techbrains.co.jp>
 > From: swd@techbrains.co.jp
 > Date: Fri,  1 September 2000 14:41:48 +0900
 > 
 > こんにちは、dieです。

 > # 「リスト」というのが heap_block_t->next によるリストという
 > # 意味でしたら、もともと各ブロックはリストから切り離されずに
 > # 処理されてますが・・ん〜やっぱり理解してない気がする。

# すいません。すっかり忘れていましたが、そこまではソースを読みました。

free した領域を管理するリストと malloc したリストを別に持てば、ヘッダのフ
ラグが要らなくなるのではないかと思ったりしたのです。(free list につながれ
たものは free ずみ)

ただ、die さんの実装のままで、ブロックは word alignment かつ必ず整列してリ
ストにつなぐことにして、next の最下位ビットをフラグに流用すれば size も不
要になるかもしれません。(こちらのほうがヘッダのサイズが小さくなる) と後か
ら思いました。


 > best fit法と言う名前は初めて知ったのですが、確かに全体的な
 > パフォーマンスを考えるとこの方が良いのかもしれませんね。

どう判断されるかはお任せしますが、あの作者は best fit が良いと主張していま
すが、手元にある教科書(*)には first fit がよいと書いてあります。small
model で扱える程度のメモリであればブロック数が少ないので best fit が不利に
ならないというところかもしれません。

# ということで前回「通説に反して」と書きました。

(*) 佐々政孝: プログラミング言語処理系 (岩波講座ソフトウェア科学 5)
巻末を見ると Knuth の Foundamental Algorithms が挙げられています。(こちら
はちゃんと読んでいません。)