tri-color inclemental gcの色

mrubyのgcを眺めていて把握したことを個人的メモ。

mrubyは世代別GC+インクリメンタルGCなわけだが、このインクリメンタルGCはtri-color inclemental gcとコメントに書いてあるようにオブジェクトのマーク状態を色で表現している。3色で白、灰色、黒となっていて、実際には白が2種類あるので4色なのだが、とりあえず3色である(?)
白はマークされていない状態、灰色は存在を確認したが参照先は見ていない状態、黒は参照先までチェックした状態となっている。

■白と黒と灰色について
とりあえず再帰型のシンプルなマーク＆スウィープGCを作ると、最初にフラグをクリアしてマークしたもののフラグをセットしていき、マークが終わってからフラグがセットされていないオブジェクトをスウィープすることになる。この場合は2色である。
再帰型のマークはマシンスタックを消費するのであまりよろしくなくて、再帰が深いとスタックオーバーフローしたりするので、マークスタックを使うようにして再帰を避ける。マークスタックは通常オブジェクトのリストで表現して、ルートから辿って発見したオブジェクトをマークスタックに突っ込んでいき、マークスタックが無くなるまでループする感じで実装する。
mrubyのマークスタックはmrb->gray_listで表現される。名前のとおり灰色のオブジェクトを入れるリストである。ルートスキャンフェイズでルートにあるオブジェクトはとりあえず灰色にしてgray_listに突っ込む。マークフェイズでgray_listにあるオブジェクトをひとつ取り出して黒にし、その参照先が白だったら灰色にしてgray_listに入れる。灰色と黒は無視する。以下gray_listが無くなるまで繰り返しとなる。

■灰色の存在意義
gray_listに入っているオブジェクトはすべて灰色であり、灰色のオブジェクトはすべてgray_listに入っている。2重管理のようで実際に2重管理なのだが、なぜ灰色という状態をフラグで保持する必要があるのかというと、たとえば白のオブジェクトがgray_listに入っていた場合、他のオブジェクトから参照した先が白だったらそのままgray_listに入れようとしてリストが破壊されてしまうし、黒のオブジェクトをgray_listに入れた場合、ライトバリアでひっかかったオブジェクトをgray_listに入れようとしてやっぱり破壊されてしまうからで、すでにgray_listに入ってますよという状態がリストを探索しなくてもわかるように色をつけるのである。探索すれば灰色は必要ないが、わざわざ探索する理由もない。
ライトバリアが無ければ再帰しないマーク処理でも黒オブジェクトをgray_listに入れておけば問題はないし、ライトバリアがあってもgray_listを探索すれば黒を入れておいても問題はない。アルゴリズム的に必須というわけではないので、効率の話だろう。
ちなみにオブジェクトリストを作るためにオブジェクトはobj->gcnextというポインタを持っているのだが、ここに値がセットされていれば灰色なので、colorフラグと共有できちゃったりするんじゃないかとか考えているのだが、ポインタが4バイトアラインされているのが前提になるので組み込み用のmruby的にはイマイチかもしれない。

■2つの白について
ところで、mrubyのgcには白が2つある。その理由を考えるには、白が1つしかなかったら何が起こるかを考えてみるとよい。
mrubyはメジャーGCの場合にインクリメンタル処理をする。マーク開始時にルートスキャンフェイズが実行され、ルートから辿れるオブジェクトをgray_listに入れる。この対象はトップのselfだとか環境とかもあるが、VMが使うスタック領域も探索している。
その後、VMを再開しつつインクリメンタルにマーク処理を進め、最後にファイナルマークフェイズが実行されてマークを完了する。ファイナルマークフェイズはライトバリアでひっかかったものをマークする。ライトバリアは各種オブジェクトの参照先を変更した場合に発生するが、スタック領域が変更されても発生しない。VMが命令を実行するたびにライトバリアしていては遅すぎるからだ。したがって、マーク中にスタックから参照されるだけの新規オブジェクトを作成(newしてローカル変数に入れるとか)した場合、ライトバリアで捕まえられずに白のままでスウィープフェイズに突入して、結果、オブジェクトはめでたく回収されてしまう。これはまずい。
また、スウィープフェイズもインクリメンタルに実行されるので、スウィープ中に作成されたオブジェクトも即座に回収される。これもまずい。
これらの現象を回避するために、ルートスキャンフェイズを実行するたびに現在の白として白Aと白Bを交互に切り替える。作成されたオブジェクトは現在の白になり、スウィープフェイズでは古い白だけを回収する。この場合、現在の白オブジェクトは実際には使われていなくても回収されない。
白が1つだけという実装も可能だろう。ファイナルマークフェイズの前か後にルートスキャンフェイズをもう一発流してやれば新オブジェクトを捕まえることができるし、スウィープ開始時に全スキャンして白リストを作ってからそれを辿って回収すればインクリメンタルスウィープもできる。しかしどう考えても白を2つにして切り替えたほうが簡単だし速い。利点は作ってすぐ捨てるオブジェクトが今回のスウィープですぐに回収されることぐらいだ。メモリ効率と実行速度の兼ね合いとなる。

■おしまい
現在のGCのマークの仕様は、なるべくしてこうなっているように見える。mrubyによくフィットしていて効率的だし無駄が無い。実装のほうはちょっと荒削りに見える。
tri-color inclemental gcはマーク側のアルゴリズムであり、スウィープ側は特に決まりもない。実際ヒープスロットとしてメモリ管理を実装しているが、このへんはもうちょっとなんとかなりそうな気がしないでもない。
とはいえ俺がどうにかしてやろうみたいな偉そうなことが言えるわけでもなく。なんかひらめいたら試してみたいとは思っている。