Re: Patch: New hash function

[Jeff Sturm <jsturm at detroit dot appnet dot com>]

Andrew Haley wrote:
> Well, the old one wasn't 64-bit clean, so it had to change somehow.

Simply truncating the value to an `int' yields a reasonable distribution
though...

Tom talked once about simply dropping off the bottom 2/3 bits, which didn't seem
like such a bad idea.

> If we're going to hash a long address into a shorter int, we might as
> well do the reduction in a nonlinear way as long as it's not unduly
> slow.

OK.  I failed to notice that 0x7fffffff is prime.

> I had hoped that gcc would optimize most of this away, but it seems
> not.  I certainly didn't expect a call to the double divide routine,
> but a perusal of i386.md reveals that this will always happen even
> though it isn't necessary.

Yep.  Worse is that some machines don't support integer division in hardware,
though gcc emulates it on Alpha with a sequence of shl/sub/shr insns, and
apparently does a reasonably good job of it...

> Strictly speaking, to ensure that the result is correct mod (2^31 - 1)
> we'd need to do something like this:
> 
>   while (quo >> 32)
>     quo -= (0x7fffffffU * 2), count++;
> 
> but it seems hardly worthwhile.

Agreed; the branch insn and resulting stall would probably dominate the
calculation.

I tried simply

  return (jint) ((unsigned long) obj % 0x7fffffff);

which i386 handles much better (about 55 cycles on my PIII), and had no effect
on alpha.  It also doesn't need any conditional compilation.  Is that good
enough?  Are there any platforms where sizeof(long) != sizeof(void*) that we
care about?

--
Jeff Sturm
jeff.sturm@appnet.com