Date: Thu, 24 Apr 1997 05:08:55 -0700 From: David Greenman <dg@root.com> To: Poul-Henning Kamp <phk@dk.tfs.com> Cc: Michael Hancock <michaelh@cet.co.jp>, fs@freebsd.org Subject: Re: the namei cache... Message-ID: <199704241208.FAA09111@root.com> In-Reply-To: Your message of "Thu, 24 Apr 1997 12:41:18 %2B0200." <801.861878478@critter>
next in thread | previous in thread | raw e-mail | index | archive | help
>>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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199704241208.FAA09111>