Bounds Check Elimination with Fast-Range

[John Rose]

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));