(cache) mrubyでマルチスレッドGCを実験する

githubがよくわかってないのでbranchとかがなんか変なことになっているような気がするのだが、それはさておき。

このあいだ、マルチコアを活用するマルチスレッドGCについてアイデアをひらめいたので、とりあえず手ごろなmrubyをいじって実験してみようと思ったわけだ。CRuby難しすぎるし。mrubyのGCは世代別GC+インクリメンタルGCで意外に複雑なことをしているので、世代別のあたりとインクリメンタルのあたりのコードをばっさりと削って、素朴なマーク＆スウィープGCにしてみた。コードはこんな感じである。

http://github.com/mirichi/mruby/tree/simpleGC

objectspaceとの相性が悪いらしくうまくうごかないのでmrbgemsから外す必要がある。あと負荷をかけるとコケるのがいまいちわからないが、完璧に動かすのが目的でもないのでこれでいいとして(ダメですな)。

ひらめいたアイデアというのは以下の感じ。

・全オブジェクトをルートから辿る素朴な再帰型マーク関数markを用意する。

・スレッドAとBを用意する。

・スレッドAでmarkを実行する。

・スレッドBでmarkを実行する。

markはルートオブジェクトからすべてを辿るので、スレッドAとBはどっちもすべてのオブジェクトを辿ることになる。先行したスレッドAが1つ目のオブジェクトをマークしてそのツリーをたどっている間に、スレッドBが1つ目のオブジェクトを見にいってマークされているので2つ目のルートオブジェクトを辿ることになる。スレッドAが1つ目を終えて2つ目を見にいくとマークされているので3つ目を辿る。この単純すぎる仕掛けでマルチスレッドGCが効率良く動くのではないか、という話だ。

マルチスレッドGCに関してはRubyコミッタの@nari3氏が試していて、その話はRuby会議で講演されて資料もある。

http://www.slideshare.net/authorNari/parallel-worlds-of-crubys-gc-10108810

このときの問題点はスレッド同期のためのロックフリーアルゴリズムのオーバーヘッドであったわけだが、上記の仕組みではそのような部分は一切無いので、CPUアーキテクチャレベルのたとえばメモリアクセス競合などといった問題が無い限りはシングルスレッドよりも速くなることが予想できる。

長くなるので以下は続きに。

githubにアップしたコードは、もとのroot_scan_phaseという関数をmarkにして再帰させるようにして、incremental_sweep_phase関数をsweepとして全体のスウィープに変更している。mrb_garbage_collectを呼べばGCが動く。ヒープスロット関連は元のままだ。メモリ拡張まわりは戦略的にイマイチなのでベンチマークをとった時の速度は非常に遅い。が、mrubyのGCを改善するのが目的ではないので問題ない。マークのフラグはcolorを流用していて、glayでマークされていない、blackでマークされている状態を表している。まあ、単純である。

んで、これをどのように改造するかというと、まずmarkをスレッドとして扱えるように定義を変更する。ついでにmrbポインタもスレッド引数で受け取れるように。Win32APIを使うのは俺の技術力の問題である。

//static void
//mark(mrb_state *mrb)
static DWORD WINAPI mark( LPVOID lpParameter )
{
  int j;
  size_t i, e;
  mrb_state *mrb = (mrb_state *)lpParameter;
(略)
  ExitThread( 0 );
}

んで、mrb_garbage_collectから呼ばれるgc関数はmarkをスレッドで呼んで終わるまで待機するようにしておく。

static size_t
gc(mrb_state *mrb)
{
    HANDLE hThread[2];
    mrb->gc_state = GC_STATE_MARK;

    hThread[0] = CreateThread(NULL, 0, &mark, mrb, 0, 0);
    hThread[1] = CreateThread(NULL, 0, &mark, mrb, 0, 0);
    WaitForMultipleObjects(2, hThread, TRUE, INFINITE);
    CloseHandle(hThread[0]);
    CloseHandle(hThread[1]);

    mrb->gc_state = GC_STATE_SWEEP;
    prepare_sweep(mrb);
    sweep(mrb);
    mrb->gc_state = GC_STATE_NONE;
    return 0;
}

まあ、ベタである。

このコードで実験してみた結果としては、サイズ64にしたao-render.rbが1スレッドで472秒だったものが、2スレッドでは500秒ちょいとなって、ようするに遅くなった。スレッドを毎回作っているのが無駄ではあるのだが、終わったら眠るようにして必要なときに起こすようにしたらマシになるかもしれない。

しかし同じオブジェクトはスレッド2つで重複してマークしないであろうことを考えると、スレッド作成の負荷が相当高いか、もしくはそれ以外の負荷が高いという話で、後者であれば対策のうちようが無い。それ以外というのは例のCPUアーキテクチャまわりのことである。

このあたりは試してみればいいのだろうが、負荷を高めるとコケちゃったりしてなにかと不安定で、ぶっちゃけGCの修正がバグっているのだろうと思うのだが、きちんと調べて動かすほどのモチベーションも無いような軽い実験だったので、この話はここまでになる。

遅いにしてもお話にならないレベルの遅さではないから(差が1割未満だし)、少しどうにかしたらシングルスレッドよりも速くなりそうな気配がある。

ほかに気になる話としては、

・ao-render.rbはオブジェクトが少なくてGC負荷が軽いのでGCベンチとしては不向きかも。WORD_BOXINGしたりGC_STRESSするとコケちゃう(これは修正品質の問題)のでお手上げ。

・GC時間の長いベンチで4スレッドにした場合にどうなるか。うちデュアルコアなので実験できない。

・毎回スレッド作らなかったら速いのかどうなのか。

・マルチスレッドsweepの可能性や、シンプルなM&S以外の世代別・インクリメンタルその他GCとの相性。

ということでタイトルに入ってはいるけどmrubyあんまり関係ない。いや、改善ネタばっかりじゃなくて、実験の素材として使えるというのもとてもとても存在価値としては高いと思うので良いことだと思う。まあ、釣りだと言うことについては異論は無い。

おまけ。

Ruby2.1のRGenGCの資料を見ていてちょっとGC熱が上がってこうなった。興味がある人はオススメ。

http://www.atdot.net/~ko1/activities/RubyKaigi2013-ko1.pdf