Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

From: Linus Torvalds
Date: Thu Aug 02 2012 - 17:50:35 EST


On Thu, Aug 2, 2012 at 2:21 PM, Josh Triplett <josh@xxxxxxxxxxxxxxxx> wrote:
>
> Did GCC's generated code have worse differences than an immediate
> versus a fetched value?

Oh, *way* worse.

Nobody just masks the low bits. You have more bits than the low bits,
and unless you have some cryptographic hash (seldom) you want to use
them.

So no, it's not just as mask. For the dcache, it's

hash = hash + (hash >> D_HASHBITS);
return dentry_hashtable + (hash & D_HASHMASK);

so it's "shift + mask", and the constants mean less register pressure
and fewer latencies. One of the advantages of the L1 dcache code is
that the code gets *so* much simpler that it doesn't need a stack save
area at all, for example.

But as mentioned, the dcache L1 patch had other simplifications than
just the hash calculations, though. It doesn't do any loop over next
fields at all (it falls back to the slow case if it isn't a direct
hit), and it doesn't care about the d_compare() case (they will never
be added to the L1, since looking those things up is so slow that
there's no point). So there are other issues at play than just
avoiding the indirection to fetch base/mask/bitcount things and the
simplified hash calculation.

Not having a loop makes the register lifetimes simpler and again
causes less register pressure.

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/