8日目: キーワード引数をコンパイルする
前回は通常の引数とsplat引数をコンパイルできるようにしました。 今回はキーワード引数をコンパイルできるようにします。
コンパイル引数のバイトコードを観察する
まずはシンプルな例からみていきます。
# 0000 putself ( 1)[Li] # 0001 putobject false # 0003 opt_send_without_block <calldata!mid:m1, argc:1, kw:[#<Symbol:0x000000000085310c>], FCALL|KWARG> # 0005 pop m1(k1: false) # 0006 putself ( 2)[Li] # 0007 putobject false # 0009 putobject true # 0011 opt_send_without_block <calldata!mid:m2, argc:2, kw:[#<Symbol:0x000000000085310c>,#<Symbol:0x000000000085510c>], FCALL|KWARG> # 0013 pop m2(k1: false, k2: true)
kwとしてopt_send_without_blockに対してkeyが直接渡されているようです。
これは最適化されているように見えます。
おそらく最適化されないであろうケースとして、keyとvalueがメソッド呼び出しのケースを考えてみます。
最適化されていない最も汎用的な方法
# 0000 putself ( 1)[Li] # 0001 putself # 0002 opt_send_without_block <calldata!mid:k1, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0004 putself # 0005 opt_send_without_block <calldata!mid:v1, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0007 newhash 2 # 0009 opt_send_without_block <calldata!mid:m1, argc:1, FCALL|KW_SPLAT> # 0011 pop m1(k1 => v1) # 0012 putself ( 2)[Li] # 0013 putself # 0014 opt_send_without_block <calldata!mid:k1, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0016 putself # 0017 opt_send_without_block <calldata!mid:v1, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0019 putself # 0020 opt_send_without_block <calldata!mid:k2, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0022 putself # 0023 opt_send_without_block <calldata!mid:v2, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0025 newhash 4 # 0027 opt_send_without_block <calldata!mid:m2, argc:1, FCALL|KW_SPLAT|KW_SPLAT_MUT> # 0029 leave m2(k1 => v1, k2 => v2)
この場合は以下の手順を踏みます。
- keyとvalueを評価してスタックに積む
newhash命令でkeyとvalueからhashをつくる- 引数が1つであるという情報とともに
opt_send_without_blockを実行する
newhashを用いた方法はkeyやvalueがどのような形式であっても使える、汎用的な方法です。
しかしnewhashとあるように必ず1つhashをつくります。
最初にあげたm1(k1: false)をみるとvalueをスタックにおくのは同じですが、keyは直接opt_send_without_block命令に埋め込まれており、hashの生成を回避しています。
最適化をするための条件
ではこの最適化はどのようなケースで可能、もしくはどのようなケースでは不可能なのでしょうか。
keyはsymbol、valueはメソッド呼び出しの場合、keyはopt_send_without_blockに埋め込まれるようです。
# 0000 putself ( 1)[Li] # 0001 putobject false # 0003 putself # 0004 opt_send_without_block <calldata!mid:m, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0006 opt_send_without_block <calldata!mid:m1, argc:2, kw:[#<Symbol:0x000000000085310c>,#<Symbol:0x000000000085410c>], FCALL|KWARG> # 0008 leave m1(k1: false, k2: m)
一方でkeyがメソッド呼び出しでvalueがsymbolの場合は埋め込まれません。 keyを埋め込もうにも、そのkeyがメソッドを呼び出すまで決定しないので、埋め込みようがありません。
# 0009 putself ( 9)[Li] # 0010 putobject :k1 # 0012 putobject false # 0014 putself # 0015 opt_send_without_block <calldata!mid:k2, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0017 putobject :v2 # 0019 newhash 4 # 0021 opt_send_without_block <calldata!mid:m1, argc:1, FCALL|KW_SPLAT|KW_SPLAT_MUT> # 0023 pop m1(k1: false, k2 => :v2)
キーワード引数の前に他の引数があっても、keyの埋め込みはおきます。
# 0009 putself ( 9)[Li] # 0010 putobject_INT2FIX_1_ # 0011 putobject false # 0013 putobject true # 0015 opt_send_without_block <calldata!mid:m1, argc:3, kw:[#<Symbol:0x000000000085310c>,#<Symbol:0x000000000085410c>], FCALL|KWARG> # 0017 leave m1(1, k1: false, k2: true)
keyがsymbol以外の場合はkeyの埋め込みはおきません。
1のようなstatic valueの場合にも起きないというのはちょっと意外かもしれません。
# 0000 putself ( 1)[Li] # 0001 putchilledstring "k1" # 0003 putobject false # 0005 putobject :k2 # 0007 putself # 0008 opt_send_without_block <calldata!mid:m, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0010 newhash 4 # 0012 opt_send_without_block <calldata!mid:m1, argc:1, FCALL|KW_SPLAT|KW_SPLAT_MUT> # 0014 pop m1("k1" => false, k2: m) # 0015 putself ( 2)[Li] # 0016 putobject_INT2FIX_1_ # 0017 putobject false # 0019 putobject :k2 # 0021 putself # 0022 opt_send_without_block <calldata!mid:m, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0024 newhash 4 # 0026 opt_send_without_block <calldata!mid:m2, argc:1, FCALL|KW_SPLAT|KW_SPLAT_MUT> # 0028 pop m2(1 => false, k2: m)
配列のsplatやhashのsplatがある場合には1つのhashにまとめられます。
# 0033 putself ( 28)[Li] # 0034 putself # 0035 opt_send_without_block <calldata!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0037 splatarray false # 0039 putobject {k1: false, k2: true} # 0041 opt_send_without_block <calldata!mid:m1, argc:2, ARGS_SPLAT|FCALL|KW_SPLAT> # 0043 leave m1(*a, k1: false, k2: true) # 0000 putself ( 1)[Li] # 0001 putobject :k1 # 0003 putself # 0004 opt_send_without_block <calldata!mid:val1, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0006 newhash 2 # 0008 putspecialobject 1 # 0010 swap # 0011 putself # 0012 opt_send_without_block <calldata!mid:kw, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0014 opt_send_without_block <calldata!mid:core#hash_merge_kwd, argc:2, ARGS_SIMPLE> # 0016 opt_send_without_block <calldata!mid:m2, argc:1, FCALL|KW_SPLAT|KW_SPLAT_MUT> # 0018 pop m2(k1: val1, **kw)
ということでおそらく2つの条件の両方が満たされた場合にkeyをopt_send_without_block命令に埋め込むという最適化が起きるようです。
- すべてのkeyがsymbolである
- 配列やhashのsplatがない
compile_keyword_argを書き換える
既存の実装ではsetup_args_coreが前提条件を確認して、条件にあわせて3つの関数のうち適切な関数を1つ呼ぶことでキーワード引数をコンパイルしています。
- NODE_LIST (
m(1, 2, k1: v1, k2: v2))- compile_keyword_arg
- compile_single_keyword_splat_mutable
- compile_hash
- NODE_ARGSCAT (
m(*a, 1, k1: v1))- compile_hash
- NODE_ARGSPUSH (
m(*a, k1: v1))- compile_single_keyword_splat_mutable
- compile_hash
compile_keyword_arg, compile_single_keyword_splat_mutable, compile_hashと3つの関数がありますが、そのうちkeyを直接埋め込むのはcompile_keyword_argだけです。
static int compile_keyword_arg(rb_iseq_t *iseq, LINK_ANCHOR *const ret, const NODE *const root_node, struct rb_callinfo_kwarg **const kw_arg_ptr, unsigned int *flag) { RUBY_ASSERT(nd_type_p(root_node, NODE_HASH)); RUBY_ASSERT(kw_arg_ptr != NULL); RUBY_ASSERT(flag != NULL); if (RNODE_HASH(root_node)->nd_head && nd_type_p(RNODE_HASH(root_node)->nd_head, NODE_LIST)) { const NODE *node = RNODE_HASH(root_node)->nd_head; int seen_nodes = 0; // 最初に `**kw` (splat) がないかチェックする // あれば FALSE を返し、この関数内部ではコンパイルは行わない // またkeyが全てsymbolであることもチェックする while (node) { const NODE *key_node = RNODE_LIST(node)->nd_head; seen_nodes++; RUBY_ASSERT(nd_type_p(node, NODE_LIST)); // key_nodeがないというのは`**h`のようなsplitのとき if (key_node && nd_type_p(key_node, NODE_SYM)) { /* can be keywords */ } else { if (flag) { *flag |= VM_CALL_KW_SPLAT; if (seen_nodes > 1 || RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next) { /* A new hash will be created for the keyword arguments * in this case, so mark the method as passing mutable * keyword splat. */ *flag |= VM_CALL_KW_SPLAT_MUT; } } return FALSE; } node = RNODE_LIST(node)->nd_next; /* skip value node */ node = RNODE_LIST(node)->nd_next; } // valueをコンパイルしつつ、keyの配列(keywords)をつくる /* may be keywords */ node = RNODE_HASH(root_node)->nd_head; { int len = 0; VALUE key_index = node_hash_unique_key_index(iseq, RNODE_HASH(root_node), &len); struct rb_callinfo_kwarg *kw_arg = rb_xmalloc_mul_add(len, sizeof(VALUE), sizeof(struct rb_callinfo_kwarg)); VALUE *keywords = kw_arg->keywords; int i = 0; int j = 0; kw_arg->references = 0; kw_arg->keyword_len = len; *kw_arg_ptr = kw_arg; for (i=0; node != NULL; i++, node = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next) { const NODE *key_node = RNODE_LIST(node)->nd_head; const NODE *val_node = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_head; int popped = TRUE; if (rb_ary_entry(key_index, i)) { keywords[j] = get_symbol_value(iseq, key_node); j++; popped = FALSE; } NO_CHECK(COMPILE_(ret, "keyword values", val_node, popped)); } RUBY_ASSERT(j == len); return TRUE; } } return FALSE; }
compile_keyword_argは全てのkeyとvalueをチェックして、最適化可能かを判断します。
最適化可能だと判断した場合は、valueをコンパイルするとともにkeyの配列を生成します(VALUE *keywords)。
ここで作ったkeyの配列が最終的にopt_send_without_blockに渡されます。
命令をdumpしたときに表示されるkw:[#<Symbol:0x000000000085310c>,#<Symbol:0x000000000085410c>]です。
書き換え前のコードではhashノードをあつかうとき、node = RNODE_LIST(node)->nd_next;のようにlistの操作をするようなコードが頻出します。
これはhashをn * 2のlistとして表現しているからです。
$ ruby --parser=parse.y --dump=p -e 'm(k1: v1, k2: v2, **h)' # @ NODE_FCALL (id: 0, line: 1, location: (1,0)-(1,22))* # +- nd_mid: :m # +- nd_args: # @ NODE_LIST (id: 13, line: 1, location: (1,2)-(1,21)) # +- as.nd_alen: 1 # +- nd_head: # | @ NODE_HASH (id: 12, line: 1, location: (1,2)-(1,21)) # | +- nd_brace: 0 (keyword argument) # | +- nd_head: # | @ NODE_LIST (id: 3, line: 1, location: (1,2)-(1,21)) # | +- as.nd_alen: 6 # | +- nd_head: # | | @ NODE_SYM (id: 2, line: 1, location: (1,2)-(1,5)) # | | +- string: :k1 # | +- nd_head: # | | @ NODE_VCALL (id: 1, line: 1, location: (1,6)-(1,8)) # | | +- nd_mid: :v1 # | +- nd_head: # | | @ NODE_SYM (id: 6, line: 1, location: (1,10)-(1,13)) # | | +- string: :k2 # | +- nd_head: # | | @ NODE_VCALL (id: 5, line: 1, location: (1,14)-(1,16)) # | | +- nd_mid: :v2 # | +- nd_head: # | | (null node) # | +- nd_head: # | | @ NODE_VCALL (id: 9, line: 1, location: (1,20)-(1,21)) # | | +- nd_mid: :h # | +- nd_next: # | (null node) # +- nd_next: # (null node)
nd_argsはk1, v1, k2, v2, null, hという構造をしています。
keyは奇数番目、valueは偶数番目に置かれています。
また**hはkeyがnullなものとして表現されています。
書き換え後はAssocNodeとAssocSplatNodeに分割されるので、それらに気をつけながらcompile_keyword_argを書き換えます。
前半部分をみれば雰囲気は伝わると思うので、後半は省略しています。
static int compile_keyword_arg(rb_iseq_t *iseq, LINK_ANCHOR *const ret, const rb_keyword_hash_node_t *const root_node, struct rb_callinfo_kwarg **const kw_arg_ptr, unsigned int *flag) { RUBY_ASSERT(kw_arg_ptr != NULL); RUBY_ASSERT(flag != NULL); rb_node_list2_t *list = &root_node->elements; if (RB_NODE_LIST_LEN(list)) { int seen_nodes = 0; const NODE *node; for (size_t i = 0; i < RB_NODE_LIST_LEN(list); i++) { node = list->nodes[i]; seen_nodes++; switch (nd_type(node)) { case RB_ASSOC_NODE: case RB_ASSOC_SPLAT_NODE: if (nd_type_p(node, RB_ASSOC_NODE) && nd_type_p(RB_NODE_ASSOC(node)->key, RB_SYMBOL_NODE)) { /* can be keywords */ } else { if (flag) { *flag |= VM_CALL_KW_SPLAT; // TODO: Enough to check `RB_NODE_LIST_LEN(list) > 1` ? if (seen_nodes > 1 || RB_NODE_LIST_LEN(list) > 1) { /* A new hash will be created for the keyword arguments * in this case, so mark the method as passing mutable * keyword splat. */ *flag |= VM_CALL_KW_SPLAT_MUT; } } return FALSE; } break; default: rb_bug("unexpected node: %s", ruby_node_name(nd_type(node))); } }
compile_single_keyword_splat_mutableを書き換える
setup_args_coreをみてみるとcompile_keyword_argによる最適化ができないときに、keyword_node_single_splat_pをチェックして分岐していることがわかります。
static int setup_args_core(rb_iseq_t *iseq, LINK_ANCHOR *const args, const NODE *argn, unsigned int *dup_rest, unsigned int *flag_ptr, struct rb_callinfo_kwarg **kwarg_ptr) { ... case NODE_LIST: { // f(x, y, z) int len = compile_args(iseq, args, argn, &kwnode); RUBY_ASSERT(flag_ptr == NULL || (*flag_ptr & VM_CALL_ARGS_SPLAT) == 0); if (kwnode) { if (compile_keyword_arg(iseq, args, kwnode, kwarg_ptr, flag_ptr)) { len -= 1; } else { if (keyword_node_single_splat_p(kwnode) && (*dup_rest & DUP_SINGLE_KW_SPLAT)) { compile_single_keyword_splat_mutable(iseq, args, argn, kwnode, flag_ptr); } else { compile_hash(iseq, args, kwnode, TRUE, FALSE); } } } return len; }
keyword_node_single_splat_pというのは以下のような実装になっています。
もとの実装ではhashがlist構造になっていることと、splatのときはkeyに相当するnodeがnullになっていることを踏まえると、この関数はm(**h)のように引数が1つかつsplatであるかどうかを判定していることがわかります。
static bool keyword_node_single_splat_p(NODE *kwnode) { RUBY_ASSERT(keyword_node_p(kwnode)); NODE *node = RNODE_HASH(kwnode)->nd_head; return RNODE_LIST(node)->nd_head == NULL && RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next == NULL; }
ではcompile_single_keyword_splat_mutableという関数は何をする関数なのでしょうか。
これは最終的にメソッド呼び出しに渡されるhashがdupされていることを保証する関数です。
static void compile_single_keyword_splat_mutable(rb_iseq_t *iseq, LINK_ANCHOR *const args, const NODE *argn, NODE *kwnode, unsigned int *flag_ptr) { *flag_ptr |= VM_CALL_KW_SPLAT_MUT; ADD_INSN1(args, argn, putspecialobject, INT2FIX(VM_SPECIAL_OBJECT_VMCORE)); ADD_INSN1(args, argn, newhash, INT2FIX(0)); compile_hash(iseq, args, kwnode, TRUE, FALSE); ADD_SEND(args, argn, id_core_hash_merge_kwd, INT2FIX(2)); }
メインの処理はcompile_hashに任せていますが、その前後に3つ命令を入れています。
arrayにしろhashにしろ、基本的に余分なオブジェクトは作りたくありません。
そのためm(**h)などはhをそのままmに渡すようなバイトコードを生成します。
# compile_single_keyword_splat_mutable ではないケース $ ruby --parser=parse.y --dump=i -e 'm(**h)' == disasm: #<ISeq:<main>@-e:1 (1,0)-(1,6)> 0000 putself ( 1)[Li] 0001 putself 0002 opt_send_without_block <calldata!mid:h, argc:0, FCALL|VCALL|ARGS_SIMPLE> 0004 opt_send_without_block <calldata!mid:m, argc:1, FCALL|KW_SPLAT> 0006 leave
一方で強制的にhashをdupしないといけないケースもあります1。
hメソッドの呼び出しの前後にputspecialobject, newhash, hash_merge_kwdの呼び出しが追加されていることがわかります。
# compile_single_keyword_splat_mutable のケース $ ruby --parser=parse.y --dump=i -e 'm(**h, &b)' == disasm: #<ISeq:<main>@-e:1 (1,0)-(1,10)> 0000 putself ( 1)[Li] 0001 putspecialobject 1 0003 newhash 0 0005 putself 0006 opt_send_without_block <calldata!mid:h, argc:0, FCALL|VCALL|ARGS_SIMPLE> 0008 opt_send_without_block <calldata!mid:core#hash_merge_kwd, argc:2, ARGS_SIMPLE> 0010 putself 0011 opt_send_without_block <calldata!mid:b, argc:0, FCALL|VCALL|ARGS_SIMPLE> 0013 send <calldata!mid:m, argc:1, ARGS_BLOCKARG|FCALL|KW_SPLAT|KW_SPLAT_MUT>, nil 0016 leave
putspecialobject 1の1はVM_SPECIAL_OBJECT_VMCOREのことを意味しています。
enum vm_special_object_type { VM_SPECIAL_OBJECT_VMCORE = 1, VM_SPECIAL_OBJECT_CBASE, VM_SPECIAL_OBJECT_CONST_BASE };
なので追加されたバイトコードはRubyVM::FrozenCore#hash_merge_kwd({}, h)を意味しています2。
こうすることで、メソッドmに渡されるhashが必ずdupされることが保証されます。
compile_single_keyword_splat_mutable関数の書き換えは型を合わせるだけなので割愛し、メインとなるcompile_hashへと進みます。
compile_hashを読む
compile.cのn大大変(nはいくつかよくわかっていない)のうちの1つがcompile_hashです。
とりあえず既存の実装を見てみましょう。
static int compile_hash(rb_iseq_t *iseq, LINK_ANCHOR *const ret, const NODE *node, int method_call_keywords, int popped) { const NODE *line_node = node; node = RNODE_HASH(node)->nd_head; if (!node || nd_type_p(node, NODE_ZLIST)) { if (!popped) { ADD_INSN1(ret, line_node, newhash, INT2FIX(0)); } return 0; } EXPECT_NODE("compile_hash", node, NODE_LIST, -1); if (popped) { for (; node; node = RNODE_LIST(node)->nd_next) { NO_CHECK(COMPILE_(ret, "hash element", RNODE_LIST(node)->nd_head, popped)); } return 1; } /* Compilation of a hash literal (or keyword arguments). * This is very similar to compile_array, but there are some differences: * * - It contains key-value pairs. So we need to take every two elements. * We can assume that the length is always even. * * - Merging is done by a method call (id_core_hash_merge_ptr). * Sometimes we need to insert the receiver, so "anchor" is needed. * In addition, a method call is much slower than concatarray. * So it pays only when the subsequence is really long. * (min_tmp_hash_len must be much larger than min_tmp_ary_len.) * * - We need to handle keyword splat: **kw. * For **kw, the key part (node->nd_head) is NULL, and the value part * (node->nd_next->nd_head) is "kw". * The code is a bit difficult to avoid hash allocation for **{}. */ const int max_stack_len = 0x100; const int min_tmp_hash_len = 0x800; int stack_len = 0; int first_chunk = 1; DECL_ANCHOR(anchor); INIT_ANCHOR(anchor); /* Convert pushed elements to a hash, and merge if needed */ #define FLUSH_CHUNK() \ if (stack_len) { \ if (first_chunk) { \ APPEND_LIST(ret, anchor); \ ADD_INSN1(ret, line_node, newhash, INT2FIX(stack_len)); \ } \ else { \ ADD_INSN1(ret, line_node, putspecialobject, INT2FIX(VM_SPECIAL_OBJECT_VMCORE)); \ ADD_INSN(ret, line_node, swap); \ APPEND_LIST(ret, anchor); \ ADD_SEND(ret, line_node, id_core_hash_merge_ptr, INT2FIX(stack_len + 1)); \ } \ INIT_ANCHOR(anchor); \ first_chunk = stack_len = 0; \ } while (node) { int count = 1; /* pre-allocation check (this branch can be omittable) */ if (static_literal_node_pair_p(node, iseq)) { /* count the elements that are optimizable */ const NODE *node_tmp = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next; for (; node_tmp && static_literal_node_pair_p(node_tmp, iseq); node_tmp = RNODE_LIST(RNODE_LIST(node_tmp)->nd_next)->nd_next) count++; if ((first_chunk && stack_len == 0 && !node_tmp) || count >= min_tmp_hash_len) { /* The literal contains only optimizable elements, or the subsequence is long enough */ VALUE ary = rb_ary_hidden_new(count); /* Create a hidden hash */ for (; count; count--, node = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next) { VALUE elem[2]; elem[0] = static_literal_value(RNODE_LIST(node)->nd_head, iseq); if (!RB_SPECIAL_CONST_P(elem[0])) RB_OBJ_SET_FROZEN_SHAREABLE(elem[0]); elem[1] = static_literal_value(RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_head, iseq); if (!RB_SPECIAL_CONST_P(elem[1])) RB_OBJ_SET_FROZEN_SHAREABLE(elem[1]); rb_ary_cat(ary, elem, 2); } VALUE hash = rb_hash_new_with_size(RARRAY_LEN(ary) / 2); rb_hash_bulk_insert(RARRAY_LEN(ary), RARRAY_CONST_PTR(ary), hash); hash = RB_OBJ_SET_FROZEN_SHAREABLE(rb_obj_hide(hash)); /* Emit optimized code */ FLUSH_CHUNK(); if (first_chunk) { ADD_INSN1(ret, line_node, duphash, hash); first_chunk = 0; } else { ADD_INSN1(ret, line_node, putspecialobject, INT2FIX(VM_SPECIAL_OBJECT_VMCORE)); ADD_INSN(ret, line_node, swap); ADD_INSN1(ret, line_node, putobject, hash); ADD_SEND(ret, line_node, id_core_hash_merge_kwd, INT2FIX(2)); } RB_OBJ_WRITTEN(iseq, Qundef, hash); } } /* Base case: Compile "count" elements */ for (; count; count--, node = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next) { if (CPDEBUG > 0) { EXPECT_NODE("compile_hash", node, NODE_LIST, -1); } if (RNODE_LIST(node)->nd_head) { /* Normal key-value pair */ NO_CHECK(COMPILE_(anchor, "hash key element", RNODE_LIST(node)->nd_head, 0)); NO_CHECK(COMPILE_(anchor, "hash value element", RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_head, 0)); stack_len += 2; /* If there are many pushed elements, flush them to avoid stack overflow */ if (stack_len >= max_stack_len) FLUSH_CHUNK(); } else { /* kwsplat case: foo(..., **kw, ...) */ FLUSH_CHUNK(); const NODE *kw = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_head; int empty_kw = nd_type_p(kw, NODE_HASH) && (!RNODE_HASH(kw)->nd_head); /* foo( ..., **{}, ...) */ int first_kw = first_chunk && stack_len == 0; /* foo(1,2,3, **kw, ...) */ int last_kw = !RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next; /* foo( ..., **kw) */ int only_kw = last_kw && first_kw; /* foo(1,2,3, **kw) */ empty_kw = empty_kw || nd_type_p(kw, NODE_NIL); /* foo( ..., **nil, ...) */ if (empty_kw) { if (only_kw && method_call_keywords) { /* **{} appears at the only keyword argument in method call, * so it won't be modified. * kw is a special NODE_LIT that contains a special empty hash, * so this emits: putobject {}. * This is only done for method calls and not for literal hashes, * because literal hashes should always result in a new hash. */ NO_CHECK(COMPILE(ret, "keyword splat", kw)); } else if (first_kw) { /* **{} appears as the first keyword argument, so it may be modified. * We need to create a fresh hash object. */ ADD_INSN1(ret, line_node, newhash, INT2FIX(0)); } /* Any empty keyword splats that are not the first can be ignored. * since merging an empty hash into the existing hash is the same * as not merging it. */ } else { if (only_kw && method_call_keywords) { /* **kw is only keyword argument in method call. * Use directly. This will be not be flagged as mutable. * This is only done for method calls and not for literal hashes, * because literal hashes should always result in a new hash. */ NO_CHECK(COMPILE(ret, "keyword splat", kw)); } else { /* There is more than one keyword argument, or this is not a method * call. In that case, we need to add an empty hash (if first keyword), * or merge the hash to the accumulated hash (if not the first keyword). */ ADD_INSN1(ret, line_node, putspecialobject, INT2FIX(VM_SPECIAL_OBJECT_VMCORE)); if (first_kw) ADD_INSN1(ret, line_node, newhash, INT2FIX(0)); else ADD_INSN(ret, line_node, swap); NO_CHECK(COMPILE(ret, "keyword splat", kw)); ADD_SEND(ret, line_node, id_core_hash_merge_kwd, INT2FIX(2)); } } first_chunk = 0; } } } FLUSH_CHUNK(); #undef FLUSH_CHUNK return 1; }
長い...
1つずつ読んでいきましょう。
if (!node || nd_type_p(node, NODE_ZLIST)) { if (!popped) { ADD_INSN1(ret, line_node, newhash, INT2FIX(0)); } return 0; }
{}などのときはnewhash 0で空のhashを生成するだけで済みます。
次の塊です。
if (popped) { for (; node; node = RNODE_LIST(node)->nd_next) { NO_CHECK(COMPILE_(ret, "hash element", RNODE_LIST(node)->nd_head, popped)); } return 1; }
poppedというのはコンパイルした結果をその後では使わないことを意味しています。
たとえば次のコードでは2行目で作ったhashを使うことはありません。
そのような場合にはkeyとvalueのコンパイルはしますが、hashの生成はしないで終わらせます3。
# == disasm: #<ISeq:m@test3.rb:1 (1,0)-(4,3)> # 0000 putself ( 2)[LiCa] # 0001 opt_send_without_block <calldata!mid:v1, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0003 pop # 0004 putobject_INT2FIX_1_ ( 3)[Li] # 0005 leave [Re] def m {k1: v1} return 1 end
FLUSH_CHUNKマクロは一旦無視してwhileループのなかをみます。
while (node) { int count = 1; /* pre-allocation check (this branch can be omittable) */ if (static_literal_node_pair_p(node, iseq)) { /* count the elements that are optimizable */ const NODE *node_tmp = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next; for (; node_tmp && static_literal_node_pair_p(node_tmp, iseq); node_tmp = RNODE_LIST(RNODE_LIST(node_tmp)->nd_next)->nd_next) count++; if ((first_chunk && stack_len == 0 && !node_tmp) || count >= min_tmp_hash_len) { /* The literal contains only optimizable elements, or the subsequence is long enough */ VALUE ary = rb_ary_hidden_new(count); /* Create a hidden hash */ for (; count; count--, node = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next) { VALUE elem[2]; elem[0] = static_literal_value(RNODE_LIST(node)->nd_head, iseq); if (!RB_SPECIAL_CONST_P(elem[0])) RB_OBJ_SET_FROZEN_SHAREABLE(elem[0]); elem[1] = static_literal_value(RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_head, iseq); if (!RB_SPECIAL_CONST_P(elem[1])) RB_OBJ_SET_FROZEN_SHAREABLE(elem[1]); rb_ary_cat(ary, elem, 2); } VALUE hash = rb_hash_new_with_size(RARRAY_LEN(ary) / 2); rb_hash_bulk_insert(RARRAY_LEN(ary), RARRAY_CONST_PTR(ary), hash); hash = RB_OBJ_SET_FROZEN_SHAREABLE(rb_obj_hide(hash)); /* Emit optimized code */ FLUSH_CHUNK(); if (first_chunk) { ADD_INSN1(ret, line_node, duphash, hash); first_chunk = 0; } else { ADD_INSN1(ret, line_node, putspecialobject, INT2FIX(VM_SPECIAL_OBJECT_VMCORE)); ADD_INSN(ret, line_node, swap); ADD_INSN1(ret, line_node, putobject, hash); ADD_SEND(ret, line_node, id_core_hash_merge_kwd, INT2FIX(2)); } RB_OBJ_WRITTEN(iseq, Qundef, hash); } }
前半の塊ではkeyとvalueの両方がstaticな部分を扱います。 staticというのはsymbolやintegerのような値のことを指します4。
staticなkeyとvalueが連続している箇所はcompile時にhashをつくり直接命令のオペランドにします5。
# 0000 duphash {k1: 1, k2: 2} ( 1)[Li] # 0002 leave {k1: 1, k2: 2}
後半の塊は前半で最適化できないケースを扱います。
/* Base case: Compile "count" elements */ for (; count; count--, node = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next) { if (CPDEBUG > 0) { EXPECT_NODE("compile_hash", node, NODE_LIST, -1); } if (RNODE_LIST(node)->nd_head) { /* Normal key-value pair */ NO_CHECK(COMPILE_(anchor, "hash key element", RNODE_LIST(node)->nd_head, 0)); NO_CHECK(COMPILE_(anchor, "hash value element", RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_head, 0)); stack_len += 2; /* If there are many pushed elements, flush them to avoid stack overflow */ if (stack_len >= max_stack_len) FLUSH_CHUNK(); } else { /* kwsplat case: foo(..., **kw, ...) */ FLUSH_CHUNK(); const NODE *kw = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_head; int empty_kw = nd_type_p(kw, NODE_HASH) && (!RNODE_HASH(kw)->nd_head); /* foo( ..., **{}, ...) */ int first_kw = first_chunk && stack_len == 0; /* foo(1,2,3, **kw, ...) */ int last_kw = !RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next; /* foo( ..., **kw) */ int only_kw = last_kw && first_kw; /* foo(1,2,3, **kw) */ empty_kw = empty_kw || nd_type_p(kw, NODE_NIL); /* foo( ..., **nil, ...) */ if (empty_kw) { if (only_kw && method_call_keywords) { /* **{} appears at the only keyword argument in method call, * so it won't be modified. * kw is a special NODE_LIT that contains a special empty hash, * so this emits: putobject {}. * This is only done for method calls and not for literal hashes, * because literal hashes should always result in a new hash. */ NO_CHECK(COMPILE(ret, "keyword splat", kw)); } else if (first_kw) { /* **{} appears as the first keyword argument, so it may be modified. * We need to create a fresh hash object. */ ADD_INSN1(ret, line_node, newhash, INT2FIX(0)); } /* Any empty keyword splats that are not the first can be ignored. * since merging an empty hash into the existing hash is the same * as not merging it. */ } else { if (only_kw && method_call_keywords) { /* **kw is only keyword argument in method call. * Use directly. This will be not be flagged as mutable. * This is only done for method calls and not for literal hashes, * because literal hashes should always result in a new hash. */ NO_CHECK(COMPILE(ret, "keyword splat", kw)); } else { /* There is more than one keyword argument, or this is not a method * call. In that case, we need to add an empty hash (if first keyword), * or merge the hash to the accumulated hash (if not the first keyword). */ ADD_INSN1(ret, line_node, putspecialobject, INT2FIX(VM_SPECIAL_OBJECT_VMCORE)); if (first_kw) ADD_INSN1(ret, line_node, newhash, INT2FIX(0)); else ADD_INSN(ret, line_node, swap); NO_CHECK(COMPILE(ret, "keyword splat", kw)); ADD_SEND(ret, line_node, id_core_hash_merge_kwd, INT2FIX(2)); } } first_chunk = 0; } }
if (RNODE_LIST(node)->nd_head)、つまりsplatではないケースではkeyとvalueをそれぞれコンパイルします。それらの結果はスタックに積まれます。
スタックに積まれる値はどこかのタイミングでhashに変換しないといけません。
そのための命令を生成するのがFLUSH_CHUNKマクロです。
/* Convert pushed elements to a hash, and merge if needed */ #define FLUSH_CHUNK() \ if (stack_len) { \ if (first_chunk) { \ APPEND_LIST(ret, anchor); \ ADD_INSN1(ret, line_node, newhash, INT2FIX(stack_len)); \ } \ else { \ ADD_INSN1(ret, line_node, putspecialobject, INT2FIX(VM_SPECIAL_OBJECT_VMCORE)); \ ADD_INSN(ret, line_node, swap); \ APPEND_LIST(ret, anchor); \ ADD_SEND(ret, line_node, id_core_hash_merge_ptr, INT2FIX(stack_len + 1)); \ } \ INIT_ANCHOR(anchor); \ first_chunk = stack_len = 0; \ }
FLUSH_CHUNKはすでにスタックにhashが生成されているかどうかで命令を使い分ける必要があります。
すでにhashがある場合には、RubyVM::FrozenCore#hash_merge_ptrを用いてそのhashへ要素をmergeします。
一方でまだhashがない場合にはnewhash命令をつかってスタックにある要素からhashをつくります。
# 0000 putspecialobject 1 ( 3)[Li] # 0002 newhash 0 # 0004 putself # 0005 opt_send_without_block <calldata!mid:kw, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0007 opt_send_without_block <calldata!mid:core#hash_merge_kwd, argc:2, ARGS_SIMPLE> # 0009 putspecialobject 1 # 0011 swap # 0012 putobject :k1 # 0014 putobject_INT2FIX_1_ # 0015 opt_send_without_block <calldata!mid:core#hash_merge_ptr, argc:3, ARGS_SIMPLE> # 0017 leave {**kw, k1: 1} # 0000 putself ( 12)[Li] # 0001 opt_send_without_block <calldata!mid:kw, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0003 pop # 0004 putobject :k1 ( 14)[Li] # 0006 putself # 0007 opt_send_without_block <calldata!mid:v1, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0009 putobject :k2 # 0011 putself # 0012 opt_send_without_block <calldata!mid:v2, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0014 newhash 4 # 0016 leave {k1: v1, k2: v2}
FLUSH_CHUNKは以下のタイミングで呼ぶ必要があります。
- static literalの最適化が効かない部分から、最適化が効く部分に移ったとき
**kwが出現したときcompile_hashから抜けるとき
最適化が効く部分は1つのhashにまとまるので、それ以前にスタックに積んだ値がある場合には、そこまでを1つのhashにしておく必要があります。
**kwも1つのhashとして扱われるので、それ以前にスタックに積んだ値がある場合には、そこまでを1つのhashにしておく必要があります。
compile_hash関数から抜けるときにスタックに要素が残っている場合にはhashにしておかないと、それらの値が無視されてしまいます。
compile_hashを書き換える
大体頭に入ったのでcompile_hashを書き換えていきます。
一つ注意点があります。
書き換え前の世界では{k1: :v1}もm(k1: :v1)も同じNODE_HASHで管理していました。
一方で書き換え後の世界ではそれぞれHashNodeとKeywordHashNodeと別のノードで管理するようになります。
どちらのノードもelementsというフィールドでノードの配列を管理しているので、compile_hash関数の引数にノードのリストを追加しておきます。
いままでリスト構造だったデータが配列になるという点を除けば、特にロジックを書き換える必要はありません6。
変更前はcountを減らすタイミングでnodeを1つ進めていたので、変更後もcountを減らすタイミングでi++をします7。
// Before while (node) { int count = 1; // static_literal の最適化 if (static_literal_node_pair_p(node, iseq)) { for (...) count++; // ここでhashを生成する場合 if (...) for (; count; count--, node = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next) {} } for (; count; count--, node = RNODE_LIST(RNODE_LIST(node)->nd_next)->nd_next) { // keyとvalueをコンパイルする } } // After for (size_t i = 0; i < RB_NODE_LIST_LEN(list);) { int count = 1; node = list->nodes[i]; // static_literal の最適化 if (static_literal_node_pair_p(node, iseq)) { size_t j = i + 1; for (; j < RB_NODE_LIST_LEN(list) && static_literal_node_pair_p(list->nodes[j], iseq); j++) count++; // ここでhashを生成する場合 if (...) for (; count; count--, i++) { node = list->nodes[i]; ... } } for (; count; count--, i++) // keyとvalueをコンパイルする node = list->nodes[i]; ... } }
ぱっと作れる範囲でそれぞれの分岐をカバーできるコードを用意して、既存の実装と差分をみてみると...
なんとdiffが0になっていました。ほんまか...?
# 一番最初分岐にいれる h1 = {} # 2つ目の分岐にいれる {k1: v1, **v2} # static_literal_node_pair_pが有効 h3 = {k1: :v1, k2: :v2} # static_literal_node_pair_pが無効 h4 = {k1: :v1, k2: v2} # empty_kw その1 h5 = {**nil} # empty_kw その2 h6 = {k1: :v1, **nil} # empty_kw ではないsplat h7 = {k1: :v1, **kw}
メソッド呼び出しのケースも簡単なコードを用意して差分をみてみます8。
# 2つ目の分岐にいれる m2(k1: v1, **v2) # static_literal_node_pair_pが有効 m3(k1: :v1, k2: :v2) # static_literal_node_pair_pが無効 m4(k1: :v1, k2: v2) # empty_kw その1 m5(**nil) # empty_kw その2 m6(k1: :v1, **nil) # empty_kw ではないsplat m7(k1: :v1, **kw) m8(**kw)
kwの値がdiffとして出てくるのはある種当然なのでいいとして、他に差分はないようです9。
ほんまか...?
diff --git a/tmp/b b/tmp/a index 4981dfee8f..33fffe4e61 100644 --- a/tmp/b +++ b/tmp/a @@ -14,13 +14,13 @@ 0019 putself ( 5)[Li] 0020 putobject :v1 0022 putobject :v2 -0024 opt_send_without_block <calldata!mid:m3, argc:2, kw:[#<Symbol:0x000000000085310c>,#<Symbol:0x000000000085710c>], FCALL|KWARG> +0024 opt_send_without_block <calldata!mid:m3, argc:2, kw:[#<Symbol:0x000000000078510c>,#<Symbol:0x000000000078910c>], FCALL|KWARG> 0026 pop 0027 putself ( 8)[Li] 0028 putobject :v1 0030 putself 0031 opt_send_without_block <calldata!mid:v2, argc:0, FCALL|VCALL|ARGS_SIMPLE> -0033 opt_send_without_block <calldata!mid:m4, argc:2, kw:[#<Symbol:0x000000000085310c>,#<Symbol:0x000000000085710c>], FCALL|KWARG> +0033 opt_send_without_block <calldata!mid:m4, argc:2, kw:[#<Symbol:0x000000000078510c>,#<Symbol:0x000000000078910c>], FCALL|KWARG> 0035 pop 0036 putself ( 11)[Li] 0037 putnil
これは完全に自分向けのメモなのですが、struct rb_callinfo_kwargのkeyword_lenはnew_callinfo関数の中でargcに加算されます。
なので、keyを埋め込むときのsymbolの数はsetup_args_coreの戻り値に含めないのが正解です。
一方で埋め込まないときのhashはkeyword_lenに含まれないのでsetup_args_coreの戻り値に含めないといけません。
KW_SPLATとKW_SPLAT_MUT
m(*a)のようなsplatにARGS_SPLATとARGS_SPLAT_MUTというフラグがあったように、キーワード引数にもKW_SPLATとKW_SPLAT_MUTというフラグがあります。
キーワード引数の場合は、keyをopt_send_without_block命令に埋め込まない場合には常にKW_SPLATのフラグが立ちます。
これはkeyを埋め込まない場合には常に1つのhashに引数を詰め込んで渡すためです。
一方でKW_SPLAT_MUTのほうはノードの種類と呼び出す関数の組み合わせでフラグが立ったり立たなかったりします。
例えばcompile_single_keyword_splat_mutableの場合は、名前からも分かるように必ずhashを作ることが保証されています。
そのためこの関数のなかで必ずKW_SPLAT_MUTをセットします。
static void compile_single_keyword_splat_mutable(rb_iseq_t *iseq, LINK_ANCHOR *const args, const NODE *argn, rb_keyword_hash_node_t *kwnode, unsigned int *flag_ptr) { *flag_ptr |= VM_CALL_KW_SPLAT_MUT; ADD_INSN1(args, argn, putspecialobject, INT2FIX(VM_SPECIAL_OBJECT_VMCORE)); ADD_INSN1(args, argn, newhash, INT2FIX(0)); compile_hash(iseq, args, kwnode, &kwnode->elements, TRUE, FALSE); ADD_SEND(args, argn, id_core_hash_merge_kwd, INT2FIX(2)); }
一方でcompile_hashの場合はsetup_args_coreのほうで判断してKW_SPLAT_MUTを立てなくてはいけません。
たとえばNODE_ARGSCATはcompile_hashを呼び出しますが、その際にKW_SPLAT_MUTを立てません。
# 0000 putself ( 1)[Li] # 0001 putself # 0002 opt_send_without_block <calldata!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0004 splatarray true # 0006 putobject_INT2FIX_1_ # 0007 pushtoarray 1 # 0009 putobject :k1 # 0011 putself # 0012 opt_send_without_block <calldata!mid:v1, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0014 newhash 2 # 0016 opt_send_without_block <calldata!mid:m1, argc:2, ARGS_SPLAT|ARGS_SPLAT_MUT|FCALL|KW_SPLAT> # 0018 leave m1(*a, 1, k1: v1) # 0000 putself ( 1)[Li] # 0001 putself # 0002 opt_send_without_block <calldata!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0004 splatarray true # 0006 putobject_INT2FIX_1_ # 0007 pushtoarray 1 # 0009 duphash {k1: :v1} # 0011 opt_send_without_block <calldata!mid:m1, argc:2, ARGS_SPLAT|ARGS_SPLAT_MUT|FCALL|KW_SPLAT> # 0013 leave m1(*a, 1, k1: :v1)
これらのバイトコードではnewhashやduphashが使われているので、KW_SPLAT_MUTを立てても問題ないはずです。
しかしNODE_ARGSCATのキーワード引数の部分が**kwのとき、compile_hashは余計なhashを作りません。
この場合にKW_SPLAT_MUTを立ててはいけません。
# 0000 putself ( 1)[Li] # 0001 putself # 0002 opt_send_without_block <calldata!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0004 splatarray true # 0006 putobject_INT2FIX_1_ # 0007 pushtoarray 1 # 0009 putself # 0010 opt_send_without_block <calldata!mid:kw, argc:0, FCALL|VCALL|ARGS_SIMPLE> # 0012 opt_send_without_block <calldata!mid:m1, argc:2, ARGS_SPLAT|ARGS_SPLAT_MUT|FCALL|KW_SPLAT> # 0014 leave m1(*a, 1, **kw)
現在のcompile_hashはhashと引数のコンパイルの両方を兼ねており、引数をコンパイルするさいのflagの更新は行いません。
また呼び出しもとのsetup_args_coreなどは、compile_hashがhashを新規に作成するようなバイトコードを生成したかを知ることができません。
そのような場合にはKW_SPLAT_MUTを立てないという安全サイドに倒すしかないでしょう。
今回の書き換えで引数をフラットに扱えるようになったので、最適化はsetup_args_coreによせてcompile_hashは常にhashを生成するように変更するのがいいかもしれません。
compile_hashはmethod_call_keywordsという引数をとりますが、この引数によって変わるのは**kwや**nilのようにsplitが1つ存在するときだけなので、setup_args_core側で判断することは可能だと思います。
まとめ
今日の成果です。
- キーワード引数を扱えるようになった
次回はブロックと&blk引数に取り組みます。
- なぜこのとき強制的にdupする必要があるかは今後機会があれば説明します。↩
-
RubyVM::FrozenCore#hash_merge_kwd({}, h)は端的言えば{}.merge!をします。Hash#merge!を使わないのは、Hash#merge!が上書きされているときでも期待した挙動をするメソッドが欲しいためだと思います。↩ - keyとvalueをコンパイルするのは、それらが副作用を持つ可能性があるからです。たとえばvalueがメソッド呼び出しなのであれば、その分の実行をスキップすることはできません。一方でこの例のようにkeyがsymbolであれば、それはバイトコードとして実行してもしなくても同じなので、keyに対応するバイトコードは生成されなくなっています。↩
-
staticか判定をする
static_literal_node_pという関数はbool hash_keyという引数をとります。これはいまのRubyではhashのkeyがstringのとき、そのstringはfreezeされるためです。keyをfreezeする処理はrb_hash_key_strというhash.cの関数が行っています。↩ -
引数の場合、最適化などで
compile_hashが呼ばれないケースがあるため、コードが複雑な場合にはhashリテラルで説明します。↩ -
当初
for (size_t i = 0; i < RB_NODE_LIST_LEN(list); i++) { ...と一番外側のループでもi++していたので、奇数番のkey & valueのみをコンパイルする実装になってしまいました(一敗)。↩ -
jとi + countは常に同じ値になる気がしますね...↩ - コードとしては短くて簡単に見えますが、ここまでの実装を考えると全然簡単ではないですね...↩
-
当初キーワード引数のhashをargcに入れ忘れていて、
opt_send_without_blockのargcが1足らないというバグを入れました(二敗)。↩
