From b575b934d80216969543535b0a05ffaab8ea030b Mon Sep 17 00:00:00 2001 From: shyouhei Date: Thu, 27 Apr 2017 04:21:04 +0000 Subject: refactor newhash (revision 58463 another try) [fix GH-1600] * st.c (rb_hash_bulk_insert): new API to bulk insert entries into a hash. Given arguments are first inserted into the table at once, then reindexed. This is faster than inserting things using rb_hash_aset() one by one. This arrangement (rb_ prefixed function placed in st.c) is unavoidable because it both touches table internal and write barrier at once. * internal.h: delcare the new function. * hash.c (rb_hash_s_create): use the new function. * vm.c (core_hash_merge): ditto. * insns.def (newhash): ditto. * test/ruby/test_hash.rb: more coverage on hash creation. * test/ruby/test_literal.rb: ditto. ----------------------------------------------------------- benchmark results: minimum results in each 7 measurements. Execution time (sec) name before after loop_whileloop2 0.136 0.137 vm2_bighash* 1.249 0.623 Speedup ratio: compare with the result of `before' (greater is better) name after loop_whileloop2 0.996 vm2_bighash* 2.004 git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@58492 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- st.c | 165 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 165 insertions(+) (limited to 'st.c') diff --git a/st.c b/st.c index 528c528572..a8c9a44096 100644 --- a/st.c +++ b/st.c @@ -1955,3 +1955,168 @@ st_numhash(st_data_t n) enum {s1 = 11, s2 = 3}; return (st_index_t)((n>>s1|(n<>s2)); } + +/* Expand TAB to be suitable for holding SIZ entries in total. + Pre-existing entries remain not deleted inside of TAB, but its bins + are cleared to expect future reconstruction. See rehash below. */ +static void +st_expand_table(st_table *tab, st_index_t siz) +{ + st_table *tmp; + st_index_t n; + + if (siz <= get_allocated_entries(tab)) + return; /* enough room already */ + + tmp = st_init_table_with_size(tab->type, siz); + n = get_allocated_entries(tab); + MEMCPY(tmp->entries, tab->entries, st_table_entry, n); + free(tab->entries); + if (tab->bins != NULL) + free(tab->bins); + if (tmp->bins != NULL) + free(tmp->bins); + tab->entry_power = tmp->entry_power; + tab->bin_power = tmp->bin_power; + tab->size_ind = tmp->size_ind; + tab->entries = tmp->entries; + tab->bins = NULL; + tab->rebuilds_num++; + free(tmp); +} + +/* Rehash using linear search. */ +static void +st_rehash_linear(st_table *tab) +{ + st_index_t i, j; + st_table_entry *p, *q; + if (tab->bins) { + free(tab->bins); + tab->bins = NULL; + } + for (i = tab->entries_start; i < tab->entries_bound; i++) { + p = &tab->entries[i]; + if (DELETED_ENTRY_P(p)) + continue; + for (j = i + 1; j < tab->entries_bound; j++) { + q = &tab->entries[j]; + if (DELETED_ENTRY_P(q)) + continue; + if (PTR_EQUAL(tab, p, q->hash, q->key)) { + st_assert(p < q); + *p = *q; + MARK_ENTRY_DELETED(q); + tab->num_entries--; + update_range_for_deleted(tab, j); + } + } + } +} + +/* Rehash using index */ +static void +st_rehash_indexed(st_table *tab) +{ + st_index_t i; + st_index_t const n = bins_size(tab); + unsigned int const size_ind = get_size_ind(tab); + st_index_t *bins = realloc(tab->bins, n); + st_assert(bins != NULL); + tab->bins = bins; + initialize_bins(tab); + for (i = tab->entries_start; i < tab->entries_bound; i++) { + st_table_entry *p = &tab->entries[i]; + st_index_t ind; +#ifdef QUADRATIC_PROBE + st_index_t d = 1; +#else + st_index_t peterb = p->hash; +#endif + + if (DELETED_ENTRY_P(p)) + continue; + + ind = hash_bin(p->hash, tab); + for(;;) { + st_index_t bin = get_bin(bins, size_ind, ind); + st_table_entry *q = &tab->entries[bin - ENTRY_BASE]; + if (EMPTY_OR_DELETED_BIN_P(bin)) { + /* ok, new room */ + set_bin(bins, size_ind, ind, i + ENTRY_BASE); + break; + } + else if (PTR_EQUAL(tab, q, p->hash, p->key)) { + /* duplicated key; delete it */ + st_assert(q < p); + q->record = p->record; + MARK_ENTRY_DELETED(p); + tab->num_entries--; + update_range_for_deleted(tab, bin); + break; + } + else { + /* hash collision; skip it */ +#ifdef QUADRATIC_PROBE + ind = hash_bin(ind + d, tab); + d++; +#else + ind = secondary_hash(ind, tab, &peterb); +#endif + } + } + } +} + +/* Reconstruct TAB's bins according to TAB's entries. This function + permits conflicting keys inside of entries. No errors are reported + then. All but one of them are discarded silently. */ +static void +st_rehash(st_table *tab) +{ + if (tab->bin_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS) + st_rehash_linear(tab); + else + st_rehash_indexed(tab); +} + +#ifdef RUBY +/* Mimics ruby's { foo => bar } syntax. This function is placed here + because it touches table internals and write barriers at once. */ +void +rb_hash_bulk_insert(long argc, const VALUE *argv, VALUE hash) +{ + int i; + st_table *tab; + + st_assert(argc % 2); + if (! argc) + return; + if (! RHASH(hash)->ntbl) + rb_hash_tbl_raw(hash); + tab = RHASH(hash)->ntbl; + + /* make room */ + st_expand_table(tab, tab->num_entries + argc); + + /* push elems */ + for (i = 0; i < argc; /* */) { + VALUE key = argv[i++]; + VALUE val = argv[i++]; + st_data_t k = (rb_obj_class(key) == rb_cString) ? + rb_str_new_frozen(key) : key; + st_table_entry e; + e.hash = do_hash(k, tab); + e.key = k; + e.record = val; + + tab->entries[tab->entries_bound++] = e; + tab->num_entries++; + RB_OBJ_WRITTEN(hash, Qundef, k); + RB_OBJ_WRITTEN(hash, Qundef, val); + } + + /* reindex */ + st_rehash(tab); +} +#endif -- cgit v1.2.3