Date: Fri, 25 Apr 1997 11:08:55 +0300 (EEST) From: Narvi <narvi@haldjas.folklore.ee> To: David Greenman <dg@root.com> Cc: Poul-Henning Kamp <phk@dk.tfs.com>, fs@freebsd.org Subject: Re: the namei cache... Message-ID: <Pine.BSF.3.95.970425103425.26643A-100000@haldjas.folklore.ee> In-Reply-To: <199704241934.MAA10488@root.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, 24 Apr 1997, David Greenman wrote: > >about 1/4th of the additions. Getting reed of the div wouldn't also be bad > >but might not be worth it. > > Not worth it? At greater than 50 cycles, the divide is more expensive > than the entire add loop. Well, it seems that division has become more expensive over time. :-( The only processor related book I had around was about the 286 and there it cost only 28 so I figured we might be hard pressed coming up something as good while not taking up more than 3/4 of the cycles (= nearly not worth). How many bits do we exactly need? If we use 32 bit additions instead of 8 bit, we could take perhaps take some bits from each byte. For say 16bit value we could do for taking the lower 4 bits: hashvalue=((sum & 0x0f000000)>>24) | ((sum & 0x000f0000)>>12) | ((sum & 0x00000f00)<<4) | ((sum & 0x0000000f)<<12) Yes, it isn't probably a good way for derviving a hash from a string. On the positive side of things - when compiled, it will work on registers and only the fastest (or so they used to be) of operations, logic is used. Taking every other bit ((sum & 0x55550000)>>8 | (sum & 0x00005555) is another way. But I am not sure how they will fare in the real world - probably quite bad. Sander PS. There really are places where such hashes work. > > -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.970425103425.26643A-100000>