Excessive memory usage of large hash_maps

[Paul Dubuc]

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. 
>  
> Paolo. 

Thanks very much for your response.  I did see that proposal and read parts of 
it when I did a Google search to research this problem.  But is there anything 
we can do to fix this problem in the mean time short of patching the header 
file?  (That's difficult for administrative reasons.)  If patching it is the 
best approach, would adding more prime numbers to the table be a good solution? 
  We have a cases when large hash tables temporarily increase size over  a given 
threshold, their size doubles and the process uses excessive memory.  It also 
appears that when one hash table is copied to another the large capacity is 
duplicated even though the number of elements in the source container may have 
decreased significantly below the high water mark.

-- 
Paul M. Dubuc                       mailto:pdubuc@cas.org
Room 4349B                          (614) 447-3600 x2692
http://www.purl.org/dubuc/cas/