まつもと ゆきひろです

礼儀としてruby-coreで報告したら、マージしてもいいんじゃない?

In message "Re: [ruby-dev:45085] [ruby-trunk - Feature #5839][Open] Proposal: Bitmap Marking GC"
    on Wed, 4 Jan 2012 21:33:17 +0900, Narihiro Nakamura <authorNari / gmail.com> writes:

|Issue #5839 has been reported by Narihiro Nakamura.
|
|----------------------------------------
|Feature #5839: Proposal: Bitmap Marking GC
|https://bugs.ruby-lang.org/issues/5839
|
|Author: Narihiro Nakamura
|Status: Open
|Priority: Normal
|Assignee: Yukihiro Matsumoto
|Category: core
|Target version: 2.0.0
|
|
|あけましておめでとうございます。nariです。
|
|ビットマップマーキングGCをRuby2.0向けに作りました。
|
|ソースコード: https://github.com/authorNari/ruby/tree/bitmap_marking
|パッチ: https://github.com/authorNari/patch_bag/blob/master/ruby/gc_bitmap_using_alignment_r33786.patch
|
|以下の環境でr33786 に対するパッチで make check が通ること、
|make TESTS="--gc-stress" test-all が無事に動いてることを確認してます。
|
|$ ruby -v
|ruby 2.0.0dev (2011-11-18 trunk 33786) [x86_64-linux]
|
|= 性能評価
|
|== make benchmark
|make benchmark OPTS="-r 5" の結果は以下です。
|https://gist.github.com/1542547
|全体的に実行時間は若干遅くなるようです。
|
|マークでRVALUEのフラグを立てるだけだったのが、ビットマップ上のフ
|ラグを立てるようになるので遅くなるのはしょうがないかなと…。
|
|== skkzipcode
|ビットマップマーキングではマークでRVALUEに対して書き込みがなくなるので、
|Linuxで複数の子プロセスを実行した場合にも無駄なCoWが発生せず、総メモリ
|使用量が少なくなるという利点があります。
|
|skkzipcodeというサンプルプログラムで上記の点を確認しました。
|skkzipcodeは、親プロセスでたくさんメモリを使ってデータを保持しておいて、
|生成した子プロセスで親プロセスと共有したデータを利用します。
|https://github.com/authorNari/skkzipcode
|(/proc/PID/smapsを使って計測しています)
|
|origin - ビットマップマーキングなし
|PROCESS_CNT : 5 
|SHARED_TOTAL: 59124     kb
|PRIV_TOTAL  : 224892    kb
|
|bmap - ビットマップマーキングあり
|PROCESS_CNT : 5 
|SHARED_TOTAL: 170744    kb
|PRIV_TOTAL  : 138336    kb
|
|PROCESS_CNTは子プロセスの数、SHARED_TOTALは子プロセスで利用している共有
|メモリ量、PRIV_TOTALは私有メモリ量です。bmapの方が共有メモリを沢山使っ
|ていることがわかり、私有メモリ使用量も少なくなっています。
|
|= 実装
|実装について簡単にまとめます。
|
|- ビットマップ探索高速化のため、ヒープ1ブロックのアドレスは16KBでアライ
|  ンメントしている
|-- Linuxではposix_memalign(),memalign()を利用
|-- Windowsでは_aligned_malloc()を利用
|- 無駄な書き込みを防ぐため、なるべくfreelistを繋ぎ変えないようにした
|-- GCの時にすでにfreelistに繋ながれていたオブジェクトを再度繋ぎ直さない
|- freelistはスロットが持つようになった
|-- 不要なスロットを解放するときにグローバルなfreelistにオブジェクトが繋
|   がれている可能性がでてくるため
|- struct heaps_slotをヒープブロックに埋め込んだ
|
|Linuxでfork()を使わないようなプログラムに対してはビットマップマーキング
|の恩恵はありません。ただ、CRubyで並列プログラミングしようとするときには
|fork()を使って云々するライブラリがけっこう多いので(例えばpassengerとか…)
|そういうものに対しては結構効くはずです。
|
|GCの実行時間もそれほど遅くなりませんので、fork()を使わないプログラムで
|もそれほど問題にならないと思っています。
|
|
|
|-- 
|http://redmine.ruby-lang.org