st.c: use power-of-two sizes to avoid slow modulo ops

* 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

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@45384 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

8 files changed, 37 insertions, 0 deletions

diff --git a/benchmark/bm_hash_aref_miss.rb b/benchmark/bm_hash_aref_miss.rb
new file mode 100644
index 0000000000..b0913dd4bb
--- /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 0000000000..19439b061b
--- /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 0000000000..54298ffc9e
--- /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 0000000000..a9be4059e6
--- /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 0000000000..b226736c6f
--- /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 0000000000..4b3b58edec
--- /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 0000000000..8582b38e31
--- /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 0000000000..4c81e3d28e
--- /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] } }