[lkml]   [2012]   [Apr]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [PATCH 3/3] x86, extable: Handle early exceptions
    On Thu, Apr 19, 2012 at 10:59 AM, H. Peter Anvin <> wrote:
    > I would argue that the O(1) hash makes things simpler as there is no
    > need to deal with collisions at all.

    Most of the O(1) hashes I have seen more than made up for the trivial
    complexity of a few linear lookups by making the hash function way
    more complicated.

    A linear probe with a step of one really is pretty simple. Sure, you
    might want to make the initial hash "good enough" to not often hit the
    probing code, but doing a few linear probes is cheap.

    In contrast, the perfect linear hashes do crazy things like having
    table lookups *JUST TO COMPUTE THE HASH*.

    Which is f*cking stupid, really. They'll miss in the cache just at
    hash compute time, never mind at hash lookup. The table-driven
    versions look beautiful in microbenchmarks that have the tables in the
    L1 cache, but for something like the exception handling, I can
    guarantee that *nothing* is in L1, and probably not even L2.

    So what you want is:
    - no table lookups for hashing
    - simple code (ie a normal "a multiply and a shift/mask or two") to
    keep the I$ footprint down too
    - you *will* take a cache miss on the actual hash table lookup, that
    cannot be avoided, but linear probing at least hopefully keeps it to
    that single cache miss even if you have to do a probe or two.

    Remember: this is very much a "cold-cache behavior matters" case. We
    would never ever call this in a loop, at most we have loads that get a
    fair amount of exceptions (but will go through the exception code, so
    the L1 is probably blown even then).


     \ /
      Last update: 2012-04-19 20:29    [W:0.023 / U:1.988 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site