Excessive memory usage of large hash_maps

[Matt Austern]

On Nov 6, 2003, at 1:30 AM, pcarlini@unitus.it wrote:

> Quoting Paul Dubuc <pdubuc@cas.org>:
>
>> Hash containers are apparently resized on based on a table of prime 
>> numbers
>>
>> (__stl_prime_list) in stl_hashtable.h.  As a hash table grows space 
>> (number
>> of
>> buckets) is reallocated based on the next higher number in this list. 
>>  The
>> numbers roughly double with each increment.  This isn't noticable in 
>> the
>> lower
>> increments, but can result in a lot of wasted space in the larger 
>> ones.  Why
>>
>> should the size continue to double once we get above, say 98317?  
>> Couldn't
>> smaller increments be inserted here to conserve memory?  Better yet 
>> provide
> a
>>
>> nice way to override the __stl_next_prime() function?
>
> Hi Paul. Thanks for your suggestion.
>
> FYI, we are in the process (at least I am ;) of adapting the current
> __gnu_cxx::hash* code to provide an experimental implementation of Matt
> Austern standard proposal for hashed containers, as described in the 
> Library
> Technical Report, see:
>
> 	http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1456.html
>
> Please have a look, this is our reference for the project. I hope to 
> provide a
> detailed roadmap in a couple of weeks.


Didn't realize you were doing that!  I was planning to rewrite the TR1 
version
of hash tables once we'd set up the infrastructure for where we'll put 
TR
extensions.

I was planning to start from scratch, though, instead of using the old 
SGI
hash tables as a base.  The interfaces are similar, but they're just 
different
enough that I think lots of stuff will have to be rewritten anyway.  
The bucket
growth algorithm is one thing that will have to be changed completely, 
since
the TR1 version of hash tables allows users to control the load factor 
and
growth factor.

(I've already done one rewrite of hash tables, from when I was at AT&T.
Alas, for bureaucratic reasons we never got around to releasing it.)

			--Matt