Feature #7095: Non-recursive marking

• Status: Closed
• Assignee: authorNari (Narihiro Nakamura)
• Target version: 2.0.0

[authorNari (Narihiro Nakamura)]

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

[ko1 (Koichi Sasada)]

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

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が「あ、スタックが溢れそう」と判断するとそれ以上
はマシンスタックを使わない方法でマークを行おうとします。

+1

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

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

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

--
// SASADA Koichi at atdot dot net

[kosaki (Motohiro KOSAKI)]

2012/10/1 SASADA Koichi [e-mail]:

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

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が「あ、スタックが溢れそう」と判断するとそれ以上
はマシンスタックを使わない方法でマークを行おうとします。

+1

+100 ぐらい入れたいんだけど、一人一票なんだっけ？

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

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

• page という言葉は適当でしょうか．

なんか page size が 4kと決めうって逆算されているような・・・
mallocを使っているのでページサイズより小さくても悪影響あんまりでそうにないけど

• GC の度に毎回 malloc？　いいんだっけ．最初の1ページは最初に alloc する
  からいいのかな．

二度とfreeしない戦略とかじゃダメなのかなーとか思いました。もしくはmarkのときにスタックを半分以下しか使わなかったら１ページだけ解放するとかにして動的に長さが調整されるようにするとか

• +#ifndef LP64 は本当にこれがやりたいんだろうか．あと -2 って何？

Linux + glibc限定だとmalloc headerがsize_t*2なのでこれで動くという決め打ちコードに見えてしまう・・・

[authorNari (Narihiro Nakamura)]

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

kosaki (Motohiro KOSAKI) wrote:

2012/10/1 SASADA Koichi [e-mail]:

(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の長さに応じて伸縮するように修正したいと思います。
（そんなに手間ではないと思いますので）

[authorNari (Narihiro Nakamura)]

• Tracker changed from Bug to Feature

[authorNari (Narihiro Nakamura)]

• Status changed from Open to Closed
• % Done changed from 0 to 100

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.

[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

[authorNari (Narihiro Nakamura)]

• Status changed from Assigned to Closed

This issue was solved with changeset r37088.
Narihiro, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

---

• gc.c (init_heap): call init_mark_stack before to allocate
  altstack. This change avoid the stack overflow at the signal
  handler on 32bit, but I don't understand reason... [Feature #7095]