std::unordered_map and the % operator

[Ryan Lewis]

Hi,

My apologies I wrote this email late last night and it might not have
been clear.

My suggestion is that we make the process of modulus operator by the
bucket size more efficient. Specifically by avoiding the division.

ala:  - http://www.hackersdelight.org/magic.htm
and/or http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html

To begin with your last concern that modulus is not division: we can
clearly replace

hash%(number of buckets) with (number of buckets) - hash/(number of buckets);

now if we can replace the division with something faster that doesn't
stall the pipeline we are in good shape. Also, it might be the case
that in the process of computing a/b the modulus might show up. but
for now lets ignore that.

Luckily this is a well understood problem, see the notes above, but I
summarize from the second link here:

Suppose we are on a 32 bit bit machine and we wish to compute n/d:
here n is the hash value and d is the number of buckets.

Precompute these two numbers (e.g. once per rehash):
-  p = ceil( log_2( d))
-  m = ceil( 2^(32+p)/d) (this is a 33 bit number, keep only the
lowest 32 bits).

Now instead of the modulus, we do the division technique above, and
replace the division with:
- compute q = (m*n) >> 32 (this becomes one instruction on many processors)
- compute t = ((n-q) >> 2) + q (this is an overflow safe way of
compute (n+q) >> 1
- compute t >> (p-1)

There is even more efficient things to do depending on the specific
number, as you are probably aware most compilers do this for
constexpr's.

Best,
-rhl