[lkml]   [2012]   [Aug]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [RFC 1/4] hashtable: introduce a small and naive hashtable
    On Thu, Aug 2, 2012 at 9:40 AM, Eric W. Biederman <> 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

    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).

    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.


     \ /
      Last update: 2012-08-02 20:01    [W:0.029 / U:3.416 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site