• Roshan Khatri's avatar
    Reduce performance impact of dict rehashing and make it shorter. (#12899) · 5358bd7c
    Roshan Khatri authored
    
    
    #### Problem Statement:
    For any read/update operation during rehashing, we're doing ~10+ random
    DRAM lookups to do the rehashing, as we are using the `rehashidx` to
    rehash 10 buckets, whose dict entries most likely aren't cached in the
    CPU or near the bucket we are operating on. If these random bucket are
    empty, the rehashing process during that command execution is skipped.
    
    #### Implementation:
    For reducing the performance recession while dict is rehashing, we
    determine the index at which the key would be stored in the 0th HT, we
    check if that index has already been rehashed, if not we will rehash the
    bucket containing the key and the bucket will be moved from 0th HT to
    the 1st HT.
    
    If the key has already been rehashed, we perform the random access
    bucket rehash (using `rehashidx`) and we again verify if rehashing is
    still ongoing and look up the key in the respective HT.
    
    This ensures rehashing is not skipped in any command call and that we
    rehash a particular bucket or random bucket in each call.
    
    #### Changes in this PR:
    - Added a new method `dictBucketRehash` to perform rehash on a single
    bucket.
    - Helper function `moveKeysInBucketOldtoNew` for `dictRehash` and
    `dictBucketRehash` to move all the keys in a bucket from the old to the
    new hash HT.
    - Helper function `verifyMoreRehashRequired` for `dictRehash` and
    `dictBucketRehash` to check if we have already rehashed the whole table
    and if more rehashing is required.
    
    ### Benchmark:
    - This PR still shows **~13%** improvement in the latency during
    rehashing.
    
    - Rehashing is now **~2%** faster for this PR when compared to unstable.
    
    ---------
    Co-authored-by: default avatarOran Agra <oran@redislabs.com>
    Co-authored-by: default avatarMadelyn Olson <34459052+madolson@users.noreply.github.com>
    5358bd7c
dict.c 72.3 KB