GCアルゴリズム詳細解説

若いやつらを優先するGC

オブジェクトの寿命について、多くのプログラムで観測されるある傾向が知られている。
それは「古くから生き残っているオブジェクトはそのまま生き残りやすく、新しく確保されたオブジェクトほどすぐにゴミになりやすい」(*)
という傾向である。

GC の実行効率は生き残るオブジェクトが少ないほどよいのだから、
古いオブジェクトはほうっておいて(無条件に生き残るとみなして) 新しいオブジェクトを重点的に探索することによって利益が得られそうである。
Generational GC (世代型GC) は、新しめのオブジェクトのためのヒープと、古めのオブジェクトのためのヒープを用いる(上図)。

Copying GC を基にするのであれば、図には示されていないが、新世代のヒープと旧世代のヒープのそれぞれがfrom/to に2 等分される。
オブジェクトはまず新世代ヒープに確保される。新世代ヒープが一杯になったら、ヒープ全体のGCを行なう代わりに、新世代ヒープだけを対象としたGC(minor collection) を行なう。
Minor collection を繰り返した結果、ある程度以上長寿命なオブジェクトが見つかったなら
(例えばGC がn 回起こる間生き残ったら)、そのオブジェクトは旧世代ヒープに移される(殿堂入り、またはpromote と呼ぶ)。
さて、minor collection においては旧世代ヒープ中のオブジェクトをスキャンする必要がない(旧世代オブジェクトは無条件に「生き」とみなされる)。
図ではオブジェクトb 以降の探索は行なわない。このため、minor collection はヒープ全体を探索するよりも速く終了する。

入れ替わりの激しい新世代ヒープと対照的に、旧世代ヒープは殿堂入りオブジェクトによってゆっくりと満たされていく。
やがて旧世代ヒープさえ一杯になったら、そこではじめて、ヒープ全体を探索するGC(major collection) を試みる。

Generational GC を実装する際には、以下のような落し穴に気をつける必要がある。
Minor collectionを行なう際に、旧→新のポインタに注意が必要である。
たとえばc → d のポインタに気付かないと、到達可能なオブジェクトd を間違って解放してしまう。
上図の場合、GC は新世代へのポインタを持っているcとe を全て覚えておき、
minor collection はそれらもルートと見なす。この目的のために(incremental GCの節で説明したような)
write barrier を用いることによって、普段から旧→新のポインタができたかどうかを全て覚えておかねばならない。

Generational GC におけるwrite barrierには、remembered list、remembered set、card marking、page markingがある。

• remembered list

旧→新の参照が発生した場合に、参照先の世代のremembered list が参照元のオブジェクトを(配列などの形で)記憶しておく。GCの際にはこのremembered list をルートとしてスキャンすることで旧→新のポインタを発見できる。

• remembered set

remembered list と似ているが、オブジェクトが登録されていることをオブジェクト自身が記憶している点が異なる。このため、オブジェクト内部に1ビット余計に取る必要がある。これにより、同じオブジェクトが2回以上登録されるのを防ぐことができる。

• card marking

ヒープを2のk乗サイズに分割し、それぞれをカードとする。各オブジェクトは1つ以上のカードに属している(複数のカードにまたがってもよい)。カード内のオブジェクトが書き換えられたかどうかを記録する配列を用意する。要素数はkである。旧→新の参照が発生したとき、参照元のオブジェクトが属するカードがマークされる。GC実行時にはこの配列をスキャンすればよい。

• page marking

card marking のカードのサイズをページと同サイズにしたものである。ページのサイズはOSにより異なるが、通常は4KBである。

1. Minor collection の実行時間はヒープ全体のGC に比べ短いので、プログラムの停止時間を改善できる。
2. 上述の(*) という傾向が成り立つようなプログラムにおいて、トータル実行時間を改善できる。

1. major collection が起こってしまえば長く停止してしまう。
2. 上述(*) の逆の傾向にある(古いオブジェクトの方が先に死にやすい) プログラムでは逆効果となりうる。

• JVM処理系(複雑なアルゴリズムの為、詳細は後述する)
• Smalltalk処理系の何か

remebered setは write barrier により増えていき，major collection の際に一新される．
具体的な手順を以下に述べる．

1. major collection の前に remebered set を破棄する．
2. mark を付ける際にオブジェクトの remebered set フラグを確認する．
3. remenbered set フラグが立っているオブジェクトであれば，remebered setに追加する．

これにより，生きているオブジェクトのみの新しい remebered set が構築される．