diff options
author | Koichi Sasada <ko1@cookpad.com> | 2019-01-17 16:53:10 +0000 |
---|---|---|
committer | Koichi Sasada <ko1@atdot.net> | 2019-07-31 09:52:03 +0900 |
commit | 72825c35b0d8b9d566663de961fddbf4f010fff7 (patch) | |
tree | 1547f1df314a9568dd31f4eed098ef10347b9645 /debug_counter.h | |
parent | ebd398ac5a4147a1e652d6943c39a29a62f12e66 (diff) |
Use 1 byte hint for ar_table [Feature #15602]
On ar_table, Do not keep a full-length hash value (FLHV, 8 bytes)
but keep a 1 byte hint from a FLHV (lowest byte of FLHV).
An ar_table only contains at least 8 entries, so hints consumes
8 bytes at most. We can store hints in RHash::ar_hint.
On 32bit CPU, we use 4 entries ar_table.
The advantages:
* We don't need to keep FLHV so ar_table only consumes
16 bytes (VALUEs of key and value) * 8 entries = 128 bytes.
* We don't need to scan ar_table, but only need to check hints
in many cases. Especially we don't need to access ar_table
if there is no match entries (in many cases).
It will increase memory cache locality.
The disadvantages:
* This technique can increase `#eql?` time because hints can
conflicts (in theory, it conflicts once in 256 times).
It can introduce incompatibility if there is a object x where
x.eql? returns true even if hash values are different.
I believe we don't need to care such irregular case.
* We need to re-calculate FLHV if we need to switch from ar_table
to st_table (e.g. exceeds 8 entries).
It also can introduce incompatibility, on mutating key objects.
I believe we don't need to care such irregular case too.
Add new debug counters to measure the performance:
* artable_hint_hit - hint is matched and eql?#=>true
* artable_hint_miss - hint is not matched but eql?#=>false
* artable_hint_notfound - lookup counts
Diffstat (limited to 'debug_counter.h')
-rw-r--r-- | debug_counter.h | 6 |
1 files changed, 5 insertions, 1 deletions
diff --git a/debug_counter.h b/debug_counter.h index 97b7312794..3ca784456a 100644 --- a/debug_counter.h +++ b/debug_counter.h @@ -223,7 +223,6 @@ RB_DEBUG_COUNTER(obj_hash_g8) RB_DEBUG_COUNTER(obj_hash_ar) RB_DEBUG_COUNTER(obj_hash_st) RB_DEBUG_COUNTER(obj_hash_transient) - RB_DEBUG_COUNTER(obj_hash_force_convert) RB_DEBUG_COUNTER(obj_struct_embed) @@ -262,6 +261,11 @@ RB_DEBUG_COUNTER(obj_iclass_ptr) RB_DEBUG_COUNTER(obj_class_ptr) RB_DEBUG_COUNTER(obj_module_ptr) +/* ar_table */ +RB_DEBUG_COUNTER(artable_hint_hit) +RB_DEBUG_COUNTER(artable_hint_miss) +RB_DEBUG_COUNTER(artable_hint_notfound) + /* heap function counts * * * heap_xmalloc/realloc/xfree: call counts |