Messages in this thread | | | Date | Fri, 9 Apr 1999 09:30:35 +0200 | From | Janos Farkas <> | Subject | Re: more on hash functions |
| |
On 1999-04-08 at 12:51:27, Chuck Lever wrote: ... > > > #define _hashfn(dev,block) \ > > > ((((unsigned long)(block) * (40499UL * 65543UL)) >> 17) & bh_hash_mask)
> i think "breaks" is a little strong, though. perhaps it is slower on > older hardware. can you say *how* slow an integer multiplication by a > constant is on older SPARC CPUs or on, say, a 486, compared to memory > references on these machines? that's the real tradeoff here, and i think > it would be good to measure the difference under load before dismissing > the idea.
Although a bit unsolicited, I have 68030 numbers at hand; this is quite a bit old CPU, not the top of the line, bit IMHO the most affordable, in fact, about half of the registered Linux/m68k owners have machines with a '030 (well, me too :)
On this chip, a shift (independent of count) takes about 4-10 clock cycles, depending where the shifted operand is; arithmetic operations are similar (or a few cycles faster), but a multiplication takes 28 cycles (in register only) with 16 bit values, and 44 cycles for a 32-bit multiplication. I'm out of touch with the discussion, so I don't know how often do you want to compute hashes, and even less who cares about the '030; but I think it's quite common, and multiplication here takes significantly more time.
It's quite common therefore to optimize constant multiplies to bit-shifting, but it depends on the value if this is better.
Janos
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |