* [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156)
@ 2018-09-13 6:43 François Dumont
2018-09-18 8:46 ` Jonathan Wakely
0 siblings, 1 reply; 8+ messages in thread
From: François Dumont @ 2018-09-13 6:43 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 993 bytes --]
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
[-- Attachment #2: 87135.patch --]
[-- Type: text/x-patch, Size: 3287 bytes --]
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;
}
}
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156)
2018-09-13 6:43 [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156) François Dumont
@ 2018-09-18 8:46 ` Jonathan Wakely
2018-09-18 21:24 ` François Dumont
0 siblings, 1 reply; 8+ messages in thread
From: Jonathan Wakely @ 2018-09-18 8:46 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156)
2018-09-18 8:46 ` Jonathan Wakely
@ 2018-09-18 21:24 ` François Dumont
2018-09-19 9:16 ` Jonathan Wakely
2018-09-19 11:21 ` Jonathan Wakely
0 siblings, 2 replies; 8+ messages in thread
From: François Dumont @ 2018-09-18 21:24 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
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)
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156)
2018-09-18 21:24 ` François Dumont
@ 2018-09-19 9:16 ` Jonathan Wakely
2018-09-19 11:21 ` Jonathan Wakely
1 sibling, 0 replies; 8+ messages in thread
From: Jonathan Wakely @ 2018-09-19 9:16 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156)
2018-09-18 21:24 ` François Dumont
2018-09-19 9:16 ` Jonathan Wakely
@ 2018-09-19 11:21 ` Jonathan Wakely
2018-09-19 16:24 ` François Dumont
2018-09-21 16:17 ` François Dumont
1 sibling, 2 replies; 8+ messages in thread
From: Jonathan Wakely @ 2018-09-19 11:21 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156)
2018-09-19 11:21 ` Jonathan Wakely
@ 2018-09-19 16:24 ` François Dumont
2018-09-21 16:17 ` François Dumont
1 sibling, 0 replies; 8+ messages in thread
From: François Dumont @ 2018-09-19 16:24 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156)
2018-09-19 11:21 ` Jonathan Wakely
2018-09-19 16:24 ` François Dumont
@ 2018-09-21 16:17 ` François Dumont
2018-09-21 17:13 ` Jonathan Wakely
1 sibling, 1 reply; 8+ messages in thread
From: François Dumont @ 2018-09-21 16:17 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 4192 bytes --]
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.
>
>
>
[-- Attachment #2: 87135.patch --]
[-- Type: text/x-patch, Size: 2456 bytes --]
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;
}
}
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156)
2018-09-21 16:17 ` François Dumont
@ 2018-09-21 17:13 ` Jonathan Wakely
0 siblings, 0 replies; 8+ messages in thread
From: Jonathan Wakely @ 2018-09-21 17:13 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2018-09-21 16:49 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-09-13 6:43 [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156) François Dumont
2018-09-18 8:46 ` Jonathan Wakely
2018-09-18 21:24 ` François Dumont
2018-09-19 9:16 ` Jonathan Wakely
2018-09-19 11:21 ` Jonathan Wakely
2018-09-19 16:24 ` François Dumont
2018-09-21 16:17 ` François Dumont
2018-09-21 17:13 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).