From owner-freebsd-fs  Thu Apr 24 17:12:24 1997
Return-Path: <owner-fs>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.5/8.8.5) id RAA11277
          for fs-outgoing; Thu, 24 Apr 1997 17:12:24 -0700 (PDT)
Received: from gatekeeper.tsc.tdk.com (root@gatekeeper.tsc.tdk.com [207.113.159.21])
          by hub.freebsd.org (8.8.5/8.8.5) with ESMTP id RAA11271
          for <fs@freebsd.org>; Thu, 24 Apr 1997 17:12:21 -0700 (PDT)
Received: from sunrise.gv.tsc.tdk.com (root@sunrise.gv.tsc.tdk.com [192.168.241.191])
          by gatekeeper.tsc.tdk.com (8.8.4/8.8.4) with ESMTP
	  id RAA00156; Thu, 24 Apr 1997 17:12:00 -0700 (PDT)
Received: from salsa.gv.tsc.tdk.com (salsa.gv.tsc.tdk.com [192.168.241.194])
	by sunrise.gv.tsc.tdk.com (8.8.5/8.8.5) with ESMTP id RAA24488;
	Thu, 24 Apr 1997 17:11:58 -0700 (PDT)
Received: (from gdonl@localhost)
	by salsa.gv.tsc.tdk.com (8.8.5/8.8.5) id RAA12811;
	Thu, 24 Apr 1997 17:11:57 -0700 (PDT)
From: Don Lewis <Don.Lewis@tsc.tdk.com>
Message-Id: <199704250011.RAA12811@salsa.gv.tsc.tdk.com>
Date: Thu, 24 Apr 1997 17:11:57 -0700
In-Reply-To: Eivind Eklund <eivind@dimaga.com>
       "Re: the namei cache..." (Apr 24,  3:09pm)
X-Mailer: Mail User's Shell (7.2.6 alpha(3) 7/19/95)
To: Eivind Eklund <eivind@dimaga.com>, Michael Hancock <michaelh@cet.co.jp>
Subject: Re: the namei cache...
Cc: fs@freebsd.org
Sender: owner-fs@freebsd.org
X-Loop: FreeBSD.org
Precedence: bulk

On Apr 24,  3:09pm, Eivind Eklund wrote:
} Subject: Re: the namei cache...
} 
} However, replacing the hash algorithm is certainly worthwhile - the present
} one is both slow and insensitive to interesting changes (e.g. swapping of
} characters).

I don't necessarily agree with slow (other than the divide at the end).
It *might* be worthwhile escapeing from the loop early on names that are
too long to cache, but since these are rare, the extra tests might be
too much of a penalty in the common case.

I think the current hash function does a poor job of distributing the
keys, especially if you have a large cache.  A directory containing
files with names up to 14 characters of all the characters < 128
can only distribute it's entries over at most 1778 hash buckets.  The
misc.jobs.offered directory on our news server, which contains 28325
files with 7 digit names, will only distribute its entries over 399
buckets.  It looks like we're very dependent on the v_id value to
give a good global distribution.

			---  Truck