Re: [Ext2-devel] Re: Shrinking ext3 directories

From: Helge Hafting (
Date: Mon Jun 24 2002 - 02:12:31 EST

Daniel Phillips wrote:

> Hashing in htree doesn't work like that - what you're thinking about
> is a traditional fixed-size hash table. HTree is a btree that uses
> hashes of names as keys. Each block has a variable amount of the key
> space assigned to it, initially just one block for the entire key
> space. When that block fills up, its entries and its key space are
> split into two, then those blocks start to fill up, get split, and
> so on.
Very interesting, thanks!

> A hash function that distributes keys better should give somewhat
> better performance, and that has indeed been my experience. But
> in the case of half-MD4, the improvement we get from better
> distribution is wiped out by the higher cost of computing the hash
> function.[1] Which is not to say that the work is without value.
> The beautiful distribution given by the half-MD4 hash gives us
> something to aim at, we just have to be more efficient about it.
There is a way to measure the effect of the better but slower
hash. Add "time-wasting" code to the faster hash so
it gets exactly as slow as MD4. Then run benchmarks and
see the effects of the better distribution undisturbed.

Helge Hafting
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Sun Jun 30 2002 - 22:00:06 EST