ruby-changes:49623
From: mame <ko1@a...>
Date: Tue, 9 Jan 2018 23:05:32 +0900 (JST)
Subject: [ruby-changes:49623] mame:r61739 (trunk): iseq.c: Add a succinct bitvector implementation for insn_info_table
mame 2018-01-09 23:05:23 +0900 (Tue, 09 Jan 2018) New Revision: 61739 https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=61739 Log: iseq.c: Add a succinct bitvector implementation for insn_info_table Modified files: trunk/compile.c trunk/iseq.c trunk/iseq.h trunk/vm_core.h Index: iseq.c =================================================================== --- iseq.c (revision 61738) +++ iseq.c (revision 61739) @@ -31,6 +31,12 @@ VALUE rb_cISeq; https://github.com/ruby/ruby/blob/trunk/iseq.c#L31 static VALUE iseqw_new(const rb_iseq_t *iseq); static const rb_iseq_t *iseqw_check(VALUE iseqw); +#if VM_INSN_INFO_TABLE_IMPL == 2 +static struct succ_index_table *succ_index_table_create(int max_pos, int *data, int size); +static unsigned int *succ_index_table_invert(int max_pos, struct succ_index_table *sd, int size); +static int succ_index_lookup(const struct succ_index_table *sd, int x); +#endif + #define hidden_obj_p(obj) (!SPECIAL_CONST_P(obj) && !RBASIC(obj)->klass) static inline VALUE @@ -76,7 +82,10 @@ rb_iseq_free(const rb_iseq_t *iseq) https://github.com/ruby/ruby/blob/trunk/iseq.c#L82 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); + if (iseq->body->insns_info.positions) ruby_xfree((void *)iseq->body->insns_info.positions); +#if VM_INSN_INFO_TABLE_IMPL == 2 + if (iseq->body->insns_info.succ_index_table) ruby_xfree(iseq->body->insns_info.succ_index_table); +#endif ruby_xfree((void *)iseq->body->local_table); ruby_xfree((void *)iseq->body->is_entries); @@ -351,6 +360,34 @@ prepare_iseq_build(rb_iseq_t *iseq, https://github.com/ruby/ruby/blob/trunk/iseq.c#L360 static void validate_get_insn_info(rb_iseq_t *iseq); #endif +void +rb_iseq_insns_info_encode_positions(const rb_iseq_t *iseq) +{ +#if VM_INSN_INFO_TABLE_IMPL == 2 + int size = iseq->body->insns_info.size; + int max_pos = iseq->body->iseq_size; + int *data = (int *)iseq->body->insns_info.positions; + if (iseq->body->insns_info.succ_index_table) ruby_xfree(iseq->body->insns_info.succ_index_table); + iseq->body->insns_info.succ_index_table = succ_index_table_create(max_pos, data, size); +#if VM_CHECK_MODE == 0 + ruby_xfree(iseq->body->insns_info.positions); + iseq->body->insns_info.positions = NULL; +#endif +#endif +} + +void +rb_iseq_insns_info_decode_positions(const rb_iseq_t *iseq) +{ +#if VM_INSN_INFO_TABLE_IMPL == 2 + int size = iseq->body->insns_info.size; + int max_pos = iseq->body->iseq_size; + struct succ_index_table *sd = iseq->body->insns_info.succ_index_table; + if (iseq->body->insns_info.positions) ruby_xfree(iseq->body->insns_info.positions); + iseq->body->insns_info.positions = succ_index_table_invert(max_pos, sd, size); +#endif +} + static VALUE finish_iseq_build(rb_iseq_t *iseq) { @@ -359,6 +396,13 @@ finish_iseq_build(rb_iseq_t *iseq) https://github.com/ruby/ruby/blob/trunk/iseq.c#L396 ISEQ_COMPILE_DATA_CLEAR(iseq); compile_data_free(data); +#if VM_INSN_INFO_TABLE_IMPL == 2 /* succinct bitvector */ + /* create succ_index_table */ + if (iseq->body->insns_info.succ_index_table == NULL) { + rb_iseq_insns_info_encode_positions(iseq); + } +#endif + #if VM_CHECK_MODE > 0 && VM_INSN_INFO_TABLE_IMPL > 0 validate_get_insn_info(iseq); #endif @@ -1326,6 +1370,42 @@ get_insn_info(const rb_iseq_t *iseq, siz https://github.com/ruby/ruby/blob/trunk/iseq.c#L1370 } #endif +#if VM_INSN_INFO_TABLE_IMPL == 2 /* succinct bitvector */ +static const struct iseq_insn_info_entry * +get_insn_info_succinct_bitvector(const rb_iseq_t *iseq, size_t pos) +{ + 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, positions[0], insns_info[0].line_no, pos); + } + + if (size == 0) { + return NULL; + } + else if (size == 1) { + return &insns_info[0]; + } + else { + int index; + VM_ASSERT(iseq->body->insns_info.succ_index_table != NULL); + index = succ_index_lookup(iseq->body->insns_info.succ_index_table, (int)pos); + return &insns_info[index-1]; + } +} + +static const struct iseq_insn_info_entry * +get_insn_info(const rb_iseq_t *iseq, size_t pos) +{ + return get_insn_info_succinct_bitvector(iseq, pos); +} +#endif + #if VM_CHECK_MODE > 0 || VM_INSN_INFO_TABLE_IMPL == 0 static const struct iseq_insn_info_entry * get_insn_info_linear_search(const rb_iseq_t *iseq, size_t pos) @@ -2715,6 +2795,138 @@ iseqw_s_load_from_binary_extra_data(VALU https://github.com/ruby/ruby/blob/trunk/iseq.c#L2795 return iseq_ibf_load_extra_data(str); } +#if VM_INSN_INFO_TABLE_IMPL == 2 + +/* An implementation of succinct bit-vector for insn_info table. + * + * A succinct bit-vector is a small and efficient data structure that provides + * a bit-vector augmented with an index for O(1) rank operation: + * + * rank(bv, n): the number of 1's within a range from index 0 to index n + * + * This can be used to lookup insn_info table from PC. + * For example, consider the following iseq and insn_info_table: + * + * iseq insn_info_table + * PC insn+operand position lineno event + * 0: insn1 0: 1 [Li] + * 2: insn2 2: 2 [Li] <= (A) + * 5: insn3 8: 3 [Li] <= (B) + * 8: insn4 + * + * In this case, a succinct bit-vector whose indexes 0, 2, 8 is "1" and + * other indexes is "0", i.e., "101000001", is created. + * To lookup the lineno of insn2, calculate rank("10100001", 2) = 2, so + * the line (A) is the entry in question. + * To lookup the lineno of insn4, calculate rank("10100001", 8) = 3, so + * the line (B) is the entry in question. + * + * A naive implementatoin of succinct bit-vector works really well + * not only for large size but also for small size. However, it has + * tiny overhead for very small size. So, this implementation consist + * of two parts: one part is the "immediate" table that keeps rank result + * as a raw table, and the other part is a normal succinct bit-vector. + */ + +#define IMMEDIATE_TABLE_SIZE 54 /* a multiple of 9, and < 128 */ + +struct succ_index_table { + uint64_t imm_part[IMMEDIATE_TABLE_SIZE / 9]; + struct succ_dict_block { + unsigned int rank; + uint64_t small_block_ranks; /* 9 bits * 7 = 63 bits */ + uint64_t bits[512/64]; + } succ_part[]; +} succ_index_table; + +#define imm_block_rank_set(v, i, r) (v) |= (uint64_t)(r) << (7 * (i)) +#define imm_block_rank_get(v, i) (((v) & 0x7fL << (i) * 7) >> ((i) * 7)) +#define small_block_rank_set(v, i, r) (v) |= (uint64_t)(r) << (9 * ((i) - 1)) +#define small_block_rank_get(v, i) ((i) == 0 ? 0 : ((v) & 0x1ffL << ((i) - 1) * 9) >> (((i) - 1) * 9)) + +static struct succ_index_table * +succ_index_table_create(int max_pos, int *data, int size) +{ + const int imm_size = (max_pos < IMMEDIATE_TABLE_SIZE ? max_pos + 8 : IMMEDIATE_TABLE_SIZE) / 9; + const int succ_size = (max_pos < IMMEDIATE_TABLE_SIZE ? 0 : (max_pos - IMMEDIATE_TABLE_SIZE + 511)) / 512; + struct succ_index_table *sd = ruby_xcalloc(imm_size * sizeof(uint64_t) + succ_size * sizeof(struct succ_dict_block), 1); /* zero cleared */ + int i, j, k, r; + + r = 0; + for (j = 0; j < imm_size; j++) { + for (i = 0; i < 9; i++) { + if (r < size && data[r] == j * 9 + i) r++; + imm_block_rank_set(sd->imm_part[j], i, r); + } + } + for (k = 0; k < succ_size; k++) { + struct succ_dict_block *sd_block = &sd->succ_part[k]; + int small_rank = 0; + sd_block->rank = r; + for (j = 0; j < 8; j++) { + uint64_t bits = 0; + if (j) small_block_rank_set(sd_block->small_block_ranks, j, small_rank); + for (i = 0; i < 64; i++) { + if (r < size && data[r] == k * 512 + j * 64 + i + IMMEDIATE_TABLE_SIZE) { + bits |= 1L << i; + r++; + } + } + sd_block->bits[j] = bits; + small_rank += rb_popcount64(bits); + } + } + return sd; +} + +static unsigned int * +succ_index_table_invert(int max_pos, struct succ_index_table *sd, int size) +{ + const int imm_size = (max_pos < IMMEDIATE_TABLE_SIZE ? max_pos + 8 : IMMEDIATE_TABLE_SIZE) / 9; + const int succ_size = (max_pos < IMMEDIATE_TABLE_SIZE ? 0 : (max_pos - IMMEDIATE_TABLE_SIZE + 511)) / 512; + unsigned int *positions = ruby_xmalloc(sizeof(unsigned int) * size), *p; + int i, j, k, r = -1; + p = positions; + for (j = 0; j < imm_size; j++) { + for (i = 0; i < 9; i++) { + int nr = imm_block_rank_get(sd->imm_part[j], i); + if (r != nr) *p++ = j * 9 + i; + r = nr; + } + } + for (k = 0; k < succ_size; k++) { + for (j = 0; j < 8; j++) { + for (i = 0; i < 64; i++) { + if (sd->succ_part[k].bits[j] & (1L << i)) { + *p++ = k * 512 + j * 64 + i + IMMEDIATE_TABLE_SIZE; + } + } + } + } + return positions; +} + +static int +succ_index_lookup(const struct succ_index_table *sd, int x) +{ + if (x < IMMEDIATE_TABLE_SIZE) { + const int i = x / 9; + const int j = x % 9; + return imm_block_rank_get(sd->imm_part[i], j); + } + else { + const int block_index = (x - IMMEDIATE_TABLE_SIZE) / 512; + const struct succ_dict_block *block = &sd->succ_part[block_index]; + const int block_bit_index = (x - IMMEDIATE_TABLE_SIZE) % 512; + const int small_block_index = block_bit_index / 64; + const int small_block_popcount = small_block_rank_get(block->small_block_ranks, small_block_index); + const int popcnt = rb_popcount64(block->bits[small_block_index] << (63 - block_bit_index % 64)); + + return block->rank + small_block_popcount + popcnt; + } +} +#endif + /* * Document-class: RubyVM::InstructionSequence * Index: iseq.h =================================================================== --- iseq.h (revision 61738) +++ iseq.h (revision 61739) @@ -181,6 +181,8 @@ unsigned int rb_iseq_line_no(const rb_is https://github.com/ruby/ruby/blob/trunk/iseq.h#L181 void rb_iseq_trace_set(const rb_iseq_t *iseq, rb_event_flag_t turnon_events); void rb_iseq_trace_set_all(rb_event_flag_t turnon_events); void rb_iseq_trace_on_all(void); +void rb_iseq_insns_info_encode_positions(const rb_iseq_t *iseq); +void rb_iseq_insns_info_decode_positions(const rb_iseq_t *iseq); VALUE rb_iseqw_new(const rb_iseq_t *iseq); const rb_iseq_t *rb_iseqw_to_iseq(VALUE iseqw); Index: vm_core.h =================================================================== --- vm_core.h (revision 61738) +++ vm_core.h (revision 61739) @@ -60,8 +60,11 @@ https://github.com/ruby/ruby/blob/trunk/vm_core.h#L60 * implementation selector of get_insn_info algorithm * 0: linear search * 1: binary search + * 2: succinct bitvector */ -#define VM_INSN_INFO_TABLE_IMPL 1 +#ifndef VM_INSN_INFO_TABLE_IMPL +# define VM_INSN_INFO_TABLE_IMPL 2 +#endif #include "ruby/ruby.h" #include "ruby/st.h" @@ -380,8 +383,11 @@ struct rb_iseq_constant_body { https://github.com/ruby/ruby/blob/trunk/vm_core.h#L383 /* insn info, must be freed */ struct iseq_insn_info { const struct iseq_insn_info_entry *body; - const unsigned int *positions; + unsigned int *positions; unsigned int size; +#if VM_INSN_INFO_TABLE_IMPL == 2 + struct succ_index_table *succ_index_table; +#endif } insns_info; const ID *local_table; /* must free */ Index: compile.c =================================================================== --- compile.c (revision 61738) +++ compile.c (revision 61739) @@ -8627,7 +8627,13 @@ ibf_dump_iseq_each(struct ibf_dump *dump https://github.com/ruby/ruby/blob/trunk/compile.c#L8627 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); +#if VM_INSN_INFO_TABLE_IMPL == 2 + rb_iseq_insns_info_decode_positions(iseq); +#endif dump_body.insns_info.positions = ibf_dump_insns_info_positions(dump, iseq); +#if VM_INSN_INFO_TABLE_IMPL == 2 + rb_iseq_insns_info_encode_positions(iseq); +#endif 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); @@ -8700,6 +8706,9 @@ ibf_load_iseq_each(const struct ibf_load https://github.com/ruby/ruby/blob/trunk/compile.c#L8706 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); +#if VM_INSN_INFO_TABLE_IMPL == 2 + rb_iseq_insns_info_encode_positions(iseq); +#endif 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); -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/