Bounds Check Elimination with Fast-Range

[Florian Weimer]

* 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:

(Back-to-back multiplications probably are not.)

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

Does this really work?  I don't think so.

I think this kind of perturbation is quite expensive.  Arm's BITR should
be helpful here.  But even though this operation is commonly needed and
easily implemented in hardware, it's rarely found in CPUs.

Any scheme with another multiplication is probably not an improvement
over the multiply-shift-multiply-subtract sequence to implement modulo
for certain convenient bucket counts, and for that, we can look up
extensive analysis. 8-)

Thanks,
Florian