Re: Common hash table implementation

Daniel Phillips
2001-07-23T14:21:02Z

On Sunday 22 July 2001 18:37, Larry McVoy wrote:
> On Sat, Jul 21, 2001 at 10:25:51PM +0200, Daniel Phillips wrote:
> > 1) How random is the hash
> > 2) How efficient is it
>
> The hash is not the only part to consider for performance. The rest
> of the code is important as well. The code I pointed you to has been
> really carefully tuned for performance.

Yes, I can see that. The linear congruential hash will be faster than
the CRC32 on most modern machines, where we have fast multiplies vs
multi-cycle table access.

If it's true that the CRC32 is actually less random as well, I'd
consider dropping the others and just going with the linear
congruential hash.

> And it can be made to be MP
> safe, SGI did that and managed to get 455,000 random fetches/second
> on an 8 way R4400 (each of these is about the same as the original
> Pentium at 150Mhz).

Did I mention that your linear congruential hash rated among the best
of all I've tested? It's possible it might be further improved along
the lines I suggested. I'll try this pretty soon.

--
Daniel