Messages in this thread | | | Date | Fri, 9 Apr 1999 19:06:03 -0400 (EDT) | From | Chuck Lever <> | Subject | Re: more on hash functions |
| |
On Fri, 9 Apr 1999, Janos Farkas wrote: > 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-
thanks for the information. the missing piece, though, is how expensive is a multiplication operation relative to a couple of memory references? that's the direct trade-off when tuning these hash tables.
- Chuck Lever -- corporate: <chuckl@netscape.com> personal: <chucklever@netscape.net> or <cel@monkey.org>
The Linux Scalability project: http://www.citi.umich.edu/projects/citi-netscape/
- 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/
| |