C++: Quickest way to get integer within a range

Question

I need to generate hash keys for about N=100 million keys. From my study it appears that murmur3 (MurmurHash3_x86_32, see murmur3 hash) would be the fastest hashing function with best latency and small enough collision rate. The problem I am facing is that the function returns key as void *. More specifically, the template is:

void MurmurHash3_x86_32 (const void *key, int len, uint32_t seed, void *out);

As my hash table size would be smaller than the largest hash it can generate, I need to get it into the table range [0, N-1]. The easiest solution seems to be to use % operator. But as it is known to be a slow operator, I wonder if there is a quicker way to solve the problem.

One interesting suggestion I found was given Is there an alternative to using % (modulus) in C/C++? on StackOverflow itself. It suggests 'a power of two, the following works (assuming twos complement representation)':

return i & (n-1);

My issue with this is that on newer CPUs, it is sometimes (or is it most of the times?), the performance degrades at around sizes 2^n, IIRC, due to multiway cache lines. (This link provides an illustration regarding insertions Big Memory, Part 3.5: Google sparsehash!).

At the moment, the advantages of murmur3 seems to be nullified by hard-ware related issues and known inefficiency of % operator. As performance is a constraint, I request for low latency and faster solutions to my requirement even if it is not MurmurHash3_x86_32.

Answer 1

The problem I am facing is that the function returns key as void *.

It does not. It returns nothing (void). The hash result is recorded in the buffer you specify (a pointer to) via last argument. For MurmurHash3_x86_32(), it makes the most sense for that to be a pointer to a uint32_t.

As my hash table size would be smaller than the largest hash it can generate, I need to get it into the table range [0, N-1]. The easiest solution seems to be to use % operator. But as it is known to be a slow operator, I wonder if there is a quicker way to solve the problem.

The % is not only the easiest solution, but the most usual one. "Slow" is relative -- % is slower than +, but much, much faster than one call to MurmurHash3_x86_32().

One interesting suggestion I found [...] suggests [using a power-of-two table size, and computing the modulus via the & operator]

Note that contrary to the assertion in the SO answer, in fact this has no dependency at all on twos' complement representation.

My issue with this is that on newer CPUs, it is sometimes (or is it most of the times?), the performance degrades at around sizes 2^n, IIRC, due to multiway cache lines. (This link provides an illustration regarding insertions Big Memory, Part 3.5: Google sparsehash!).

The performance degredation described in the report you linked is attributed to re-hashing, which seems quite plausible. That has nothing to do with the operations you're asking about. It is conceivable that cache (lack of) associativity could impact performance for large hash tables, but probably not more so than having large hash tables does generally. The memory access patterns inherent in use of a hash table naturally produce poor cache locality. That's practically the point.

At the moment, the advantages of murmur3 seems to be nullified by hard-ware related issues and known inefficiency of % operator. As performance is a constraint, I request for low latency and faster solutions to my requirement even if it is not MurmurHash3_x86_32.

You are way overthinking this. Lack of effective use of your CPU cache is simply a price you pay for using a large hash table. It is not associated with the hash function (as long as the hash function does its job well). The cost of a single arithmetic operation, whether it be % or &, will not be noticeable compared to the cost of computing a hash to operate on, so it hardly matters which of those you choose. If you want a tiny advantage for that operation then use a power-of-two sized table and the & operator. On the other hand, that throws away some of the hash bits that you went to so much trouble to compute. Consider instead choosing a prime hash table size and the % operator -- then all the hash bits will contribute to bucket selection, which may improve your spread.