From owner-freebsd-hackers Sat Apr 26 18:42:44 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.5/8.8.5) id SAA22444 for hackers-outgoing; Sat, 26 Apr 1997 18:42:44 -0700 (PDT) Received: from parkplace.cet.co.jp (parkplace.cet.co.jp [202.32.64.1]) by hub.freebsd.org (8.8.5/8.8.5) with ESMTP id SAA22434 for ; Sat, 26 Apr 1997 18:42:40 -0700 (PDT) Received: from localhost (michaelh@localhost) by parkplace.cet.co.jp (8.8.5/CET-v2.1) with SMTP id BAA25261; Sun, 27 Apr 1997 01:42:13 GMT Date: Sun, 27 Apr 1997 10:42:13 +0900 (JST) From: Michael Hancock To: Terry Lambert cc: Bruce Evans , msmith@atrad.adelaide.edu.au, hackers@hub.freebsd.org Subject: Re: namei & hash functions In-Reply-To: <199704261953.MAA07467@phaeton.artisoft.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-hackers@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk On Sat, 26 Apr 1997, Terry Lambert wrote: > Knuth is very clear in "Sorting and Searching" that primacy helps to > disperse the bucket hits; however, once they are dispersed, it's not > a big deal what intelligence caused the dispersion, so long as you > don't get unbalanced hash chain lengths. I don't know if the shift > by 5 version is really inferior; it depends on whether or not it > causes disproportionate hash chain length between buckets, doesn't it? I was playing around with the strength of the intelligence that made the dispersion. I'm a little weak on Intel assembler so I wasn't sure how much faster a integer mult was over an integer divide. Anyway, I think phk's suggestion made earlier on the fs list makes sense. He's saying that there are a lot of stale entries sitting in the buckets so a larger hashsize would reduce the time throwing out stale entries that get in the way during the search aside from the obvious performance enhancement of a larger hash table. He's working on another approach that simplifies keeping the name cache and active vnode in sync by hanging the name cache of the directory vnode. A lot of us are saying that operations like article list request against innd would suffer with this approach. Mike Hancock