@@ -420,8 +420,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Prime_rehash_policy::
_M_next_bkt(std::size_t __n) const
{
- const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
- + _S_n_primes, __n);
+ // Don't include the last prime in the search, so that anything
+ // higher than the second-to-last prime returns a past-the-end
+ // iterator that can be dereferenced to get the last prime.
+ const unsigned long* __p
+ = std::lower_bound(__prime_list, __prime_list + _S_n_primes - 1, __n);
_M_next_resize =
static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
return *__p;
@@ -434,11 +437,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_bkt_for_elements(std::size_t __n) const
{
const float __min_bkts = __n / _M_max_load_factor;
- const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
- + _S_n_primes, __min_bkts);
- _M_next_resize =
- static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
- return *__p;
+ return _M_next_bkt(__builtin_ceil(__min_bkts));
}
// Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
@@ -462,12 +461,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__min_bkts > __n_bkt)
{
__min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
- const unsigned long* __p =
- std::lower_bound(__prime_list, __prime_list + _S_n_primes,
- __min_bkts);
- _M_next_resize = static_cast<std::size_t>
- (__builtin_ceil(*__p * _M_max_load_factor));
- return std::make_pair(true, *__p);
+ return std::make_pair(true,
+ _M_next_bkt(__builtin_ceil(__min_bkts)));
}
else
{
@@ -46,22 +46,38 @@ 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);
return __fast_bkt[__n];
}
+ // Number of primes (without sentinel).
constexpr auto __n_primes
= sizeof(__prime_list) / sizeof(unsigned long) - 1;
+
+ // Don't include the last prime in the search, so that anything
+ // higher than the second-to-last prime returns a past-the-end
+ // 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 + 5, __prime_list + __n_primes, __n);
+ std::lower_bound(__prime_list + 6, __last_prime, __n + 1);
+
+ if (__next_bkt == __last_prime)
+ // 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;
}
@@ -25,6 +25,7 @@
namespace __detail
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
+ // The sentinel value is kept only for abi backward compatibility.
extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
{
2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
new file mode 100644
@@ -0,0 +1,63 @@
+// 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(int threshold)
+ {
+ 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 != threshold; ++i)
+ {
+ if (i == nb_reserved)
+ {
+ nb_reserved = bkts;
+ us.reserve(nb_reserved);
+ bkts = us.bucket_count();
+ }
+
+ us.insert(i);
+
+ VERIFY( us.bucket_count() == bkts );
+ }
+ }
+
+template<typename _Value>
+ using unordered_set_power2_rehash =
+ std::_Hashtable<_Value, _Value, std::allocator<_Value>,
+ std::__detail::_Identity,
+ std::equal_to<_Value>,
+ std::hash<_Value>,
+ std::__detail::_Mask_range_hashing,
+ std::__detail::_Default_ranged_hash,
+ std::__detail::_Power2_rehash_policy,
+ std::__detail::_Hashtable_traits<false, true, true>>;
+
+int main()
+{
+ test<std::unordered_set<int>>(150);
+ test<unordered_set_power2_rehash<int>>(150);
+ return 0;
+}
@@ -17,6 +17,7 @@
//
// { dg-options "-std=gnu++11" }
+#include <limits>
#include <unordered_set>
#include <testsuite_hooks.h>
@@ -35,8 +36,32 @@ void test01()
== (std::size_t(1) << (sizeof(std::size_t) * 8 - 1)) );
}
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::__detail::_Power2_rehash_policy policy;
+
+ for (std::size_t i = 1;;)
+ {
+ auto nxt = policy._M_next_bkt(i);
+
+ if (nxt == i)
+ {
+ // Equals only when reaching max.
+ constexpr auto mx = std::numeric_limits<std::size_t>::max();
+ VERIFY( nxt == policy._M_next_bkt(mx) );
+ break;
+ }
+
+ VERIFY( nxt > i );
+ i = nxt;
+ }
+}
+
int main()
{
test01();
+ test02();
return 0;
}
new file mode 100644
@@ -0,0 +1,52 @@
+// 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 <limits>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::__detail::_Prime_rehash_policy policy;
+
+ for (std::size_t i = 1;;)
+ {
+ auto nxt = policy._M_next_bkt(i);
+
+ if (nxt == i)
+ {
+ // Equals only when reaching max.
+ constexpr auto mx = std::numeric_limits<std::size_t>::max() - 1;
+ VERIFY( nxt == policy._M_next_bkt(mx) );
+ break;
+ }
+
+ VERIFY( nxt > i );
+ i = nxt;
+ }
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
@@ -34,8 +34,8 @@ void test()
us.insert(i);
if (bkt_count != us.bucket_count())
{
- // Container has been rehashed, lets check that it won't be rehash again
- // if we remove and restore the last 2 inserted elements:
+ // Container has been rehashed, lets check that it won't be rehash
+ // again if we remove and restore the last 2 inserted elements:
rehashed = true;
bkt_count = us.bucket_count();
VERIFY( us.erase(i) == 1 );
Here is a new version compiling all your feedbacks. PR libstdc++/71181 * include/tr1/hashtable_policy.h (_Prime_rehash_policy::_M_next_bkt): Make past-the-end iterator dereferenceable to avoid check on lower_bound result. (_Prime_rehash_policy::_M_bkt_for_elements): Call latter. (_Prime_rehash_policy::_M_need_rehash): Likewise. * 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 max value when reaching highest prime number. * src/shared/hashtable-aux.cc (__prime_list): Add comment about sentinel being now useless. * testsuite/23_containers/unordered_set/hash_policy/71181.cc: New. * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc (test02): New. * testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc: New. * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: Fix indentation. On 15/06/2016 10:29, Jonathan Wakely wrote: > On 14/06/16 22:34 +0200, François Dumont wrote: >>>> const unsigned long* __next_bkt = >>>> - std::lower_bound(__prime_list + 5, __prime_list + >>>> __n_primes, __n); >>>> + std::lower_bound(__prime_list + 6, __prime_list_end, __n); >>>> + >>>> + if (*__next_bkt == __n && __next_bkt != __prime_list_end) >>>> + ++__next_bkt; >>> >>> Can we avoid this check by searching for __n + 1 instead of __n with >>> the lower_bound call? >> >> Yes, that's another option, I will give it a try. > > I did some comparisons and this version seems to execute fewer > instructions in some simple tests, according to cachegrind. > The only drawback is that calling _M_next_bkt(size_t(-1)) doesn't give the right result. But reaching this kind of value is not likely to happen in real use cases so it is acceptable. Tested under Linux x86_64. François