Hatena::ブログ(Diary)

oupoの日記

2013-06-05

RGenGCの発表資料を読んだ

21:21

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

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

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

世代GCの復習

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

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

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

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

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

f:id:oupo:20130606181127p:image

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

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

f:id:oupo:20130606181128p:image

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

なお、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オブジェクトについてはマークしても移行しないという方法はどうでしょうか。

f:id:oupo:20130605204803p:image

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

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

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

shade操作

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

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

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

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

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

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

oupooupo 2013/06/06 19:00 ソースコードを読んで裏付けをとって、いくらか推敲しました。
変更点: https://gist.github.com/oupo/5720241/revisions

oupooupo 2013/06/09 09:34 http://d.hatena.ne.jp/nagachika/20130607/ruby_trunk_changes_41110_41150
"Sunny"という名前は廃止されて"Normal"という名前を使うようになったり、旧世代フラグをビットマップに記録するようにしたりといろいろ変更があったようです。
このような記事を書いても、ソースコードはどんどん変わっていってしまいますね (=o=;)