RubyのBitmap Marking GCによるメモリ使用量の改善(意訳)

そういえばBitmapMarking GCについて@m_stさんにInfoQで質問をうけました。

だいぶん残念な英語を返したのですが、向こうのインタビュイーさんの方でいろいろ修正していただいたみたいです。感謝感謝。
で、ちと意訳ですが以下に日本語訳も書いておきます。
ちょっとだけ補足したいこともあったので。

InfoQ Japanの方でも日本語訳していただいてます。ありがとうございます。
CGの話も追加してもらったみたいですね。

RubyのBitmap Marking GCによるメモリ使用量の改善

原文

Narihiro Nakamuraによって書かれたGCの最大停止時間を短くするLazy Sweep Garbage Collector(参照:InfoQによるレポート) が、Ruby1.9.3には導入されている。
最近、Narihiroはcopy-on-wirte(CoW) friendlyなBitmapMarkingGC(以降、"bmap"と呼ぶ)を実装し、提案した。
これはRuby Enterprise Edition(REE)のcopy-on-write-friendly GCと似たものである。

POSIXのfork()システムコールでは、子プロセスとその親プロセスでメモリを共有しており、メモリ内の一部が変更された場合にその部分を子プロセスにコピーする方式により、メモリ使用量を削減している。
しかし、残念ながら現在のRubyGCではこの仕組みはうまく動作しない

Rubyはマーク・スイープGCを採用している。
このGCでは、はじめにすべての生きているオブジェクトを走査し、マークを行う。
マークではオブジェクトのヘッダフィールド上のFL_MARKフラグを立てる。
その後、すべてのオブジェクトをもう一度走査して、すべての死んでいるオブジェクトのマークを外す。
これの問題点は、CoWのセマンティクスを破壊することだ: マークするすべてのページがDirtyになってしまう.

InfoQはNarihiroのbmap実装が現在のLazySweepGCよりも改善されているのかを質問した。

Bitmap Markingアルゴリズムの良い点は以下のとおりです。

 - ビットマップは、オブジェクトヘッダにマークビットを置くよりも、ビットを密集した領域に格納する
   - 高い局所性
 - マークはオブジェクトを変更しない。そして、スイープは生きているオブジェクトを変更しない。
   - CoW friendly, ダーティキャッシュラインが少ない
 - マークビットのクリアにmemset()が使える(訳注: マークビットが一気に消せる)
   - スイープがちょっぴり早い

CRubyの事情ではCoW firendlyがもっとも重要だと思います。
BitmapMarkingはLinuxでfork()を使っているようなプログラムでメモリ使用量を改善するものです。
で、CRubyでは本当の並列のパフォーマンスを得るためにfork()を使わないといけません。
さらに、CRubyはすでにfork()を使った多くのライブラリを持っています(Unicorn, Resqueとか)

(訳注: あんまLazySweepとは関係ないです、とも言いたかったんですけど…深刻な英語力不足が…)

InfoQ:
LazySweepGCはスループットを悪化させますよね。
話によるとbmapもまたスループットを少しだけ悪化させると聞いてます。
bmapは現在のGCを置き換えようとしていますか? 
それともユーザ/開発者が設定で選択できるようなものですか?

私のプランは「Bitmap Marking GCをデフォルトのGCする」ものです。
あなたは「bmapは*少しだけ*遅くなる」と言いましたね。
それはたしかにそうですが、私はその速度低下はすべての人にとって許容範囲だと考えています。
なので、ユーザは設定のようなものをBitmapMarkingに対して必要としない、と考えています。

(訳注: あんまり速度低下ないから、標準にしても困らない。というより、ユーザに選択させる際には何らかの強いデメリット・メリットがある場合に限られると思っていて、今回の場合はデメリットが少ないから標準でいいんでは、と思った次第です)

InfoQ:
あなたはBitmap Markingを組み合わせたParallel Marking GCを作るつもりだとおっしゃってましたね。
大幅にGCが高速化するように思えますが、あなたはこれがどれくらい高速化するか(もしくはどれくらい速度低下するか)について何か考えをもっていますか?

実は、Bitmap Marking抜きのParallel Marking GCは作っています。
2コアのマシンで、いくらかのケースでは、総GC時間を40%くらい改善することできました。
Bitmap MarkingとParallel Marking GCを組み合わせると, たぶん少しだけ改善率は落ちるかもしれません。

すでにParallel Marking GCの詳細についてはRubyConfUS 2011で話しています(ビデオ[1]とスライド[2])。

MatzはすでにこのGCパッチをtrunkにコミットしている。そのため、これは次のリリース(たぶん2.0)に含まれるだろう。

(訳注: 細かい点ですが実際にはまつもとさんに許可をもらって、私がコミットしました)