[ruby-trunk - Bug #7095][Open] Non-recursive marking

Ruby Development
1

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

Bug #7095: Non-recursive marking

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

nariです。

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

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

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

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

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

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

2.についてですが、以下の報告でもある通り、

現在のマシンスタックのオーバーフローチェックはそれなり精度でおこなわれ
ています。そのためスタック領域が非常に小さい場合（たとえば
FIBER_USE_NATIVE が有効なケース）では、運悪くマーキングでのチェックが漏
れてしまい、たまにSEGVを吐くようです。

上記のチケットでは頑張って直してみたのですがそれでもなおSEGVってしま

うという悲しい結論になりました。

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

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

(target 0が修正前, target 1が非再帰的マーキング）
“average total difference is -7.793935319666676”

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

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

2

(2012/10/02 0:21), authorNari (Narihiro N.) wrote:

Assignee: authorNari (Narihiro N.)
パッチ: https://github.com/authorNari/ruby/compare/non_recursion_marking.patch

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

+1

遅くなっていない，ということで，デメリットが思いつかないのでよろしいの
じゃないかと思います．素晴らしい（パッチあんまり真面目に読んでないけど）．

あまり本質じゃないんですが，

  • page という言葉は適当でしょうか．
  • GC の度に毎回 malloc？ いいんだっけ．最初の1ページは最初に alloc する
    からいいのかな．
  • +#ifndef LP64 は本当にこれがやりたいんだろうか．あと -2 って何？
3

2012/10/1 SASADA Koichi [email protected]:

Priority: Normal
$B:9J,(B: Comparing ruby:master...authorNari:non_recursion_marking · ruby/ruby · GitHub
$B%Q%C%A(B:
https://github.com/authorNari/ruby/compare/non_recursion_marking.patch

= $B8=>u$NLdBjE@(B
$B8=:_$N%^!<%/$O!"4pK\E*$K$O%%V%8%'%/%H!";R%%V%8%'%/%H!"B9%%V%8%'%/%H(B
$B$H!"(Bgc_mark()$B$r:F5"E$K8F$S=P$9$H$$$&<BAu$K$J$C$F$$$^$9!#(B
$B$b$7$b%%V%8%'%/%H$,$9$4$/?<$$%0%i%U$r;}$C$F$$$?>l9g$K$O%^%7%s%9%?%C%/(B
$B$,0n$l$F$7$^$&$N$G!“(BGC$B$,!V$”!"%9%?%C%/$,0n$l$=$&!W$HH=CG$9$k$H$=$l0J>e(B
$B$O%^%7%s%9%?%C%/$r;H$o$J$$J}K!$G%^!<%/$r9T$$&$H$7$^$9!#(B

+1

+100 $B$0$i$$F~$l$?$$$s$@$1$I!"0l?M0lI<$J$s$@$C$1!)(B

$BCY$/$J$C$F$$$J$$!$$H$$$&$3$H$G!$%G%a%j%C%H$,;W$$$D$+$J$$$N$G$h$m$7$$$N(B
$B$8$c$J$$$+$H;W$$$^$9!%AG@2$i$7$$!J%Q%C%A$"$s$^$j??LLL$KFI$s$G$J$$$1$I!K!%(B

$B$"$^$jK<A$8$c$J$$$s$G$9$,!$(B

  • page $B$H$$$&8@MU$OE,Ev$G$7$g$&$+!%(B

$B$J$s$+(B page size $B$,(B 4k$B$H7h$a$&$C$F5U;;$5$l$F$$$k$h$&$J!&!&!&(B
malloc$B$r;H$C$F$$$k$N$G%Z!<%8%5%$%:$h$j>.$5$/$F$b0-1F6A$"$s$^$j$G$=$&$K$J$$$1$I(B

  • GC $B$NEY$KKh2s(B malloc$B!)!!$$$$$s$@$C$1!%:G=i$N(B1$B%Z!<%8$O:G=i$K(B alloc
    $B$9$k(B
    $B$+$i$$$$$N$+$J!%(B

$BFsEY$H(Bfree$B$7$J$$@oN,$H$+$8$c%@%a$J$N$+$J!<$H$+;W$$$^$7$?!#$b$7$/$O(Bmark$B$N$H$-$K%9%?%C%/$rH>J,0J2<$7$+;H$o$J$+$C$?$i#1%Z!<%8$@$12rJ|$9$k$H$+$K$7$FF0E*$KD9$5$,D4@0$5$l$k$h$&$K$9$k$H$+(B

  • +#ifndef LP64 $B$OK\Ev$K$3$l$,$d$j$?$$$s$@$m$&$+!%$"$H(B -2 $B$C$F2?!)(B

Linux + glibc$B8BDj$@$H(Bmalloc
header$B$,(Bsize_t*2$B$J$N$G$3$l$GF0$/$H$$$&7h$aBG$A%3!<%I$K8+$($F$7$^$&!&!&!&(B

4

Issue #7095 has been updated by authorNari (Narihiro N.).

パッチのレビューありがとうございます！

kosaki (Motohiro KOSAKI) wrote:

2012/10/1 SASADA Koichi [email protected]:

(2012/10/02 0:21), authorNari (Narihiro N.) 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

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

nariです。

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

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

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

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

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

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

2.についてですが、以下の報告でもある通り、

現在のマシンスタックのオーバーフローチェックはそれなり精度でおこなわれ
ています。そのためスタック領域が非常に小さい場合（たとえば
FIBER_USE_NATIVE が有効なケース）では、運悪くマーキングでのチェックが漏
れてしまい、たまにSEGVを吐くようです。

上記のチケットでは頑張って直してみたのですがそれでもなおSEGVってしま

うという悲しい結論になりました。

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

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

(target 0が修正前, target 1が非再帰的マーキング）
“average total difference is -7.793935319666676”

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

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

5

Issue #7095 has been updated by naruse (Yui NARUSE).

Status changed from Closed to Assigned

authorNari (Narihiro N.) wrote:

  • 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

Author: authorNari (Narihiro N.)
Status: Assigned
Priority: Normal
Assignee: authorNari (Narihiro N.)
Category: core
Target version: 2.0.0

nariです。

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

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

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

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

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

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

2.についてですが、以下の報告でもある通り、

現在のマシンスタックのオーバーフローチェックはそれなり精度でおこなわれ
ています。そのためスタック領域が非常に小さい場合（たとえば
FIBER_USE_NATIVE が有効なケース）では、運悪くマーキングでのチェックが漏
れてしまい、たまにSEGVを吐くようです。

上記のチケットでは頑張って直してみたのですがそれでもなおSEGVってしま

うという悲しい結論になりました。

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

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

(target 0が修正前, target 1が非再帰的マーキング）
“average total difference is -7.793935319666676”

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

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

6

Issue #7095 has been updated by authorNari (Narihiro N.).

Tracker changed from Bug to Feature

Feature #7095: Non-recursive marking

Author: authorNari (Narihiro N.)
Status: Open
Priority: Normal
Assignee: authorNari (Narihiro N.)
Category: core
Target version: 2.0.0

nariです。

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

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

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

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

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

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

2.についてですが、以下の報告でもある通り、

現在のマシンスタックのオーバーフローチェックはそれなり精度でおこなわれ
ています。そのためスタック領域が非常に小さい場合（たとえば
FIBER_USE_NATIVE が有効なケース）では、運悪くマーキングでのチェックが漏
れてしまい、たまにSEGVを吐くようです。

上記のチケットでは頑張って直してみたのですがそれでもなおSEGVってしま

うという悲しい結論になりました。

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

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

(target 0が修正前, target 1が非再帰的マーキング）
“average total difference is -7.793935319666676”

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

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