diff options
| -rw-r--r-- | ChangeLog | 16 | ||||
| -rw-r--r-- | NEWS | 6 | ||||
| -rw-r--r-- | benchmark/bm_hash_aref_miss.rb | 5 | ||||
| -rw-r--r-- | benchmark/bm_hash_aref_str.rb | 4 | ||||
| -rw-r--r-- | benchmark/bm_hash_aref_sym.rb | 4 | ||||
| -rw-r--r-- | benchmark/bm_hash_aref_sym_long.rb | 8 | ||||
| -rw-r--r-- | benchmark/bm_hash_ident_num.rb | 4 | ||||
| -rw-r--r-- | benchmark/bm_hash_ident_obj.rb | 4 | ||||
| -rw-r--r-- | benchmark/bm_hash_ident_str.rb | 4 | ||||
| -rw-r--r-- | benchmark/bm_hash_ident_sym.rb | 4 | ||||
| -rw-r--r-- | hash.c | 1 | ||||
| -rw-r--r-- | st.c | 74 |
12 files changed, 77 insertions, 57 deletions
@@ -1,3 +1,19 @@ +Sun Mar 23 08:12:27 2014 Eric Wong <e@80x24.org> + + * 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@ruby-lang.org> * addr2line.c (fill_lines): compare the file names of object in which @@ -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] } } @@ -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) { @@ -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<<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) 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)); } |