From: eregontp@... Date: 2019-02-13T20:27:38+00:00 Subject: [ruby-core:91535] [Ruby trunk Feature#15602] Eliminate recording full-width hash value for small Hash Issue #15602 has been updated by Eregon (Benoit Daloze). IIRC, not storing #hash breaks specs, does it pass test-spec? Maybe the 8-bit #hash is enough to avoid problems? ---------------------------------------- Feature #15602: Eliminate recording full-width hash value for small Hash https://bugs.ruby-lang.org/issues/15602#change-76792 * Author: ko1 (Koichi Sasada) * Status: Open * Priority: Normal * Assignee: * Target version: ---------------------------------------- # Abstract Let's shape up small hash value (1 to 8 entries) from 192B to 128B on 64bit ptr environments. # Data structure proposal (step 1) Record only key and value pairs. Now Ruby 2.6, 1 to 8 entry Hash objects allocate 192 byte (8B * 3 (key, value and hash value triple) * 8 entry = 192B) with ar_table (instead of st_table). Eliminating to record hash value will reduce this allocation from 192B to 128B (8 * 2 * 8). (step 2) 1 byte hash value For 1 to 8 entry, full-width Hash value (8B) may be too long to select the entry. 1 byte hash value generated can be generate from 8 byte hash value. (`hash_value & 0xff` is most simple way to get it, but not sure it is enough) Name 1 byte hash value as "hash hint" on my patch. (step 3) Embed hash hint into RHash `RHash::iter_lev` is used to recognize nesting level of a hash. However, there are only a few cases that this value is bigger than 1. So we can put this value into flags (if it exceeds the limit, we can store this value as hidden attribute). 8 hash hints becomese 8B == sizeof(VALUE), so we can embed this value into RHash. # Discussion * Pros. * We can reduce allocation size of small Hash. * Increase cache locality on hash lookup * We don't need to touch ar_table (allocate memory) if hash hints doesn't match. * We can access correct ar_table entry directly. * Cons. * hash hints can conflict more than full-width hash value => may increase `eql?` call. * performance down * incompatibility # Evaluation I tested this patch and it slightly increase performance (not so big, on my micro-benchmark). Memory consumption is reduced theoretically. # Patch https://github.com/ko1/ruby/tree/hash_small_ar -- https://bugs.ruby-lang.org/ Unsubscribe: