[lkml]   [1999]   [Apr]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    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.


    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:51    [W:0.019 / U:30.944 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site