summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ChangeLog16
-rw-r--r--NEWS6
-rw-r--r--benchmark/bm_hash_aref_miss.rb5
-rw-r--r--benchmark/bm_hash_aref_str.rb4
-rw-r--r--benchmark/bm_hash_aref_sym.rb4
-rw-r--r--benchmark/bm_hash_aref_sym_long.rb8
-rw-r--r--benchmark/bm_hash_ident_num.rb4
-rw-r--r--benchmark/bm_hash_ident_obj.rb4
-rw-r--r--benchmark/bm_hash_ident_str.rb4
-rw-r--r--benchmark/bm_hash_ident_sym.rb4
-rw-r--r--hash.c1
-rw-r--r--st.c74
12 files changed, 77 insertions, 57 deletions
diff --git a/ChangeLog b/ChangeLog
index 45a5ad9..8a230d4 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+Sun Mar 23 08:12:27 2014 Eric Wong <e@80x24.org>
+
+ * st.c (hash_pos): use bitwise AND to avoid slow modulo op
+ (new_size): power-of-two sizes for hash_pos change
+ (st_numhash): adjust for common keys due to lack of prime modulo
+ [Feature #9425]
+ * hash.c (rb_any_hash): right shift for symbols
+ * benchmark/bm_hash_aref_miss.rb: added to show improvement
+ * benchmark/bm_hash_aref_sym_long.rb: ditto
+ * benchmark/bm_hash_aref_str.rb: ditto
+ * benchmark/bm_hash_aref_sym.rb: ditto
+ * benchmark/bm_hash_ident_num.rb: added to prevent regression
+ * benchmark/bm_hash_ident_obj.rb: ditto
+ * benchmark/bm_hash_ident_str.rb: ditto
+ * benchmark/bm_hash_ident_sym.rb: ditto
+
Sat Mar 22 22:56:45 2014 NARUSE, Yui <naruse@ruby-lang.org>
* addr2line.c (fill_lines): compare the file names of object in which
diff --git a/NEWS b/NEWS
index 753ebd8..0214298 100644
--- a/NEWS
+++ b/NEWS
@@ -84,3 +84,9 @@ with all sufficient information, see the ChangeLog file.
* struct RBignum is hidden. [Feature #6083]
Use rb_integer_pack and rb_integer_unpack instead.
+
+* st hash table uses power-of-two sizes for speed [Feature #9425].
+ Lookups are 10-25% faster if using appropriate hash functions.
+ However, weaknesses in hash distribution can no longer be masked
+ by prime number-sized tables, so extensions may need to tweak
+ hash functions to ensure good distribution.
diff --git a/benchmark/bm_hash_aref_miss.rb b/benchmark/bm_hash_aref_miss.rb
new file mode 100644
index 0000000..b0913dd
--- /dev/null
+++ b/benchmark/bm_hash_aref_miss.rb
@@ -0,0 +1,5 @@
+h = {}
+strs = ('a'..'z').to_a.map!(&:freeze)
+strs.each { |s| h[s] = s }
+strs = ('A'..'Z').to_a
+200_000.times { strs.each { |s| h[s] } }
diff --git a/benchmark/bm_hash_aref_str.rb b/benchmark/bm_hash_aref_str.rb
new file mode 100644
index 0000000..19439b0
--- /dev/null
+++ b/benchmark/bm_hash_aref_str.rb
@@ -0,0 +1,4 @@
+h = {}
+strs = ('a'..'z').to_a.map!(&:freeze)
+strs.each { |s| h[s] = s }
+200_000.times { strs.each { |s| h[s] } }
diff --git a/benchmark/bm_hash_aref_sym.rb b/benchmark/bm_hash_aref_sym.rb
new file mode 100644
index 0000000..54298ff
--- /dev/null
+++ b/benchmark/bm_hash_aref_sym.rb
@@ -0,0 +1,4 @@
+h = {}
+syms = ('a'..'z').to_a.map(&:to_sym)
+syms.each { |s| h[s] = s }
+200_000.times { syms.each { |s| h[s] } }
diff --git a/benchmark/bm_hash_aref_sym_long.rb b/benchmark/bm_hash_aref_sym_long.rb
new file mode 100644
index 0000000..a9be405
--- /dev/null
+++ b/benchmark/bm_hash_aref_sym_long.rb
@@ -0,0 +1,8 @@
+h = {}
+syms = %w[puts warn syswrite write stat bacon lettuce tomato
+some symbols in this array may already be interned others should not be
+hash browns make good breakfast but not cooked using prime numbers
+shift for division entries delete_if keys exist?
+].map!(&:to_sym)
+syms.each { |s| h[s] = s }
+200_000.times { syms.each { |s| h[s] } }
diff --git a/benchmark/bm_hash_ident_num.rb b/benchmark/bm_hash_ident_num.rb
new file mode 100644
index 0000000..b226736
--- /dev/null
+++ b/benchmark/bm_hash_ident_num.rb
@@ -0,0 +1,4 @@
+h = {}.compare_by_identity
+nums = (1..26).to_a
+nums.each { |n| h[n] = n }
+200_000.times { nums.each { |n| h[n] } }
diff --git a/benchmark/bm_hash_ident_obj.rb b/benchmark/bm_hash_ident_obj.rb
new file mode 100644
index 0000000..4b3b58e
--- /dev/null
+++ b/benchmark/bm_hash_ident_obj.rb
@@ -0,0 +1,4 @@
+h = {}.compare_by_identity
+objs = 26.times.map { Object.new }
+objs.each { |o| h[o] = o }
+200_000.times { objs.each { |o| h[o] } }
diff --git a/benchmark/bm_hash_ident_str.rb b/benchmark/bm_hash_ident_str.rb
new file mode 100644
index 0000000..8582b38
--- /dev/null
+++ b/benchmark/bm_hash_ident_str.rb
@@ -0,0 +1,4 @@
+h = {}.compare_by_identity
+strs = ('a'..'z').to_a
+strs.each { |s| h[s] = s }
+200_000.times { strs.each { |s| h[s] } }
diff --git a/benchmark/bm_hash_ident_sym.rb b/benchmark/bm_hash_ident_sym.rb
new file mode 100644
index 0000000..4c81e3d
--- /dev/null
+++ b/benchmark/bm_hash_ident_sym.rb
@@ -0,0 +1,4 @@
+h = {}.compare_by_identity
+syms = ('a'..'z').to_a.map(&:to_sym)
+syms.each { |s| h[s] = s }
+200_000.times { syms.each { |s| h[s] } }
diff --git a/hash.c b/hash.c
index 0023e84..56917ed 100644
--- a/hash.c
+++ b/hash.c
@@ -132,6 +132,7 @@ rb_any_hash(VALUE a)
if (SPECIAL_CONST_P(a)) {
if (a == Qundef) return 0;
+ if (SYMBOL_P(a)) a >>= (RUBY_SPECIAL_SHIFT + 3); /* 3=ID_SCOPE_SHIFT */
hnum = rb_objid_hash((st_index_t)a);
}
else if (BUILTIN_TYPE(a) == T_STRING) {
diff --git a/st.c b/st.c
index 5943982..5a0b62a 100644
--- a/st.c
+++ b/st.c
@@ -33,8 +33,7 @@ typedef struct st_packed_entry {
#define STATIC_ASSERT(name, expr) typedef int static_assert_##name##_check[(expr) ? 1 : -1];
#define ST_DEFAULT_MAX_DENSITY 5
-#define ST_DEFAULT_INIT_TABLE_SIZE 11
-#define ST_DEFAULT_SECOND_TABLE_SIZE 19
+#define ST_DEFAULT_INIT_TABLE_SIZE 16
#define ST_DEFAULT_PACKED_TABLE_SIZE 18
#define PACKED_UNIT (int)(sizeof(st_packed_entry) / sizeof(st_table_entry*))
#define MAX_PACKED_HASH (int)(ST_DEFAULT_PACKED_TABLE_SIZE * sizeof(st_table_entry*) / sizeof(st_packed_entry))
@@ -85,7 +84,7 @@ static void rehash(st_table *);
#define EQUAL(table,x,y) ((x)==(y) || (*(table)->type->compare)((x),(y)) == 0)
#define do_hash(key,table) (st_index_t)(*(table)->type->hash)((key))
-#define hash_pos(h,n) ((h) % (n))
+#define hash_pos(h,n) ((h) & (n - 1))
#define do_hash_bin(key,table) hash_pos(do_hash((key), (table)), (table)->num_bins)
/* preparation for possible allocation improvements */
@@ -140,69 +139,18 @@ remove_safe_packed_entry(st_table *table, st_index_t i, st_data_t never)
PHASH_SET(table, i, 0);
}
-/*
- * MINSIZE is the minimum size of a dictionary.
- */
-
-#define MINSIZE 8
-
-/*
-Table of prime numbers 2^n+a, 2<=n<=30.
-*/
-static const unsigned int primes[] = {
- ST_DEFAULT_INIT_TABLE_SIZE,
- ST_DEFAULT_SECOND_TABLE_SIZE,
- 32 + 5,
- 64 + 3,
- 128 + 3,
- 256 + 27,
- 512 + 9,
- 1024 + 9,
- 2048 + 5,
- 4096 + 3,
- 8192 + 27,
- 16384 + 43,
- 32768 + 3,
- 65536 + 45,
- 131072 + 29,
- 262144 + 3,
- 524288 + 21,
- 1048576 + 7,
- 2097152 + 17,
- 4194304 + 15,
- 8388608 + 9,
- 16777216 + 43,
- 33554432 + 35,
- 67108864 + 15,
- 134217728 + 29,
- 268435456 + 3,
- 536870912 + 11,
- 1073741824 + 85,
- 0
-};
-
static st_index_t
new_size(st_index_t size)
{
- int i;
+ st_index_t i;
-#if 0
for (i=3; i<31; i++) {
- if ((1<<i) > size) return 1<<i;
- }
- return -1;
-#else
- st_index_t newsize;
-
- for (i = 0, newsize = MINSIZE; i < numberof(primes); i++, newsize <<= 1) {
- if (newsize > size) return primes[i];
+ if ((st_index_t)(1<<i) > size) return 1<<i;
}
- /* Ran out of primes */
#ifndef NOT_RUBY
rb_raise(rb_eRuntimeError, "st_table too big");
#endif
return -1; /* should raise exception */
-#endif
}
#ifdef HASH_LOG
@@ -1685,5 +1633,17 @@ st_numcmp(st_data_t x, st_data_t y)
st_index_t
st_numhash(st_data_t n)
{
- return (st_index_t)n;
+ /*
+ * This hash function is lightly-tuned for Ruby. Further tuning
+ * should be possible. Notes:
+ *
+ * - (n >> 3) alone is great for heap objects and OK for fixnum,
+ * however symbols perform poorly.
+ * - (n >> (RUBY_SPECIAL_SHIFT+3)) was added to make symbols hash well,
+ * n.b.: +3 to remove ID scope, +1 worked well initially, too
+ * - (n << 3) was finally added to avoid losing bits for fixnums
+ * - avoid expensive modulo instructions, it is currently only
+ * shifts and bitmask operations.
+ */
+ return (st_index_t)((n>>(RUBY_SPECIAL_SHIFT+3)|(n<<3)) ^ (n>>3));
}