Issue #7095 has been reported by authorNari (Narihiro Nakamura).

----------------------------------------
Bug #7095: Non-recursive marking
https://bugs.ruby-lang.org/issues/7095

Author: authorNari (Narihiro Nakamura)
Status: Open
Priority: Normal
Assignee: authorNari (Narihiro Nakamura)
Category: core
Target version: 2.0.0
ruby -v: ruby 2.0.0dev (2012-09-25 trunk 37032) [x86_64-linux]


nariです。

GCのマーキングで関数の再帰呼び出しを使わないバージョンを書いてみました。

差分: https://github.com/authorNari/ruby/compare/non_recursion_marking
パッチ: https://github.com/authorNari/ruby/compare/non_recursion_marking.patch

= 現状の問題点
現在のマークは、基本的にはオブジェクト、子オブジェクト、孫オブジェクト
と、gc_mark()を再帰的に呼び出すという実装になっています。
もしもオブジェクトがすごく深いグラフを持っていた場合にはマシンスタック
が溢れてしまうので、GCが「あ、スタックが溢れそう」と判断するとそれ以上
はマシンスタックを使わない方法でマークを行おうとします。

現在のマークには次の2つの問題があると考えています。

1. 参照の深いオブジェクトが多くあるとマーキングが遅くなる
2. スタックオーバーフローを検知する関数の精度が悪い

1.についてですが、フェイルセーフであるマシンスタックを使わないマークの
方法が最悪の場合「ヒープを全走査」なので、ワーストケースが結構遅いです。
しかも、参照の深いデータ群が生き残り続ける限りGCが遅いまんまなのでこれ
はあんまり嬉しくないです。

2.についてですが、以下の報告でもある通り、
https://bugs.ruby-lang.org/issues/3781
現在のマシンスタックのオーバーフローチェックはそれなり精度でおこなわれ
ています。そのためスタック領域が非常に小さい場合(たとえば
FIBER_USE_NATIVE が有効なケース)では、運悪くマーキングでのチェックが漏
れてしまい、たまにSEGVを吐くようです。
# 上記のチケットでは頑張って直してみたのですがそれでもなおSEGVってしま
# うという悲しい結論になりました。

= 改善案
自前でスタック構造を作り、それを使って非再帰的にマーキングするというの
が今回の提案です。関数による再帰呼び出しを使わないので上記の問題はなく
なります。

= 速度改善
mark benchmark OPTS="-r 5" を走らせてみたところ、それなりに早くなってい
るようです。

https://gist.github.com/3806667
(target 0が修正前, target 1が非再帰的マーキング)
"average total difference is -7.793935319666676"

また、参照関係の深いオブジェクトを故意に作るベンチマークで意地悪してみ
たら(あたりまえですが)非再帰的マーキングのほうが早くなりました。
https://gist.github.com/3812118

depthが240の場合
origin 総GC時間(sec): 1.96
non-recursive 総GC時間(sec): 1.87

depthが500の場合
origin 総GC時間(sec): 14.73
non-recursive 総GC時間(sec): 5.49



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