lkml.org 
[lkml]   [1999]   [Apr]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 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/

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.069 / U:1.308 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site