ruby-changes:33305
From: normal <ko1@a...>
Date: Sun, 23 Mar 2014 08:34:27 +0900 (JST)
Subject: [ruby-changes:33305] normal:r45384 (trunk): st.c: use power-of-two sizes to avoid slow modulo ops
normal 2014-03-23 08:34:21 +0900 (Sun, 23 Mar 2014) New Revision: 45384 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=45384 Log: 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 Added files: trunk/benchmark/bm_hash_aref_miss.rb trunk/benchmark/bm_hash_aref_str.rb trunk/benchmark/bm_hash_aref_sym.rb trunk/benchmark/bm_hash_aref_sym_long.rb trunk/benchmark/bm_hash_ident_num.rb trunk/benchmark/bm_hash_ident_obj.rb trunk/benchmark/bm_hash_ident_str.rb trunk/benchmark/bm_hash_ident_sym.rb Modified files: trunk/ChangeLog trunk/NEWS trunk/hash.c trunk/st.c Index: ChangeLog =================================================================== --- ChangeLog (revision 45383) +++ ChangeLog (revision 45384) @@ -1,3 +1,19 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Sun Mar 23 08:12:27 2014 Eric Wong <e@8...> + + * 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@r...> * addr2line.c (fill_lines): compare the file names of object in which Index: st.c =================================================================== --- st.c (revision 45383) +++ st.c (revision 45384) @@ -33,8 +33,7 @@ typedef struct st_packed_entry { https://github.com/ruby/ruby/blob/trunk/st.c#L33 #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 *); https://github.com/ruby/ruby/blob/trunk/st.c#L84 #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 https://github.com/ruby/ruby/blob/trunk/st.c#L139 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) https://github.com/ruby/ruby/blob/trunk/st.c#L1633 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)); } Index: hash.c =================================================================== --- hash.c (revision 45383) +++ hash.c (revision 45384) @@ -132,6 +132,7 @@ rb_any_hash(VALUE a) https://github.com/ruby/ruby/blob/trunk/hash.c#L132 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) { Index: NEWS =================================================================== --- NEWS (revision 45383) +++ NEWS (revision 45384) @@ -84,3 +84,9 @@ with all sufficient information, see the https://github.com/ruby/ruby/blob/trunk/NEWS#L84 * 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. Index: benchmark/bm_hash_ident_obj.rb =================================================================== --- benchmark/bm_hash_ident_obj.rb (revision 0) +++ benchmark/bm_hash_ident_obj.rb (revision 45384) @@ -0,0 +1,4 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/bm_hash_ident_obj.rb#L1 +h = {}.compare_by_identity +objs = 26.times.map { Object.new } +objs.each { |o| h[o] = o } +200_000.times { objs.each { |o| h[o] } } Index: benchmark/bm_hash_ident_num.rb =================================================================== --- benchmark/bm_hash_ident_num.rb (revision 0) +++ benchmark/bm_hash_ident_num.rb (revision 45384) @@ -0,0 +1,4 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/bm_hash_ident_num.rb#L1 +h = {}.compare_by_identity +nums = (1..26).to_a +nums.each { |n| h[n] = n } +200_000.times { nums.each { |n| h[n] } } Index: benchmark/bm_hash_ident_str.rb =================================================================== --- benchmark/bm_hash_ident_str.rb (revision 0) +++ benchmark/bm_hash_ident_str.rb (revision 45384) @@ -0,0 +1,4 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/bm_hash_ident_str.rb#L1 +h = {}.compare_by_identity +strs = ('a'..'z').to_a +strs.each { |s| h[s] = s } +200_000.times { strs.each { |s| h[s] } } Index: benchmark/bm_hash_ident_sym.rb =================================================================== --- benchmark/bm_hash_ident_sym.rb (revision 0) +++ benchmark/bm_hash_ident_sym.rb (revision 45384) @@ -0,0 +1,4 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/bm_hash_ident_sym.rb#L1 +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] } } Index: benchmark/bm_hash_aref_str.rb =================================================================== --- benchmark/bm_hash_aref_str.rb (revision 0) +++ benchmark/bm_hash_aref_str.rb (revision 45384) @@ -0,0 +1,4 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/bm_hash_aref_str.rb#L1 +h = {} +strs = ('a'..'z').to_a.map!(&:freeze) +strs.each { |s| h[s] = s } +200_000.times { strs.each { |s| h[s] } } Index: benchmark/bm_hash_aref_miss.rb =================================================================== --- benchmark/bm_hash_aref_miss.rb (revision 0) +++ benchmark/bm_hash_aref_miss.rb (revision 45384) @@ -0,0 +1,5 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/bm_hash_aref_miss.rb#L1 +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] } } Index: benchmark/bm_hash_aref_sym.rb =================================================================== --- benchmark/bm_hash_aref_sym.rb (revision 0) +++ benchmark/bm_hash_aref_sym.rb (revision 45384) @@ -0,0 +1,4 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/bm_hash_aref_sym.rb#L1 +h = {} +syms = ('a'..'z').to_a.map(&:to_sym) +syms.each { |s| h[s] = s } +200_000.times { syms.each { |s| h[s] } } Index: benchmark/bm_hash_aref_sym_long.rb =================================================================== --- benchmark/bm_hash_aref_sym_long.rb (revision 0) +++ benchmark/bm_hash_aref_sym_long.rb (revision 45384) @@ -0,0 +1,8 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/bm_hash_aref_sym_long.rb#L1 +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] } } -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/