Messages in this thread | | | Date | Wed, 8 Oct 2008 05:27:15 +0200 | From | Nick Piggin <> | Subject | Re: [patch][rfc] ddds: "dynamic dynamic data structure" algorithm, for adaptive dcache hash table sizing |
| |
On Tue, Oct 07, 2008 at 08:12:45PM -0700, Paul E. McKenney wrote: > 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 <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). > > IIRC, one of the weaknesses of rcuhashbash was that the elements had > to be copied in some cases.
Yes, I noticed that.
> Josh has been working on a variant that > (hopefully) allows elements to be moved without copying, as is required > by dcache.
So is it able to actually resize the hash table? If so, I couldn't quite see how it works; if not, I'd be interested to know what is the application to dcache. Josh?
Thanks, Nick
| |