X-Debbugs-Cc: email@example.com On Wed, 2003-08-20 at 23:24, Falk Hueffner wrote: > Scott James Remnant <firstname.lastname@example.org> writes: > > > 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 > > > http://burtleburtle.net/bob/hash/doobs.html > > > > All well and good, except the replacement FMV code is at least 20% > > faster. > > I don't know FMV, but if it is a reasonable hash, it shouldn't depend > on prime table sizes. Maybe you could just also benchmark it with a > power-of-two table size? > FMV was a typo, FNV is the correct spelling of that abbreviation. By the way, the URL you provide specifically states that the author knows FNV to be faster than their own hashing algorithm. I've run some proper benchmarks against the two useful machines I had available to me. i686 Athlon 1.7Ghz 1GB RAM. dpkg knows about 904 packages alpha 250Mhz Alpha 64MB RAM. dpkg knows about 493 packages Each test was run 20 times, and the average time computed. The three hashing algorithms were existing The algorithm currently used by dpkg 1.10.10 FNV 8191 FNV algorithm with 8191 bins, Daniel's patch FNV 8192 as above, but with 8192 bins ("power of two") existing FNV 8191 FNV 8192 i686 alpha i686 alpha i686 alpha ------------ ------------ ------------ dpkg -l 2.999 5.672 1.850 4.871 1.913 4.998 dpkg -p dpkg 2.856 5.501 1.792 4.623 1.806 4.891 dpkg -p nonexistant 2.780 5.525 1.755 4.596 1.836 4.639 The results indicate the following improvements could be made by changing the algorithm. i686 alpha ---------------------- ---------------------- existing -> FNV 8191 60% speed increase 19% speed increase existing -> FNV 8192 55% speed increase 15% speed increase FNV 8191 -> FNV 8192 3% speed DECREASE 3% speed DECREASE Firstly this shows that the existing algorithm really needs to be replaced. The i686 is probably a fairly typical high-end user machine, and it gains a 50%-60% speed increase from the new algorithm! An "interesting hardware" machine like the alpha gains a 20% speed increase, and as Vince discovered ARM hardware gets a phenomenal speed boost! Secondly this shows that changing the number of bins from a prime-1 to a power of two DECREASES the speed of the algorithm by 3% on both i386 and alpha. Scott -- Have you ever, ever felt like this? Had strange things happen? Are you going round the twist?
Description: This is a digitally signed message part