Bug#206416: dpkg package hash table insufficient

[Scott James Remnant <scott@netsplit.com>]

Falk Hueffner <falk.hueffner@student.uni-tuebingen.de> wrote:

> Daniel Silverstone <dsilvers@digital-scurf.org> writes:
> 
> > *hauls out...
> >  (a) Practical Algorithms for Programmers, Binstock & Rex
> >  (b) The Art of Computer Programming Vol 3. "Sorting and Searching", Knuth
> >  (c) Introduction to algorithms, Cormen, Leiserson & Rivest
> 
> Those all fall into "hash functions that really suck". IMHO it should
> be intuitively obvious that your hash function sucks when it is
> affected by the bucket size being a power of two, since that means the
> input value affects upper bits more than lower bits. See also
> http://burtleburtle.net/bob/hash/doobs.html
> 

All well and good, except the replacement FMV code is at least 20%
faster.

I've tested this patch on a ~2Ghz Athlon w/ 1GB RAM and on a
200Mhz Alpha w/ 64MB RAM and in both cases it gave between 20% and 30%
increase in speed of basic dpkg functions.

So if, as hash functions go, FMV "really sucks"; the current hash
function in dpkg must be a professional?

Scott
-- 
Have you ever, ever felt like this?
Had strange things happen?  Are you going round the twist?