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

    David