[ruby-core:72046] Re: [Ruby trunk - Feature #11405] [Assigned] [PATCH] hash.c: minor speedups to int/fixnum keys

Eric Wong <[e-mail]> wrote:
> [e-mail] wrote:
> > This caused a lot of trivial hash conflicts of Fixnums that is >= 16384.
> 
> Thanks for noticing, I will investigate.

Work-in-progress:

http://80x24.org/spew/20151211014045.19614-1-e%4080x24.org/raw

Subject: [PATCH v2] hash.c (rb_num_hash_start): avoid pathological behavior

The OR-ing itself is bad for a hash function, and shifting 3 bits
left was not enough to undo the damage done by shifting
(RUBY_SPECIAL_SHIFT+3) bits right.  Experimentally, shifting 16-17
bits seemed to work well in preparing the number for murmur hash.

Add a few more benchmarks to based on bm_hash_shift to ensure
we don't hurt performance too much with tweaks.

[ruby-core:72028] [Feature #11405]

target 0: a (ruby 2.3.0dev (2015-12-11 trunk 53027) [x86_64-linux]) at "/home/ew/rrrr/b/ruby"
target 1: b (ruby 2.3.0dev (2015-12-11 master 53027) [x86_64-linux]) at "/home/ew/ruby/b/ruby"

benchmark results:
minimum results in each 5 measurements.
Execution time (sec)
name	a	b
hash_aref_dsym	0.279	0.276
hash_aref_dsym_long	4.951	4.936
hash_aref_fix	0.281	0.283
hash_aref_flo	0.060	0.060
hash_aref_miss	0.409	0.410
hash_aref_str	0.387	0.385
hash_aref_sym	0.275	0.270
hash_aref_sym_long	0.410	0.411
hash_flatten	0.252	0.237
hash_ident_flo	0.035	0.032
hash_ident_num	0.254	0.251
hash_ident_obj	0.252	0.256
hash_ident_str	0.250	0.252
hash_ident_sym	0.259	0.270
hash_keys	0.267	0.267
hash_shift	0.016	0.015
hash_shift_u16	0.074	0.072
hash_shift_u24	0.071	0.071
hash_shift_u32	0.073	0.072
hash_to_proc	0.008	0.008
hash_values	0.263	0.264

Speedup ratio: compare with the result of `a' (greater is better)
name	b
hash_aref_dsym	1.009
hash_aref_dsym_long	1.003
hash_aref_fix	0.993
hash_aref_flo	1.001
hash_aref_miss	0.996
hash_aref_str	1.006
hash_aref_sym	1.017
hash_aref_sym_long	0.998
hash_flatten	1.061
hash_ident_flo	1.072
hash_ident_num	1.012
hash_ident_obj	0.987
hash_ident_str	0.993
hash_ident_sym	0.959
hash_keys	0.997
hash_shift	1.036
hash_shift_u16	1.039
hash_shift_u24	1.001
hash_shift_u32	1.017
hash_to_proc	1.001
hash_values	0.995
---
 benchmark/bm_hash_shift_u16.rb | 10 ++++++++++
 benchmark/bm_hash_shift_u24.rb | 10 ++++++++++
 benchmark/bm_hash_shift_u32.rb | 10 ++++++++++
 hash.c                         |  4 ++--
 4 files changed, 32 insertions(+), 2 deletions(-)
 create mode 100644 benchmark/bm_hash_shift_u16.rb
 create mode 100644 benchmark/bm_hash_shift_u24.rb
 create mode 100644 benchmark/bm_hash_shift_u32.rb

diff --git a/benchmark/bm_hash_shift_u16.rb b/benchmark/bm_hash_shift_u16.rb
new file mode 100644
index 0000000..ec800d0
--- /dev/null
+++ b/benchmark/bm_hash_shift_u16.rb
@@ -0,0 +1,10 @@
+h = {}
+
+(16384..65536).each do |i|
+  h[i] = nil
+end
+
+300000.times do
+  k, v = h.shift
+  h[k] = v
+end
diff --git a/benchmark/bm_hash_shift_u24.rb b/benchmark/bm_hash_shift_u24.rb
new file mode 100644
index 0000000..de4e0fa
--- /dev/null
+++ b/benchmark/bm_hash_shift_u24.rb
@@ -0,0 +1,10 @@
+h = {}
+
+(0xff4000..0xffffff).each do |i|
+  h[i] = nil
+end
+
+300000.times do
+  k, v = h.shift
+  h[k] = v
+end
diff --git a/benchmark/bm_hash_shift_u32.rb b/benchmark/bm_hash_shift_u32.rb
new file mode 100644
index 0000000..656aa55
--- /dev/null
+++ b/benchmark/bm_hash_shift_u32.rb
@@ -0,0 +1,10 @@
+h = {}
+
+(0xffff4000..0xffffffff).each do |i|
+  h[i] = nil
+end
+
+300000.times do
+  k, v = h.shift
+  h[k] = v
+end
diff --git a/hash.c b/hash.c
index 1fd9d12..42d377c 100644
--- a/hash.c
+++ b/hash.c
@@ -191,11 +191,11 @@ rb_num_hash_start(st_index_t n)
      * - (n >> (RUBY_SPECIAL_SHIFT+3)) was added to make symbols hash well,
      *   n.b.: +3 to remove most ID scope, +1 worked well initially, too
      *   n.b.: +1 (instead of 3) worked well initially, too
-     * - (n << 3) was finally added to avoid losing bits for fixnums
+     * - (n << 16) was finally added to avoid losing bits for fixnums
      * - avoid expensive modulo instructions, it is currently only
      *   shifts and bitmask operations.
      */
-    return (n >> (RUBY_SPECIAL_SHIFT + 3) | (n << 3)) ^ (n >> 3);
+    return (n >> (RUBY_SPECIAL_SHIFT + 3) ^ (n << 16)) ^ (n >> 3);
 }
 
 long
-- 
EW