Bounds Check Elimination with Fast-Range

[Vladimir Ivanov]

(CCing hotspot-compiler-dev at ...)

Thanks for the reference, August.

Indeed the proposed approach looks very promising.

I don't think range-check elimination in C2 can optimize such code shape 
(haven't verified it with test cases yet though). Filed an RFE for it:
   https://bugs.openjdk.java.net/browse/JDK-8234333

It looks like it should be pretty straightforward to cover this 
particular case.

Also, it's worth looking at how Graal handles it and file a separate RFE 
if it doesn't optimize it well.

Best regards,
Vladimir Ivanov

On 18.11.2019 07:02, August Nagro wrote:
> 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/
>