oupoの日記

RGenGCの発表資料を読んだ

21:21

ささだこういちさんによるRGenGCの発表資料を読みました。

英語だったので条件反射的にｳｯとなったのですが印刷してボールペンを片手に辞書を開きながら読み通しました。

RGenGCとは何物か、その仕組みはどうなっているのかということに注目してまとめます。誤りがあれば指摘していただけると助かります。

世代別GCの復習

世代別GCではオブジェクトを新世代と旧世代にわけます。

オブジェクトは最初新世代として生成され、一度でもGCして生き残ったオブジェクトは旧世代となります。ふだんのGC (minor GC)では新世代のみを扱い、旧世代オブジェクトは死んでいても回収しません。たまに行うmajor GCで旧世代も含めてGCします。

世代別GCのminor GCでは次のことをします:

• ルートオブジェクトからたどれるオブジェクトにマークをつけます
• マークをつけたオブジェクトは旧世代へ移行します
• ただしマークの最中に旧世代オブジェクトに行き着いた場合、そこから先はtraverseしません
• マーク処理が終わったのち、マークのつかなかった新世代オブジェクトを回収します

さて上の方法だけでは問題があります。マーク時、旧世代オブジェクトからその先はtraverseしないという部分です。これでは旧世代オブジェクトを通してしかルートからたどれない新世代オブジェクトにマークがつきません。

つまり生きているオブジェクトを誤って回収してしまう可能性があります。

そこで旧世代オブジェクトから新世代オブジェクトへの参照関係 (old→new)が発生したら、旧世代オブジェクトの方をRemember Setという集合に入れ、新世代へ移行させます。

そしてRemeber Setをminor GCのマーク時に一つのルートとして扱います。

これで生きているオブジェクトを誤って回収してしまう可能性はなくなりました。

なお、Remember Setに入れたのと同時に新世代へ移行していますが、これをしないとRemember Setからマークしにいこうとしても旧世代だからといってすぐに突っぱねられてしまうからこうしています。

さて、これを実現するためには、オブジェクトに書き込みがあったとき、それがold→newの参照関係を発生させていないかチェックする必要があります。

これをライトバリアといい、オブジェクトの属性に書き込むコードの位置には必ずライトバリアを挿入しなければなりません (Cレベルの話)。

ここがCRubyに世代別GCを導入できない理由でした。ライトバリアを挿入しないといけないとなると、既存の拡張ライブラリとの互換性がなくなり、また開発コストも増大します。

そこでRGenGCです。

RGenGC

RGenGCとはRestricted Generatinal GCの略でライトバリア保護されたオブジェクトとそうでないオブジェクトを同じヒープ内に共存することを許容した新しいGCのアルゴリズムです。RGenGCを導入しても拡張ライブラリの互換性は100%保たれます。

ライトバリア保護されたオブジェクトをsunnyオブジェクト、そうでないオブジェクトをshadyオブジェクトといいます。これをアプリケーション側からみるとshadyオブジェクトは何も気を配らず作ったり書き換えたりできますが、sunnyオブジェクトはきちんと漏らさずにライトバリアを挿入するという注意深さが要求されます。つまりsunnyオブジェクトの方が実装コストは高めです。

もちろんshadyオブジェクトがsunnyオブジェクトよりも少なければ少ないほどGCのパフォーマンスは向上します。

Cレベルのオブジェクト生成時にFL_KEEP_WBというフラグを設定すればsunnyオブジェクトとして生成され、特に指定しなければshadyとなります。sunnyオブジェクトをshady化することは可能ですがその逆はできません。

現在、Array, String, Hash, Object, Numericといったオブジェクトはsunnyオブジェクトとして生成されます。

sunnyオブジェクトをshady化するのは、もう書き換えを追跡しきれない！という状況で使えます。たとえばArrayオブジェクトの実体のポインタを得るRARRAY_PTRというマクロがC APIにありますが、これを使われるともう書き換えは追跡しようがありません。そこでRARRAY_PTRマクロには使われたらshady化するという動作が加えられています。これによってRARRAY_PTRを用いる拡張ライブラリとも互換性を保っています。

結局のところ次の2つの利点がいえます:

• 明示的にsunnyオブジェクトとしてオブジェクトを生成しない限りライトバリア挿入の必要はないので拡張ライブラリの互換性が保たれます
• 一気にすべてのコードをライトバリア対応にすることは困難ですが、徐々にライトバリア対応コードを増やしてGCのパフォーマンスを伸ばしていくことができます

RGenGCの仕組み

RGenGCがどのような仕組みなのか見ていきます。

まずRGenGCの高速化の肝はどこかというと、minor GCのマークフェーズで旧世代オブジェクトより先をたどらないことです。

一方、スイープフェーズは従来通り、ヒープを全て見るのでスピードは変わりません。

さてshadyなオブジェクトとはライトバリアなしで書き換えが行われうるオブジェクトでした。するとshadyなオブジェクトがもし仮に旧世代に移行しても、自身の属性に新世代への参照ができることを検知できません。

したがってshadyなオブジェクトは旧世代に移行せずずっと新世代のままにしておきます。

minor GC

minor GCでのマークフェーズでの処理を考えます。

通常の世代別GCのやり方通りにマークしてマークしたものは旧世代へ、ただしshadyオブジェクトについてはマークしても移行しないという方法はどうでしょうか。

この方法だと旧世代オブジェクトを通さないとルートからたどれない新世代オブジェクトができてしまいます。

そこでこの方法に加えて、shadyオブジェクトをマークするときはもし親が旧世代化したのであればRemember Setへ入れます。これで上の問題は解決します。

なお親という言葉はマーク処理を木構造のtraverseだとして考えたコンテキストで使っています。「親が旧世代化した」以外の場合として「親はなくルートから直接来た場合」、「親がshadyな場合」があります。

shade操作

次にRARRAY_PTRなどによって、オブジェクトがshadyに切り替わる場面を考えます。このshadyに切り替える操作をshade操作といいます。

特に旧世代のsunnyオブジェクトがshadeされる場合が考察を必要とします。

shadyオブジェクトは常に新世代であるとしていたので、このオブジェクトは新世代に移行します。

しかしこのとき、このオブジェクトが「旧世代オブジェクトを通さないとルートからたどれない新世代オブジェクト」と化してしまう可能性があるので、このオブジェクトをRemember Setに入れます。

これがオブジェクトをshadyに切り替えるときに一緒に行うことです。

以上でRGenGCの仕組みを取り上げました。案外あっさりしていますね。