YARV Maniacs 【第 12 回】 インクリメンタル GC の導入
書いた人：ささだ
はじめに
Ruby 2.2 から、インクリメンタル GC を導入しようと開発を進めています。本稿では、この話題を取り上げたいと思います。
YARV というと、仮想機械、Virtual machine、バイトコード実行系、という気もしますが、インタプリタ全体で VM ととらえて、一つこの話題におつきあい下さい。
インクリメンタル GC は、GC の停止時間を短くするためのアルゴリズムの 1 つです。Ruby 2.2 に導入することで、GC による停止時間を短くしようとしています。
というか、この連載も、とても久々ですね…。そういえば、今年で YARV を作り始めてから 10 年目でした。
これまでの話
Ruby は当初から mark & sweep GC が搭載されていました。ルートから辿れるオブジェクトをマークしていき、マークされていないオブジェクトをゴミと判定して回収する、という、最も基本的な GC アルゴリズムです。また、C 言語で拡張機能を簡単に作るために、保守的 GC として実装してあります。これは、例えば C のマシンスタックをルートオブジェクトととらえ、「オブジェクトのポインタっぽかったら」マークする、というアルゴリズムです。このアルゴリズムのおかげで、オブジェクトへのポインタを C 言語でとくに意識することなく利用することができました。Java とか他の処理系ですと、ポインタ操作時なんかにいろいろとおまじないを追記しないといけません。
このアルゴリズムは実装が簡単で正しく動く、それなりに良いものだったので、Ruby 1.8 まであまり変更なく進んできました。しかし、次のような問題がありました。
- (1) オブジェクト領域用に一度確保したメモリが、オブジェクトの数が減ってもなかなか解放されない
- (2) 停止時間が長い（GC のために、アプリが一時停止する時間が長い）
- (3) fork での Copy on Write（以下、CoW）が効きづらい（mark するたびにメモリ書き込みを行なうので、fork した後 CoW で共有したメモリを dirty にしてしまって結局共有できなくなってしまう）
- (4) マークが再帰処理なのでマシンスタックを消費してしまう
- (5) GC の時間が遅い
(1) の問題は、次のような理由です。まず、ある程度の大きさのメモリブロック（Ruby の GC ではこれをページといいます）を OS から確保して処理をするのですが、そのページ中に 1 つでもオブジェクトが生きていると、メモリブロック自体が解放できないためです。これを解決する最もよい方法は、使っているオブジェクトを一箇所に集めるコンパクション（デフラグみたいな操作、って今はデフラグなんて使わないか）ですが、保守的 GC ではオブジェクトの移動が出来ない（難しい）のでこの方法が使えません。
この (1) の問題を解決するため、（たしか）Ruby 1.9 からページのサイズを数 MB （Ruby 1.8 以前は可変長だった）から、小さく（具体的には 16KB）することで、解放されやすくする、ということをしました。
(2) の問題に対しては、Ruby 1.9.3 から lazy sweep が導入され、スイープ（回収）処理が細切れに実行されるようになりました。この処置により、最大の停止時間が（マーク＋スイープの全部の処理）から（マーク＋スイープの一部の処理）となり、少し改善しました。
(3) は、オブジェクト自体にマークフラグを持っていたため、GC のたびに生きているオブジェクトに書き込みが発生してしまう、というのが原因でした。fork でせっかくメモリを共有しているのに、そのたびに共有が解除されてしまい、（無駄かもしれない）コピーが発生してしまう、という問題です。
この問題を解決するため、Ruby 2.0 からマークする場所をビットマップとして別途用意して、マーク時にそこに書き込むようにすることでこの問題を解決しました（もともと、Ruby EE がやっていた手法ではありましたが、ページサイズを小さくしながらこれを実現する方法にちょっと問題があったため、対応が遅れました）。ちなみに、このビットマップによってマークビットを走査するような処理（例えばスイープ処理）はキャッシュ効率が（圧倒的に）よくなりました。
(4) の問題に対しては、再帰処理をしていてマシンスタックを深いところまで使ってしまうため、別途マーク用のスタックをヒープに用意することでこの問題を解決しました（Ruby 2.0.0 より）。
(5) については、そもそもマーク＆スイープは遅いアルゴリズムとして知られているため、Ruby 2.1 から、もっと速いアルゴリズムとして知られている世代別 GC が導入され、GC の速度が改善しました。
世代別 GC を適切に実装するためにはライトバリアという、オブジェクトの参照関係の変化をチェックする仕組みが必要（配列 a について、a[0] = b としたとき、a が b を参照しますが、こういうのを全部トレースしたい）になりますが、世代別 GC には最初に説明したような C 言語で書いてあるところにおまじない的なものを書く必要が無いため、そういうのを全部適切にチェックする仕組みがありませんでした。そのため、互換性を崩さないで実装するのは難しいと思われていたのですが、ライトバリアで保護しているオブジェクトと保護していないオブジェクトとを明確にわけることで正しく実装できることがわかったため、Ruby 2.1 から世代別 GC を導入することができました。ちなみに、これを RGenGC と名付けています。
世代別 GC は、新しく作られたオブジェクト（新世代オブジェクト）のみを対象とする GC と、それ以外のオブジェクト（古い世代のオブジェクト）を含んで行なう GC の 2 つに分けて実行します。前者をマイナー GC、後者をメジャー GC と言います。この新世代、と古い世代で話を分けるので、世代別 GC といいます。殆どの場合は、すぐに終了する（新世代オブジェクトだけ対象にするから）マイナー GC だけで済むので、トータルの実行時間は短くなる、という話です。
この辺の話題は、次の記事にまとまっています。
- レアでアレなGCの話
- Ruby 2.0.0 の GC 改善
- WEB+DB PRESS Vol.79 特集の RGenGC の章（Ruby徹底攻略にも掲載）
停止時間の問題
さて、前節で (2) を解決するために lazy sweep を導入した、と紹介しました。lazy sweep の導入によって、最大停止時間は
（マーク＋スイープの全部の処理）
から
（マーク＋スイープの一部の処理）
となりました。ただ、そもそもマークの時間が長いので、あまり問題は解決していませんでした。世代別 GC が入って、若い世代のオブジェクトだけを対象にするマイナー GC だけなら、まだ我慢できる時間になったみたいなんですが、すべてのオブジェクトを対象とするメジャー GC を実行すると、停止時間の問題は厳然として存在していました。
アプリ側では、たとえば GC を止める（GC.disable）、GC を暇なときにまとめてやる（OOB GC）などのテクニックが知られています。
で、このメジャー GC の長いマーク時間を解決しよう、というのがインクリメンタル GC です。
インクリメンタル GC アルゴリズム
ここでは、よく知られたインクリメンタル GC アルゴリズムをご紹介します。 インクリメンタル GC は、マークやスイープの処理を細切れにして、GC をちょっとずつ進めていくための仕組みです。 すでに導入できている lazy sweep はインクリメンタル GC の一部となります。
なお、ここで紹介する方法以外にも、GC をインクリメンタルにする方法は知られているので、興味がある人はググってみて下さい。
で、アルゴリズムは … nari3 がまとめてくれていました。IncrementalGC 。が、ちょっと短いですね……。まぁ、ググれば色々出てきます。
簡単に言うと、オブジェクトを 3 つのカテゴリに分けます。
- 白：マークされていないオブジェクト
- 灰：マークされており、これからこのオブジェクトから直接辿れるオブジェクトをマークしようとしているオブジェクト
- 黒：マークされたオブジェクト、このオブジェクトから直接辿れるオブジェクトはすべてマーク済みである
通常のマーク＆スイープですと、白か黒しか無かったのですが、灰状態のオブジェクトが増えています。
まず、初期状態として、ルートオブジェクトを灰状態にしてマークスタックに積んでおきます。
そして、マークを複数のステップに分け、プログラムを実行しながらときどきマークのステップを実行し、処理を進めていきます。
マークの 1 ステップは次のようになります。
マークスタックから灰状態のオブジェクトを取り出し、黒状態にします。そして、そのオブジェクトから直接辿れる白オブジェクトを灰状態にしてマークスタックに積みます。 何回かこれを繰り返すとステップを終了します。
これを進めていくと、段々白が灰、黒になっていくことがわかると思います。最終的に、マークスタックが空になると処理が終了します。生きているオブジェクトは黒、死んでいる（用済みとなった）オブジェクトは白となっているため、白を回収しておしまいです。回収は lazy sweep でやれば良いです。灰状態のオブジェクトは残りません。
ちなみに、細かいことを言うと、本当は最後にルートオブジェクトの再スキャンが必要になります。なぜなら、ルートオブジェクトが変化しているかもしれないからです。
さて、ここで問題なのが、マークステップの合間に Ruby の実行が進んで、黒状態のオブジェクトから白状態へのオブジェクトを参照してしまうような場合です。さっき書いた a[0] = b という処理があって、a が黒、b が白、というときに起こります。このようなことが起こると、「黒状態のオブジェクトから直接辿れるオブジェクトはすべてマーク済みである」という前提が崩れてしまうので、問題です。具体的には、b がマークされず白状態のままになり、間違えて回収されてしまうことになります。
で、困ってしまうので、このような「黒状態のオブジェクトから白状態のオブジェクトへの参照の生成」を世代別 GC と同様にライトバリアによってチェックします。ライトバリアでこのような参照の生成を検知して、黒状態の a を灰状態に戻し、マークスタックに積みます。これによって、最終的には b が白から黒にマークされます。
Ruby でのインクリメンタル GC の実装
さて、インクリメンタル GC（のマーク処理）にはライトバリアが必要であることがわかりました。幸い、ライトバリアは Ruby 2.1 で導入しているので、インクリメンタル GC も簡単に作れるかな、と思うのですが、RGenGC では「ライトバリアで保護されたオブジェクト」と「ライトバリアで保護されないオブジェクト」を適切に処理することで世代別 GC が実現できた、とご紹介しました。つまり、ライトバリアが不完全なわけです。ちゃんとインクリメンタル GC が動かせるでしょうか。
ライトバリアがないと、インクリメンタル GC では、どうまずいか考えてみます。マーク処理終了後に、「ライトバリアで保護されない黒状態のオブジェクト」から、「白状態のオブジェクト」への参照がある場合にまずいことがわかります。さて、これをどうすれば良いか。
Ruby 2.2 で導入しようとしている GC では、これを対処するために、マーク終了時に「黒状態のライトバリアで保護されていないオブジェクト」すべてについて、再スキャンすることでこの問題に対処します。再スキャン後、発見した「白状態のオブジェクト」を一気に（インクリメンタルではなく）マークしていきます。これによって、適切にマークを終了することができます。
なかなか強引ですし、停止時間が気になります。インクリメンタル GC の目的は停止時間を短くすることだったのですから。大丈夫でしょうか？
この状態で停止する時間は (a)「黒状態のライトバリアで保護されていないオブジェクト」の数と (b) 残っている「白状態のオブジェクト」の数に比例する時間になります。(b) は正直そんなに無いんじゃ無いかな、と楽観的に考えると、(a) の時間が問題です。が、目標の停止時間を「マイナー GC の停止時間と同じくらいならいいや」と割り切ろうと考え、マイナー GC の停止時間よりは明らかに短い（生きているライトバリアで保護されていないオブジェクトは、マイナー GC では毎回マークされるため）から、まぁ、いいかなー、と思っている次第です。もちろん、運が悪いと (b) が凄くでかくなって停止時間が延びちゃいますが。
で、さらっと「黒状態のライトバリアで保護されていないオブジェクト全部を再スキャン」と言ったのですが、これを行なうためには、何も考えないとすべてのオブジェクトをチェックして、「生きている」かつ「ライトバリアで保護されていない」ことをチェックしなければなりません。ちょっとした Rails アプリでも数百万オブジェクト作るので、全部見て回ると凄い時間がかかります。
そこで、「ライトバリアで保護されていないオブジェクト」を bitmap で管理するようにしました（それまではオブジェクトについているフラグでした）。生きているかどうかをチェックするためのフラグは、すでに bitmap で管理されているため、この 2 つの bitmap の論理積をチェックすることで、高速に走査することができます。
これを実装しているのが gc.c の gc_marks_wb_unprotected_objects() 関数になります。実測してみると、そんなに時間がかかっていないことがわかります。
おまけですが、これまで「ライトバリアで保護されていないオブジェクト」をオブジェクトについているフラグとして管理していた、と紹介していましたが、このフラグが無用になりました。そこで、すでにある、旧世代であることを示すフラグとあわせて、2 bit で 0～3 を数えられるカウンタを作り、オブジェクトの年齢を管理するようにしました。
オブジェクトは 0 歳から始まり、GC を経て 1 歳ずつ年をとっていき、3 歳になると旧世代のオブジェクトとなります。Ruby 2.1 では 1 度 GC を経験するとすぐに旧世代のオブジェクトにしていましたが、これで 3 回 GC を経験しないと旧世代のオブジェクトにならないことになります。間違って（寿命が短いのに）旧世代のオブジェクトになってしまうと、メジャー GC の回数を増やしてしまうことになるので、このようにしています。
そのほか、いろんな処理の整理をしました。関数名とか。
チューニング
アルゴリズム自体は簡単だし、実装もすでに述べたところを注意すれば、ちゃんと動くものができるのですが、実はチューニングが難しいです。
例えば (1) いつマークステップを起動するのか？ (2) 1 回のマークステップではどれくらい処理をするのか？ (3) そもそもインクリメンタルマークを開始するときには、Ruby の処理を同時に進めなければならないため、ある程度空き領域を用意しておかなければならないが、それはどれくらい用意しなければならないのか、といったパラメータを適切に検討する必要があるためです。
たとえば、(2) や (3) が十分でないと、マークステップが十分進まないうちに Ruby プログラムが進めなくなってしまい、結局長時間の停止時間になってしまう可能性があります。(1) が短すぎると、アプリが十分に進めないまま、マークステップが始まってしまう、といった問題があります。
すでにインクリメンタル GC を備えている mruby では (1)、(2) をコントロールするためのパラメータをユーザが指定できるようになっています。CRuby もそのようにするべきか、それとも、もっと賢く、自動的に適切なパラメータを考えて用意するか、など、考えることが多いです。この辺の検討は十分じゃないので今後も進めていきたいです。
計測
gc.c のソースコードを整理したいので、GC 開始時、終了時をきっちりと捕捉するための TracePoint 用の内部イベント RUBY_INTERNAL_EVENT_GC_ENTER と RUBY_INTERNAL_EVENT_GC_EXIT を用意することができました。この内部イベントをフックすることで、GC での本当の停止時間を知ることが出来ます。
興味がある人は、これを使ったプロファイラを作って貰えるといいんじゃないかと思います。
おわりに
今回は、Ruby 2.2 に導入しようとしているインクリメンタル GC について、アルゴリズムとその実装を紹介しました。 すでに、この変更は Ruby 処理系の trunk に入っており、問題無ければこのまま Ruby 2.2 としてリリースされる予定です。
実は、まだチューニングが十分じゃ無いかもしれなくて、本当に停止時間が短くなっているかチェックがうまくいっていない状態です。 そこで、興味を持った人は Ruby 2.2 がリリースされる前でも試して貰えると助かります。
著者について
ささだこういち。RubyKaigi 2014 で初めて日本語のキーノートをする、ということで、緊張しています。この記事は現実逃避に書きました。まぁ、いいか。