[OSASK 3824] BOARD: Re: malloc/free の動作

[mone !Atmark! imasy.org]

このメールは、OSASK伝言板に書き込まれた内容です。
この書き込みに返事を書く場合は、下のURLから書き込みを行なって下さい
http://www.imasy.org/~mone/osask/index.cgi?REFER=3d0bf1d6_fca5

2002/06/16 11:03
川合秀実

[OSASK 3823]へのレスです。

>http://eieweb.yz.yamagata-u.ac.jp/~m01873/data/sample.lzh
>
>a.bin の動作ですが、期待通りになっていないように見えます。
>微妙な差ですが。

  確かにおかしいです。・・・いや、おかしくないかもしれませんが。

  stdlib5のmalloc/freeはK&Rのmalloc/freeをアセンブラ化したものを使ってい
るのですが、おかしいとしたらそのアセンブラ化の際に僕が間違えたということ
が考えられます。

  一方、K&Rのmalloc/freeアルゴリズムでは複数の領域をmallocしてからfreeし
た場合空き領域については元どおりになりますが、次のmallocでどこのメモリが
割り当てられるかは(特に空き領域が複数のブロックに分割されている場合)、最
後にどの領域をfreeしたのかによって変化します。・・・これはメモリの使用機
会をできるだけ均一に使うためのテクニックで、最後に開放された領域を覚えて
いて、次はその周辺から割り当てようとしているためです。mallocも同様で割り
当てる領域が決まると次回の空き領域検索はその周辺から始めるようになってい
ます。・・・そんなわけで1回目と2回目で結果が異なるということはありうる訳
です。

  しかし考えてみるとこの仕様はあまりよろしくありません。むしろ集中的に一
個所を使おうとする方がアクセスの局在化が進み、キャッシュの効率が上がると
思われます(このキャッシュにはL1, L2のみならずTLBなども含まれます)。とい
うことで、stdlib5のmalloc/freeにバグがあってもなくても、とにかくもっと単
純なアルゴリズムに書き換えることにします。しばらくおまちください。