Project

General

Profile

« Previous | Next » 

Revision 72825c35

Added by Koichi Sasada over 4 years ago

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