Minimal bucket count in hashtable.h

[Robert Zeh]

Robert Zeh wrote:

> We are having trouble with the amount of memory that hash_set is using.
>
> After looking at the list of primes (which are used to determine the 
> bucket count) in ext/hashtable.h, it looks like the smallest number of 
> buckets that a hash can have is 53, because 53 is the first prime listed.
>
> We'd like to create a relatively large number of small hash sets with 
> their initial bucket sizes set to 8.  However, the 8 is bumped to 53 
> by hashtable::_M_initialize_buckets, and now the hash sets are no 
> longer quite so small.
>
> Is there any reason that primes in hashtable start with 53, rather 
> then, 7 or 13? I believe that many primes have been skipped so that 
> the bucket sizes will approximately double, but why was the lower 
> range left out?  Was someone worried about poor performance for the 
> initial resizing on an empty hash table? Doesn't the default bucket 
> count of 100 takes care of that case?
>
> If the primes 7 and 19 were added to __stl_prime_list users of the 
> default bucket count would never notice the change.  Users setting 
> bucket counts less then 53 would notice that the hash table was more 
> closely matching their request.
>
> Thanks,
> Robert Zeh
>
For our application, setting the initial bucket size to 6 and adding the 
primes 7 and 17 to the list in hashtable.h reduced the overall memory 
footprint by half.  It's still more then the std::set implementation, 
but by only 10% or so.

Robert Zeh