Messages in this thread |  | | | Date | Mon, 24 Jun 2002 09:12:31 +0200 | | From | Helge Hafting <> | | Subject | Re: [Ext2-devel] Re: Shrinking ext3 directories |
| |
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 majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
|  |