From: Narihiro Nakamura <redmine@...>
Date: 2010-04-27T01:11:50+09:00
Subject: [ruby-dev:41067] [Feature #3203] LazySweepGC patch

Feature #3203: LazySweepGC patch
http://redmine.ruby-lang.org/issues/show/3203

起票者: Narihiro Nakamura
ステータス: Open, 優先度: Normal

ご無沙汰しています。nariです。

CRubyのGCにLazySweepを組み込んだパッチを作成しました（リビジョン27489向
け）。

= 実装について

== 概要
基本的に以下の動作を繰り返します。
0. オブジェクトが足りなくなったら 1.へ
1. マーク済みのRubyヒープスロットの一つをスイープ
2. もし、空きオブジェクトが見つかればオブジェクトを返却し、LazySweep終
   了
3. もし、空きオブジェクトな見つからなければ、次のマーク済みRubyヒープス
   ロットをLazySweepの対象とし、1.へ
4. マーク済みRubyヒープスロットがすべてなくなった場合はマークを実施し、
   1.へ

LazySweepしないGC（普通のGC）も残しており、GC.startの時はこちらを呼びま
す。

== Rubyヒープ拡張＆縮小
Rubyヒープの拡張と縮小はタイミングが異なるだけです。

Rubyのヒープ拡張はLazySweepと同時に行います。具体的にはヒープスロットを
1個増やすと同時に、Rubyヒープスロットを1個スイープするようにしています。
この工夫によって、Rubyヒープ内にまったく空きがない場合でも、GC停止時間
を最低限に抑えることができます。

Rubyヒープ拡張をLazySweep時に行うため、マーク後には拡張の決定をしなけれ
ばなりません。そのため、マーク時に生きているオブジェクト数をカウントし
ています。これによってマークフェーズは以前と比べて少しだけ遅くなります。

Rubyヒープ縮小も同じくLazySweep時に行います。

== sorted_heaps_slot構造体の追加
heaps_slot構造体は配列として管理するのをやめ、LazySweepの対象となる
Rubyヒープスロットは双方向リストで管理しています。

is_pointer_to_heap()関数ではheaps_slot構造体の変わりに
sorted_heaps_slot構造体を使用するように変更しました。

= 性能評価

== ベンチマークプログラム
生きているオブジェクト、死んでいるオブジェクトがある程度バラバラにRuby
ヒープ内に分布するようなベンチマークプログラムを作成し、計測に使用しま
した（※添付ファイル参照）。

== 結果
GC最大停止時間：48.00ms => 28.00ms (58%)
GC総停止時間：0.83ms => 0.92ms (110%)

総停止時間は悪くなりますが、最大停止時間については改善が見られます。

その他、有用なベンチマークをご存じでしたら測ってご報告いただけると嬉し
いです。

= 動作検証
以下の環境でのmake test-allが通る（パッチ対象のリビジョンと比較して変化
がない）ことを確認しています。

$ uname -a
Linux nari-laptop 2.6.31-20-generic #58-Ubuntu SMP Fri Mar 12 05:23:09 UTC 2010 i686 GNU/Linux


----------------------------------------
http://redmine.ruby-lang.org