Re: [patch][rfc] ddds: "dynamic dynamic data structure" algorithm, for adaptive dcache hash table sizing

Nick Piggin
2008-10-08T02:48:13Z

On Tue, Oct 07, 2008 at 02:08:25PM -0700, David Miller wrote:
> From: Nick Piggin <npiggin@suse.de>
> Date: Tue, 7 Oct 2008 08:48:34 +0200
>
> > I'm cc'ing netdev because Dave did express some interest in using this for
> > some networking hashes, and network guys in general are pretty cluey when it
> > comes to hashes and such ;)
>
> Interesting stuff.
>
> Paul, many months ago, forwarded to me a some work done by Josh
> Triplett called "rcuhashbash" which had similar objectives. He did
> post it to linux-kernel, and perhaps even your ideas are inspired by
> his work, I don't know. :-)

Hmm yes I did see that. It's not too similar, as it focuses on re-keying
an existing element into the same hash table. ddds can't do that kind of
thing (the underlying data structure isn't visible to the algorithm, so
it can't exactly modify data structures in-place), although in another
sense it is more general because the transfer function could transfer
items into another hash table and re-key them as it goes (if it did that,
it could probably use Josh's "atomic" re-keying algorithm too).

But largely it does seem like they are orthogonal (if I'm reading
rcuhashbash correctly).