Messages in this thread | | | Date | Thu, 19 Apr 2012 13:17:14 -0700 | From | David Daney <> | Subject | Re: [PATCH 3/3] x86, extable: Handle early exceptions |
| |
On 04/19/2012 11:55 AM, H. Peter Anvin wrote: > Either way I suggest picking up David's presorting patchset since it is already done and use its infrastructure for any further improvements. >
It does have the advantage of already being implemented. There was a little feedback on the kbuild portions of the patch.
If you would like, I will send an updated version of the patch.
> As far as a linear probe you get an average of n lookups with a packing density of 1-1/n so you are right; a linear probe with a density of say 1/2 is probably best. >
I usually see exception table sizes on the order of 2^10 entries, so I have to wonder how much you really gain from an O(1) implementation.
David Daney
> Linus Torvalds<torvalds@linux-foundation.org> wrote: > >> On Thu, Apr 19, 2012 at 10:59 AM, H. Peter Anvin<hpa@zytor.com> 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). >> >> Linus >
| |