From: "naruse (Yui NARUSE)" Date: 2012-10-04T11:00:57+09:00 Subject: [ruby-dev:46200] [ruby-trunk - Feature #7095][Assigned] Non-recursive marking Issue #7095 has been updated by naruse (Yui NARUSE). Status changed from Closed to Assigned authorNari (Narihiro Nakamura) wrote: > This issue was solved with changeset r37075. > Narihiro, thank you for reporting this issue. > Your contribution to Ruby is greatly appreciated. > May Ruby be with you. > ---------- > * gc.c: Use the non-recursive marking instead of recursion. The > recursion marking of CRuby needs checking stack overflow and the > fail-safe system, but these systems not good at partial points, > for example, marking deep tree structures. [ruby-dev:46184] > [Feature #7095] > > * configure.in (GC_MARK_STACKFRAME_WORD): removed. It's used by > checking stack overflow of marking. > > * win32/Makefile.sub (GC_MARK_STACKFRAME_WORD): ditto. この変更以降、Linux 32bit 環境で SEGV 時の backtrace がでなくなっているので確認お願いします。 % ./ruby -e'Process.kill :SEGV, $$' -e:1: [BUG] Segmentation fault ruby 2.0.0dev (2012-10-03 trunk 37076) [i686-linux] zsh: segmentation fault ./ruby -e'Process.kill :SEGV, $$' http://u32.rubyci.org/~chkbuild/ruby-trunk/log/20121003T130302Z.diff.html.gz ---------------------------------------- Feature #7095: Non-recursive marking https://bugs.ruby-lang.org/issues/7095#change-30015 Author: authorNari (Narihiro Nakamura) Status: Assigned Priority: Normal Assignee: authorNari (Narihiro Nakamura) Category: core Target version: 2.0.0 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/