From owner-freebsd-fs Thu Apr 24 05:07:22 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.5/8.8.5) id FAA03014 for fs-outgoing; Thu, 24 Apr 1997 05:07:22 -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 FAA03009 for ; Thu, 24 Apr 1997 05:07:19 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by root.com (8.8.5/8.6.5) with SMTP id FAA09111; Thu, 24 Apr 1997 05:08:55 -0700 (PDT) Message-Id: <199704241208.FAA09111@root.com> X-Authentication-Warning: implode.root.com: localhost [127.0.0.1] didn't use HELO protocol To: Poul-Henning Kamp cc: Michael Hancock , fs@freebsd.org Subject: Re: the namei cache... In-reply-to: Your message of "Thu, 24 Apr 1997 12:41:18 +0200." <801.861878478@critter> From: David Greenman Reply-To: dg@root.com Date: Thu, 24 Apr 1997 05:08:55 -0700 Sender: owner-fs@freebsd.org X-Loop: FreeBSD.org Precedence: bulk >>With hashing you can work on the hashing algorithm. Btw, what is the hash >>key now? vp+name[20]? > >directory vnode v_id + the regular namei hash. Calculating the hash is expensive since it involves doing a byte sum of all of the characters in the name, adding in the directory v_id, and dividing by a prime number. There's got to be a better way. I haven't carefully read what Poul-Henning is proposing, but the gist I got was that he intends to hang the file name cache entries off of the directory vnode? It seems to me that this works well for small directories and poorly for large directories unless you construct a binary tree and keep the entries sorted. Then the problem becomes managing the tree (keeping it balanced, etc), which itself can be expensive...although lookups happen far more often than creates and deletes. It's interesting that the single largest CPU consumer on wcarchive appears to be the namei cache lookups. I think the hash algorithm needs to be re-visited at the very least, perhaps changing the divide by a prime into some sort of xor of the filename characters (xored in pairs as int16's). -DG David Greenman Core-team/Principal Architect, The FreeBSD Project