From 29dbb034cb3199167a9d0aaed040733c72326eed Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Mon, 20 Jun 2016 20:04:25 +0000 Subject: [PATCH] re PR libstdc++/71181 (Reserving in unordered_map doesn't reserve enough) MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2016-06-20 François Dumont 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. From-SVN: r237617 --- libstdc++-v3/ChangeLog | 20 ++++++ libstdc++-v3/include/tr1/hashtable_policy.h | 21 +++---- libstdc++-v3/src/c++11/hashtable_c++0x.cc | 28 +++++++-- libstdc++-v3/src/shared/hashtable-aux.cc | 1 + .../unordered_set/hash_policy/71181.cc | 63 +++++++++++++++++++ .../hash_policy/power2_rehash.cc | 25 ++++++++ .../unordered_set/hash_policy/prime_rehash.cc | 52 +++++++++++++++ .../unordered_set/hash_policy/rehash.cc | 50 +++++++-------- 8 files changed, 216 insertions(+), 44 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index a9748517114..10ffc4169d1 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,23 @@ +2016-06-20 François Dumont + + 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. + 2016-06-17 Jonathan Wakely PR libstdc++/71545 diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h b/libstdc++-v3/include/tr1/hashtable_policy.h index 4ee6d45044e..c5cf866b1fe 100644 --- a/libstdc++-v3/include/tr1/hashtable_policy.h +++ b/libstdc++-v3/include/tr1/hashtable_policy.h @@ -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(__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(__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 - (__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 { diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index a5e6520dcdb..ce4961fbd5e 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -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); - _M_next_resize = - __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); + 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; } diff --git a/libstdc++-v3/src/shared/hashtable-aux.cc b/libstdc++-v3/src/shared/hashtable-aux.cc index 081bb1236bc..ec9841e06a1 100644 --- a/libstdc++-v3/src/shared/hashtable-aux.cc +++ b/libstdc++-v3/src/shared/hashtable-aux.cc @@ -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, 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 00000000000..a8bbfc736d9 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc @@ -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 +// . +// +// { dg-options "-std=gnu++11" } + +#include + +#include + +template + 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 + 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>; + +int main() +{ + test>(150); + test>(150); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc index 1d01d0a19f5..5805f7aafc6 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc @@ -17,6 +17,7 @@ // // { dg-options "-std=gnu++11" } +#include #include #include @@ -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::max(); + VERIFY( nxt == policy._M_next_bkt(mx) ); + break; + } + + VERIFY( nxt > i ); + i = nxt; + } +} + int main() { test01(); + test02(); return 0; } 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 new file mode 100644 index 00000000000..403382349fa --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc @@ -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 +// . +// +// { dg-options "-std=gnu++11" } + +#include +#include + +#include + +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::max() - 1; + VERIFY( nxt == policy._M_next_bkt(mx) ); + break; + } + + VERIFY( nxt > i ); + i = nxt; + } +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc index 2dac583598d..96581317446 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc @@ -22,40 +22,40 @@ #include template -void test() -{ - bool test __attribute__((unused)) = true; - _USet us; - typedef typename _USet::size_type size_type; - bool rehashed = false; - for (int i = 0; i != 100000; ++i) + void test() { - size_type bkt_count = us.bucket_count(); - us.insert(i); - if (bkt_count != us.bucket_count()) + bool test __attribute__((unused)) = true; + _USet us; + typedef typename _USet::size_type size_type; + bool rehashed = false; + for (int i = 0; i != 100000; ++i) { - // 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 ); - VERIFY( bkt_count == us.bucket_count() ); - if (i > 0) + size_type bkt_count = us.bucket_count(); + us.insert(i); + if (bkt_count != us.bucket_count()) { - VERIFY( us.erase(i - 1) == 1 ); + // 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 ); VERIFY( bkt_count == us.bucket_count() ); + if (i > 0) + { + VERIFY( us.erase(i - 1) == 1 ); + VERIFY( bkt_count == us.bucket_count() ); - VERIFY( us.insert(i - 1).second ); + VERIFY( us.insert(i - 1).second ); + VERIFY( bkt_count == us.bucket_count() ); + } + VERIFY( us.insert(i).second ); VERIFY( bkt_count == us.bucket_count() ); } - VERIFY( us.insert(i).second ); - VERIFY( bkt_count == us.bucket_count() ); } - } - // At lest we check a rehash once: - VERIFY( rehashed ); -} + // At lest we check a rehash once: + VERIFY( rehashed ); + } template using unordered_set_power2_rehash = -- 2.30.2