Project

General

Profile

Feature #5839

Proposal: Bitmap Marking GC

Added by authorNari (Narihiro Nakamura) about 8 years ago. Updated over 7 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

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

Also available in: Atom PDF