Re: Minimal bucket count in hashtable.h

[Matt Austern <austern at gmail dot com>]

On Mon, 28 Mar 2005 12:15:00 -0600, Robert Zeh <rzeh@efs-us.com> wrote:
> 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.

At this point, I think, the real answer is that hash_set is no longer
being actively maintained.  You might want to consider the new
unordered_set instead.

                             --Matt