Subject: Re: New hash algorithm - FNV - for use in the kernel
To: None <email@example.com, firstname.lastname@example.org>
From: Thor Lancelot Simon <email@example.com>
Date: 11/27/2001 18:43:52
On Tue, Nov 27, 2001 at 01:25:43PM -0800, Tom Spindler wrote:
> > > There is a potential issue however; FNV uses multiply (*) and xor (^),
> > > whereas a lot of the existing hashes on strings and buffers just use
> > > addition (+). Whilst FNV has much better distribution than the latter,
> > > it will be slower on platforms without hardware multiply. The question
> > > is as to whether the reduction in hash collisions (and the subsequent
> > > following of collision list chains) is effective on these systems.
> Perl uses the following for hashing strings; while it contains a
> multiply (* 33), it could be converted into a shift and an add pretty
> easily. (IIRC, there's been some discussion about the various hash
A few things in the kernel (mostly stuff I've done) use % (some prime) as
the hash function, obviously for numeric values. I was originally using
the ubiquitous &hashmask, but it was suggested to me that this was a poor
choice of hash function for the data in question (interface IP addresses)
so I switched. Then it was suggested to me that, of course, modulo isn't
exactly as fast as &...
...but it turned out that GCC is smart enough to do the obvious
optimization with the shift. If it can do % constant I'd be quite
surprised if it can't do * constant, but it's not exactly tough to
compile a quick example to assembly and check.
Thor Lancelot Simon firstname.lastname@example.org
And now he couldn't remember when this passion had flown, leaving him so
foolish and bewildered and astray: can any man?