Minimal bucklet count in hashtable.h

Robert Zeh rzeh@efs-us.com
Mon Mar 28 17:04:00 GMT 2005


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



More information about the Libstdc++ mailing list