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

Nick Piggin
2008-10-07T07:53:09Z

On Tue, Oct 07, 2008 at 03:18:27AM -0400, Christoph Hellwig wrote:
> >
> > 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 ;)
>
> Without even looking at the code I'd say geeting the dcache lookup data
> structure as a hash is the main problem here. Dcache lookup is
> fundamentally a tree lookup, with some very nice domain splits
> (superblocks or directories).

Dcache lookup is partially a tree lookup, but also how do you look up
entries in a given directory? That is not naturally a tree lookup. Could
be a per directory tree, though, or a hash, or trie.

Anyway, I don't volunteer to change that just yet ;)

> Mapping these back to a global hash is
> a rather bad idea, not just for scalability purposes.

I don't disagree. But it can be improved by dynamically resizing
until it is replaced. I guess it is also a demonstration of how to
implement the algorithm.

PID hash is probably another good one to convert.