Bounds Check Elimination with Fast-Range
vladimir.x.ivanov at oracle.com
Mon Nov 18 12:34:55 UTC 2019
(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:
It looks like it should be pretty straightforward to cover this
Also, it's worth looking at how Graal handles it and file a separate RFE
if it doesn't optimize it well.
On 18.11.2019 07:02, August Nagro wrote:
> 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.
> - August
> : https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
More information about the hotspot-dev