• Ozan Tezcan's avatar
    Improve performance of hfe listpack (#13279) · a25b1539
    Ozan Tezcan authored
    
    
    This PR contains a few optimizations for hfe listpack.
    - Hfe fields are ordered by TTL in the listpack. There are two cases
    that we want to search listpack according to TTLs:
    - As part of active-expiry, we need to find the fields that are expired.
    e.g. find fields that have smaller TTLs than given timestamp.
    - When we want to add a new field, we need to find the correct position
    to maintain the order by TTL. e.g. find the field that has a higher TTL
    than the one we want to insert.
      
    Iterating with lpNext() to compare TTLs has a performance cost as
    lpNext() calls lpValidateIntegrity() for each entry. Instead, this PR
    adds `lpFindCb()` to the listpack which accepts a comparator callback.
    It preserves same validation logic of lpFind() which is faster than
    search with lpNext().
      
    - We have field name, value, ttl for a single hfe field. Inserting these
    items one by one to listpack is costly. Especially, as we place fields
    according to TTL, most additions will end up in the middle of the
    listpack. Each insert causes realloc + memmove. This PR introduces
    `lpBatchInsert()` to add multiple items in one go.
    
    - For hsetf, if we are going to update value and TTL at the same time,
    currently, we update the value first and later update the TTL (two
    distinct listpack operation). This PR improves it by doing it with a
    single update operation.
    
    ---------
    Co-authored-by: default avatardebing.sun <debing.sun@redis.com>
    a25b1539
listpack.h 4.75 KB