Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.misc > #5324

Re: Relativistic hash tables, part 1: Algorithms

Show all headers | View raw

On 25/09/2014 9:49 AM, Rich wrote:
> http://lwn.net/SubscriberLink/612021/92c8ccb5b82d4d90/
>
>     Hash tables are heavily used within the kernel to speed access to
>     objects of interest. Using a hash table will be faster than, say, a
>     linear search through a single list, but there is always value in making
>     accesses faster yet. Quite a bit of work has been done toward this goal
>     over the years; for example, the use of read-copy-update (RCU) can allow
>     the addition and removal of items from a hash bucket list without
>     locking out readers. Some operations have proved harder to make
>     concurrent in that manner, though, with table resizing being near the
>     top of the list. As of 3.17, the Linux kernel has gotten around this
>     problem with an implementation of "relativistic hash tables" that can be
>     resized while lookups proceed concurrently. This article will describe
>     the algorithm that is used; a companion article will look at the kernel
>     API for these new hash tables.
>
>     One might wonder whether the resizing of hash tables is common enough to
>     be worth optimizing. As it turns out, picking the correct size for a
>     hash table is not easy; the kernel has many tables whose size is
>     determined at system initialization time with a combination of
>     heuristics and simple guesswork. But even if the initial guess is
>     perfect, workloads can vary over time. A table that was optimally sized
>     may, after a change, end up too small (and thus perform badly) or too
>     big (wasting memory). Resizing the table would fix these problems, but,
>     since that is hard to do without blocking access to the table, it tends
>     not to happen. The longer-term performance gains are just not seen to be
>     worth the short-term latency caused by shutting down access to the table
>     while it is resized.
>
>     ...
>

I don't like the RCU grace period concept, at least as it seems to be 
expressed.

It appears to require the identification of an upper bound on the 
elapsed time for any thread to complete traversal of a list.

I'd have thought access counters could be used.

Sylvia.

Back to comp.misc | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Relativistic hash tables, part 1: Algorithms Rich <rich@example.invalid> - 2014-09-24 23:49 +0000
  Re: Relativistic hash tables, part 1: Algorithms Sylvia Else <sylvia@not.at.this.address> - 2014-10-16 12:47 +1100

csiph-web