Bounds Check Elimination with Fast-Range

August Nagro augustnagro at
Mon Nov 18 04:02:22 UTC 2019


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:


- August 


More information about the hotspot-dev mailing list