PR 71181 Avoid rehash after reserve

François Dumont frs.dumont@gmail.com
Sun May 22 15:16:00 GMT 2016


Hi

     To fix 71181 problem I propose to change how we deal with reserve 
called with pivot values that is to say prime numbers. Now _M_next_bkt 
always return a value higher than the input value. This way when 
reverse(97) is called we end up with 199 buckets and so enough space to 
store 97 values without rehashing.

     I have integrated in this patch several other enhancements on the 
same subject. Improvement of _M_next_resize management when reaching 
highest bucket number. Remove sentinel value in __prime_list, just need 
to limit range when calling lower_bound.

     PR libstdc++/71181
     * include/tr1/hashtable_policy.h (_S_n_primes): Minus 1 to avoid check
     on lower_bound call.
     * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
     Always return a value greater than input value. Set _M_next_resize to
     value when reaching highest prime number.
     * src/shared/hashtable-aux.cc (__prime_list): Remove sentinel value.
     * testsuite/23_containers/unordered_set/hash_policy/71181.cc: New.
     * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc:
     Adapt.

Tested under Linux x86_64, ok to commit ?

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 71181.patch
Type: text/x-patch
Size: 6810 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20160522/a4471283/attachment.bin>


More information about the Libstdc++ mailing list