• Viktor Söderqvist's avatar
    Key as dict entry - memory optimization for sets (#11595) · f3f6f7c0
    Viktor Söderqvist authored
    If a dict has only keys, and no use of values, then a key can be stored directly in a
    dict's hashtable. The key replaces the dictEntry. To distinguish between a key and
    a dictEntry, we only use this optimization if the key is odd, i.e. if the key has the least
    significant bit set. This is true for sds strings, since the sds header is always an odd
    number of bytes.
    
    Dict entries are used as a fallback when there is a hash collision. A special dict entry
    without a value (only key and next) is used so we save one word in this case too.
    
    This saves 24 bytes per set element for larges sets, and also gains some speed improvement
    as a side effect (less allocations and cache misses).
    
    A quick test adding 1M elements to a set using the command below resulted in memory
    usage of 28.83M, compared to 46.29M on unstable.
    That's 18 bytes per set element on average.
    
        eval 'for i=1,1000000,1 do redis.call("sadd", "myset", "x"..i) end' 0
    
    Other changes:
    
    Allocations are ensured to have at least 8 bits alignment on all systems. This affects 32-bit
    builds compiled without HAVE_MALLOC_SIZE (not jemalloc or glibc) in which Redis
    stores the size of each allocation, after this change in 8 bytes instead of previously 4 bytes
    per allocation. This is done so we can reliably use the 3 least significant bits in a pointer to
    encode stuff.
    f3f6f7c0
t_set.c 59.5 KB