Repository: valkey-io/valkey
File: src/bitops.c (C)

Code before:
    6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
    3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4,
    5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
    6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};

#ifdef HAVE_AVX2
/* The SIMD version of popcount enhances performance through parallel lookup tables. */
ATTRIBUTE_TARGET_AVX2
static long long serverPopcountAVX2(void *s, long count) {
    long i = 0;
    unsigned char *p = (unsigned char *)s;
    long long bits = 0;

    const __m256i lookup = _mm256_setr_epi8(
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4,
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4);

    const __m256i low_mask = _mm256_set1_epi8(0x0f);
    __m256i acc = _mm256_setzero_si256();

/* Count 32 bytes per iteration. */
#define ITER_32_BYTES                                                             \
    {                                                                             \
        const __m256i vec = _mm256_loadu_si256((const __m256i *)(p + i));         \
        const __m256i lo = _mm256_and_si256(vec, low_mask);                       \
        const __m256i hi = _mm256_and_si256(_mm256_srli_epi16(vec, 4), low_mask); \
        const __m256i popcnt1 = _mm256_shuffle_epi8(lookup, lo);                  \
        const __m256i popcnt2 = _mm256_shuffle_epi8(lookup, hi);                  \
        local = _mm256_add_epi8(local, popcnt1);                                  \
        local = _mm256_add_epi8(local, popcnt2);                                  \
        i += 32;                                                                  \
    }

    /* We divide the array into the following three parts
     *        Part A         Part B       Part C
     * +-----------------+--------------+---------+
     * | 8 * 32bytes * X |  32bytes * Y | Z bytes |
     * +-----------------+--------------+---------+
     */

    /* Parrt A: loop unrolling, processing 8 * 32 bytes per iteration. */
    while (i + 8 * 32 <= count) {
        __m256i local = _mm256_setzero_si256();
        ITER_32_BYTES
        ITER_32_BYTES

Review comment (refactor):
Perhaps add comments to explain why the data is duplicated (due lane to isolation). Eg:
```
const __m256i lookup = _mm256_setr_epi8(
    /* First Lane [0:127] */
    /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
    /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
    /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
    /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4,

    /* Second Lane [128:255] (identical to first lane due to lane isolation in _mm256_shuffle_epi8) */
    /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
    /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
    /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
    /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4);
```

Code after:
    6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
    3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4,
    5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
    6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};

#ifdef HAVE_AVX2
/* The SIMD version of popcount enhances performance through parallel lookup tables which is based on the following article:
 * https://arxiv.org/pdf/1611.07612 */
ATTRIBUTE_TARGET_AVX2
long long popcountAVX2(void *s, long count) {
    long i = 0;
    unsigned char *p = (unsigned char *)s;
    long long bits = 0;

    /* clang-format off */
    const __m256i lookup = _mm256_setr_epi8(
        /* First Lane [0:127] */
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4,

        /* Second Lane [128:255] identical to first lane due to lane isolation in _mm256_shuffle_epi8.
         * For more information, see following URL
         * https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=_mm256_shuffle_epi8 */
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4);
    /* clang-format on */
    const __m256i low_mask = _mm256_set1_epi8(0x0f);
    __m256i acc = _mm256_setzero_si256();

/* Count 32 bytes per iteration. */
#define ITER_32_BYTES                                                             \
    {                                                                             \
        const __m256i vec = _mm256_loadu_si256((const __m256i *)(p + i));         \
        const __m256i lo = _mm256_and_si256(vec, low_mask);                       \
        const __m256i hi = _mm256_and_si256(_mm256_srli_epi16(vec, 4), low_mask); \
        const __m256i popcnt1 = _mm256_shuffle_epi8(lookup, lo);                  \
        const __m256i popcnt2 = _mm256_shuffle_epi8(lookup, hi);                  \
        local = _mm256_add_epi8(local, popcnt1);                                  \
        local = _mm256_add_epi8(local, popcnt2);                                  \
        i += 32;                                                                  \
    }

    /* We divide the array into the following three parts
     *        Part A         Part B       Part C
     * +-----------------+--------------+---------+
     * | 8 * 32bytes * X |  32bytes * Y | Z bytes |
     * +-----------------+--------------+---------+