From: Yukihiro Matsumoto Date: 2012-01-05T14:46:28+09:00 Subject: [ruby-dev:45093] Re: [ruby-trunk - Feature #5839][Open] Proposal: Bitmap Marking GC まつもと ゆきひろです 礼儀として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 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