Bounds Check Elimination with Fast-Range
John Rose
john.r.rose at oracle.com
Mon Nov 18 17:45:38 UTC 2019
On Nov 18, 2019, at 5:10 AM, Florian Weimer <fweimer at redhat.com> wrote:
>
>>
>> The idea is that, given (int) hash h and (int) size N, then ((long) h)
>> * N) >>> 32 is a good mapping.
>
> I looked at this in the past weeks in a different context, and I don't
> think this would work because we have:
That technique appears to require either a well-conditioned hash code
(which is not the case with Integer.hashCode) or else a value of N that
performs extra mixing on h. (So a very *non-*power-of-two value of N
would be better here, i.e., N with larger popcount.)
A little more mixing should help the problem Florian reports with a
badly conditioned h. Given this:
int fr(int h) { return (int)(((long)h * N) >>> 32); }
int h = x.hashCode();
//int bucket = fr(h); // weak if h is badly conditioned
then, assuming multiplication is cheap:
int bucket = fr(h * M); // M = 0x2357BD or something
or maybe something fast and sloppy like:
int bucket = fr(h + (h << 8));
or even:
int bucket = fr(h) ^ (h & (N-1));
More information about the hotspot-dev
mailing list