Re: more on hash functions
Chuck Lever (cel@monkey.org)
Fri, 9 Apr 1999 19:06:03 -0400 (EDT)
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/