Subject: Re: New hash algorithm - FNV - for use in the kernel
To: ozan s. yigit <oz@zonzorp.canada.sun.com>
From: Luke Mewburn <lukem@wasabisystems.com>
List: tech-kern
Date: 11/29/2001 12:37:04
On Wed, Nov 28, 2001 at 11:42:41AM -0500, ozan s. yigit wrote:
> | I recently added <sys/fnv_hash.h> (from FreeBSD), which provides an
> | implementation of the Fowler / Noll / Vo (FNV) hash, as described at:
> | 	http://www.isthe.com/chongo/tech/comp/fnv/
> | 
> | I've done some initial investigation and testing of the effectiveness
> | of this hash algorithm, and I'm getting similar improvements that
> | Peter Wemm (of FreeBSD) found when he switched parts of FreeBSD over
> | to using the FNV hash.
> |
> | [etc]
> 
> i'm joining this discussion a bit late, so sorry if i say anything that
> has been said before. there are a number of very fast functions that do
> as well or better than Fowler/Vo[1] in speed and distribution, at least
> for basic string inputs, such as all filenames in netbsd /usr, using a
> table size of 8k. [tests on a voyager running netbsd 1.5, which i happen
> to have sitting next to me] here, i have dusted off a test harness i
> use for non-cryptographic hash functions [but i rarely see one that is
> worth testing.]

thanks for this stuff; much more informative than just making blanket
assertions without hard data.  any chance of making your test harness
available?


> i guess i should do a more comprehensive set of tests, with graphs to
> show that people have many more choices than the best-advertised function
> that is around.

good work!

btw; maybe you should take up your idea of having this stuff
published. :)

luke.