Project

General

Profile

Feature #15602

Updated by ko1 (Koichi Sasada) about 5 years ago

# 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 entries, entry, full-width Hash value (8 bytes) (8B) may be too long to lookup select the entry. 
 1 byte hash value generated can be generated 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 (`h.each{ "h's iter_lev is 1 here" }`). 
 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 into as hidden attribute). 
 8 hash hints becomese `8B 8B == sizeof(VALUE)`, 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 

Back