Project

General

Profile

Actions
Copy link

Feature #7095

closed

Non-recursive marking

Added by authorNari (Narihiro Nakamura) about 12 years ago. Updated about 12 years ago.

Status:
Closed
Assignee:
authorNari (Narihiro Nakamura)
Target version:
2.0.0
[ruby-dev:46184]

Description

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

Related issues 1 (0 open — 1 closed)

Related to Ruby master - Bug #7141: ALT_STACK_SIZE is not enoughClosedkosaki (Motohiro KOSAKI)10/11/2012Actions
Actions
Copy link
 #1 [ruby-dev:46185]

Updated by ko1 (Koichi Sasada) about 12 years ago

(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

Actions
Copy link
 #2 [ruby-dev:46186]

Updated by kosaki (Motohiro KOSAKI) about 12 years ago

2012/10/1 SASADA Koichi :

(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なのでこれで動くという決め打ちコードに見えてしまう・・・

Actions
Copy link
 #3 [ruby-dev:46188]

Updated by authorNari (Narihiro Nakamura) about 12 years ago

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

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

Actions
Copy link
 #4 [ruby-dev:46196]

Updated by authorNari (Narihiro Nakamura) about 12 years ago

  • Tracker changed from Bug to Feature
Actions
Copy link
 #5

Updated by authorNari (Narihiro Nakamura) about 12 years ago

  • 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.

Actions
Copy link
 #6 [ruby-dev:46200]

Updated by naruse (Yui NARUSE) about 12 years ago

  • 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

Actions
Copy link
 #7

Updated by authorNari (Narihiro Nakamura) about 12 years ago

  • 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]
Actions
Copy link

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0