Date: Thu, 24 Apr 1997 15:09:59 +0200 From: Eivind Eklund <eivind@dimaga.com> To: Michael Hancock <michaelh@cet.co.jp> Cc: fs@freebsd.org Subject: Re: the namei cache... Message-ID: <3.0.32.19970424150956.01100be0@dimaga.com>
next in thread | raw e-mail | index | archive | help
At 09:30 PM 4/24/97 +0900, Michael Hancock wrote: >On Thu, 24 Apr 1997, David Greenman wrote: > >> 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). > >I don't think you need to even look at all the characters. You can take >the first and last and couple in the middle. To get the middle ones, >instead of dividing the length by 2 do a bit shift on the length. Then >xor the 2 pairs. Any hash guru's on the list? Experimenting with this is easy if we pull the hash code out into a seperate file - we can just run it against a find on a 'normal machine'. I don't know how much just adding the last and first characters will buy us, as finding the end of the string still include parsing the entire string. However, replacing the hash algorithm is certainly worthwhile - the present one is both slow and insensitive to interesting changes (e.g. swapping of characters). A speedup could be to use an algorithm that work on words instead of bytes; however, this mean that a read-overrun of up to three bytes _must be tolerable_. This can only work as long as we control the implementation. Testing for zero-termination is fairly easy - the following expression will do it, assuming a 2s complement machine, a 32-bit word, and 8-bit chars. ((w-0x01010101)&~w&0x80808080) Unfortuneatly, a test for both / and NUL is over twice as expensive, involving xors to change / to NUL and double tests :-( I haven't got time to test right now (will see if I can do it later tonight), but that should give anybody interesting in trying enough information to have a go. The original code is in sys/kern/vfs_lookup.c (for anybody that hasn't looked yet) Eivind Eklund perhaps@yes.no http://maybe.yes.no/perhaps/ eivind@freebsd.org
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3.0.32.19970424150956.01100be0>