Re: [PATCH 3/3] x86, extable: Handle early exceptions

[David Daney]

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@xxxxxxxxxxxxxxxxxxxx>  wrote:
>
> > On Thu, Apr 19, 2012 at 10:59 AM, H. Peter Anvin<hpa@xxxxxxxxx>  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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/