Bug #982

stack level too deep for long Array initialization

Added by Martin Dürst over 5 years ago. Updated about 2 years ago.

[ruby-dev:37701]
Status:Closed
Priority:Normal
Assignee:Koichi Sasada
Category:YARV
Target version:2.0.0
ruby -v:- Backport:

Description

=begin
次のスクリプトが stack level too deep (SystemStackError) で終わります。

ruby -e 'puts "A=["; 0.upto(1000000) { puts " [22, 55]," }; puts "]"' | ruby

これは Bug #943 のコピーで、長期的にどうするのか
を考えるとめのバグです。

ruby -e 'puts "A=[]"; 0.upto(1000000) { puts "A<<[22, 55]" }' | ruby

で意図のものができるが、どうしてもデータの初期化を宣言的でできなく、
手続的にしないといけないのはよくないと思っています。ユーザから見ると
メゾドの深い呼び出しなどがスタックオーバフローになるのは分かるはず
ですが、データの初期化だけでそういう問題になるのはビックリする
でしょう。

笹田さんによりますと、

 上記例のように,空の配列を作って,それに push するように変更することも
可能ですが,それを出来るようにしたほうがいいですかねぇ.するにしても,
1.9.2 で命令追加ってことになると思いますが.そう変更したら,ちょっと速度
が遅くなるってくらいかなぁ.

もう一つのやり方は stack level too deep になったときに、スタックにある
配列の要素を一気に配列に追加し、次の要素からまだスタックに載せること
が考えられる。でも、こういうのを実装するのはどのぐらい難しいでしょうか。

よろしくお願いします。 Martin.
=end


Related issues

Related to ruby-trunk - Bug #4040: SystemStackError with Hash[*a] for Large _a_ Assigned 11/10/2010

History

#1 Updated by Yusuke Endoh over 5 years ago

=begin
遠藤です。

次のスクリプトが stack level too deep (SystemStackError) で終わります。

ruby -e 'puts "A=["; 0.upto(1000000) { puts " [22, 55]," }; puts "]"' | ruby

どういうときにこれが必要になったのか興味があります。

