河野真治 @ 琉球大学情報工学です。(う、こんなこと議論するの〜)

Conservative GCが malloc/free に負けないってな話はそういえば、
あったなぁ。

In article <m3wtzc8uwc.fsf@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <maeda-news@ialab.is.tsukuba.ac.jp> writes
> まさか動的「割り付け」を使わない場合とGCを比べてるんじゃないですよね。
> 手動で「解放」するかGCを使うかで計算量(定数倍)が変わるという主張ですよ
> ね?  (オーダーは普通かわりませんよね?)

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

> でも、そもそも、割り付け/手動解放のコストを見積もるのもかなり難しいと
> 思うんだが… まさかmallocやfreeがO(1)とか思ってませんよね。

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

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

なんか避ける方法あるのかなぁ。

---
Shinji KONO @ Information Engineering, University of the Ryukyus
河野真治 @ 琉球大学工学部情報工学科