From: "authorNari (Narihiro Nakamura)" Date: 2012-10-02T14:38:56+09:00 Subject: [ruby-dev:46188] [ruby-trunk - Bug #7095] Non-recursive marking Issue #7095 has been updated by authorNari (Narihiro Nakamura). パッチのレビューありがとうございます！ kosaki (Motohiro KOSAKI) wrote: > 2012/10/1 SASADA Koichi : > > (2012/10/02 0:21), authorNari (Narihiro Nakamura) wrote: (snip) > > 遅くなっていない，ということで，デメリットが思いつかないのでよろしいの > > じゃないかと思います．素晴らしい（パッチあんまり真面目に読んでないけど）． > > > > > > あまり本質じゃないんですが， > > - page という言葉は適当でしょうか． > > なんか page size が 4kと決めうって逆算されているような・・・ > mallocを使っているのでページサイズより小さくても悪影響あんまりでそうにないけど > > > - +#ifndef __LP64__ は本当にこれがやりたいんだろうか．あと -2 って何？ > > Linux + glibc限定だとmalloc headerがsize_t*2なのでこれで動くという決め打ちコードに見えてしまう・・・ いろいろ気にしすぎました…。 この辺はあんまり効果なさそうなのでテキトーに決め打ちしたいと思います。 pageは紛らわしいのでchunkとか、segmentがいいですかね。 > > - GC の度に毎回 malloc？　いいんだっけ．最初の1ページは最初に alloc する > > からいいのかな． > > 二度とfreeしない戦略とかじゃダメなのかなーとか思いました。もしくはmarkのときにスタックを半分以下しか使わなかったら１ページだけ解放するとかにして動的に長さが調整されるようにするとか > 今は決め打ちで4つだけfreeしない戦略になっています。 小崎さんのご指摘通り、使用したstackの長さに応じて収縮するように修正したいと思います。 （そんなに手間ではないと思いますので） ---------------------------------------- Bug #7095: Non-recursive marking https://bugs.ruby-lang.org/issues/7095#change-29933 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/