lkml.org 
[lkml]   [2002]   [Jun]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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/

\
 
 \ /
  Last update: 2005-03-22 13:27    [from the cache]
©2003-2011 Jasper Spaans