ruby-changes:57649
From: Yusuke <ko1@a...>
Date: Sat, 7 Sep 2019 22:22:34 +0900 (JST)
Subject: [ruby-changes:57649] 8c908c9890 (master): compile.c (compile_array): rewrite the compilation algorithm
https://git.ruby-lang.org/ruby.git/commit/?id=8c908c9890 From 8c908c989077c74eed26e02912b98362e509b8a3 Mon Sep 17 00:00:00 2001 From: Yusuke Endoh <mame@r...> Date: Sat, 7 Sep 2019 22:08:39 +0900 Subject: compile.c (compile_array): rewrite the compilation algorithm The original code looks unnecessarily complicated (to me). Also, it creates a pre-allocated array only for the prefix of the array. The new code optimizes not only the prefix but also the subsequence that is longer than 0x40 elements. # not optimized 10000000.times { [1+1, 1,2,3,4,...,63] } # 2.12 sec. # (1+1; push 1; push 2; ...; puts 63; newarray 64; concatarray) # optimized 10000000.times { [1+1, 1,2,3,4,...,63,64] } # 1.46 sec. # (1+1; newarray 1; putobject [1,2,3,...,64]; concatarray) diff --git a/compile.c b/compile.c index ac035bd..7177623 100644 --- a/compile.c +++ b/compile.c @@ -3936,75 +3936,111 @@ compile_array(rb_iseq_t *iseq, LINK_ANCHOR *const ret, const NODE *node, int pop https://github.com/ruby/ruby/blob/trunk/compile.c#L3936 return 1; } - int opt_p = 1; - int first = 1, i; + /* Compilation of an array literal. + * The following code is essentially the same as: + * + * for (int count = 0; node; count++; node->nd_next) { + * compile(node->nd_head); + * } + * ADD_INSN(newarray, count); + * + * However, there are three points. + * + * - The code above causes stack overflow for a big string literal. + * The following limits the stack length up to max_stack_len. + * + * [x1,x2,...,x10000] => + * push x1 ; push x2 ; ...; push x256; newarray 256; + * push x257; push x258; ...; push x512; newarray 256; concatarray; + * push x513; push x514; ...; push x768; newarray 256; concatarray; + * ... + * + * - Long subarray can be optimized by pre-allocating a hidden array. + * + * [1,2,3,...,100] => + * duparray [1,2,3,...,100] + * + * [x, 1,2,3,...,100, z] => + * push x; newarray 1; + * putobject [1,2,3,...,100] (<- hidden array); concatarray; + * push z; newarray 1; concatarray + * + * - If the last element is a keyword, newarraykwsplat should be emitted + * to check and remove empty keyword arguments hash from array. + * (Note: a keyword is NODE_HASH which is not static_literal_node_p.) + * + * [1,2,3,**kw] => + * putobject 1; putobject 2; putobject 3; push kw; newarraykwsplat + */ - while (node) { - const NODE *start_node = node, *end_node, *prev_node; - const int max = 0x100; - DECL_ANCHOR(anchor); - INIT_ANCHOR(anchor); + const int max_stack_len = 0x100; + const int min_tmp_ary_len = 0x40; + int stack_len = 0; + int first_chunk = 1; - for (i=0; i<max && node; i++, prev_node = node, node = node->nd_next) { - if (CPDEBUG > 0) { - EXPECT_NODE("compile_array", node, NODE_LIST, -1); - } + /* Convert pushed elements to an array, and concatarray if needed */ +#define FLUSH_CHUNK(newarrayinsn) \ + if (stack_len) { \ + ADD_INSN1(ret, line, newarrayinsn, INT2FIX(stack_len)); \ + if (!first_chunk) ADD_INSN(ret, line, concatarray); \ + first_chunk = stack_len = 0; \ + } - if (opt_p && !static_literal_node_p(node, iseq)) { - opt_p = 0; + while (node) { + int count = 1; + + /* pre-allocation check (this branch can be omittable) */ + if (static_literal_node_p(node, iseq)) { + /* count the elements that are optimizable */ + const NODE *node_tmp = node->nd_next; + for(; node_tmp && static_literal_node_p(node_tmp, iseq); node_tmp = node_tmp->nd_next) + count++; + + if ((first_chunk && stack_len == 0 && !node_tmp) || count >= min_tmp_ary_len) { + /* The literal contains only optimizable elements, or the subarray is long enough */ + + VALUE ary = rb_ary_tmp_new(count); + + /* Create a hidden array */ + for (; count; count--, node = node->nd_next) + rb_ary_push(ary, static_literal_value(node, iseq)); + OBJ_FREEZE(ary); + iseq_add_mark_object_compile_time(iseq, ary); + + /* Emit optimized code */ + FLUSH_CHUNK(newarray); + if (first_chunk) { + ADD_INSN1(ret, line, duparray, ary); + first_chunk = 0; + } + else { + ADD_INSN1(ret, line, putobject, ary); + ADD_INSN(ret, line, concatarray); + } } - - NO_CHECK(COMPILE_(anchor, "array element", node->nd_head, 0)); } - if (opt_p) { - VALUE ary = rb_ary_tmp_new(i); - - end_node = node; - node = start_node; - - while (node != end_node) { - rb_ary_push(ary, static_literal_value(node, iseq)); - node = node->nd_next; - } - while (node && static_literal_node_p(node, iseq)) { - rb_ary_push(ary, static_literal_value(node, iseq)); - node = node->nd_next; + /* Base case: Compile "count" elements */ + for (; count; count--, node = node->nd_next) { + if (CPDEBUG > 0) { + EXPECT_NODE("compile_array", node, NODE_LIST, -1); } - OBJ_FREEZE(ary); - - iseq_add_mark_object_compile_time(iseq, ary); - - if (first) { - first = 0; - ADD_INSN1(ret, line, duparray, ary); - } - else { - ADD_INSN1(ret, line, putobject, ary); - ADD_INSN(ret, line, concatarray); - } - } - else { - /* Find last node in array, and if it is a keyword argument, then set - flag to check and remove empty keyword arguments hash from array */ - if (!node && nd_type(prev_node->nd_head) == NODE_HASH && prev_node->nd_head->nd_brace == 0) { - ADD_INSN1(anchor, line, newarraykwsplat, INT2FIX(i)); - } - else { - ADD_INSN1(anchor, line, newarray, INT2FIX(i)); - } + NO_CHECK(COMPILE_(ret, "array element", node->nd_head, 0)); + stack_len++; - if (first) { - first = 0; - } - else { - ADD_INSN(anchor, line, concatarray); + if (!node->nd_next && nd_type(node->nd_head) == NODE_HASH && node->nd_head->nd_brace == 0) { + /* Reached the end, and the last element is a keyword */ + FLUSH_CHUNK(newarraykwsplat); + return 1; } - APPEND_LIST(ret, anchor); + /* If there are many pushed elements, flush them to avoid stack overflow */ + if (stack_len >= max_stack_len) FLUSH_CHUNK(newarray); } } + + FLUSH_CHUNK(newarray); return 1; } -- cgit v0.10.2 -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/