それはそれとして、パッチを書いてみました。

  • concatarray 命令を廃止して、引数をとる concatarrays 命令を導入した
  • checkints 命令を導入した
  • 巨大な配列リテラルは 1000 個ごとに newarray して最後に concatarrays する

    とりあえず配列だけの対処なので、巨大なハッシュリテラルを書くとたぶん落ちます。

    Index: insns.def

    --- insns.def (revision 21356)
    +++ insns.def (working copy)
    @@ -40,6 +40,20 @@
    /* none */
    }

    +/**

  • @c check interrupts

  • @e check interrupts

  • @j

  • */
    +DEFINE_INSN
    +checkints
    +()
    +()
    +()
    +{

  • RUBYVMCHECK_INTS();
    +}
    +
    /*******************************************************/
    /
    deal with variables */
    /
    ********************************************************/
    @@ -486,31 +500,27 @@

    /**
    @c put

  • @e concat two arrays

  • @j 二つの配列 ary1, ary2 を連結しスタックへプッシュする。

  • @e put concatenate arrays

  • @j スタックトップの配列を n 個連結し,結果をスタックにプッシュする。
    */
    DEFINEINSN
    -concatarray
    -()
    -(VALUE ary1, VALUE ary2st)
    -(VALUE ary)
    +concatarrays
    +(rb
    num_t num)
    +(...)
    +(VALUE val) // inc += 1 - num;
    {

  • const VALUE ary2 = ary2st;

  • VALUE tmp1 = rbcheckconverttype(ary1, TARRAY, "Array", "to_a");

  • VALUE tmp2 = rbcheckconverttype(ary2, TARRAY, "Array", "to_a");

  • int i;

  • if (NIL_P(tmp1)) {

  • tmp1 = rbarynew3(1, ary1);

  • val = rbarynew();

  • for (i = num - 1; i >= 0; i--) {

  • const VALUE v = TOPN(i);

  • VALUE tmp = rbcheckconverttype(v, TARRAY, "Array", "to_a");

  • if (NIL_P(tmp)) {

  •  tmp = rb_ary_new3(1, v);
    
  • }

  • rbaryconcat(val, tmp);

    }

  • if (NIL_P(tmp2)) {

  • tmp2 = rbarynew3(1, ary2);

  • }

  • if (tmp1 == ary1) {

  • tmp1 = rbarydup(ary1);

  • }

  • ary = rbaryconcat(tmp1, tmp2);

  • POPN(num);
    }

    /**

    Index: compile.c

    --- compile.c (revision 21356)
    +++ compile.c (working copy)
    @@ -2195,12 +2195,14 @@
    return COMPILE_OK;
    }

    +#define ARRAYLITERALSPLITTHRESHOLD 1000
    +
    static int
    -compile
    array(rbiseqt *iseq, LINKANCHOR ret, NODE node_root,

  •     VALUE opt_p, int poped)
    

    +compilearray(rbiseqt *iseq, LINKANCHOR ret, NODE noderoot, int poped)
    {
    NODE *node = node
    root;

  • int len = node->ndalen, line = ndline(node), i=0;

  • int len = node->ndalen, line = ndline(node), i=0, split = 0;

  • VALUE optp = Qtrue;
    DECL
    ANCHOR(anchor);

    INITANCHOR(anchor);
    @@ -2211,6 +2213,11 @@
    ruby
    nodename(ndtype(node)));
    }

  •  if (i > 0 && i % ARRAY_LITERAL_SPLIT_THRESHOLD == 0 && !poped) {
    
  •  ADD_INSN1(anchor, line, newarray, INT2FIX(ARRAY_LITERAL_SPLIT_THRESHOLD));
    
  •  ADD_INSN(anchor, line, checkints);
    
  •  split++;
    
  •  }
    i++;
    if (opt_p && nd_type(node->nd_head) != NODE_LIT) {
    opt_p = Qfalse;
    

    @@ -2243,17 +2250,36 @@
    }
    else {
    if (!poped) {

  •  ADD_INSN1(anchor, line, newarray, INT2FIX(len));
    
  •  if (len % ARRAY_LITERAL_SPLIT_THRESHOLD) {
    
  •  ADD_INSN1(anchor, line, newarray, INT2FIX(len % ARRAY_LITERAL_SPLIT_THRESHOLD));
    
  •  split++;
    
  •  }
    
  •  if (split >= 2) ADD_INSN1(anchor, line, concatarrays, INT2FIX(split));
    

    }
    APPEND_LIST(ret, anchor);
    }
    return len;
    }

    -static VALUE
    -compilearray(rbiseqt *iseq, LINKANCHOR ret, NODE noderoot, VALUE optp)
    +static long
    +compilelist(rbiseqt *iseq, LINKANCHOR ret, NODE node_root)
    {

  • return compilearray(iseq, ret, noderoot, optp, 0);

  • NODE *node = node_root;

  • int i = 0;
    +

  • if (ndtype(node) != NODEZARRAY) {

  • while (node) {

  •  if (nd_type(node) != NODE_ARRAY) {
    
  •  rb_bug("compile_list: This node is not NODE_ARRAY, but %s",
    
  •         ruby_node_name(nd_type(node)));
    
  •  }
    
  •  i++;
    
  •  COMPILE(ret, "list element", node->nd_head);
    
  •  node = node->nd_next;
    
  • }

  • }
    +

  • return i;
    }

    static VALUE
    @@ -2841,8 +2867,7 @@
    *flag |= VMCALLARGSSPLATBIT;

    if (next_is_array) {
    
  •  argc = INT2FIX(compile_array(iseq, args, argn->nd_head, Qfalse) + 1);
    
  •  POP_ELEMENT(args);
    
  •  argc = INT2FIX(compile_list(iseq, args, argn->nd_head) + 1);
    }
    else {
    argn = argn->nd_head;
    

    @@ -2851,8 +2876,7 @@
    break;
    }
    case NODE_ARRAY: {

  •  argc = INT2FIX(compile_array(iseq, args, argn, Qfalse));
    
  •  POP_ELEMENT(args);
    
  •  argc = INT2FIX(compile_list(iseq, args, argn));
    break;
    

    }
    default: {
    @@ -2862,10 +2886,7 @@
    }

    if (nsplat > 1) {

  • int i;

  • for (i=1; i<nsplat; i++) {

  •  ADD_INSN(args_splat, nd_line(args), concatarray);
    
  • }

  • ADDINSN1(argssplat, nd_line(args), concatarrays, INT2FIX(nsplat));
    }

    if (!LISTSIZEZERO(argssplat)) {
    @@ -3746,7 +3767,7 @@
    COMPILE(ret, "NODE
    OPASGN1 args->head: ", node->ndargs->ndhead);
    if (flag & VM
    CALLARGSSPLATBIT) {
    ADD
    INSN1(ret, nd_line(node), newarray, INT2FIX(1));

  •  ADD_INSN(ret, nd_line(node), concatarray);
    
  •  ADD_INSN1(ret, nd_line(node), concatarrays, INT2FIX(2));
    ADD_SEND_R(ret, nd_line(node), ID2SYM(idASET),
           argc, Qfalse, LONG2FIX(flag));
    }
    

    @@ -3769,7 +3790,7 @@
    ADDSEND(ret, ndline(node), ID2SYM(id), INT2FIX(1));
    if (flag & VMCALLARGSSPLATBIT) {
    ADDINSN1(ret, ndline(node), newarray, INT2FIX(1));

  •  ADD_INSN(ret, nd_line(node), concatarray);
    
  •  ADD_INSN1(ret, nd_line(node), concatarrays, INT2FIX(2));
    ADD_SEND_R(ret, nd_line(node), ID2SYM(idASET),
           argc, Qfalse, LONG2FIX(flag));
    }
    

    @@ -4070,7 +4091,7 @@
    ADDINSN1(args, ndline(node), getlocal, INT2FIX(idx));
    }
    ADDINSN1(args, ndline(node), newarray, INT2FIX(j));

  •      ADD_INSN (args, nd_line(node), concatarray);
    
  •      ADD_INSN1(args, nd_line(node), concatarrays, INT2FIX(2));
        /* argc is setteled at above */
        }
        else {
    

    @@ -4098,7 +4119,7 @@
    break;
    }
    case NODE_ARRAY:{

  • compilearray(iseq, ret, node, Qtrue, poped);

  • compilearray(iseq, ret, node, poped);
    break;
    }
    case NODE
    ZARRAY:{
    @@ -4127,8 +4148,7 @@
    INITANCHOR(list);
    switch (type) {
    case NODE
    ARRAY:{

  •  compile_array(iseq, list, node->nd_head, Qfalse);
    
  •  size = OPERAND_AT(POP_ELEMENT(list), 0);
    
  •  size = INT2FIX(compile_list(iseq, list, node->nd_head));
    ADD_SEQ(ret, list);
    break;
    

    }
    @@ -4426,14 +4446,14 @@
    case NODEARGSCAT:{
    COMPILE(ret, "argscat head", node->nd
    head);
    COMPILE(ret, "argscat body", node->nd_body);

  • ADDINSN(ret, ndline(node), concatarray);

  • ADDINSN1(ret, ndline(node), concatarrays, INT2FIX(2));
    break;
    }
    case NODEARGSPUSH:{
    COMPILE(ret, "arsgpush head", node->nd
    head);
    COMPILE(ret, "argspush body", node->ndbody);
    ADD
    INSN1(ret, nd_line(node), newarray, INT2FIX(1));

  • ADDINSN(ret, ndline(node), concatarray);

  • ADDINSN1(ret, ndline(node), concatarrays, INT2FIX(2));
    break;
    }
    case NODE_SPLAT:{

    Yusuke ENDOH mame@tsg.ne.jp

=end

#2 Updated by Yusuke Endoh almost 4 years ago

  • Target version changed from 1.9.2 to 2.0.0
  • ruby -v set to -

=begin
遠藤です。

ささださんが「1.9.2 には不要ではないでしょうか」との見解を出したので、
target を 1.9.x とします。当面は Array#<< などを使ってください。

何とかして欲しいと言う声が多数あれば、早めに直されるかもしれません。

--
Yusuke Endoh mame@tsg.ne.jp
=end

#3 Updated by Shyouhei Urabe over 3 years ago

  • Status changed from Open to Assigned

=begin

=end

#4 Updated by Martin Dürst over 3 years ago

=begin

どういうときにこれが必要になったのか興味があります。

具体的に言いますと、GB-18030 の変換テーブルのためです。
=end

#5 Updated by Hiroshi Nakamura almost 3 years ago

  • Target version changed from 2.0.0 to 1.9.3

#6 Updated by Koichi Sasada almost 3 years ago

  • Target version changed from 1.9.3 to 2.0.0

すみません,1.9.3 の後の課題とさせて下さい.

#7 Updated by Koichi Sasada about 2 years ago

  • Status changed from Assigned to Closed

なおしました.
命令をいじるのではなく,core メソッドを呼ぶようにしてみました.
ちょっと,余計な配列が増えちゃうのが良くないかも....
誰か性能評価してくれると助かります.

#8 Updated by Shugo Maeda about 2 years ago

前田です。

ko1 (Koichi Sasada) wrote:

なおしました.
命令をいじるのではなく,core メソッドを呼ぶようにしてみました.
ちょっと,余計な配列が増えちゃうのが良くないかも....
誰か性能評価してくれると助かります.

内容はぜんぜん追っていないのですが、r35306のcommitから以下のような警告が出るようになっているようです。

compile.c: 関数 ‘iseqcompileeach’ 内:
compile.c:4363:8: 警告: 変数 ‘size’ が設定されましたが使用されていません [-Wunused-but-set-variable]

たしかに使われなくなっているように見えるのですが、これはこういうものでしょうか。

Also available in: Atom PDF