Bounds Check Elimination with Fast-Range

[August Nagro]

Hi!

The fast-range[1] algorithm is used to map well-distributed hash functions to a range of size N. It is ~4x faster than using integer modulo, and does not require the table to be a power of two. It is used by libraries like Tensorflow and the StockFish chess engine.

The idea is that, given (int) hash h and (int) size N, then ((long) h) * N) >>> 32 is a good mapping.

However, will the compiler be able to eliminate array range-checking? HashMap’s approach using power-of-two xor/mask was patched here: https://bugs.openjdk.java.net/browse/JDK-8003585.

Sincerely,

- August 

[1]: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/