Re: [rfc] Near-constant time directory index for Ext2

[torvalds@transmeta.com (Linus Torvalds)]

In article <20010221023515.6DF8E18C99@oscar.casa.dyndns.org>,
Ed Tomlinson  <tomlins@cam.org> wrote:
>
>The default in reiserfs is now the R5 hash, but you are right that lots of efforts went 
>into finding this hash.  This includes testing various hashes on real directory 
>structures to see which one worked best.  R5 won.

That's interesting.  The R5 hash is easily also the only one of the
reiser hashes that might be useable for the generic VFS hashing.  It's
not so different in spirit from the current one, and if you've done the
work to test it, it's bound to be a lot better.

(The current VFS name hash is probably _really_ stupid - I think it's
still my original one, and nobody probably ever even tried to run it
through any testing.  For example, I bet that using a shift factor of 4
is really bad, because it evenly divides a byte, which together with the
xor means that you can really easily generate trivial bad cases). 

What did you use for a test-case? Real-life directory contents? Did you
do any worst-case analysis too?

		Linus