Re: Improved dcache name hash

Bill Hawes (whawes@star.net)
Sat, 12 Sep 1998 09:22:07 -0400

Colin Plumb wrote:

> A trickier question is where to include the parent dentry
> pointer. The current code does this after the hash is computed
> on the name. It could be added in using this algorithm, just
> like it was a character, but that breaks some of the assumptions
> the hash is based on.
>
> An alternative which might do better is to include it at
> the *beginning*, in the initial hash value.
>
> Question: other than messing up the qstr abstraction, is there
> any reason why the dcache can't just have one kind of hash,
> a hash of the name plus the parent dentry?

Hi Colin,

The new hash looks interesting and it would be good to see some
comparisons of lookup times with the old and new. I recall that someone
did some tests indicating that the current scheme wasn't too bad, though
I'm sure it can be improved.

Putting the parent pointer into the hash in the beginning would likely
be a problem, as then you'd need to recompute hashes when the parents
change.

Probably a good starting point for comparison would be to gather some
stats on the evenness of the current hash chains, and then see what the
new algorithm can do.

Regards,
Bill

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/faq.html