Project

General

Profile

Actions

Feature #5839

closed

Proposal: Bitmap Marking GC

Added by authorNari (Narihiro Nakamura) over 10 years ago. Updated over 9 years ago.

Status:
Closed
Priority:
Normal
Target version:
[ruby-dev:45085]

Description

あけましておめでとうございます。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()を使わないプログラムで
もそれほど問題にならないと思っています。


Related issues 1 (0 open1 closed)

Related to Ruby master - Bug #5901: OpenBSD "[FATAL] failed to allocate memory"ClosedauthorNari (Narihiro Nakamura)01/17/2012Actions
Actions

Also available in: Atom PDF