LKML Archive on
help / color / mirror / Atom feed
From: Nick Piggin <>
To: "Michael K. Edwards" <>
Cc: Zach Brown <>,
	Linux Kernel Mailing List <>,
	Davide Libenzi <>,
	"Paul E. McKenney" <>
Subject: Re: [rfc][patch] dynamic resizing dentry hash using RCU
Date: Sat, 24 Feb 2007 02:52:44 +0100	[thread overview]
Message-ID: <> (raw)
In-Reply-To: <>

On Fri, Feb 23, 2007 at 05:31:30PM -0800, Michael K. Edwards wrote:
> On 2/23/07, Zach Brown <> wrote:
> >I'd love to see a generic implementation of RCU hashing that
> >subsystems can then take advantage of.  It's long been on the fun
> >side of my todo list.  The side I never get to :/.
> There's an active thread on netdev about implementing an RCU hash.
> I'd suggest a 2-left (or possibly even k-left) hash for statistical
> reasons discussed briefly there, and in greater depth in a paper by
> Michael Mitzenmacher at
> Despite his paper's emphasis on hardware parallelism, there's a bigger
> win associated with Poisson statistics and decreasing occupation
> fraction (and therefore collision probability) in successive hashes.

Thanks for the link, I'll take a look.

I'm *pretty* sure that my algorithm will work with any kind of data
structure. It could even change from one to another completely different
data structure.

The important point is that, when a switch is in progress, the data
structure effectively becomes the union of the old and the new. Readers
insert items only into the new structure, but it is implicit that they
have checked for collisions in the union (in the case where collisions are

And finally, (you probably gathered this, but I'll just make it clear),
I haven't implemented a lockless hash lookup. The dcache already has this.
My algorithm is a lockless dynamic data structure switch, rather than
having anything specifically to do with a specific type of hash, or even
a hash at all. So yes, it should be applicable to resizing a 2-left hash or


  reply	other threads:[~2007-02-24  1:52 UTC|newest]

Thread overview: 20+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-02-23 15:37 Nick Piggin
2007-02-23 16:31 ` Eric Dumazet
2007-02-24  1:08   ` Nick Piggin
2007-02-23 17:25 ` Zach Brown
2007-02-24  1:26   ` Nick Piggin
2007-02-24  2:07     ` Nick Piggin
2007-02-24  1:31   ` Michael K. Edwards
2007-02-24  1:52     ` Nick Piggin [this message]
2007-02-24  4:07 ` KAMEZAWA Hiroyuki
2007-02-24  5:15   ` Nick Piggin
2007-02-24  4:24 ` William Lee Irwin III
2007-02-24  5:09   ` Nick Piggin
2007-02-24 22:56     ` William Lee Irwin III
2007-02-25  0:56       ` David Miller
2007-02-25  2:15         ` William Lee Irwin III
2007-02-25  6:21 ` Paul E. McKenney
2007-03-05  4:11 ` David Miller
2007-03-05  4:27   ` Nick Piggin
2007-03-05  4:38     ` David Miller
2007-03-05  4:42     ` Nick Piggin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \ \ \
    --subject='Re: [rfc][patch] dynamic resizing dentry hash using RCU' \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).