kono@ie.u-ryukyu.ac.jp (Shinji KONO) writes:

> ううむ... 破壊的append と非破壊的appendではオーダは変わりますよね。

オーダーは同じだと思うなあ。 Lispで言えば (append a b) と (nconc a b)
ですよね。どっちも O(length(a))だと思う。

> free を O(1) にするには、memory pool みたいなのを使うと可能
> です。非破壊append bench mark を別プロセスでやって GC しない
> で抜けて来るみたいな感じ。それが一般的なGCの仮定に反する(自
> 由に参照をコピーできる) のはその通りです。で、そういうことす
> ると GC を持っているシステムでは、まずいってな話でしたよね。

なるほど。RTSJ (Real-time Specification for Java)のRegionみたいに一括
解放するわけね。dangling pointerのチェックもしなくて良いなら、確かに最
速ですね。

しかしですね。以下の条件が満たされるならオーダーは変わんないですよ。

・割り付けた領域には、少なくとも一回データが書き込まれる(初期化でも可)
・ヒープサイズは生きているデータの量に比例して増加させてよい
・GCのルート集合の大きさは、高々生きているデータの量に比例する程度

この条件だと、「Nバイト割り付けて解放する」サイクル全体のコストは、GC
使おうと使うまいとO(N)になりますよね。

実際の話、一括解放でよいプログラムの場合、ある期間に割り付けられたオブ
ジェクトが全部ゴミになるわけですよね。これは、現在よく使われているコピー
式の世代別GC がうまくアジャストできれば、全くコピーしないでGCが終る可
能性があります。この場合、ほとんどコストは変わらないでしょう。コピーGCっ
て結局「dangling pointerにならないようにコピー ＋ 一括解放」ですから。

そう都合良くサイズが合わないで、何回かコピーしちゃったとしても、オーダー
は変わらない。たかだか定数倍。

> 二乗でゴミを吐くプログラムなんてダメダメなのは、その通りなん
> だけど、線形でゴミを出すのは良くありますよね。というか、これ
> までの話だと、むしろ推奨されている。で、そうやって生成したゴ
> ミを回収するコストが、ゴミの量に比例するかって言うと、それは
> アルゴリズムによります。

上のとおりヒープを増加させて良いなら、ゴミの量というか割り付けた量に比
例するコストで回収できます。つまり、1バイトあたりの割り付け＋回収のコ
ストは定数オーダー。

                                前田敦司