Bounds Check Elimination with Fast-Range
augustnagro at gmail.com
Mon Nov 18 04:02:22 UTC 2019
The fast-range 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.
More information about the hotspot-dev