Bug#206416: dpkg package hash table insufficient
Daniel Silverstone <email@example.com> 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.