RubyとGCについて
思ったことをつらつらと支離滅裂な個人的メモ。
１．シンプルマルチスレッドGC
このあいだからいじってるやつだが、とりあえず世代別GCがあるのとないので3倍も違うというのはおかしいのでまだどこかバグっているんじゃないかと思う。効率面での話なのでヒープスロットの取得・解放戦略のへんが怪しい。
単純な再帰型マーク関数を2つのスレッドで同時に動かすというのは、まあそれなりに短時間で終わるのだろうが、それはあくまでも遊んでるCPUがあるという前提であって、システム全体のスループットとしてはたぶんあまり嬉しい話ではないだろう。作るのは楽だが無駄が多い。
このシンプルな手法が通用するのは関数を再帰呼び出しするというマシンスタックを使った探索の場合のみであり、たとえばmrubyやrubyのようにリストを繋いだりたどったりする方法ではリストのアクセスに排他制御が必要になって思ったような性能は出ないと思われる。スレッドごとに違うリストを持つとかそういうことができればいいのだが、オブジェクト内に次のポインタを持つ場合はオブジェクト内に全スレッド用のポインタをそれぞれ持つわけにもいかないので多分なかなか難しい。
２．世代別GC
mrubyやRuby2.1のRGenGCではスウィープした後に残ったオブジェクトを長い寿命のオブジェクトであると認識して、次からはそれらをあらかじめマークする。ような感じに動く。ので2回目のGCからはマークの探索対象が減ってマーク処理が速くなる。
この方式を実装するための課題は2つあって、ひとつはあらかじめマークされたオブジェクトがどこからも参照されなくなってもマークされっぱなしであること、もうひとつは長い寿命のオブジェクトが他のオブジェクトを参照しても、長い寿命のオブジェクトはマークされているのでそこから先は探索されないこと。
これらを解決する手段として、前者はメジャーGCという全体を探索する動作をときどきさせ(遅い)、後者はライトバリアという参照に変更があったオブジェクトに印をつけて後でマーク探索する処理をする。
昔はライトバリアのオーバーヘッドが大きくてダメという感じだったのだが、最近では世代別GCが流行りのようである。ライトバリアのアルゴリズムになんらかのブレークスルーがあったのか、CPUの高性能化で相対的に負荷が下がったのか。よくわからん。
３．mruby
世代別GC+インクリメンタルGCである。インクリメンタルGCというのはVMとGCの動作を交互にちょこっとずつ進めるというもので、シングルスレッドだけど2つの処理を並行に実行することができる。
マーク処理をはじめてからVMがオブジェクトの参照を変えたらどうなるのかというのが問題なのだが、これは世代別GCで必要なライトバリアの処理があればマークが終わってから最後のファイナルマークフェイズで処理できる。
世代別GCが流行りなんじゃなくてライトバリアが流行りなのだろうか。なんにせよライトバリアが現実的に使えるようになるならインクリメンタルGCも世代別GCもコンカレントGCもばしばし実現できる。いい世の中になったもんだ。
４．mrubyでスレッド並列GC
インクリメンタルGCは並行処理なので、排他制御の問題さえ解決すれば別スレッドでそのまま並列処理をさせることができる。具体的にはVMのスタック領域がVM実行中に伸びたり縮んだりするので並列にアクセスするのはまずい。ルートスキャンフェイズはVMを止めて、ルートオブジェクトをとりあえずgray_listに突っ込んで、別スレッドを起動して探索させて、VM再開という感じにする必要があるだろう。
スウィープが完了した直後にコンカレントマークを動かすと、さくっと考える範囲では存在するオブジェクトが全部マークされそうだ。これはスウィープで残ったものを長寿命オブジェクトとする世代別GCと同様の動きであり、別スレッドとはいえマークしなおすのが無駄に見える。
でももう少し考えると、前回のスウィープで生き残ったものでも今回のマークでマークされないものというのは存在するだろうし、それは次回のスウィープで回収される。つまり、全体を探索してやれば長寿命オブジェクトをきちんと探索して回収することができる。世代別GCでいうところのメジャーGC−マイナーGCの処理を毎回別スレッドで動かしているようなもので、他のCPUが遊んでいるという前提で考えればGCの停止時間は毎回マイナーGCと同等に抑えられる。
もちろんコンカレントマークの起動は遅ければ遅いほどライトバリアが発生するタイミングが遅くなるのでGCの効率は上がるのだが、遅すぎるとメモリが足りなくなってもコンカレントマークが終わっていないという悲しい状態になるので、このタイミングの調整が問題になる。mrubyのインクリメンタルGCではオブジェクト数の閾値でマークの起動を判定する。動かすプログラムやハードウェアによって閾値の最適値は異なるからまじめに効率を狙う場合はチューニングが必須である。HotSpotVMはナイスなタイミングでマークが終わるように動的にGCのスレッド数を調整してくれるらしい。すごすぎる。
Ruby2.1で実装されつつあるRGenGCはC拡張ライブラリの修正なしで世代別GCを実現する。この仕掛けが気になる人は適当に検索して調べてみるとよいだろう。なんにせよCRubyでライトバリアがきちんと実装できるとすれば、インクリメンタルGCだろうがコンカレントGCだろうがやりたい放題となる。
RGenGCで改善されない部分は最大停止時間なので、なんらかの方法でそれを削る必要がたぶん今後はあって、有力候補はインクリメンタルGCである。コンカレントGCも技術的には面白いのだが、やっぱりどうしてもオーバーヘッドがあって、つまり最大停止時間は減るがスループットも減るという典型的なパターンにハマる。
俺みたいな個人でRubyを使う人には別スレッドで処理してくれたほうがCPUを有効活用できるのだが、サーバで複数プロセス同時起動してフルに活用してるような用途では別スレッドで処理しても嬉しくない。そういう場合はスループットこそが大事なのである。
６．今後について
結局のところ、なんかすごいものが作れるのかというとそんなことはなく、当面はmrubyのGCをいじり倒して遊ぶぐらいになりそうだ。mrubyはマシンスタックに置かれたオブジェクトをマークしに行かないので保守的である必要がなく、CRubyよりも少しだけ自由度が高い。とはいえC側がポインタを保持するタイミングがあるのでコピーGCが実装できるわけでもない。なんとかこれを有効活用して何か作れないかなーとか考えているのだが、すぐに何かがひらめくこともなさそうである。
まあ、いつものようにまた気が向いたら、ということで。
