世代別とインクリメンタル

Ruby

mrubyでどのように実現しているのかを眺めてみたので把握したことを個人的メモ。

■世代別GCとインクリメンタルGC
mrubyでの世代別GCは全探索するメジャーGCと、差分探索するマイナーGCに分かれる。このうちマイナーGCはルートスキャンからスウィープまで一気にやるが、メジャーGCのほうは時間がかかるのでインクリメンタルに処理される。世代別GCは他の言語やVMでも採用されているが、ものによって世代ごとにGCのアルゴリズムを変えたり、世代が3つ以上に分かれていたりと実装はまちまちである。mrubyは新旧2世代の管理でメジャー/マイナーともにマーク＆スウィープGCとなっている。
インクリメンタルGCはVMを長時間止めないようにGCのマークおよびスウィープ処理を途中で止めて、VM処理に戻ることができるアルゴリズムで、マーク中やスウィープ中にVMによってオブジェクトが新規作成されたり、参照が書き換えられたりすることがありえる。新規作成されたオブジェクトに対応する仕掛けは2種類の白であり、参照の書き換えに対応する仕掛けがライトバリアである。世代別のマイナーGCでも差分を認識するために書き換えられたオブジェクトを知る必要があり、これも同じライトバリアの仕掛けを使える。世代別GCとインクリメンタルGCは相性がよい。
VM実行中に参照が書き換えられるというのは並列実行されるコンカレントGCでも同様で、これもライトバリアで参照の書き換えを認識する。インクリメンタルGCはシングルスレッド用のアルゴリズムで、別スレッドでGCを走らせられるならコンカレントGCでよい。GCスレッドを複数起動すると排他制御がややこしくなるが、なによりmrubyは組み込み向けという側面もあるので処理系としてスレッドを活用するのは少し微妙である。

■世代別GCの大枠の動き
まずメジャーGCで使っているオブジェクトをマークし、使っていないオブジェクトをスウィープする。その後、マイナーGCに移行する。メジャーGCでマークされたオブジェクトはマークされっぱなしで、変更があった場合はライトバリアで捕まえる。マイナーGCはライトバリアで捕まえられたものと、新規作成されたオブジェクトのルートから辿れるものをマークし、残ったオブジェクトを回収する。
マイナーGC起動のタイミングは前回のメジャー/マイナーGC後に残ったオブジェクトの数+GC_STEP_SIZE(デフォルトでは1024)となっていて、GC_STEP_SIZEの数だけオブジェクトが作成されたらマイナーGCが動く。つまり新規作成された1024のうち、参照がなくなって捨てられたオブジェクトが回収される。このタイミングで参照が残っていたオブジェクトはマークされて、そのままマークされっぱなしになる。マークされっぱのオブジェクトは世代別GCで言うところの長寿命オブジェクトというものである。すぐに捨てられるオブジェクトが偶然にも悪いタイミングで捕まえられる可能性はあるにしても、長いこと残るオブジェクトをマークし直さないことの性能改善効果が大きい。
マイナーGCが終わったときにmrb->majorgc_old_threshold(メジャーGCを起動するオブジェクト数)とmrb->live(残ったオブジェクト数)が比較されて、mrb->liveが大きければ次はメジャーGCが動作することになる。メジャーGCはマイナーGC終了直後に動作し始める。メジャーGCはインクリメンタルGCなのでちょこっとずつマークされていく。メジャーGCが終わるとそれ以降はまたマイナーGCとなる。

■インクリメンタルGCの大枠の動き
メジャーGCはインクリメンタルに動作する。動作タイミングはオブジェクト生成時で、GC_STEP_SIZE個のオブジェクトが生成されるたびに1区切りぶんだけ動作する。この1区切りというのが微妙で、マーク側の処理だとマークしたオブジェクト数というわけではなく、gray化したオブジェクト数でもなく、チェックしたオブジェクトの総数である。チェックしたオブジェクトがGC_STEP_SIZE/100*mrb->gc_step_ratioを超えるまで実行される。mrb->gc_step_ratioはGC.step_ratio=で設定できるので、都合が悪いときは変更することができる。
スウィープもインクリメンタルに処理される。ヒープスロット1個単位で処理され、ヒープスロット1個ぶんのオブジェクト数を加算していって1区切りを判定する。解放数は無視する。
つまり、インクリメンタルGCはVMを長時間停止させないための仕掛けだが、時間で測っているわけではない。そもそも起動タイミングがオブジェクト生成なのでオブジェクト生成が集中していると(極端な例ではArray.new(100000){[]}とか)集中して止まるし、オブジェクト生成が無ければ止まらない。停止する時間もチェックしたオブジェクト数なので、オブジェクトの参照構造により増減する。ファイナルマークフェイズは一気に処理するのでライトバリアが多いと長時間停止する。Cで実装されたオブジェクトの解放処理に時間がかかるようならその時間や数も影響する。結局のところ、それなりに停止時間を短くする努力はするが何も保証はしてくれない。
シビアな組み込みで使うことを想定していないという話なのだが、たとえばGCの実行間隔の制御や停止時間の制御などを気合入れて作り込めばリアルタイム処理用に細かい制御が可能にはなるはずで、まあおそらくそれ相応の性能低下はあるだろうが、できないことはなさそうだ。ただ、そういう用途に使うCPUでそういう処理にmrubyを使うという話にはまずならないのでそこまでする理由はいまのところは無い。

■起動直後の動き
mruby起動直後はmrb_init_heapで各変数が初期化される。これはmrb_openから呼ばれるのでVMインスタンス生成時である。この中でmrb->gc_full=TRUEとしているのでまずはメジャーGCが動くようだ。とはいえはじめはオブジェクト数0なので、動いても困る。mrb->thresholdはここで初期化されないので0になっていて(なるのかな)、1個目のオブジェクト生成でまずヒープスロットが1個作られてオブジェクトが生成され、でもGCは動作せず、2個目のオブジェクトを生成したときに動作する。オブジェクトが1個しかないのでスウィープまで一気に走り(なにもされない)、マイナーGCに移行する。1個目に生成されるオブジェクトというのはコードを眺めた限りではおそらくBasicObjectクラスのクラスオブジェクトじゃないかと思う。
そこから先は通常のマイナーGCの動作で、オブジェクト数がmrb->gc_thresholdを超えるたびにマイナーGCが走り、残ったオブジェクトがmrb->majorgc_old_thresholdを超えたらメジャーGCになる。
実際このように動いているのかどうかは内部情報を出力させながら眺めてみるしかない。そのうち気がむいたらやるかもしれない。

■おしまい
これより先の動作詳細については気合を入れて読み解くか、内部情報を眺めるかといった感じになるだろう。わりとコンパクトなつくりになっているのでGCに興味がある人はmrubyのGCで勉強してみるのもよいかもしれない。