aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorshyouhei <shyouhei@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2017-09-05 04:49:01 +0000
committershyouhei <shyouhei@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2017-09-05 04:49:01 +0000
commit1db01c19d01afda88155734627000b3c56c54798 (patch)
tree66a0f1642b67696014252506f24642ec34a9c4b2
parent9380f3b62a53fb84cae0fa505be64dec9b94d8ce (diff)
downloadruby-1db01c19d01afda88155734627000b3c56c54798.tar.gz
optimize rb_hash_bulk_insert to generally outperform 2.4.
Specialized routine for small linear-probling hash instances to boost creation of such things [Bug #13861] Signed-off-by: Urabe, Shyouhei <shyouhei@ruby-lang.org> git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@59746 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r--st.c92
1 files changed, 67 insertions, 25 deletions
diff --git a/st.c b/st.c
index dd45912899..f4ae0e8387 100644
--- a/st.c
+++ b/st.c
@@ -2102,42 +2102,84 @@ st_rehash(st_table *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)
+static st_data_t
+st_stringify(VALUE key)
{
- int i;
- st_table *tab;
+ return (rb_obj_class(key) == rb_cString) ?
+ rb_str_new_frozen(key) : key;
+}
- st_assert(argc % 2);
- if (! argc)
- return;
- if (! RHASH(hash)->ntbl)
- rb_hash_tbl_raw(hash);
- tab = RHASH(hash)->ntbl;
+static void
+st_insert_single(st_table *tab, VALUE hash, VALUE key, VALUE val)
+{
+ st_data_t k = st_stringify(key);
+ st_table_entry e;
+ e.hash = do_hash(k, tab);
+ e.key = k;
+ e.record = val;
- /* make room */
- st_expand_table(tab, tab->num_entries + argc);
+ tab->entries[tab->entries_bound++] = e;
+ tab->num_entries++;
+ RB_OBJ_WRITTEN(hash, Qundef, k);
+ RB_OBJ_WRITTEN(hash, Qundef, val);
+}
+
+static void
+st_insert_linear(st_table *tab, long argc, const VALUE *argv, VALUE hash)
+{
+ long i;
+
+ for (i = 0; i < argc; /* */) {
+ st_data_t k = st_stringify(argv[i++]);
+ st_data_t v = argv[i++];
+ st_insert(tab, k, v);
+ RB_OBJ_WRITTEN(hash, Qundef, k);
+ RB_OBJ_WRITTEN(hash, Qundef, v);
+ }
+}
+
+static void
+st_insert_generic(st_table *tab, long argc, const VALUE *argv, VALUE hash)
+{
+ int i;
/* 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);
+ st_insert_single(tab, hash, key, val);
}
/* reindex */
st_rehash(tab);
}
+
+/* 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)
+{
+ st_index_t n;
+ st_table *tab = RHASH(hash)->ntbl;
+
+ st_assert(argc % 2);
+ if (! argc)
+ return;
+ if (! tab) {
+ VALUE tmp = rb_hash_new_with_size(argc / 2);
+ RBASIC_CLEAR_CLASS(tmp);
+ RHASH(hash)->ntbl = tab = RHASH(tmp)->ntbl;
+ RHASH(tmp)->ntbl = NULL;
+ }
+ n = tab->num_entries + argc / 2;
+ st_expand_table(tab, n);
+ if (UNLIKELY(tab->num_entries))
+ st_insert_generic(tab, argc, argv, hash);
+ else if (argc <= 2)
+ st_insert_single(tab, hash, argv[0], argv[1]);
+ else if (tab->bin_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS)
+ st_insert_linear(tab, argc, argv, hash);
+ else
+ st_insert_generic(tab, argc, argv, hash);
+}
#endif