[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Bug#206416: dpkg package hash table insufficient

Daniel Silverstone <dsilvers@digital-scurf.org> writes:

> Attached is a patch which resizes the hashtable to 8191 chains of
> buckets. This is the largest prime less than 8192 and offers an
> improvement (over common things like dpkg -p or dpkg -l) of between
> 20 and 30 percent on the runtime. An option would be to reduce the
> table to only 4093 chains, but that reduces the gains to between 20
> and 25 percent.

There is no reason to make the number of buckets a prime number unless
either your hash function really sucks or you use double hashing. In
fact, it is a bad idea to do so, since modulo powers of two is a lot
faster than general modulo.


Reply to: