PR libstdc++/87135 Rehash only when necessary (LWG2156)

Message ID 1ad7ad86-0f0c-e8b0-8f29-2b5303718988@gmail.com
State New
Headers show
Series
  • PR libstdc++/87135 Rehash only when necessary (LWG2156)
Related show

Commit Message

François Dumont Sept. 13, 2018, 5:49 a.m.
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

Comments

Jonathan Wakely Sept. 18, 2018, 8:41 a.m. | #1
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.
François Dumont Sept. 18, 2018, 8:39 p.m. | #2
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)
Jonathan Wakely Sept. 19, 2018, 9:13 a.m. | #3
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.
Jonathan Wakely Sept. 19, 2018, 11:07 a.m. | #4
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.
François Dumont Sept. 19, 2018, 4:20 p.m. | #5
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
François Dumont Sept. 21, 2018, 4:10 p.m. | #6
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;
     }
 }
Jonathan Wakely Sept. 21, 2018, 4:49 p.m. | #7
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.

Patch

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;
     }
 }