| Message ID | 1ad7ad86-0f0c-e8b0-8f29-2b5303718988@gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | PR libstdc++/87135 Rehash only when necessary (LWG2156) | expand |
On 13/09/18 07:49 +0200, François Dumont wrote: >All changes limited to hashtable_c++0x.cc file. > >_Prime_rehash_policy::_M_next_bkt now really does what its comment was >declaring that is to say: > // Return a prime no smaller than n. > >_Prime_rehash_policy::_M_need_rehash rehash only when _M_next_size is >exceeded, not only when it is reach. > > PR libstdc++/87135 > * src/c++11/hashtable_c++0x.cc: > (_Prime_rehash_policy::_M_next_bkt): Return a prime no smaller than > requested size, but not necessarily greater. > (_Prime_rehash_policy::_M_need_rehash): Rehash only if target size is > strictly greater than next resize threshold. > * testsuite/23_containers/unordered_map/modifiers/reserve.cc: >Adapt test > to validate that there is no rehash as long as number of insertion is > lower or equal to the reserved number of elements. > >unordered_map tests successful, ok to commit once all other tests >completed ? > >François >diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >index a776a8506fe..ec6031b3f5b 100644 >--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >@@ -46,10 +46,10 @@ namespace __detail > { > // Optimize lookups involving the first elements of __prime_list. > // (useful to speed-up, eg, constructors) >- static const unsigned char __fast_bkt[13] >- = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >+ static const unsigned char __fast_bkt[] >+ = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; > >- if (__n <= 12) >+ if (__n < sizeof(__fast_bkt) / sizeof(unsigned char)) sizeof(unsigned char) is defined to be 1, always. I think this should be just sizeof(__fast_bkt), or if you're trying to guard against the type of __fast_bkt changing, then use sizeof(__fast_bkt) / sizeof(__fast_bkt[0])) OK for trunk with either of those, instead of sizeof(unsigned char). Thanks.
On 09/18/2018 10:41 AM, Jonathan Wakely wrote: > On 13/09/18 07:49 +0200, François Dumont wrote: >> All changes limited to hashtable_c++0x.cc file. >> >> _Prime_rehash_policy::_M_next_bkt now really does what its comment >> was declaring that is to say: >> // Return a prime no smaller than n. >> >> _Prime_rehash_policy::_M_need_rehash rehash only when _M_next_size is >> exceeded, not only when it is reach. >> >> PR libstdc++/87135 >> * src/c++11/hashtable_c++0x.cc: >> (_Prime_rehash_policy::_M_next_bkt): Return a prime no smaller than >> requested size, but not necessarily greater. >> (_Prime_rehash_policy::_M_need_rehash): Rehash only if target >> size is >> strictly greater than next resize threshold. >> * testsuite/23_containers/unordered_map/modifiers/reserve.cc: >> Adapt test >> to validate that there is no rehash as long as number of >> insertion is >> lower or equal to the reserved number of elements. >> >> unordered_map tests successful, ok to commit once all other tests >> completed ? >> >> François > >> diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >> b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >> index a776a8506fe..ec6031b3f5b 100644 >> --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >> +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >> @@ -46,10 +46,10 @@ namespace __detail >> { >> // Optimize lookups involving the first elements of __prime_list. >> // (useful to speed-up, eg, constructors) >> - static const unsigned char __fast_bkt[13] >> - = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >> + static const unsigned char __fast_bkt[] >> + = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >> >> - if (__n <= 12) >> + if (__n < sizeof(__fast_bkt) / sizeof(unsigned char)) > > sizeof(unsigned char) is defined to be 1, always. I also though it was overkill but there are so many platforms that I prefer to be caution. Good to know that it can't be otherwise. > > I think this should be just sizeof(__fast_bkt), or if you're trying to > guard against the type of __fast_bkt changing, then use > sizeof(__fast_bkt) / sizeof(__fast_bkt[0])) I committed with simply sizeof(__fast_bkt)
On 18/09/18 22:39 +0200, François Dumont wrote: >On 09/18/2018 10:41 AM, Jonathan Wakely wrote: >>On 13/09/18 07:49 +0200, François Dumont wrote: >>>All changes limited to hashtable_c++0x.cc file. >>> >>>_Prime_rehash_policy::_M_next_bkt now really does what its comment >>>was declaring that is to say: >>> // Return a prime no smaller than n. >>> >>>_Prime_rehash_policy::_M_need_rehash rehash only when _M_next_size >>>is exceeded, not only when it is reach. >>> >>> PR libstdc++/87135 >>> * src/c++11/hashtable_c++0x.cc: >>> (_Prime_rehash_policy::_M_next_bkt): Return a prime no smaller than >>> requested size, but not necessarily greater. >>> (_Prime_rehash_policy::_M_need_rehash): Rehash only if target >>>size is >>> strictly greater than next resize threshold. >>> * testsuite/23_containers/unordered_map/modifiers/reserve.cc: >>>Adapt test >>> to validate that there is no rehash as long as number of >>>insertion is >>> lower or equal to the reserved number of elements. >>> >>>unordered_map tests successful, ok to commit once all other tests >>>completed ? >>> >>>François >> >>>diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>index a776a8506fe..ec6031b3f5b 100644 >>>--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>@@ -46,10 +46,10 @@ namespace __detail >>> { >>> // Optimize lookups involving the first elements of __prime_list. >>> // (useful to speed-up, eg, constructors) >>>- static const unsigned char __fast_bkt[13] >>>- = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>>+ static const unsigned char __fast_bkt[] >>>+ = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>> >>>- if (__n <= 12) >>>+ if (__n < sizeof(__fast_bkt) / sizeof(unsigned char)) >> >>sizeof(unsigned char) is defined to be 1, always. > >I also though it was overkill but there are so many platforms that I >prefer to be caution. Good to know that it can't be otherwise. > >> >>I think this should be just sizeof(__fast_bkt), or if you're trying to >>guard against the type of __fast_bkt changing, then use >>sizeof(__fast_bkt) / sizeof(__fast_bkt[0])) > >I committed with simply sizeof(__fast_bkt) Thanks.
On 18/09/18 22:39 +0200, François Dumont wrote: >On 09/18/2018 10:41 AM, Jonathan Wakely wrote: >>On 13/09/18 07:49 +0200, François Dumont wrote: >>>All changes limited to hashtable_c++0x.cc file. >>> >>>_Prime_rehash_policy::_M_next_bkt now really does what its comment >>>was declaring that is to say: >>> // Return a prime no smaller than n. >>> >>>_Prime_rehash_policy::_M_need_rehash rehash only when _M_next_size >>>is exceeded, not only when it is reach. >>> >>> PR libstdc++/87135 >>> * src/c++11/hashtable_c++0x.cc: >>> (_Prime_rehash_policy::_M_next_bkt): Return a prime no smaller than >>> requested size, but not necessarily greater. >>> (_Prime_rehash_policy::_M_need_rehash): Rehash only if target >>>size is >>> strictly greater than next resize threshold. >>> * testsuite/23_containers/unordered_map/modifiers/reserve.cc: >>>Adapt test >>> to validate that there is no rehash as long as number of >>>insertion is >>> lower or equal to the reserved number of elements. >>> >>>unordered_map tests successful, ok to commit once all other tests >>>completed ? >>> >>>François >> >>>diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>index a776a8506fe..ec6031b3f5b 100644 >>>--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>@@ -46,10 +46,10 @@ namespace __detail >>> { >>> // Optimize lookups involving the first elements of __prime_list. >>> // (useful to speed-up, eg, constructors) >>>- static const unsigned char __fast_bkt[13] >>>- = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>>+ static const unsigned char __fast_bkt[] >>>+ = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>> >>>- if (__n <= 12) >>>+ if (__n < sizeof(__fast_bkt) / sizeof(unsigned char)) >> >>sizeof(unsigned char) is defined to be 1, always. > >I also though it was overkill but there are so many platforms that I >prefer to be caution. Good to know that it can't be otherwise. > >> >>I think this should be just sizeof(__fast_bkt), or if you're trying to >>guard against the type of __fast_bkt changing, then use >>sizeof(__fast_bkt) / sizeof(__fast_bkt[0])) > >I committed with simply sizeof(__fast_bkt) This caused some testsuite regressions: FAIL: 23_containers/unordered_set/hash_policy/71181.cc execution test /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc:42: void test(int) [with _USet = std::unordered_set<int>]: Assertion 'us.bucket_count() == bkts' failed. FAIL: 23_containers/unordered_set/hash_policy/load_factor.cc execution test /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc:50: void test() [with _USet = std::unordered_set<int>]: Assertion 'us.load_factor() <= us.max_load_factor()' failed. FAIL: 23_containers/unordered_set/hash_policy/prime_rehash.cc execution test /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc:37: void test01(): Assertion 'nxt == policy._M_next_bkt(mx)' failed.
On 09/19/2018 01:07 PM, Jonathan Wakely wrote: > On 18/09/18 22:39 +0200, François Dumont wrote: >> On 09/18/2018 10:41 AM, Jonathan Wakely wrote: >>> On 13/09/18 07:49 +0200, François Dumont wrote: >>>> All changes limited to hashtable_c++0x.cc file. >>>> >>>> _Prime_rehash_policy::_M_next_bkt now really does what its comment >>>> was declaring that is to say: >>>> // Return a prime no smaller than n. >>>> >>>> _Prime_rehash_policy::_M_need_rehash rehash only when _M_next_size >>>> is exceeded, not only when it is reach. >>>> >>>> PR libstdc++/87135 >>>> * src/c++11/hashtable_c++0x.cc: >>>> (_Prime_rehash_policy::_M_next_bkt): Return a prime no smaller >>>> than >>>> requested size, but not necessarily greater. >>>> (_Prime_rehash_policy::_M_need_rehash): Rehash only if target >>>> size is >>>> strictly greater than next resize threshold. >>>> * testsuite/23_containers/unordered_map/modifiers/reserve.cc: >>>> Adapt test >>>> to validate that there is no rehash as long as number of >>>> insertion is >>>> lower or equal to the reserved number of elements. >>>> >>>> unordered_map tests successful, ok to commit once all other tests >>>> completed ? >>>> >>>> François >>> >>>> diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> index a776a8506fe..ec6031b3f5b 100644 >>>> --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> @@ -46,10 +46,10 @@ namespace __detail >>>> { >>>> // Optimize lookups involving the first elements of __prime_list. >>>> // (useful to speed-up, eg, constructors) >>>> - static const unsigned char __fast_bkt[13] >>>> - = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>>> + static const unsigned char __fast_bkt[] >>>> + = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>>> >>>> - if (__n <= 12) >>>> + if (__n < sizeof(__fast_bkt) / sizeof(unsigned char)) >>> >>> sizeof(unsigned char) is defined to be 1, always. >> >> I also though it was overkill but there are so many platforms that I >> prefer to be caution. Good to know that it can't be otherwise. >> >>> >>> I think this should be just sizeof(__fast_bkt), or if you're trying to >>> guard against the type of __fast_bkt changing, then use >>> sizeof(__fast_bkt) / sizeof(__fast_bkt[0])) >> >> I committed with simply sizeof(__fast_bkt) > > > This caused some testsuite regressions: > > FAIL: 23_containers/unordered_set/hash_policy/71181.cc execution test > /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc:42: > void test(int) [with _USet = std::unordered_set<int>]: Assertion > 'us.bucket_count() == bkts' failed. > > FAIL: 23_containers/unordered_set/hash_policy/load_factor.cc execution > test > /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc:50: > void test() [with _USet = std::unordered_set<int>]: Assertion > 'us.load_factor() <= us.max_load_factor()' failed. > > FAIL: 23_containers/unordered_set/hash_policy/prime_rehash.cc > execution test > /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc:37: > void test01(): Assertion 'nxt == policy._M_next_bkt(mx)' failed. > > > I forgot I only run unordered_map tests. I'll run the others this evening and will fix those. François
Here is the patch complement. load_factor.cc failure revealed a bug in load factor management. Now computation of _M_next_resize is consistent throughout the different places where it is set. The 2 other tests only have to be adapted. PR libstdc++/87135 * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt): Use __builtin_floor to compute _M_next_resize. * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt. * testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc: Adapt. Now fully tested under x86_64. Ok to commit ? François On 09/19/2018 01:07 PM, Jonathan Wakely wrote: > On 18/09/18 22:39 +0200, François Dumont wrote: >> On 09/18/2018 10:41 AM, Jonathan Wakely wrote: >>> On 13/09/18 07:49 +0200, François Dumont wrote: >>>> All changes limited to hashtable_c++0x.cc file. >>>> >>>> _Prime_rehash_policy::_M_next_bkt now really does what its comment >>>> was declaring that is to say: >>>> // Return a prime no smaller than n. >>>> >>>> _Prime_rehash_policy::_M_need_rehash rehash only when _M_next_size >>>> is exceeded, not only when it is reach. >>>> >>>> PR libstdc++/87135 >>>> * src/c++11/hashtable_c++0x.cc: >>>> (_Prime_rehash_policy::_M_next_bkt): Return a prime no smaller >>>> than >>>> requested size, but not necessarily greater. >>>> (_Prime_rehash_policy::_M_need_rehash): Rehash only if target >>>> size is >>>> strictly greater than next resize threshold. >>>> * testsuite/23_containers/unordered_map/modifiers/reserve.cc: >>>> Adapt test >>>> to validate that there is no rehash as long as number of >>>> insertion is >>>> lower or equal to the reserved number of elements. >>>> >>>> unordered_map tests successful, ok to commit once all other tests >>>> completed ? >>>> >>>> François >>> >>>> diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> index a776a8506fe..ec6031b3f5b 100644 >>>> --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> @@ -46,10 +46,10 @@ namespace __detail >>>> { >>>> // Optimize lookups involving the first elements of __prime_list. >>>> // (useful to speed-up, eg, constructors) >>>> - static const unsigned char __fast_bkt[13] >>>> - = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>>> + static const unsigned char __fast_bkt[] >>>> + = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>>> >>>> - if (__n <= 12) >>>> + if (__n < sizeof(__fast_bkt) / sizeof(unsigned char)) >>> >>> sizeof(unsigned char) is defined to be 1, always. >> >> I also though it was overkill but there are so many platforms that I >> prefer to be caution. Good to know that it can't be otherwise. >> >>> >>> I think this should be just sizeof(__fast_bkt), or if you're trying to >>> guard against the type of __fast_bkt changing, then use >>> sizeof(__fast_bkt) / sizeof(__fast_bkt[0])) >> >> I committed with simply sizeof(__fast_bkt) > > > This caused some testsuite regressions: > > FAIL: 23_containers/unordered_set/hash_policy/71181.cc execution test > /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc:42: > void test(int) [with _USet = std::unordered_set<int>]: Assertion > 'us.bucket_count() == bkts' failed. > > FAIL: 23_containers/unordered_set/hash_policy/load_factor.cc execution > test > /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc:50: > void test() [with _USet = std::unordered_set<int>]: Assertion > 'us.load_factor() <= us.max_load_factor()' failed. > > FAIL: 23_containers/unordered_set/hash_policy/prime_rehash.cc > execution test > /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc:37: > void test01(): Assertion 'nxt == policy._M_next_bkt(mx)' failed. > > > diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index 462767612f0..b9b11ff4385 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -52,7 +52,7 @@ namespace __detail if (__n < sizeof(__fast_bkt)) { _M_next_resize = - __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); + __builtin_floor(__fast_bkt[__n] * (long double)_M_max_load_factor); return __fast_bkt[__n]; } @@ -75,7 +75,7 @@ namespace __detail _M_next_resize = std::size_t(-1); else _M_next_resize = - __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); + __builtin_floor(*__next_bkt * (long double)_M_max_load_factor); return *__next_bkt; } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc index 0270ea52b9c..ba783d26847 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc @@ -30,7 +30,7 @@ template<typename _USet> auto bkts = us.bucket_count(); for (int i = 0; i != threshold; ++i) { - if (i == nb_reserved) + if (i >= nb_reserved) { nb_reserved = bkts; us.reserve(nb_reserved); diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc index 7110a3afb39..916c5ad702c 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc @@ -26,20 +26,22 @@ void test01() { std::__detail::_Prime_rehash_policy policy; - for (std::size_t i = 1;;) + // Starts at 4 because 2 & 3 are two consecutives primes that make this test + // fail. + for (std::size_t i = 4;;) { auto nxt = policy._M_next_bkt(i); - if (nxt == i) + if (nxt <= i) { - // Equals only when reaching max. - constexpr auto mx = std::numeric_limits<std::size_t>::max() - 1; + // Lower or equals only when reaching max prime. + constexpr auto mx = std::numeric_limits<std::size_t>::max(); VERIFY( nxt == policy._M_next_bkt(mx) ); break; } VERIFY( nxt > i ); - i = nxt; + i = nxt + 1; } }
On 21/09/18 18:10 +0200, François Dumont wrote: >Here is the patch complement. > >load_factor.cc failure revealed a bug in load factor management. Now >computation of _M_next_resize is consistent throughout the different >places where it is set. > >The 2 other tests only have to be adapted. > > PR libstdc++/87135 > * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt): > Use __builtin_floor to compute _M_next_resize. > * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt. > * testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc: > Adapt. > >Now fully tested under x86_64. > >Ok to commit ? OK, thanks.
diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index a776a8506fe..ec6031b3f5b 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -46,10 +46,10 @@ namespace __detail { // Optimize lookups involving the first elements of __prime_list. // (useful to speed-up, eg, constructors) - static const unsigned char __fast_bkt[13] - = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; + static const unsigned char __fast_bkt[] + = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; - if (__n <= 12) + if (__n < sizeof(__fast_bkt) / sizeof(unsigned char)) { _M_next_resize = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); @@ -65,9 +65,8 @@ namespace __detail // iterator that can be dereferenced to get the last prime. constexpr auto __last_prime = __prime_list + __n_primes - 1; - // Look for 'n + 1' to make sure returned value will be greater than n. const unsigned long* __next_bkt = - std::lower_bound(__prime_list + 6, __last_prime, __n + 1); + std::lower_bound(__prime_list + 6, __last_prime, __n); if (__next_bkt == __last_prime) // Set next resize to the max value so that we never try to rehash again @@ -95,7 +94,7 @@ namespace __detail _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const { - if (__n_elt + __n_ins >= _M_next_resize) + if (__n_elt + __n_ins > _M_next_resize) { long double __min_bkts = (__n_elt + __n_ins) / (long double)_M_max_load_factor; diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/reserve.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/reserve.cc index e9cf7fd6f67..7f34325df87 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/reserve.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/reserve.cc @@ -18,23 +18,46 @@ // <http://www.gnu.org/licenses/>. #include <unordered_map> + #include <testsuite_hooks.h> void test01() { - const int N = 1000; - typedef std::unordered_map<int, int> Map; Map m; - m.reserve(N); - std::size_t bkts = m.bucket_count(); - for (int i = 0; i != N; ++i) + // Make sure max load factor is 1 so that reserved elements is directly + // the bucket count. + m.max_load_factor(1); + + int i = -1; + for (;;) { - m.insert(std::make_pair(i, i)); - // As long as we insert less than the reserved number of elements we - // shouldn't experiment any rehash. + m.reserve(m.bucket_count()); + + std::size_t bkts = m.bucket_count(); + + m.reserve(bkts); VERIFY( m.bucket_count() == bkts ); + + for (++i; i < bkts; ++i) + { + m.insert(std::make_pair(i, i)); + + // As long as we insert less than the reserved number of elements we + // shouldn't experiment any rehash. + VERIFY( m.bucket_count() == bkts ); + + VERIFY( m.load_factor() <= m.max_load_factor() ); + } + + // One more element should rehash. + m.insert(std::make_pair(i, i)); + VERIFY( m.bucket_count() != bkts ); + VERIFY( m.load_factor() <= m.max_load_factor() ); + + if (i > 1024) + break; } }