Re: more on hash functions

Janos Farkas (chexum@shadow.banki.hu)
Sat, 10 Apr 1999 08:51:27 +0200


On 1999-04-09 at 19:06:03, Chuck Lever wrote:
> 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.

[About '030 again]

Sorry, missed it; its two cycles for every additional memory access, in
most circumstances. This is the difference even between an instruction
operating in registers and the same doing it from/to memory, and this is
how longer an instruction takes if it has more instruction words. It's
true even for 32-bit accesses on the right system (ie. 32-bit memory
bus -- common).

[Just to shortly recap: a multiplication is taking 28/44 cycles at worst,
(16/32 bit), and highly depends on the bit patterns; very roughly about
how much 1 bit is set in the multiplier (not true, just to get the picture)]

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/