From owner-freebsd-hackers Sat Apr 26 12:57:55 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.5/8.8.5) id MAA05832 for hackers-outgoing; Sat, 26 Apr 1997 12:57:55 -0700 (PDT) Received: from phaeton.artisoft.com (phaeton.Artisoft.COM [198.17.250.50]) by hub.freebsd.org (8.8.5/8.8.5) with SMTP id MAA05825 for ; Sat, 26 Apr 1997 12:57:50 -0700 (PDT) Received: (from terry@localhost) by phaeton.artisoft.com (8.6.11/8.6.9) id MAA07467; Sat, 26 Apr 1997 12:53:17 -0700 From: Terry Lambert Message-Id: <199704261953.MAA07467@phaeton.artisoft.com> Subject: Re: namei & hash functions To: bde@zeta.org.au (Bruce Evans) Date: Sat, 26 Apr 1997 12:53:17 -0700 (MST) Cc: michaelh@cet.co.jp, msmith@atrad.adelaide.edu.au, hackers@hub.freebsd.org In-Reply-To: <199704261753.DAA12300@godzilla.zeta.org.au> from "Bruce Evans" at Apr 27, 97 03:53:57 am X-Mailer: ELM [version 2.4 PL24] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-hackers@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk > The mask version is the original 4.4Lite version. The prime version is > supposed to be a FreeBSD enhancement. One would hope that whoever changed > it did extensive tests :-). I was going to say the same. 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? It would be nice if people would test these things, beyond cookbooking; using a prime number-of-buckets is an obvious win; changing the hash algorithm is not obvious without testing, and not even then if there is any bias in the test data. Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.