• Nugine's avatar
    Optimize PFCOUNT, PFMERGE command by SIMD acceleration (#13558) · fdeb9762
    Nugine authored
    This PR optimizes the performance of HyperLogLog commands (PFCOUNT,
    PFMERGE) by adding AVX2 fast paths.
    
    Two AVX2 functions are added for conversion between raw representation
    and dense representation. They are 15 ~ 30 times faster than scalar
    implementaion. Note that sparse representation is not accelerated.
    
    AVX2 fast paths are enabled when the CPU supports AVX2 (checked at
    runtime) and the hyperloglog configuration is default (HLL_REGISTERS ==
    16384 && HLL_BITS == 6).
    
    When merging 3 dense hll structures, the benchmark shows a 12x speedup
    compared to the scalar version.
    
    ```
    pfcount key1 key2 key3
    pfmerge keyall key1 key2 key3
    ```
    
    ```
    ======================================================================================================
    Type             Ops/sec    Avg. Latency     p50 Latency     p99 Latency   p99.9 Latency       KB/sec 
    ------------------------------------------------------------------------------------------------------
    PFCOUNT-scalar    5570.09        35.89060        32.51100        65.27900        69.11900       299.17
    PFCOUNT-avx2     72604.92         2.82072         2.73500         5.50300         7.13500      3899.68
    ------------------------------------------------------------------------------------------------------
    PFMERGE-scalar    7879.13        25.52156        24.19100        46.33500        48.38300       492.45
    PFMERGE-avx2    126448.64         1.58120         1.53500         3.08700         4.89500      7903.04
    ------------------------------------------------------------------------------------------------------
    
    scalar: redis:unstable   9906daf5
    avx2:   Nugine:hll-simd  02e09f85ac07eace50ebdddd0fd70822f7b9152d 
    
    CPU:    13th Gen Intel® Core™ i9-13900H × 20
    Memory: 32.0 GiB
    OS:     Ubuntu 22.04.5 LTS
    ```
    
    Experiment repo: https://github.com/Nugine/redis-hyperloglog
    Benchmark script:
    https://github.com/Nugine/redis-hyperloglog/blob/main/scripts/memtier.sh
    Algorithm:
    https://github.com/Nugine/redis-hyperloglog/blob/main/cpp/bench.cpp
    
    
    
    resolves #13551
    
    ---------
    Co-authored-by: default avatarYuan Wang <wangyuancode@163.com>
    Co-authored-by: default avatardebing.sun <debing.sun@redis.com>
    fdeb9762
config.h 9.24 KB