Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
	id <S129170AbRBUXPO>; Wed, 21 Feb 2001 18:15:14 -0500
Received: (majordomo@vger.kernel.org) by vger.kernel.org
	id <S129181AbRBUXOz>; Wed, 21 Feb 2001 18:14:55 -0500
Received: from neon-gw.transmeta.com ([209.10.217.66]:57610 "EHLO
	neon-gw.transmeta.com") by vger.kernel.org with ESMTP
	id <S129170AbRBUXOO>; Wed, 21 Feb 2001 18:14:14 -0500
To: linux-kernel@vger.kernel.org
From: torvalds@transmeta.com (Linus Torvalds)
Subject: Re: [rfc] Near-constant time directory index for Ext2
Date: 21 Feb 2001 15:13:42 -0800
Organization: Transmeta Corporation
Message-ID: <971i36$180$1@penguin.transmeta.com>
In-Reply-To: <E14VNAU-00014j-00@the-village.bc.nu> <20010221023515.6DF8E18C99@oscar.casa.dyndns.org>
Sender: linux-kernel-owner@vger.kernel.org
X-Mailing-List: linux-kernel@vger.kernel.org

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
-
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/