> 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.
i have done some profiling in the early days of the dcache code. It gave
near ideal distribution with the current hashing function. I have
implemented a hash that adds the parent pointer to the hash too, but it
made absolutely no difference for all kinds of testcases i tried. The
current hash already randomizes pretty well.
> 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.
not if you XOR it with the rest of the hash. Then the rehash is O(1). (the
effect of all childs can be XOR-ed off).
> 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.
yeah i posted a histogram computing patch some time ago on linux-kernel,
with some results too. The conclusion was: the hashing is pretty good,
although we could use assembly functions to do the hashing itself.
-- mingo
-
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