Re: hashed waitqueues

Daniel Phillips
2002-01-05T02:41:08Z

On January 5, 2002 02:39 am, William Lee Irwin III wrote:
> 2 or 3 shift/adds is really not possible, the population counts of the
> primes in those ranges tends to be high, much to my chagrin.

It doesn't really have to be a prime, being relatively prime is also
good, i.e., not too many or too small factors. Surely there's a multiplier
in the right range with just two prime factors that can be computed with 3
shift-adds.

> I actually
> tried unrolling it by hand a few times, and it was slower than
> multiplication on i386 (and uncomfortably lengthy).

Right, it's not worth it unless you can get it down to a handful of
shift-adds. How does 2**17 - 1 (Mersenne prime #6) with right-shift by
(16 - bits) work?

> I believe to address architectures where multiplication is prohibitively
> expensive I should do some reading to determine a set of theoretically
> sound candidates for non-multiplicative hash functions and benchmark them.
> Knuth has some general rules about design but I would rather merely test
> some already verified by someone else and use the one that benches best
> than duplicate the various historical efforts to find good hash functions.

It would be nice if you could just look up good ones in a cookbook, but you
can't, that cookbook doesn't exist.

--
Daniel