From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS39351 185.65.132.0/22 X-Spam-Status: No, score=-2.1 required=3.0 tests=AWL,BAYES_00,RCVD_IN_XBL shortcircuit=no autolearn=no version=3.3.2 X-Original-To: spew@80x24.org Received: from 80x24.org (torproxy02.31173.se [185.65.135.227]) by dcvr.yhbt.net (Postfix) with ESMTP id 25B496362CA for ; Tue, 8 Dec 2015 08:08:42 +0000 (UTC) From: Eric Wong To: spew@80x24.org Subject: [PATCH v3] micro-optimize case dispatch even harder Date: Tue, 8 Dec 2015 08:08:40 +0000 Message-Id: <20151208080840.24265-1-e@80x24.org> List-Id: I noticed these optimizations while working on r52931. By using a bare hash table, we avoid the overhead of rb_hash_* functions as well as the cost of translating FIX2INT for jump labels. This only reduces GC overhead slightly, as we can only mark keys instead of values. * vm_core.h (CDHASH): change to st_table * * benchmark/bm_vm2_case_small.rb: new benchmark * compile.c (struct cdhash_set_label_struct): change to st_table * (cdhash_set_label_i): adjust to store int in cdhash (iseq_set_sequence): adjust for type change (when_vals): ditto (iseq_compile_each): ditto (iseq_build_from_ary_body): ditto (cdhash_from_ary): extract from iseq_build_from_ary_body * insns.def (opt_case_dispatch): ditto * iseq.c (cdhash_each): ditto (iseq_data_to_ary): ditto * test/ruby/test_iseq.rb (test_memleak): new test [ruby-core:71931] [Feature #11786] Slightly smaller improvements with leak fix, but it could be noise for the small cases. benchmark results: minimum results in each 10 measurements. Execution time (sec) name a b loop_whileloop2 0.104 0.104 vm2_case* 0.072 0.062 vm2_case_lit* 0.540 0.539 vm2_case_small* 0.060 0.053 Speedup ratio: compare with the result of `a' (greater is better) name b loop_whileloop2 0.994 vm2_case* 1.153 vm2_case_lit* 1.002 vm2_case_small* 1.136 --- benchmark/bm_vm2_case_small.rb | 9 +++++ compile.c | 80 ++++++++++++++++++++++-------------------- insns.def | 6 ++-- iseq.c | 6 ++-- test/ruby/test_iseq.rb | 22 ++++++++++++ vm_core.h | 2 +- 6 files changed, 80 insertions(+), 45 deletions(-) create mode 100644 benchmark/bm_vm2_case_small.rb diff --git a/benchmark/bm_vm2_case_small.rb b/benchmark/bm_vm2_case_small.rb new file mode 100644 index 0000000..b009a3e --- /dev/null +++ b/benchmark/bm_vm2_case_small.rb @@ -0,0 +1,9 @@ +i = 0 +while i<6_000_000 # while loop 2 + case :foo + when :foo + i += 1 + else + raise + end +end diff --git a/compile.c b/compile.c index bb0a07c..afd177c 100644 --- a/compile.c +++ b/compile.c @@ -1492,17 +1492,17 @@ static const struct st_hash_type cdhash_type = { }; struct cdhash_set_label_struct { - VALUE hash; + st_table *cdh; int pos; int len; }; static int -cdhash_set_label_i(VALUE key, VALUE val, void *ptr) +cdhash_set_label_i(VALUE key, long val, void *ptr) { - struct cdhash_set_label_struct *data = (struct cdhash_set_label_struct *)ptr; + struct cdhash_set_label_struct *d = (struct cdhash_set_label_struct *)ptr; LABEL *lobj = (LABEL *)(val & ~1); - rb_hash_aset(data->hash, key, INT2FIX(lobj->position - (data->pos+data->len))); + st_insert(d->cdh, key, lobj->position - (d->pos + d->len)); return ST_CONTINUE; } @@ -1630,15 +1630,14 @@ iseq_set_sequence(rb_iseq_t *iseq, LINK_ANCHOR *anchor) } case TS_CDHASH: { - VALUE map = operands[j]; - struct cdhash_set_label_struct data; - data.hash = map; - data.pos = code_index; - data.len = len; - rb_hash_foreach(map, cdhash_set_label_i, (VALUE)&data); - - freeze_hide_obj(map); - generated_iseq[code_index + 1 + j] = map; + st_table *cdh = (st_table *)operands[j]; + struct cdhash_set_label_struct d; + d.cdh = cdh; + d.pos = code_index; + d.len = len; + + st_foreach(cdh, cdhash_set_label_i, (st_data_t)&d); + generated_iseq[code_index + 1 + j] = (VALUE)cdh; break; } case TS_LINDEX: @@ -2932,7 +2931,8 @@ case_when_optimizable_literal(NODE * node) } static int -when_vals(rb_iseq_t *iseq, LINK_ANCHOR *cond_seq, NODE *vals, LABEL *l1, int only_special_literals, VALUE literals) +when_vals(rb_iseq_t *iseq, LINK_ANCHOR *cond_seq, NODE *vals, LABEL *l1, + int only_special_literals, st_table *literals) { while (vals) { NODE* val = vals->nd_head; @@ -2942,11 +2942,11 @@ when_vals(rb_iseq_t *iseq, LINK_ANCHOR *cond_seq, NODE *vals, LABEL *l1, int onl only_special_literals = 0; } else { - if (rb_hash_lookup(literals, lit) != Qnil) { + if (st_lookup(literals, lit, 0)) { rb_compile_warning(ruby_sourcefile, nd_line(val), "duplicated when clause is ignored"); } else { - rb_hash_aset(literals, lit, (VALUE)(l1) | 1); + st_add_direct(literals, lit, (VALUE)(l1) | 1); } } @@ -3703,14 +3703,14 @@ iseq_compile_each(rb_iseq_t *iseq, LINK_ANCHOR *ret, NODE * node, int poped) DECL_ANCHOR(body_seq); DECL_ANCHOR(cond_seq); int only_special_literals = 1; - VALUE literals = rb_hash_new(); + st_table *literals = st_init_table(&cdhash_type); + VALUE lit_wrapper; + lit_wrapper = Data_Wrap_Struct(0, rb_mark_set, st_free_table, literals); INIT_ANCHOR(head); INIT_ANCHOR(body_seq); INIT_ANCHOR(cond_seq); - rb_hash_tbl_raw(literals)->type = &cdhash_type; - if (node->nd_head == 0) { COMPILE_(ret, "when", node->nd_body, poped); break; @@ -3789,8 +3789,7 @@ iseq_compile_each(rb_iseq_t *iseq, LINK_ANCHOR *ret, NODE * node, int poped) } if (only_special_literals) { - iseq_add_mark_object(iseq, literals); - + iseq_add_mark_object(iseq, lit_wrapper); ADD_INSN(ret, nd_line(tempnode), dup); ADD_INSN2(ret, nd_line(tempnode), opt_case_dispatch, literals, elselabel); LABEL_REF(elselabel); @@ -6298,6 +6297,27 @@ iseq_build_callinfo_from_hash(rb_iseq_t *iseq, VALUE op) return (VALUE)new_callinfo(iseq, mid, orig_argc, flag, kw_arg, (flag & VM_CALL_ARGS_SIMPLE) == 0); } +static VALUE +cdhash_from_ary(rb_iseq_t *iseq, st_table *labels_table, VALUE op) +{ + int i; + st_table *literals = st_init_table(&cdhash_type); + VALUE lit_wrap = Data_Wrap_Struct(0, rb_mark_set, st_free_table, literals); + + iseq_add_mark_object(iseq, lit_wrap); + op = rb_convert_type(op, T_ARRAY, "Array", "to_ary"); + for (i = 0; i < RARRAY_LEN(op); i += 2) { + VALUE key = RARRAY_AREF(op, i); + VALUE sym = RARRAY_AREF(op, i + 1); + LABEL *label = register_label(iseq, labels_table, sym); + + st_add_direct(literals, key, (VALUE)label | 1); + } + RB_GC_GUARD(op); + + return (VALUE)literals; +} + static int iseq_build_from_ary_body(rb_iseq_t *iseq, LINK_ANCHOR *anchor, VALUE body, VALUE labels_wrapper) @@ -6401,23 +6421,7 @@ iseq_build_from_ary_body(rb_iseq_t *iseq, LINK_ANCHOR *anchor, "Symbol", "to_sym"); break; case TS_CDHASH: - { - int i; - VALUE map = rb_hash_new(); - - rb_hash_tbl_raw(map)->type = &cdhash_type; - op = rb_convert_type(op, T_ARRAY, "Array", "to_ary"); - for (i=0; i