- SlideBoom

mrubyの
Tri-color incremental mark & sweep GC
その2
GC Advent Calendar 24日目
前回の資料のつづき
http://bit.ly/WGqOGp
前回のまま実装したら
マーク漏れが起こる
『スイープ中に
新しいオブジェクトが
割り当てられてしまう』
の例
Incremental sweep phase
roots
黒色のオブジェクト間のグラフを変更されても問題ないが…
ククク、参照関係を
変更してやる
ミューテータさん
Incremental sweep phase
roots
新しいオブジェクトを作られると…
マーク漏れ
新しいオブジェクト
を作ってやる
ミューテータさん
Incremental sweep phase
roots
スイープ!!
逝ってしまった…
どうやってマーク漏れを防ぐのか?
実は白色は2パターンあるのです。ここでは以下のように分類。
白A
白B
mruby全体では『現在の白色』として白A or 白Bのどちらかを記録。
それによって新しいオブジェクトの白色のパターンが変わる。
現在の白 => 白A
オブジェクトちょうだい
はい、どうぞ
(白Aのオブジェクト)
なので…
そして現在の白はinitnal mark phaseの
直後に切り替わり、スイープは
切り替わる前の白色だけを対象とする
1. root scan phase
現在の白
roots
切り替わる
ルートスキャン終わり
スイープ対象
現在の白
2.incremental marking phase
roots
スイープ対象
3.incremental sweep phase 現在の白
スイープ対象
roots
新しいオブジェクトを
作ってやる
ミューテータさん
3.incremental sweep phase 現在の白
スイープ対象
roots
スイープ対象ではないのでスイープされない!!
スイープ!!
ククク、消えろおお
ミューテータさん
3.incremental sweep phase 現在の白
スイープ対象
roots
スイープ対象ではないのでスイープされない!!
アバババ
ミューテータさん
白を2パターンにわけることで
GC中に生成されたオブジェクトは
そのGCのサイクル内では無視されるのだ
(こうして世界に平和が訪れたッ)
明日は2種類のライトバリアの話