From owner-freebsd-fs  Thu Apr 24 13:17:00 1997
Return-Path: <owner-fs>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.5/8.8.5) id NAA28354
          for fs-outgoing; Thu, 24 Apr 1997 13:17:00 -0700 (PDT)
Received: from root.com (implode.root.com [198.145.90.17])
          by hub.freebsd.org (8.8.5/8.8.5) with ESMTP id NAA28349
          for <fs@freebsd.org>; Thu, 24 Apr 1997 13:16:57 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by root.com (8.8.5/8.6.5) with SMTP id NAA10732; Thu, 24 Apr 1997 13:18:33 -0700 (PDT)
Message-Id: <199704242018.NAA10732@root.com>
X-Authentication-Warning: implode.root.com: localhost [127.0.0.1] didn't use HELO protocol
To: Poul-Henning Kamp <phk@dk.tfs.com>
cc: fs@freebsd.org
Subject: Re: the namei cache... 
In-reply-to: Your message of "Thu, 24 Apr 1997 21:40:49 +0200."
             <1303.861910849@critter> 
From: David Greenman <dg@root.com>
Reply-To: dg@root.com
Date: Thu, 24 Apr 1997 13:18:33 -0700
Sender: owner-fs@freebsd.org
X-Loop: FreeBSD.org
Precedence: bulk

>In message <199704241934.MAA10488@root.com>, David Greenman writes:
>>>about 1/4th of the additions. Getting reed of the div wouldn't also be bad
>>>but might not be worth it.
>>
>>   Not worth it? At greater than 50 cycles, the divide is more expensive
>>than the entire add loop.
>
>But loosing the hash entirely is >even< faster, right ?  :-)

   Maybe. Here's the problem with your approach as I see it: On wcarchive,
we have about 44,000 files in the namei cache. The hash table size is
approximately 44,000 entries large (rounded up or down to the nearest
prime...I forget). This means that there is an average of about 1 file in
each hash bucket...or very little to search through. Of course there are
far fewer than 1 directory per file, so now if you change this so that all
of the files for a directory are on one list, then you're going to have to do
a lot more work to find it. I think the average directory length on wcarchive
is about 50 files or so, so this would be about 50 times more entries in the
list compared to the old hash table scheme.

-DG

David Greenman
Core-team/Principal Architect, The FreeBSD Project