It turns out that it can be trusted to always produce consistent results regardless of which compiler or optimization settings you're using. Here's a quick proof:
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
int64_t b = 1, j = 0;
while (j < num_buckets) {
b = j;
key = key * 2862933555777941757ULL + 1;
j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
}
return b;
}
key = key * 2862933555777941757ULL + 1;
Step 2:
double(1LL << 31) / double((key >> 33) + 1)
In order to understand what can happen, let's examine extreme inputs.
If key is 0, the denominator will be 1, and the result will be (double)0x80000000, which can be represented exactly. (A 64-bit float can exactly represent all integers in the range [-2^53, 2^53].)
If key is (2^64 - 1), then the denominator((key >> 33) + 1) is 0x80000000, which is equal to the numerator (1 << 31), so the result will be 1.
Let's plot this equation for all possible values of key: http://www.wolframalpha.com/input/?i=plot+%282%5E31%29+%2F+%...
(Wolfram Alpha doesn't understand bitshift notation, but that formula is equivalent to the C code.)
Step 3:
j = (b + 1) * ( /*...result from step 2...*/ );
'num_buckets' is an int32_t, so its max value is 0x7FFFFFFF.
The result from step 2 has a maximum possible value of (double)0x80000000 and a minimum possible value of 1.0.
(b + 1) is promoted to a double, which is then multiplied with step 2's result.
Since all of the following conditions are true...
- step 2's result has a max value of 0x80000000
- the final result must be less than 'num_buckets' to continue iterating
- the final result is less than 2^53 (the maximum integer that can be exactly represented by a 64-bit float)
- each iteration of the loop quantizes the final result from a 64-bit float to a 64-bit integer (by storing it into the variable 'j'), preventing error from accumulating
... then it must be true that this floating point arithmetic will always yield consistent results. It can't matter which compiler you use or which optimization level / strictness settings you choose.
(It's probably possible to trim this proof down, but since it gets the job done, I'm just going to post it as-is.)
EDIT: In fact, I'm pretty sure that the algorithm would still produce consistent results even if it tried to store integers larger than 2^53 into a 64-bit float. Even though that would be out of range, the truncation would still be consistent.
The reason why it's consistent is because at each iteration of the loop, it quantizes the intermediate 64-bit float result into a 64-bit integer, essentially flooring the result. This prevents small floating point errors from carrying over into the next iteration. A secondary reason why it's consistent is because the actual values being divided and multiplied are very small (less than 0x80000000). For small integers x and y, it seems like (uint64_t)((double)x / (double)y) will always truncate consistently regardless of compiler variation or floating point optimization settings.
Maybe (uint64_t)((double)x / (double)y) will always yield a consistent result regardless of compiler or optimization settings, even if x and y aren't small. But I'm definitely sure that (uint64_t)(9.0/5.0) will always result in 1, and (uint_64)t)(11.0/5.0) will always result in 2, etc, and in that case, x and y are small. So, since the max intermediate values are less than 0x80000000, it seems likely that there's no numerator/denominator combination that could cause inconsistent results if you switch compilers or float optimization settings, as long as numerator > denominator.