From ef59670a44f30df7f07dd7a1438a2c27652bcb3c Mon Sep 17 00:00:00 2001 From: normal Date: Sat, 22 Mar 2014 23:34:21 +0000 Subject: 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 --- ChangeLog | 16 +++++++++ NEWS | 6 ++++ benchmark/bm_hash_aref_miss.rb | 5 +++ benchmark/bm_hash_aref_str.rb | 4 +++ benchmark/bm_hash_aref_sym.rb | 4 +++ benchmark/bm_hash_aref_sym_long.rb | 8 +++++ benchmark/bm_hash_ident_num.rb | 4 +++ benchmark/bm_hash_ident_obj.rb | 4 +++ benchmark/bm_hash_ident_str.rb | 4 +++ benchmark/bm_hash_ident_sym.rb | 4 +++ hash.c | 1 + st.c | 74 +++++++++----------------------------- 12 files changed, 77 insertions(+), 57 deletions(-) create mode 100644 benchmark/bm_hash_aref_miss.rb create mode 100644 benchmark/bm_hash_aref_str.rb create mode 100644 benchmark/bm_hash_aref_sym.rb create mode 100644 benchmark/bm_hash_aref_sym_long.rb create mode 100644 benchmark/bm_hash_ident_num.rb create mode 100644 benchmark/bm_hash_ident_obj.rb create mode 100644 benchmark/bm_hash_ident_str.rb create mode 100644 benchmark/bm_hash_ident_sym.rb diff --git a/ChangeLog b/ChangeLog index 45a5ad9afd..8a230d4e4b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,19 @@ +Sun Mar 23 08:12:27 2014 Eric Wong + + * 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 * addr2line.c (fill_lines): compare the file names of object in which diff --git a/NEWS b/NEWS index 753ebd891b..021429867c 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 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] } } diff --git a/hash.c b/hash.c index 0023e84b1a..56917ed056 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 5943982761..5a0b62a664 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< size) return 1< size) return primes[i]; + if ((st_index_t)(1< size) return 1<> 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)); } -- cgit v1.2.3