Copying GC
コピーGC
ある領域上の生きていているオブジェクトだけをすべて別の領域にコピーし、元の領域のものはすべて破棄する
ヒープ全体を同じサイズのfrom空間とTo空間に分ける
↑この「わけること」を半空間アルゴリズム(semi-space algorithm)というらしい
深さ優先探索が行われる
手順
1. ルートから参照できるオブジェクト、その子どもたちを再帰的にコピー
2. 終わったら、From空間に残っているオブジェクトを全部削除
3. ポインタを変更
4. From空間とTo空間を入れ替える
ヘッダに格納するもの
COPIEDタグ
コピーされたかどうかのフラグ
forwardingポインタ
あとでコピー元オブジェクトを指すポインタが見つかった時にそのポインタをコピー先へ付け替えるためのもの(p.74下図がわかりやすい)
アロケートするときの方法？
JVMやRubiniusがコピーGCを使って新しいオブジェクトにメモリを割り当てる時に使用するアルゴリズム
概要
メリット
高速、実装がシンプル、参照の局所性、異なるサイズのオブジェクトを作成できる
メリット
チャンクの中身が分裂していない、一つの塊になっているのでフリーリストをたどったりする必要がない
→アロケーションは高速
MarkSweepGCなどと違い、生きているオブジェクトのみを探索するのでスループットが小さい
参照関係になるオブジェクト同士がヒープ上で近い位置に配置されるので、CPUのキャッシュメモリの仕組みが良く利き、ミューテータの実行が高速になる
もうちょい調べよう
デメリット
常に半分が未使用になっているので、ヒープ領域の使用効率が悪い
保守的GCと相性が悪い
再帰的関数呼び出しが遅く、スタックオーバーフローの恐れもある
デメリットへの対策
CheneyのコピーGC
再帰的ではなく、反復的にコピーを行う
COPIEDタグを使わずに、コピー済みかどうかを判断する
コピー済みのオブジェクトはTo空間のどこかへのポインタを持っているよな
幅優先探索を行っている
ヒープ領域がキューを兼ねている
従来のものに比べるとキャッシュメモリの恩恵を受けづらくなってしまう
これへの対策が「近似的深さ優先探索」
近似的にコピーGCを深さ優先探索によって行う(? もともとそうなのでは？)
未読！！！！
キャッシュメモリの恩恵を十分に受けられる
ヒープ領域を半分しか使えないデメリットを解消
ヒープ領域をn等分にし、そのうちの2つをFrom,To空間として使う
残りの部分(n-2)はMarkSweepGCを使う
デメリットはMarkSweepGCと同じ。
緩和するためには、MarkSweepとして使う部分を減らせばよいが、そうすると未使用の部分のサイズも大きくなってしまう
JVM,RubiniusはEdenヒープろいう新しいオブジェクトを割り当てるための第3のヒープ領域を有する
Fromには、前のGCでコピーされたもの。Toは空。新しいオブジェクトはEden空間にアロケートする
GC時はFromとEdenからToにコピーする
メリット
EdenヒープはGCが終わるたびに空になるのでより多くのメモリを新しいオブジェクトに割り当てることができる(よくわからん)
Copying GCが用いられている言語
Ruby (JRuby, Rubinius)
Java
OCaml
Haskell