From: mame@...
Date: 2015-12-10T10:34:29+00:00
Subject: [ruby-core:72028] [Ruby trunk - Feature #11405] [Assigned] [PATCH] hash.c: minor speedups to int/fixnum keys

Issue #11405 has been updated by Yusuke Endoh.

Status changed from Closed to Assigned
Assignee set to Eric Wong

This caused a lot of trivial hash conflicts of Fixnums that is >= 16384.

~~~~
$ ./miniruby -ve 'p 16384.hash; p 16385.hash'
ruby 2.3.0dev (2015-12-10 master 52945) [x86_64-linux]
1104801043349207800
1104801043349207800
~~~~

Other pairs:

~~~~
p [16386, 16387].map {|n| n.hash }.uniq #=> [2133837449075777600]
p [16388, 16389].map {|n| n.hash }.uniq #=> [3903799135928350277]
p [16390, 16391].map {|n| n.hash }.uniq #=> [-3836391686716480155]
p [16392, 16393].map {|n| n.hash }.uniq #=> [1714559302010572050]
p [16394, 16395].map {|n| n.hash }.uniq #=> [2147130354083423794]
p [16396, 16397].map {|n| n.hash }.uniq #=> [-679539024000319657]
p [16398, 16399].map {|n| n.hash }.uniq #=> [4056286416392832887]
p [16400, 16401].map {|n| n.hash }.uniq #=> [2733766810351706956]
p [16402, 16403].map {|n| n.hash }.uniq #=> [-1228876631044862612]
p [16404, 16405].map {|n| n.hash }.uniq #=> [1418226818996216529]
~~~~

Unlike the name suggests, rb_objid_hash is also used to calculate a hash value of Fixnum.

IMO, we must fix this issue before 2.3.0 release.

-- 
Yusuke Endoh <mame@ruby-lang.org>

----------------------------------------
Feature #11405: [PATCH] hash.c: minor speedups to int/fixnum keys
https://bugs.ruby-lang.org/issues/11405#change-55440

* Author: Eric Wong
* Status: Assigned
* Priority: Normal
* Assignee: Eric Wong
----------------------------------------
Noticed with [ruby-core:70159] [Bug #11396]

The low bits of Ruby object IDs are rarely populated in the current
implementation, so ensure the get used.

Early versions of this patch redundantly shifted static symbols in
`any_hash`, causing regressions with static symbols in `hash_aref_sym`

* hash.c (any_hash): skip rb_objid_hash for static syms
  (rb_num_hash_start): extract from rb_ident_hash
  (rb_objid_hash): call rb_num_hash_start
  (rb_ident_hash): ditto

~~~
target 0: a (ruby 2.3.0dev (2015-07-30 trunk 51437) [x86_64-linux]
target 1: b (ruby 2.3.0dev (2015-07-30 patch 51437) [x86_64-linux]

benchmark results from Xeon E3-1230 v3 @ 3.30GHz (turbo disabled):
minimum results in each 10 measurements.
Execution time (sec)
name                a       b
hash_aref_dsym        0.316   0.300
hash_aref_dsym_long   5.106   5.063
hash_aref_fix         0.304   0.297
hash_aref_flo         0.061   0.060
hash_aref_miss        0.433   0.430
hash_aref_str         0.408   0.396
hash_aref_sym         0.312   0.306
hash_aref_sym_long    0.482   0.469
hash_flatten          0.385   0.273
hash_ident_flo        0.036   0.037
hash_ident_num        0.277   0.276
hash_ident_obj        0.291   0.284
hash_ident_str        0.289   0.286
hash_ident_sym        0.285   0.281
hash_keys             0.269   0.271
hash_shift            0.020   0.016
hash_values           0.264   0.264
loop_whileloop2       0.101   0.099
vm2_bighash*          3.066   2.972

Speedup ratio: compare with the result of `a' (greater is better)
name                b
hash_aref_dsym        1.052
hash_aref_dsym_long   1.008
hash_aref_fix         1.024
hash_aref_flo         1.015
hash_aref_miss        1.007
hash_aref_str         1.031
hash_aref_sym         1.018
hash_aref_sym_long    1.027
hash_flatten          1.410
hash_ident_flo        0.994
hash_ident_num        1.001
hash_ident_obj        1.022
hash_ident_str        1.012
hash_ident_sym        1.016
hash_keys             0.992
hash_shift            1.237
hash_values           1.001
loop_whileloop2       1.013
vm2_bighash*          1.032
~~~

I will commit in a few weeks if everyone is OK with this.


---Files--------------------------------
0001-hash.c-improve-integer-fixnum-hashing.patch (5.17 KB)


-- 
https://bugs.ruby-lang.org/