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