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

Code before:
 * If 'table_index' is provided, it is set to the index of the table (0 or 1)
 * the returned bucket belongs to. */
#if HAVE_X86_SIMD
#include <immintrin.h>
ATTRIBUTE_TARGET_SSE2
#endif
static bucket *findBucket(hashtable *ht, uint64_t hash, const void *key, int *pos_in_bucket, int *table_index) {
    if (hashtableSize(ht) == 0) return 0;
    uint8_t h2 = highBits(hash);
    int table;

    /* Do some incremental rehashing. */
    rehashStepOnReadIfNeeded(ht);

    for (table = 0; table <= 1; table++) {
        if (ht->used[table] == 0) continue;
        size_t mask = expToMask(ht->bucket_exp[table]);
        size_t bucket_idx = hash & mask;
        /* Skip already rehashed buckets. */
        if (table == 0 && ht->rehash_idx >= 0 && bucket_idx < (size_t)ht->rehash_idx) {
            continue;
        }
        bucket *b = &ht->tables[table][bucket_idx];
        do {
#if HAVE_X86_SIMD
            if (__builtin_cpu_supports("sse2")) {
                /* Get the bucket's presence mask - indicates which positions are filled. */
                BUCKET_BITS_TYPE presence_mask = b->presence & ((1 << ENTRIES_PER_BUCKET) - 1);
                __m128i hash_vector = _mm_loadu_si128((__m128i *)b->hashes);
                __m128i h2_vector = _mm_set1_epi8(h2);
                /* Compare all hash values against the target hash simultaneously.
                 * The result is a vector of 16 bytes, where each byte is 0xFF if
                 * the corresponding hash matches the target hash, and 0x00 if it
                 * doesn't. */
                __m128i result = _mm_cmpeq_epi8(hash_vector, h2_vector);
                BUCKET_BITS_TYPE newmask = _mm_movemask_epi8(result);
                /* Only consider positions that are both filled (presence) and match the hash (newmask). */
                newmask &= presence_mask;
                while (newmask > 0) {
                    int pos = __builtin_ctz(newmask);
                    /* It's a candidate. */
                    void *entry = b->entries[pos];
                    const void *elem_key = entryGetKey(ht, entry);
                    if (compareKeys(ht, key, elem_key) == 0) {
                        /* It's a match. */
                        assert(pos_in_bucket != NULL);
                        *pos_in_bucket = pos;
                        if (table_index) *table_index = table;
                        return b;
                    }
                    /* Clear the processed bit and continue with next match. */

Review comment (refactor):
If we want to guard the code SSE2-specific code with a runtime check, then we need to check the CPU support before we enter code marked with the SSE2 attribute, don't we?

We can create a helper function where we use the SSE2 attribute and call it here. It can be a static inline function.

```c
#if HAVE_X86_SIMD
            if (__builtin_cpu_supports("sse2")) {
                if (findKeyInBucketSSE2(b, key, h2, pos_in_bucket, table_index)) return b;
                b = getChildBucket(b);
                continue;
            }
#endif
            /* Fallback non-SIMD code here */
```

The helper function can have the attribute.

```c
#if HAVE_X86_SIMD
ATTRIBUTE_TARGET_SSE2 static findInBucketSSE2(...) {
    ...
}
#endif
```

However, SSE2 appears to be mandatory in all x86-64 CPUs, according to https://en.wikipedia.org/wiki/X86-64, so maybe we don't need to check `__builtin_cpu_supports("sse2")` at all? Only the `HAVE_X86_SIMD` check is enough?

If yes, then we can use `#else` for the non-SIMD code.

```C
#if HAVE_X86_SIMD
            /* All x64-64 CPUs have SSE2. */
            if (findKeyInBucketSSE2(b, key, h2, pos_in_bucket, table_index)) return b;
#else
            /* Fallback non-SIMD code here */
            ...
#endif
            b = getChildBucket(b);
```

Do you know if SSE2 always exists on x86-64?

Code after:
 *
 * This function examines a specific position in a bucket to determine if the
 * entry at that position matches the provided key. If a match is found, it
 * updates the position and table index pointers and returns 1. Otherwise,
 * it returns 0. */
static inline int checkCandidateInBucket(hashtable *ht, bucket *b, int pos, const void *key, int table, int *pos_in_bucket, int *table_index) {
    /* It's a candidate. */
    void *entry = b->entries[pos];
    const void *elem_key = entryGetKey(ht, entry);
    if (compareKeys(ht, key, elem_key) == 0) {
        /* It's a match. */
        assert(pos_in_bucket != NULL);
        *pos_in_bucket = pos;
        if (table_index) *table_index = table;
        return 1;
    }
    return 0;
}

#if HAVE_X86_SIMD
ATTRIBUTE_TARGET_SSE2
static int findKeyInBucketSSE2(hashtable *ht, bucket *b, uint8_t h2, const void *key, int table, int *pos_in_bucket, int *table_index) {
    /* Get the bucket's presence mask - indicates which positions are filled. */
    BUCKET_BITS_TYPE presence_mask = b->presence & ((1 << ENTRIES_PER_BUCKET) - 1);
    __m128i hash_vector = _mm_loadu_si128((__m128i *)b->hashes);
    __m128i h2_vector = _mm_set1_epi8(h2);
    /* Compare all hash values against the target hash simultaneously.
     * The result is a vector of 16 bytes, where each byte is 0xFF if
     * the corresponding hash matches the target hash, and 0x00 if it
     * doesn't. */
    __m128i result = _mm_cmpeq_epi8(hash_vector, h2_vector);
    BUCKET_BITS_TYPE newmask = _mm_movemask_epi8(result);
    /* Only consider positions that are both filled (presence) and match the hash (newmask). */
    newmask &= presence_mask;
    while (newmask > 0) {
        int pos = __builtin_ctz(newmask);
        if (checkCandidateInBucket(ht, b, pos, key, table, pos_in_bucket, table_index)) return 1;
        /* Clear the processed bit and continue with next match. */
        newmask &= ~(1 << pos);
    }
    return 0;
}
#endif

/* Finds an entry matching the key. If a match is found, returns a pointer to
 * the bucket containing the matching entry and points 'pos_in_bucket' to the
 * index within the bucket. Returns NULL if no matching entry was found.
 *
 * If 'table_index' is provided, it is set to the index of the table (0 or 1)
 * the returned bucket belongs to. */
static bucket *findBucket(hashtable *ht, uint64_t hash, const void *key, int *pos_in_bucket, int *table_index) {