ruby-changes:49420
From: mame <ko1@a...>
Date: Mon, 1 Jan 2018 21:51:25 +0900 (JST)
Subject: [ruby-changes:49420] mame:r61536 (trunk): iseq.h: Extract position array from iseq_insn_info_entry
mame 2018-01-01 21:51:21 +0900 (Mon, 01 Jan 2018) New Revision: 61536 https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=61536 Log: iseq.h: Extract position array from iseq_insn_info_entry This makes TracePoint a bit fast by reducing cache misses of `get_insn_info_binary_search`. Also, I plan to use succinct bitvector algorithm for `get_insn_info` instead of binary search. This change will make it easy. Modified files: trunk/compile.c trunk/iseq.c trunk/iseq.h trunk/vm_core.h Index: vm_core.h =================================================================== --- vm_core.h (revision 61535) +++ vm_core.h (revision 61536) @@ -373,6 +373,7 @@ struct rb_iseq_constant_body { https://github.com/ruby/ruby/blob/trunk/vm_core.h#L373 /* insn info, must be freed */ struct iseq_insn_info { const struct iseq_insn_info_entry *body; + const unsigned int *positions; unsigned int size; } insns_info; Index: compile.c =================================================================== --- compile.c (revision 61535) +++ compile.c (revision 61536) @@ -1829,16 +1829,16 @@ fix_sp_depth(rb_iseq_t *iseq, LINK_ANCHO https://github.com/ruby/ruby/blob/trunk/compile.c#L1829 } static int -add_insn_info(struct iseq_insn_info_entry *insns_info, int insns_info_index, int code_index, LINK_ELEMENT *list) +add_insn_info(struct iseq_insn_info_entry *insns_info, unsigned int *positions, int insns_info_index, int code_index, LINK_ELEMENT *list) { if (list->type == ISEQ_ELEMENT_INSN) { INSN *iobj = (INSN *)list; if (insns_info_index == 0 || insns_info[insns_info_index-1].line_no != iobj->insn_info.line_no || insns_info[insns_info_index-1].events != iobj->insn_info.events) { - insns_info[insns_info_index].position = code_index; insns_info[insns_info_index].line_no = iobj->insn_info.line_no; insns_info[insns_info_index].events = iobj->insn_info.events; + positions[insns_info_index] = code_index; return TRUE; } else { @@ -1849,9 +1849,9 @@ add_insn_info(struct iseq_insn_info_entr https://github.com/ruby/ruby/blob/trunk/compile.c#L1849 ADJUST *adjust = (ADJUST *)list; if (insns_info_index > 0 || insns_info[insns_info_index-1].line_no != adjust->line_no) { - insns_info[insns_info_index].position = code_index; insns_info[insns_info_index].line_no = adjust->line_no; insns_info[insns_info_index].events = 0; + positions[insns_info_index] = code_index; return TRUE; } else { @@ -1870,6 +1870,7 @@ static int https://github.com/ruby/ruby/blob/trunk/compile.c#L1870 iseq_set_sequence(rb_iseq_t *iseq, LINK_ANCHOR *const anchor) { struct iseq_insn_info_entry *insns_info; + unsigned int *positions; LINK_ELEMENT *list; VALUE *generated_iseq; rb_event_flag_t events = 0; @@ -1929,6 +1930,7 @@ iseq_set_sequence(rb_iseq_t *iseq, LINK_ https://github.com/ruby/ruby/blob/trunk/compile.c#L1930 /* make instruction sequence */ generated_iseq = ALLOC_N(VALUE, code_index); insns_info = ALLOC_N(struct iseq_insn_info_entry, insn_num); + positions = ALLOC_N(unsigned int, insn_num); iseq->body->is_entries = ZALLOC_N(union iseq_inline_storage_entry, iseq->body->is_size); iseq->body->ci_entries = (struct rb_call_info *)ruby_xmalloc(sizeof(struct rb_call_info) * iseq->body->ci_size + sizeof(struct rb_call_info_with_kwarg) * iseq->body->ci_kw_size); @@ -2057,7 +2059,7 @@ iseq_set_sequence(rb_iseq_t *iseq, LINK_ https://github.com/ruby/ruby/blob/trunk/compile.c#L2059 return COMPILE_NG; } } - if (add_insn_info(insns_info, insns_info_index, code_index, (LINK_ELEMENT *)iobj)) insns_info_index++; + if (add_insn_info(insns_info, positions, insns_info_index, code_index, (LINK_ELEMENT *)iobj)) insns_info_index++; code_index += len; break; } @@ -2082,7 +2084,7 @@ iseq_set_sequence(rb_iseq_t *iseq, LINK_ https://github.com/ruby/ruby/blob/trunk/compile.c#L2084 if (adjust->line_no != -1) { const int diff = orig_sp - sp; if (diff > 0) { - if (add_insn_info(insns_info, insns_info_index, code_index, (LINK_ELEMENT *)adjust)) insns_info_index++; + if (add_insn_info(insns_info, positions, insns_info_index, code_index, (LINK_ELEMENT *)adjust)) insns_info_index++; } if (diff > 1) { generated_iseq[code_index++] = BIN(adjuststack); @@ -2095,6 +2097,7 @@ iseq_set_sequence(rb_iseq_t *iseq, LINK_ https://github.com/ruby/ruby/blob/trunk/compile.c#L2097 int label_no = adjust->label ? adjust->label->label_no : -1; xfree(generated_iseq); xfree(insns_info); + xfree(positions); debug_list(anchor); COMPILE_ERROR(iseq, adjust->line_no, "iseq_set_sequence: adjust bug to %d %d < %d", @@ -2117,9 +2120,12 @@ iseq_set_sequence(rb_iseq_t *iseq, LINK_ https://github.com/ruby/ruby/blob/trunk/compile.c#L2120 /* get rid of memory leak when REALLOC failed */ iseq->body->insns_info.body = insns_info; + iseq->body->insns_info.positions = positions; REALLOC_N(insns_info, struct iseq_insn_info_entry, insns_info_index); iseq->body->insns_info.body = insns_info; + REALLOC_N(positions, unsigned int, insns_info_index); + iseq->body->insns_info.positions = positions; iseq->body->insns_info.size = insns_info_index; return COMPILE_OK; @@ -8356,17 +8362,29 @@ ibf_load_param_keyword(const struct ibf_ https://github.com/ruby/ruby/blob/trunk/compile.c#L8362 } static struct iseq_insn_info_entry * -ibf_dump_insns_info(struct ibf_dump *dump, const rb_iseq_t *iseq) +ibf_dump_insns_info_body(struct ibf_dump *dump, const rb_iseq_t *iseq) { return IBF_W(iseq->body->insns_info.body, struct iseq_insn_info_entry, iseq->body->insns_info.size); } static struct iseq_insn_info_entry * -ibf_load_insns_info(const struct ibf_load *load, const struct rb_iseq_constant_body *body) +ibf_load_insns_info_body(const struct ibf_load *load, const struct rb_iseq_constant_body *body) { return IBF_R(body->insns_info.body, struct iseq_insn_info_entry, body->insns_info.size); } +static unsigned int * +ibf_dump_insns_info_positions(struct ibf_dump *dump, const rb_iseq_t *iseq) +{ + return IBF_W(iseq->body->insns_info.positions, unsigned int, iseq->body->insns_info.size); +} + +static unsigned int * +ibf_load_insns_info_positions(const struct ibf_load *load, const struct rb_iseq_constant_body *body) +{ + return IBF_R(body->insns_info.positions, unsigned int, body->insns_info.size); +} + static ID * ibf_dump_local_table(struct ibf_dump *dump, const rb_iseq_t *iseq) { @@ -8515,18 +8533,19 @@ ibf_dump_iseq_each(struct ibf_dump *dump https://github.com/ruby/ruby/blob/trunk/compile.c#L8533 dump_body.location.base_label = ibf_dump_object(dump, dump_body.location.base_label); dump_body.location.label = ibf_dump_object(dump, dump_body.location.label); - dump_body.iseq_encoded = ibf_dump_code(dump, iseq); - dump_body.param.opt_table = ibf_dump_param_opt_table(dump, iseq); - dump_body.param.keyword = ibf_dump_param_keyword(dump, iseq); - dump_body.insns_info.body = ibf_dump_insns_info(dump, iseq); - dump_body.local_table = ibf_dump_local_table(dump, iseq); - dump_body.catch_table = ibf_dump_catch_table(dump, iseq); - dump_body.parent_iseq = ibf_dump_iseq(dump, iseq->body->parent_iseq); - dump_body.local_iseq = ibf_dump_iseq(dump, iseq->body->local_iseq); - dump_body.is_entries = NULL; - dump_body.ci_entries = ibf_dump_ci_entries(dump, iseq); - dump_body.cc_entries = NULL; - dump_body.mark_ary = ISEQ_FLIP_CNT(iseq); + dump_body.iseq_encoded = ibf_dump_code(dump, iseq); + dump_body.param.opt_table = ibf_dump_param_opt_table(dump, iseq); + dump_body.param.keyword = ibf_dump_param_keyword(dump, iseq); + dump_body.insns_info.body = ibf_dump_insns_info_body(dump, iseq); + dump_body.insns_info.positions = ibf_dump_insns_info_positions(dump, iseq); + dump_body.local_table = ibf_dump_local_table(dump, iseq); + dump_body.catch_table = ibf_dump_catch_table(dump, iseq); + dump_body.parent_iseq = ibf_dump_iseq(dump, iseq->body->parent_iseq); + dump_body.local_iseq = ibf_dump_iseq(dump, iseq->body->local_iseq); + dump_body.is_entries = NULL; + dump_body.ci_entries = ibf_dump_ci_entries(dump, iseq); + dump_body.cc_entries = NULL; + dump_body.mark_ary = ISEQ_FLIP_CNT(iseq); return ibf_dump_write(dump, &dump_body, sizeof(dump_body)); } @@ -8584,18 +8603,19 @@ ibf_load_iseq_each(const struct ibf_load https://github.com/ruby/ruby/blob/trunk/compile.c#L8603 load_body->location.first_lineno = body->location.first_lineno; load_body->location.code_range = body->location.code_range; - load_body->is_entries = ZALLOC_N(union iseq_inline_storage_entry, body->is_size); - load_body->ci_entries = ibf_load_ci_entries(load, body); - load_body->cc_entries = ZALLOC_N(struct rb_call_cache, body->ci_size + body->ci_kw_size); - load_body->param.opt_table = ibf_load_param_opt_table(load, body); - load_body->param.keyword = ibf_load_param_keyword(load, body); - load_body->insns_info.body = ibf_load_insns_info(load, body); - load_body->local_table = ibf_load_local_table(load, body); - load_body->catch_table = ibf_load_catch_table(load, body); - load_body->parent_iseq = ibf_load_iseq(load, body->parent_iseq); - load_body->local_iseq = ibf_load_iseq(load, body->local_iseq); + load_body->is_entries = ZALLOC_N(union iseq_inline_storage_entry, body->is_size); + load_body->ci_entries = ibf_load_ci_entries(load, body); + load_body->cc_entries = ZALLOC_N(struct rb_call_cache, body->ci_size + body->ci_kw_size); + load_body->param.opt_table = ibf_load_param_opt_table(load, body); + load_body->param.keyword = ibf_load_param_keyword(load, body); + load_body->insns_info.body = ibf_load_insns_info_body(load, body); + load_body->insns_info.positions = ibf_load_insns_info_positions(load, body); + load_body->local_table = ibf_load_local_table(load, body); + load_body->catch_table = ibf_load_catch_table(load, body); + load_body->parent_iseq = ibf_load_iseq(load, body->parent_iseq); + load_body->local_iseq = ibf_load_iseq(load, body->local_iseq); - load_body->iseq_encoded = ibf_load_code(load, iseq, body); + load_body->iseq_encoded = ibf_load_code(load, iseq, body); rb_iseq_translate_threaded_code(iseq); } Index: iseq.c =================================================================== --- iseq.c (revision 61535) +++ iseq.c (revision 61536) @@ -75,6 +75,7 @@ rb_iseq_free(const rb_iseq_t *iseq) https://github.com/ruby/ruby/blob/trunk/iseq.c#L75 if (iseq->body) { ruby_xfree((void *)iseq->body->iseq_encoded); ruby_xfree((void *)iseq->body->insns_info.body); + ruby_xfree((void *)iseq->body->insns_info.positions); ruby_xfree((void *)iseq->body->local_table); ruby_xfree((void *)iseq->body->is_entries); @@ -157,7 +158,7 @@ iseq_memsize(const rb_iseq_t *iseq) https://github.com/ruby/ruby/blob/trunk/iseq.c#L158 size += sizeof(struct rb_iseq_constant_body); size += body->iseq_size * sizeof(VALUE); - size += body->insns_info.size * sizeof(struct iseq_insn_info_entry); + size += body->insns_info.size * (sizeof(struct iseq_insn_info_entry) + sizeof(unsigned int)); size += body->local_table_size * sizeof(ID); if (body->catch_table) { size += iseq_catch_table_bytes(body->catch_table->size); @@ -1256,12 +1257,13 @@ get_insn_info_binary_search(const rb_ise https://github.com/ruby/ruby/blob/trunk/iseq.c#L1257 { size_t size = iseq->body->insns_info.size; const struct iseq_insn_info_entry *insns_info = iseq->body->insns_info.body; + const unsigned int *positions = iseq->body->insns_info.positions; const int debug = 0; if (debug) { printf("size: %"PRIuSIZE"\n", size); printf("insns_info[%"PRIuSIZE"]: position: %d, line: %d, pos: %"PRIuSIZE"\n", - (size_t)0, insns_info[0].position, insns_info[0].line_no, pos); + (size_t)0, positions[0], insns_info[0].line_no, pos); } if (size == 0) { @@ -1274,10 +1276,10 @@ get_insn_info_binary_search(const rb_ise https://github.com/ruby/ruby/blob/trunk/iseq.c#L1276 size_t l = 1, r = size - 1; while (l <= r) { size_t m = l + (r - l) / 2; - if (insns_info[m].position == pos) { + if (positions[m] == pos) { return &insns_info[m]; } - if (insns_info[m].position < pos) { + if (positions[m] < pos) { l = m + 1; } else { @@ -1287,7 +1289,7 @@ get_insn_info_binary_search(const rb_ise https://github.com/ruby/ruby/blob/trunk/iseq.c#L1289 if (l >= size) { return &insns_info[size-1]; } - if (insns_info[l].position > pos) { + if (positions[l] > pos) { return &insns_info[l-1]; } return &insns_info[l]; @@ -1300,12 +1302,13 @@ get_insn_info_linear_search(const rb_ise https://github.com/ruby/ruby/blob/trunk/iseq.c#L1302 { size_t i = 0, size = iseq->body->insns_info.size; const struct iseq_insn_info_entry *insns_info = iseq->body->insns_info.body; + const unsigned int *positions = iseq->body->insns_info.positions; const int debug = 0; if (debug) { printf("size: %"PRIuSIZE"\n", size); printf("insns_info[%"PRIuSIZE"]: position: %d, line: %d, pos: %"PRIuSIZE"\n", - i, insns_info[i].position, insns_info[i].line_no, pos); + i, positions[i], insns_info[i].line_no, pos); } if (size == 0) { @@ -1317,12 +1320,12 @@ get_insn_info_linear_search(const rb_ise https://github.com/ruby/ruby/blob/trunk/iseq.c#L1320 else { for (i=1; i<size; i++) { if (debug) printf("insns_info[%"PRIuSIZE"]: position: %d, line: %d, pos: %"PRIuSIZE"\n", - i, insns_info[i].position, insns_info[i].line_no, pos); + i, positions[i], insns_info[i].line_no, pos); - if (insns_info[i].position == pos) { + if (positions[i] == pos) { return &insns_info[i]; } - if (insns_info[i].position > pos) { + if (positions[i] > pos) { return &insns_info[i-1]; } } @@ -2346,7 +2349,7 @@ iseq_data_to_ary(const rb_iseq_t *iseq) https://github.com/ruby/ruby/blob/trunk/iseq.c#L2349 if (ti < iseq->body->insns_info.size) { const struct iseq_insn_info_entry *info = &iseq->body->insns_info.body[ti]; - if (info->position == pos) { + if (iseq->body->insns_info.positions[ti] == pos) { int line = info->line_no; rb_event_flag_t events = info->events; Index: iseq.h =================================================================== --- iseq.h (revision 61535) +++ iseq.h (revision 61536) @@ -210,7 +210,6 @@ struct rb_compile_option_struct { https://github.com/ruby/ruby/blob/trunk/iseq.h#L210 }; struct iseq_insn_info_entry { - unsigned int position; int line_no; rb_event_flag_t events; }; -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/