GC/extend/世代別GC
最終更新：
author_nari 2009年04月18日(土) 16:16:08履歴
世代別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がある。
それは「古くから生き残っているオブジェクトはそのまま生き残りやすく、新しく確保されたオブジェクトほどすぐにゴミになりやすい」(*)
という傾向である。
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 set
- card marking
- page marking
利点
- Minor collection の実行時間はヒープ全体のGC に比べ短いので、プログラムの停止時間を改善できる。
- 上述の(*) という傾向が成り立つようなプログラムにおいて、トータル実行時間を改善できる。
欠点
- major collection が起こってしまえば長く停止してしまう。
- 上述(*) の逆の傾向にある(古いオブジェクトの方が先に死にやすい) プログラムでは逆効果となりうる。
実コードを見たい場合
- JVM処理系(複雑なアルゴリズムの為、詳細は後述する)
- Smalltalk処理系の何か
おまけ
remembered setの更新
remebered setは write barrier により増えていき，major collection の際に一新される．
具体的な手順を以下に述べる．
これにより，生きているオブジェクトのみの新しい remebered set が構築される．
具体的な手順を以下に述べる．
- major collection の前に remebered set を破棄する．
- mark を付ける際にオブジェクトの remebered set フラグを確認する．
- remenbered set フラグが立っているオブジェクトであれば，remebered setに追加する．
これにより，生きているオブジェクトのみの新しい remebered set が構築される．
- カテゴリ：
- パソコン
- ガーベッジコレクタ（GC）
コメントをかく