ガベージコレクションのアルゴリズムと実装 3,4章

Shinichi Tokunaga @deepneko

CheneyのコピーGCの場合、A→B、A→C、B→D、B→E、B→H、B→I、C→F…っていう参照があったとすると

Shinichi Tokunaga @deepneko

ページサイズをオブジェクト3個分とすると、[A・B・C] [D・E・F] [H・I]・・・っていう風にヒープには配置されちゃうわけ。

Shinichi Tokunaga @deepneko

でも、この手法ならページサイズ分の深さ探索ができるわけよ。

Shinichi Tokunaga @deepneko

だめだ。どうやってもうまく説明できない。

Shinichi Tokunaga @deepneko

複数空間コピー法

Shinichi Tokunaga @deepneko

コピーGCの最大の欠点はヒープ領域が半分になること。じゃ、もっと細かく分割しよっか。

Shinichi Tokunaga @deepneko

ヒープ領域を2等分して、ある2つに対してはコピーGC。残りの全部に対してはマークスイープをする。

Shinichi Tokunaga @deepneko

あ、うそ。ヒープ領域をN等分してｗ

Shinichi Tokunaga @deepneko

だんだんややこしくなってきたな。ここも簡単にいこう。

Shinichi Tokunaga @deepneko

N等分にわける。To空間がGCのたびに1つずつ右にずれていくイメージ。

Shinichi Tokunaga @deepneko

オブジェクトがFrom空間にある場合はコピーする。From空間以外にある場合はマークして、子オブジェクトを再帰的にマークまたはコピー。

Shinichi Tokunaga @deepneko

まぁ、つまりmark_or_copyに渡されるオブジェクトは、From空間にあるならコピーGC、From空間以外にあるならマークスイープの対象だと思えばよい。

Shinichi Tokunaga @deepneko

複数空間コピーのメリット: 使用できないのはヒープ領域の1/Nだけ。

Shinichi Tokunaga @deepneko

複数空間コピーのデメリット: マークスイープのデメリットが乗っかる。結局マークスイープとコピーGCの領域の比率によるんだが、どっちの良いとこも悪いとこも背負うことになる。