[ruby-core:93962] [Ruby master Feature#15602] Eliminate recording full-width hash value for small Hash

Issue #15602 has been updated by ko1 (Koichi Sasada).

Assignee set to ko1 (Koichi Sasada)
Status changed from Open to Assigned

Patch is updated:
https://github.com/ko1/ruby/tree/hash_small_ar

NEWS:
* Support 32bit CPU
* Support > 127 Hash iteration level
* Fix bugs

# Evaluation

## Discourse benchmark

### overall benchmark

With discourse benchmark, there is no speed improvement.

```
# master
ruby 2.7.0dev (2019-07-26T07:34:15Z master 51f22deadb) [x86_64-linux]
categories:
  50: 37
  75: 38
  90: 46
  99: 76
home:
  50: 38
  75: 39
  90: 47
  99: 83
topic:
  50: 38
  75: 39
  90: 41
  99: 63
categories_admin:
  50: 60
  75: 64
  90: 75
  99: 113
home_admin:
  50: 63
  75: 64
  90: 77
  99: 111
topic_admin:
  50: 64
  75: 66
  90: 73
  99: 102
timings:
  load_rails: 3593
ruby-version: 2.7.0-p-1
rss_kb: 316540
pss_kb: 307648

# this patch
ruby 2.7.0dev (2019-07-26T08:11:10Z :detached: 8f8d83fa3f) [x86_64-linux]

categories:
  50: 36
  75: 37
  90: 44
  99: 70
home:
  50: 37
  75: 38
  90: 47
  99: 82
topic:
  50: 37
  75: 38
  90: 45
  99: 71
categories_admin:
  50: 62
  75: 65
  90: 74
  99: 130
home_admin:
  50: 62
  75: 64
  90: 76
  99: 125
topic_admin:
  50: 63
  75: 65
  90: 75
  99: 118
timings:
  load_rails: 3674
ruby-version: 2.7.0-p-1
rss_kb: 269296
pss_kb: 260475
```

However, it achieves 50MB memory efficiency.

```
master:
rss_kb: 316540
pss_kb: 307648

this patch:
rss_kb: 269296
pss_kb: 260475
```

### conflict measurement

I added new debug counters:

* hit: the count hint match and `eql?() #=> true`
* miss: the count hint match but `eql?() #=> false`
* notfound: the count that there are no hint match.

In otherwords, lookup count is "hit + notfound".

```
[RUBY_DEBUG_COUNTER]    artable_hint_hit                    81,394,995
[RUBY_DEBUG_COUNTER]    artable_hint_miss                      968,533
[RUBY_DEBUG_COUNTER]    artable_hint_notfound               84,984,795
```

With discourse benchmark, we can see 160M lookup and 1M miss.
Hint values will be conflict in 1/256 (because hint is 1B). So not strange result (*1).

(*1) 0.6M is ideal, so there is a room to improve. However, making hint algorithm more complicated introduce additional overhead.

1M times usless `eql?` can be a matter.

### hint algorithm

To make 1B from hash value (8B), now I only use `(unsigned char)hash_value`, the lowest 8 bits.
There are several algorithm:

* (1) lowest 8 bit
* (2) xor with least 4B
* (3) xor with least 2B
* (4) using 15 to 8 bits (`(unsigned char)hash_value >> 8`)

However, (1) got high-score (1M misses. others > 2M misses).

## Rdoc benchmark

(`make gcbench-rdoc`)

```
master
{:count=>179,
 :heap_allocated_pages=>9008,
 :heap_sorted_length=>9008,
 :heap_allocatable_pages=>0,
 :heap_available_slots=>3671670,
 :heap_live_slots=>2609737,
 :heap_free_slots=>1061933,
 :heap_final_slots=>0,
 :heap_marked_slots=>2447202,
 :heap_eden_pages=>9008,
 :heap_tomb_pages=>0,
 :total_allocated_pages=>9008,
 :total_freed_pages=>0,
 :total_allocated_objects=>33443045,
 :total_freed_objects=>30833308,
 :malloc_increase_bytes=>222056,
 :malloc_increase_bytes_limit=>33554432,
 :minor_gc_count=>151,
 :object_id_collisions=>0,
 :major_gc_count=>28,
 :remembered_wb_unprotected_objects=>2490,
 :remembered_wb_unprotected_objects_limit=>4976,
 :old_objects=>2443098,
 :old_objects_limit=>4848924,
 :oldmalloc_increase_bytes=>8658088,
 :oldmalloc_increase_bytes_limit=>71306460}
ruby 2.7.0dev (2019-07-26T07:34:15Z master 51f22deadb) [x86_64-linux] ["USE_RGENGC", "RGENGC_DEBUG", "RGENGC_ESTIMATE_OLDMALLOC", "GC_ENABLE_LAZY_SWEEP"]

/home/ko1/ruby/v2/src/trunk/benchmark/gc/rdoc.rb
      user     system      total        real
 25.753310   0.308549  26.061859 ( 26.065280)
GC total time (sec): 0

VmHWM: 467852 kB

Summary of rdoc on 2.7.0dev     26.065279869362712      0       179
         (real time in sec, GC time in sec, GC count)

small_hash
{:count=>175,
 :heap_allocated_pages=>10295,
 :heap_sorted_length=>10295,
 :heap_allocatable_pages=>0,
 :heap_available_slots=>4196252,
 :heap_live_slots=>2687349,
 :heap_free_slots=>1508903,
 :heap_final_slots=>0,
 :heap_marked_slots=>2445290,
 :heap_eden_pages=>10295,
 :heap_tomb_pages=>0,
 :total_allocated_pages=>10295,
 :total_freed_pages=>0,
 :total_allocated_objects=>33443475,
 :total_freed_objects=>30756126,
 :malloc_increase_bytes=>8655184,
 :malloc_increase_bytes_limit=>33554432,
 :minor_gc_count=>146,
 :object_id_collisions=>0,
 :major_gc_count=>29,
 :remembered_wb_unprotected_objects=>2490,
 :remembered_wb_unprotected_objects_limit=>4976,
 :old_objects=>2441968,
 :old_objects_limit=>4848944,
 :oldmalloc_increase_bytes=>16372800,
 :oldmalloc_increase_bytes_limit=>89024695}
ruby 2.7.0dev (2019-07-26T08:11:10Z :detached: 8f8d83fa3f) [x86_64-linux] ["USE_RGENGC", "RGENGC_DEBUG", "RGENGC_ESTIMATE_OLDMALLOC", "GC_ENABLE_LAZY_SWEEP"]

../../src/hash_small_ar/benchmark/gc/rdoc.rb
      user     system      total        real
 25.876454   0.392925  26.269379 ( 26.273089)
GC total time (sec): 0

VmHWM: 495984 kB

Summary of rdoc on 2.7.0dev     26.273089297115803      0       175
         (real time in sec, GC time in sec, GC count)
```

VmHWM is corrupted :(

Maybe because GC count is not so high because of low `xmalloc()` consumption.



----------------------------------------
Feature #15602: Eliminate recording full-width hash value for small Hash
https://bugs.ruby-lang.org/issues/15602#change-80153

* Author: ko1 (Koichi Sasada)
* Status: Assigned
* Priority: Normal
* Assignee: ko1 (Koichi Sasada)
* 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 entries, full-width Hash value (8 bytes) may be too long to lookup the entry.
1 byte hash value can be generated 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" }`).
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 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: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>