lkml.org 
[lkml]   [1999]   [Apr]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: more on hash functions
Iain> This random_table actually seems pretty reasonable to me: the
Iain> random_table is 512 bytes, which is a small fraction of P6's 16KB
Iain> L1 data cache. The four loads take four cycles' load slots, but
Iain> P6 probably uses a radix-4 or radix-8 integer multiplier, which
Iain> would take 9 or 5 cycles latency anyway.

I take it back. I tried putting random table hash functions into my
BDD code, and got slower results than the existing multiplicative
hashes. It appears that the bucket distribution didn't improve much
at all, and as you point out, computing the hash function is slow.
The loads don't appear to be the problem: most of the work is in
unpacking the bytes, which turns out to be more work than the multiply.

Bottom line: random table hash function is slower than multiplicative
hash function, bucket distribution is no better, so its a loss.

Sorry for the distraction.

-Iain

-
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    [from the cache]
©2003-2011 Jasper Spaans