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

[Josh Triplett <josh@xxxxxxxxxxxxxxxx>]

On Thu, Aug 02, 2012 at 11:08:06AM -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 10:59 AM, Josh Triplett <josh@xxxxxxxxxxxxxxxx> wrote:
> >
> > You shouldn't have any extra indirection for the base, if it lives
> > immediately after the size.
> 
> Umm. You *always* have the extra indirection. Because you have that allocation.
> 
> So you have to follow the pointer to get the base/size, because they
> aren't compile/link-time constants.

Sorry, I should clarify what I meant: you'll have a total of one extra
indirection, not two.  You have to follow the pointer to get to both the
size and the buckets.  However, I would *hope* that you'd keep that line
in cache during any repeated activity using that hash table, which ought
to eliminate the cost of the indirection.  Does that line really get
evicted from cache entirely by the time you touch the dcache again?

> The cache misses were noticeable in macro-benchmarks, and in
> micro-benchmarks the smaller L1 hash table means that things fit much
> better in the L2.
>
> It really improved performance. Seriously. Even things like "find /"
> that had a lot of L1 misses ended up faster, because "find" is
> apparently pretty moronic and does some things over and over. For
> stuff that fit in the L1, it qas quite noticeable.
> 
> Of course, one reason for the speedup for the dcache was that I also
> made the L1 only contain the simple cases (ie no "d_compare" thing
> etc), so it speeded up dcache lookups in other ways too. But according
> to the profiles, it really looked like better cache behavior was one
> of the bigger things.

Seems like avoiding some of the longer paths through the dcache code
would also improve your cache behavior.  But in any case, I can easily
believe that the small L1 cache provides a win.

> Trust me: every problem in computer science may be solved by an
> indirection, but those indirections are *expensive*. Pointer chasing
> is just about the most expensive thing you can do on modern CPU's.

By that argument, it might make sense to make the L1 cache a closed hash
table and drop the chaining, to get rid of one more indirection, or
several.

Does your two-level dcache handle eviction?

Mind posting the WIP patches?

- Josh Triplett
--
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/