[lkml]   [2008]   [Oct]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [patch][rfc] ddds: "dynamic dynamic data structure" algorithm, for adaptive dcache hash table sizing
On Wed, Oct 08, 2008 at 04:48:13AM +0200, Nick Piggin wrote:
> On Tue, Oct 07, 2008 at 02:08:25PM -0700, David Miller wrote:
> > From: Nick Piggin <>
> > 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).

IIRC, one of the weaknesses of rcuhashbash was that the elements had
to be copied in some cases. Josh has been working on a variant that
(hopefully) allows elements to be moved without copying, as is required
by dcache.

Thanx, Paul

 \ /
  Last update: 2008-10-08 05:15    [W:0.041 / U:24.632 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site