Date: Thu, 24 Apr 1997 15:41:12 +0200 From: Poul-Henning Kamp <phk@dk.tfs.com> To: dg@root.com Cc: Poul-Henning Kamp <phk@dk.tfs.com>, Michael Hancock <michaelh@cet.co.jp>, fs@freebsd.org Subject: Re: the namei cache... Message-ID: <332.861889272@critter> In-Reply-To: Your message of "Thu, 24 Apr 1997 05:08:55 PDT." <199704241208.FAA09111@root.com>
next in thread | previous in thread | raw e-mail | index | archive | help
In message <199704241208.FAA09111@root.com>, David Greenman writes: >>>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. I don't think that the tradeoff to a binary tree will make sense, but it may be worth a try. It's true that my scheme may penalize large directories, but I'm pretty convinced that "large" in this context may be quite a lot larger than one would think. If "large" is anything above 100 I think that we can pretty safely ignore it. It may also pay off to sort the lists by componentname, which will cut the number of comparisons in half. Making it a circleq and searching from whichever end is nearest can cut this further. > 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). It may actually be worth optimizing ".." out with special case code. If we added a "parent dir vnode" pointer to the vnodes, ".." can be taken out, and the namecache entries they occupy can be used for something more valuable. Another thing, try setting the size of the namecache to 1.5 * desiredvnodes instead of the 1:1 factor we use now. Ohh, and if you run the code I sent in the other email, please sysctl -bn debug.vfscachedump > somefile and send me that file for analysis. Poul-Henning -- Poul-Henning Kamp | phk@FreeBSD.ORG FreeBSD Core-team. http://www.freebsd.org/~phk | phk@login.dknet.dk Private mailbox. whois: [PHK] | phk@tfs.com TRW Financial Systems, Inc. Power and ignorance is a disgusting cocktail.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?332.861889272>