久野です。

kono@ie.u-ryukyu.ac.jpさん:
> GC がないとメモリが足りない例っていうのは、unbound っていう意味
> なわけなんだけど...

  違うよ! 所要合計がヒープ量の倍で、でもワーキングセットは収まる
とかそういう意味ですが。

> でもさぁ、メモリ使用量がunboundなアプリケーションって実は、
> インタプリタ的なものしかないんじゃないかなぁ。Conservative GC
> とかでも対象は awk interpreter だったりしますよね。

  それも大嘘だよ…でもとにかくunboundの話じゃないので。

> 生きているセルが定数の場合なんかそうですね。

  それで結構ですよ。

> mark and sweep で

  ちょっと! markするのもsweepするのもヒープサイズに比例するじゃ
ないですか。それはO(1)ではなくO(N)です。

  それにGCはそういうもんで、私が河野さんに質問していたのは自前で
alloc/freeするならO(1)で済むという方の具体例。セルの総量は平均定
数、でもランダムに割り付けと開放が行われる。で、どうやってヒープ
サイズに関わらずに定数時間でalloc/freeするかというと。

                    うーん、その場合は…              久野

P.S. もしかしてセルは全部2のべきサイズでそのサイズ種類数だけリス
     トを作るってやつかな。無駄が最大50%だけどそれなら定数かも。
     前田さんどうしますか。