GCアルゴリズム詳細解説

Old世代を車両に分割してインクリメンタルにGC

世代別GCの欠点であるメジャーGCの停止時間の短縮化を図った手法である。
この手法では、旧世代を固定サイズのブロックに分割し、そのブロックを車両と呼び、
一つ以上の車両を連結したものを列車と呼ぶ。
一度のメジャーGC で一つの車両のみをGCの対象とする。
各車両には通し番号をつけ、この順にGCを進めていく。

新世代と各車両にはremembered set を用意する。
新世代のremembered setには旧世代のオブジェクトからの参照を記録する。
各車両のremembered set には車両間の参照のみを記録する。
新世代から旧世代への参照を記録しておかなくてよいのは、
メジャーGC がマイナーGC の直後に行われるため、メジャーGC の際にそのような参照はないからである。
また、車両間の参照のうち番号の小さい車両のオブジェクトからから番号の大きい車両のオブジェクトへの参照も記録しなくてよい。
これは、GCを車両の番号順に進めていくためである。
つまりその車両がGCされる際には常に先頭にその車両があるため、参照の記録は後続のみで事足りる。
各車両のremembered set を上図 に示す。

メジャーGC では、まずルートスキャンによりごみ集め対象の車両にあるオブジェクトを，適当な列車の最後尾の車両へコピーする。
ルートスキャン後はコピーされたオブジェクトをスキャンし、GC対象となっている車両のオブジェクトのみをルートスキャンと同様にコピーしていく。
次にGC対象の車両のremembered set をスキャンする。
remembered setに登録されているオブジェクトを辿り、参照元のオブジェクトの列車の最後尾の車両にコピーする。

コピーする際に車両がいっぱいであれば空の車両を連結し、そこにコピーする。
ごみ集め対象の車両には生きているオブジェクトは残っていないのでフリーリストに連結し、あとで再利用できるようにしておく。

remembered set に参照を記録するかをチェックするタイミングはポインタを書き換える時である。
車両番号を比較し、コピーされた車両より、参照先の車両の方が若い番号だった場合のみremembered setに記録する。
具体的なタイミングは以下となる。

1. 新世代から旧世代へコピーされる時
2. 古い車両をGCし最後尾にコピーする時
3. ミュテータによって参照が変更された時

この手法では参照関係のあるオブジェクト同士が同じ列車に配置されるようになっており、
大きな循環構造を持ったオブジェクト群もやがて列車ごと回収することができるのが特長である。

1. 最大停止時間を軽減できる
2. 大きな循環構造を取り除くことができる

1. スループット性能が悪くなる

　・不明