おひさしぶり。
GC sweep時間はわりと短縮できそうなので(authorNariくんがLazySweepパッチを書いてくれたし)、 このところGC mark時間を短縮するアイディアはないか、考えている。 今のRubyに入れたいので、制約として、
というものがある。
しばらく前にTwitterで、「いくつかのオブジェクトをまとめて、その単位でマークする」というアイディアを披露してみたが、すぐに三浦さんから「トラバースのコストが減らないから効果ないんじゃない」との指摘が。ちょっと考えてみたら、確かにその通り。かっくり。
まあ、50年間、いろんな人が考えてきたGCで、画期的なアイディアを思いつくのは難しいよね。
まあ、そういう「誰も知らない系」ではなくて、mark時間短縮に効果のありそうなアイディアは、私の思いつく限り3つ。
ひとつはビットマップマーキング。GC markをオブジェクトヘッダ内ではなく、外に用意したビットマップに置く。 マークチェックにメモリ中オブジェクトにアクセスしなくて済むこと、それによりワーキングセットが小さくなることと、仮想記憶のページを汚さないことがメリット。
もうひとつはGC markフェーズの並列化。スレッドを活用する。markは相互依存が少ないので、マルチコアマシンでは効果的。ただし、ビットマップ操作はアトミックではないので前日のビットマップマーキングとは相性が悪い。ビットマップのチェックや更新のたびにロックをかけてちゃコストが高すぎる。 大概のCPUはバイト単位の操作ならアトミックに行うことができるので、 ビットマップじゃなくて、1オブジェクトあたり1バイト使う、バイトマップにすることでロックは回避可能だと思う(だよね)。 バイトマップにするとメモリ消費量が8倍になっちゃうけど、この領域は他の最適化に使えるかも。
最後はGC mark対象のオブジェクトそのものを減らしちゃうこと。たとえば、ノードやメソッド、組み込みクラスなどをmark対象から外しちゃう。あとはオブジェクトのimmediate化。ある意味、もっとも正統的なアプローチ。1.9.2ではだいぶ外したから、後は組み込みクラスかな。
組み込みクラスを別扱いすると、ユーザー定義クラスだけ一気に消去のようなことが可能になって、mod_rubyのようなタイプがうれしいかも。あと、MVMで組み込みクラスを共有できて、初期化コストが下がるとか。これらを直接書き換えないようにしないといけないけど、それは隠しクラスで実現できそう。