Bug#206416: dpkg package hash table insufficient
Falk Hueffner <email@example.com> wrote:
> Daniel Silverstone <firstname.lastname@example.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
All well and good, except the replacement FMV code is at least 20%
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?
Have you ever, ever felt like this?
Had strange things happen? Are you going round the twist?