Messages in this thread | | | Date | Wed, 14 Apr 1999 19:54:05 -0700 | From | Iain McClatchie <> | Subject | Re: 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/
| |