Date: Thu, 24 Apr 1997 20:24:11 +0300 (EEST) From: Narvi <narvi@haldjas.folklore.ee> To: David Greenman <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: <Pine.BSF.3.95.970424200621.17927A-100000@haldjas.folklore.ee> In-Reply-To: <199704241208.FAA09111@root.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, 24 Apr 1997, David Greenman wrote: > >>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 How about not adding byte values but say, long values? We may have to keep upto 3 bytes of additional space (avoiding overuns) but get it done in about 1/4th of the additions. Getting reed of the div wouldn't also be bad but might not be worth it. Sander > 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?Pine.BSF.3.95.970424200621.17927A-100000>