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
diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h b/libstdc++-v3/include/tr1/hashtable_policy.h
index 4ee6d45..67a1339 100644
--- a/libstdc++-v3/include/tr1/hashtable_policy.h
+++ b/libstdc++-v3/include/tr1/hashtable_policy.h
@@ -403,7 +403,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
std::size_t __n_ins) const;
- enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
+ enum { _S_n_primes = (sizeof(unsigned long) != 8 ? 256 : 256 + 48) - 1 };
float _M_max_load_factor;
float _M_growth_factor;
diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index a5e6520..dc0dab5 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[12]
- = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
+ static const unsigned char __fast_bkt[13]
+ = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
- if (__n <= 11)
+ if (__n <= 12)
{
_M_next_resize =
__builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
@@ -58,10 +58,22 @@ namespace __detail
constexpr auto __n_primes
= sizeof(__prime_list) / sizeof(unsigned long) - 1;
+ constexpr auto __prime_list_end = __prime_list + __n_primes;
const unsigned long* __next_bkt =
- std::lower_bound(__prime_list + 5, __prime_list + __n_primes, __n);
- _M_next_resize =
- __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+ std::lower_bound(__prime_list + 6, __prime_list_end, __n);
+
+ if (*__next_bkt == __n && __next_bkt != __prime_list_end)
+ ++__next_bkt;
+
+ if (__next_bkt == __prime_list_end)
+ // Set next resize to the max value so that we never try to rehash again
+ // as we already reach the biggest possible bucket number.
+ // Note that it might result in max_load_factor not being respected.
+ _M_next_resize = std::size_t(-1);
+ else
+ _M_next_resize =
+ __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+
return *__next_bkt;
}
diff --git a/libstdc++-v3/src/shared/hashtable-aux.cc b/libstdc++-v3/src/shared/hashtable-aux.cc
index 081bb12..7623b46 100644
--- a/libstdc++-v3/src/shared/hashtable-aux.cc
+++ b/libstdc++-v3/src/shared/hashtable-aux.cc
@@ -25,7 +25,7 @@
namespace __detail
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
- extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
+ extern const unsigned long __prime_list[] = // 256 or 256 + 48
{
2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
@@ -66,13 +66,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, 1725587117ul,
1866894511ul, 2019773507ul, 2185171673ul, 2364114217ul, 2557710269ul,
2767159799ul, 2993761039ul, 3238918481ul, 3504151727ul, 3791104843ul,
- 4101556399ul, 4294967291ul,
- // Sentinel, so we don't have to test the result of lower_bound,
- // or, on 64-bit machines, rest of the table.
-#if __SIZEOF_LONG__ != 8
- 4294967291ul
-#else
- 6442450933ul, 8589934583ul, 12884901857ul, 17179869143ul,
+ 4101556399ul, 4294967291ul
+#if __SIZEOF_LONG__ >= 8
+ ,6442450933ul, 8589934583ul, 12884901857ul, 17179869143ul,
25769803693ul, 34359738337ul, 51539607367ul, 68719476731ul,
103079215087ul, 137438953447ul, 206158430123ul, 274877906899ul,
412316860387ul, 549755813881ul, 824633720731ul, 1099511627689ul,
@@ -86,7 +82,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
288230376151711717ul, 576460752303423433ul,
1152921504606846883ul, 2305843009213693951ul,
4611686018427387847ul, 9223372036854775783ul,
- 18446744073709551557ul, 18446744073709551557ul
+ 18446744073709551557ul
#endif
};
_GLIBCXX_END_NAMESPACE_VERSION
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
new file mode 100644
index 0000000..6bd88fa
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc
@@ -0,0 +1,51 @@
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+//
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+template<typename _USet>
+ void test(std::size_t max)
+ {
+ bool test __attribute__((unused)) = true;
+ _USet us;
+ auto nb_reserved = us.bucket_count();
+ us.reserve(nb_reserved);
+ auto bkts = us.bucket_count();
+ for (int i = 0; i != max; ++i)
+ {
+ if (i == nb_reserved)
+ {
+ nb_reserved = bkts;
+ us.reserve(nb_reserved);
+ bkts = us.bucket_count();
+ }
+
+ us.insert(i);
+
+ VERIFY( us.bucket_count() == bkts );
+ }
+ }
+
+int main()
+{
+ test<std::unordered_set<int>>(150);
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
index 95cc1cd..eb1ad5d 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
@@ -41,7 +41,7 @@ void test01()
std::size_t thrown_exceptions = 0;
// Reduce max load factor.
- us.max_load_factor(us.max_load_factor() / 2);
+ us.max_load_factor(us.max_load_factor() / 4);
// At this point load factor is higher than max_load_factor because we can't
// rehash in max_load_factor call.
@@ -65,7 +65,7 @@ void test01()
catch (const __gnu_cxx::forced_error&)
{
// max load factor doesn't change.
- VERIFY( us.max_load_factor() == .5f );
+ VERIFY( us.max_load_factor() == .25f );
++thrown_exceptions;
}
