[WitchTech 00436] Re: 手抜き malloc

[Daisuke Sawada <swd@techbrains.co.jp>]

dieです。

On Fri, 1 Sep 2000 23:46:30 +0900 (JST)
in [WitchTech 00415] Re: 手抜き malloc
narunaru@123mail.net wrote:

> なるなると申します。

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

大昔、私もK&Rのmalloc()を読んだ覚えがあります。最近は手元にないので
参考にしてませんが、今もう一度そこだけ読んでみたいです(^^;

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

それは面白そうなアイデアですね。
ただ管理リストが二系統あると、断片化が余計進んでしまう気がします。

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

あ、こっちも凄いな。私自身、nextかsizeのどちらかは潰しても良いかな、
とは思っていましたが・・上記のアイデアなら各ヘッダたったの２バイト。
結局sizeを潰さなかったのは「安直でわかりやすいコード」を心がけたから
です。理由は実装時間の短縮(笑)。「ヘッダあたり２バイト」までチューン
出来るというならやってみる価値はあるかもしれませんね。問題はそれに
よるコードの複雑化がどの程度かですね。

# もちろんこちらも、微少なメモリを大量malloc()とかでなければ頑張るだけ
# のメリットが薄れます。そういうのを求めるユーザがいるかどうか。
# そういうリクエストがなければ私自身は取り組まないです。面倒(^^;;;

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

「どこでも効率が良いmalloc()」というのは、どう頑張ったところで
「要求されるメモリは不定長」という仮定からは逃れられないですよね。
だからメモリアロケートが速度に影響を与えるようなソフトを書く場合は、
malloc()を直接使うような事はしないと思います。
ワンダースワンのような「クロック数が速度に直結しちゃうCPU」なんか
だと(笑)、もはや「弾を一個撃つたびに弾オブジェクトをnewする」なんて
考え方は駄目扱い。最初に最大弾数分の配列をmalloc()して、あとは
射出中フラグとかで管理するんじゃないかと。

極論すれば「malloc()なんて要らない」となっちゃうわけで(^^;、それぐらい
ちゃんとした理由があってWitchのライブラリには付いていなかった・・
のかもしれません（多分考えすぎ(^^;）。私はそれでも欲しかったのですけど。

___
澤田　大輔(die)
email: die@zonze.nu(home), swd@techbrains.co.jp(office)