From: David Laight <David.Laight@btinternet.com>
Date: 11/28/2001 00:48:49
> A few things in the kernel (mostly stuff I've done) use % (some prime) as
> the hash function, obviously for numeric values.
Ah the old 'divide by prime' rule - where on earth did that come from!
If your hash function is any good masking out some bits is as good.
If you EXPECT to serach a list afterwards it isn't going to make
a big enough difference.....
> I was originally using
> the ubiquitous &hashmask, but it was suggested to me that this was a poor
> choice of hash function for the data in question (interface IP addresses)
> so I switched. Then it was suggested to me that, of course, modulo isn't
> exactly as fast as &...
Your interface or theirs!
I wrote the binary tree code to keep track of token ring source routes
- then tested it on the corparate ethernet network. We used to see broadcast
packets (from which you need to keep the route) from over 2000 stations.
> ...but it turned out that GCC is smart enough to do the obvious
> optimization with the shift. If it can do % constant I'd be quite
> surprised if it can't do * constant, but it's not exactly tough to
> compile a quick example to assembly and check.
But if you have a configurable multiplier (or divisor) then it can't do the
shortcut. (gcc will do divisions by constants by multplying by the reciprocal
as well - actually it isn't obvious that the 'mul' instruction wouldn't
sometimes be better!)