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

Linus Torvalds
2012-04-19T18:25:40Z

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