From owner-freebsd-fs Fri Apr 25 01:07:59 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.5/8.8.5) id BAA01214 for fs-outgoing; Fri, 25 Apr 1997 01:07:59 -0700 (PDT) Received: from haldjas.folklore.ee (Haldjas.folklore.ee [193.40.6.121]) by hub.freebsd.org (8.8.5/8.8.5) with ESMTP id BAA01181 for ; Fri, 25 Apr 1997 01:06:55 -0700 (PDT) Received: from localhost (narvi@localhost) by haldjas.folklore.ee (8.8.4/8.8.4) with SMTP id LAA27386; Fri, 25 Apr 1997 11:08:56 +0300 (EEST) Date: Fri, 25 Apr 1997 11:08:55 +0300 (EEST) From: Narvi Reply-To: Narvi To: David Greenman cc: Poul-Henning Kamp , fs@freebsd.org Subject: Re: the namei cache... In-Reply-To: <199704241934.MAA10488@root.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-fs@freebsd.org X-Loop: FreeBSD.org Precedence: bulk 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 >