lkml.org 
[lkml]   [2012]   [Aug]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC 1/4] hashtable: introduce a small and naive hashtable
On Thu, Aug 02, 2012 at 10:32:13AM -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 9:40 AM, Eric W. Biederman <ebiederm@xmission.com> wrote:
> >
> > For a trivial hash table I don't know if the abstraction is worth it.
> > For a hash table that starts off small and grows as big as you need it
> > the incent to use a hash table abstraction seems a lot stronger.
>
> I'm not sure growing hash tables are worth it.
>
> In the dcache layer, we have an allocated-at-boot-time sizing thing,
> and I have been playing around with a patch that makes the hash table
> statically sized (and pretty small). And it actually speeds things up!
>
> A statically allocated hash-table with a fixed size is quite
> noticeably faster, because you don't have those extra indirect reads
> of the base/size that are in the critical path to the actual lookup.
> So for the dentry code I tried a small(ish) direct-mapped fixed-size
> "L1 hash" table that then falls back to the old dynamically sized one
> when it misses ("main memory"), and it really does seem to work really
> well.

You shouldn't have any extra indirection for the base, if it lives
immediately after the size. You should only have a single extra
indirection for the size, and in a workload that uses that hash table
heavily, I'd hope that cache line sticks around.

Also, if you want to use a fixed-size "L1" hash table to reduce
indirections, you might as well use a non-chaining hash table to
eliminate another few indirections.

> The reason it's not committed in my tree is that the filling of the
> small L1 hash is racy for me right now (I don't want to take any locks
> for filling the small one, and I haven't figured out how to fill it
> racelessly without having to add the sequence number to the hash table
> itself, which would make it annoyingly bigger).

I'd be interested to see the performance numbers for an L1 hash that
doesn't cheat by skipping synchronization. :) If you benchmarked an L1
hash with no synchronization against the existing dcache with its pile
of synchronization, that would make a large difference in performance,
but not necessarily because of a single extra indirection.

> Anyway, what I really wanted to bring up was the fact that static hash
> tables of a fixed size are really quite noticeably faster. So I would
> say that Sasha's patch to make *that* case easy actually sounds nice,
> rather than making some more complicated case that is fundamentally
> slower and more complicated.

The current approach that Sasha and I have iterated on should make the
fixed-size case equally easy and efficient, while also making the
resizable case possible. Any particular reason not to use that
approach?

- Josh Triplett


\
 
 \ /
  Last update: 2012-08-02 20:41    [W:0.073 / U:0.336 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site