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

Code before:
        size_t table_size = numBuckets(ht->bucket_exp[table_index]);
        size_t next_index = bucket_index + 1;
        if (next_index < table_size) {
            next_bucket = &ht->tables[table_index][next_index];
        }
    }
    return next_bucket;
}

/* This function prefetches data that will be needed in subsequent iterations:
 * - The entries of the next bucket
 * - The next of the next bucket
 * It attempts to bring this data closer to the L1 cache to reduce future memory access latency.
 *
 * Cache state before this function is called(due to last call for this function):
 * 1. The current bucket and its entries are likely already in cache.
 * 2. The next bucket is in cache.
 */
static void prefetchNextBucketEntries(iter *iter, bucket *current_bucket) {
    size_t next_index = iter->index + 1;
    bucket *next_bucket = getNextBucket(current_bucket, next_index, iter->hashtable, iter->table);
    if (next_bucket) {
        prefetchBucketEntries(next_bucket);
        bucket *next_next_bucket = getNextBucket(next_bucket, next_index + 1, iter->hashtable, iter->table);
        if (next_next_bucket) {
            valkey_prefetch(next_next_bucket);
        }
    }
}

/* Prefetches the values associated with the entries in the given bucket by
 * calling the entryPrefetchValue callback in the hashtableType */
static void prefetchBucketValues(bucket *b, hashtable *ht) {
    if (!b->presence) return;
    assert(ht->type->entryPrefetchValue != NULL);
    for (int pos = 0; pos < numBucketPositions(b); pos++) {
        if (isPositionFilled(b, pos)) {
            ht->type->entryPrefetchValue(b->entries[pos]);
        }
    }
}

static inline int isSafe(iter *iter) {
    return (iter->flags & HASHTABLE_ITER_SAFE);
}

static inline int shouldPrefetchValues(iter *iter) {
    return (iter->flags & HASHTABLE_ITER_PREFETCH_VALUES);
}

/* --- API functions --- */

Review comment (suggestion):
This PR looks correct, but I think the code might be slightly cleaner if we increment the index in `getNextBucket` only, instead of here.

I mean we can keep `getNextBucket` unchanged and instead skip increment it here. Passing current bucket and current index appears to be a cleaner API of the getNextBucket function, to me.

How about this?

```c
    size_t current_index = iter->index;
    bucket *next_bucket = getNextBucket(current_bucket, current_index, iter->hashtable, iter->table);
    if (next_bucket) {
        prefetchBucketEntries(next_bucket);
        /* Calculate the target top-level index for the next bucket. */
        size_t next_index = current_bucket->chained ? current_index : current_index + 1;
        bucket *next_next_bucket = getNextBucket(next_bucket, next_index, iter->hashtable, iter->table);
```

Code after:
    } else {
        size_t table_size = numBuckets(ht->bucket_exp[table_index]);
        if (next_top_level_index < table_size) {
            next_bucket = &ht->tables[table_index][next_top_level_index];
        }
    }
    return next_bucket;
}

/* This function prefetches data that will be needed in subsequent iterations:
 * - The entries of the next bucket
 * - The next of the next bucket
 * It attempts to bring this data closer to the L1 cache to reduce future memory access latency.
 *
 * Cache state before this function is called (due to last call for this function):
 * 1. The current bucket and its entries are likely already in cache.
 * 2. The next bucket is in cache.
 */
static void prefetchNextBucketEntries(iter *iter, bucket *current_bucket) {
    size_t next_index = iter->index + 1;
    bucket *next_bucket = getNextBucket(current_bucket, next_index, iter->hashtable, iter->table);
    if (next_bucket) {
        prefetchBucketEntries(next_bucket);
        /* Calculate the target top-level index for the next-next bucket. */
        if (!current_bucket->chained) next_index++;
        bucket *next_next_bucket = getNextBucket(next_bucket, next_index, iter->hashtable, iter->table);
        if (next_next_bucket) {
            valkey_prefetch(next_next_bucket);
        }
    }
}

/* Prefetches the values associated with the entries in the given bucket by
 * calling the entryPrefetchValue callback in the hashtableType */
static void prefetchBucketValues(bucket *b, hashtable *ht) {
    if (!b->presence) return;
    assert(ht->type->entryPrefetchValue != NULL);
    for (int pos = 0; pos < numBucketPositions(b); pos++) {
        if (isPositionFilled(b, pos)) {
            ht->type->entryPrefetchValue(b->entries[pos]);
        }
    }
}

static inline int isSafe(iter *iter) {
    return (iter->flags & HASHTABLE_ITER_SAFE);
}

static inline int shouldPrefetchValues(iter *iter) {
    return (iter->flags & HASHTABLE_ITER_PREFETCH_VALUES);
}