From 732eb07625bc086833506374f1ce452096716874 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Tue, 24 May 2016 20:55:57 +0000 Subject: [PATCH] c++config (_GLIBCXX14_USE_CONSTEXPR): New. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2016-05-24 François Dumont * include/bits/c++config (_GLIBCXX14_USE_CONSTEXPR): New. * include/bits/hashtable_policy.h (_Prime_rehash_policy::__has_load_factor): New. Mark rehash policy having load factor management. (_Mask_range_hashing): New. (__clp2): New. (_Power2_rehash_policy): New. (_Inserts<>): Remove last template parameter, _Unique_keys, so that partial specializations only depend on whether iterators are constant or not. * testsuite/23_containers/unordered_set/hash_policy/26132.cc: Adapt to test new hash policy. * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc: Likewise. * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: Likewise. * testsuite/23_containers/unordered_set/insert/hash_policy.cc: Likewise. * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc: Likewise. * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc: New. * testsuite/performance/23_containers/insert/54075.cc: Add benchmark using the new hash policy. * testsuite/performance/23_containers/insert_erase/41975.cc: Likewise. From-SVN: r236669 --- libstdc++-v3/ChangeLog | 28 +++ libstdc++-v3/include/bits/c++config | 2 + libstdc++-v3/include/bits/hashtable_policy.h | 219 +++++++++++++----- .../unordered_set/hash_policy/26132.cc | 67 +++--- .../unordered_set/hash_policy/load_factor.cc | 60 +++-- .../hash_policy/power2_rehash.cc | 42 ++++ .../unordered_set/hash_policy/rehash.cc | 22 +- .../unordered_set/insert/hash_policy.cc | 184 ++++++++------- .../max_load_factor/robustness.cc | 108 +++++---- .../performance/23_containers/insert/54075.cc | 35 ++- .../23_containers/insert_erase/41975.cc | 30 ++- 11 files changed, 565 insertions(+), 232 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 449ad0c2943..3fc811d1611 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,31 @@ +2016-05-24 François Dumont + + * include/bits/c++config (_GLIBCXX14_USE_CONSTEXPR): New. + * include/bits/hashtable_policy.h + (_Prime_rehash_policy::__has_load_factor): New. Mark rehash policy + having load factor management. + (_Mask_range_hashing): New. + (__clp2): New. + (_Power2_rehash_policy): New. + (_Inserts<>): Remove last template parameter, _Unique_keys, so that + partial specializations only depend on whether iterators are constant + or not. + * testsuite/23_containers/unordered_set/hash_policy/26132.cc: Adapt to + test new hash policy. + * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc: + Likewise. + * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: + Likewise. + * testsuite/23_containers/unordered_set/insert/hash_policy.cc: + Likewise. + * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc: + Likewise. + * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc: + New. + * testsuite/performance/23_containers/insert/54075.cc: Add benchmark + using the new hash policy. + * testsuite/performance/23_containers/insert_erase/41975.cc: Likewise. + 2016-05-24 Jonathan Wakely * include/bits/stl_queue.h (priority_queue::value_compare): Define. diff --git a/libstdc++-v3/include/bits/c++config b/libstdc++-v3/include/bits/c++config index 57024e40ec0..78353ae9eb6 100644 --- a/libstdc++-v3/include/bits/c++config +++ b/libstdc++-v3/include/bits/c++config @@ -106,8 +106,10 @@ #ifndef _GLIBCXX14_CONSTEXPR # if __cplusplus >= 201402L # define _GLIBCXX14_CONSTEXPR constexpr +# define _GLIBCXX14_USE_CONSTEXPR constexpr # else # define _GLIBCXX14_CONSTEXPR +# define _GLIBCXX14_USE_CONSTEXPR const # endif #endif diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 2c24c195bd1..0b317c335b8 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -31,6 +31,8 @@ #ifndef _HASHTABLE_POLICY_H #define _HASHTABLE_POLICY_H 1 +#include // for std::min. + namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION @@ -457,6 +459,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// smallest prime that keeps the load factor small enough. struct _Prime_rehash_policy { + using __has_load_factor = std::true_type; + _Prime_rehash_policy(float __z = 1.0) noexcept : _M_max_load_factor(__z), _M_next_resize(0) { } @@ -501,6 +505,135 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION mutable std::size_t _M_next_resize; }; + /// Range hashing function assuming that second arg is a power of 2. + struct _Mask_range_hashing + { + typedef std::size_t first_argument_type; + typedef std::size_t second_argument_type; + typedef std::size_t result_type; + + result_type + operator()(first_argument_type __num, + second_argument_type __den) const noexcept + { return __num & (__den - 1); } + }; + + /// Compute closest power of 2. + _GLIBCXX14_CONSTEXPR + inline std::size_t + __clp2(std::size_t n) noexcept + { +#if __SIZEOF_SIZE_T__ >= 8 + std::uint_fast64_t x = n; +#else + std::uint_fast32_t x = n; +#endif + // Algorithm from Hacker's Delight, Figure 3-3. + x = x - 1; + x = x | (x >> 1); + x = x | (x >> 2); + x = x | (x >> 4); + x = x | (x >> 8); + x = x | (x >>16); +#if __SIZEOF_SIZE_T__ >= 8 + x = x | (x >>32); +#endif + return x + 1; + } + + /// Rehash policy providing power of 2 bucket numbers. Avoids modulo + /// operations. + struct _Power2_rehash_policy + { + using __has_load_factor = std::true_type; + + _Power2_rehash_policy(float __z = 1.0) noexcept + : _M_max_load_factor(__z), _M_next_resize(0) { } + + float + max_load_factor() const noexcept + { return _M_max_load_factor; } + + // Return a bucket size no smaller than n (as long as n is not above the + // highest power of 2). + std::size_t + _M_next_bkt(std::size_t __n) const noexcept + { + _GLIBCXX14_USE_CONSTEXPR size_t __max_width + = std::min(sizeof(size_t), 8); + _GLIBCXX14_USE_CONSTEXPR auto __max_bkt + = std::size_t(1) << (__max_width * __CHAR_BIT__ - 1); + + std::size_t __res = __clp2(__n); + + if (__res == __n) + __res <<= 1; + + if (__res == 0) + __res = __max_bkt; + + if (__res == __max_bkt) + // 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(__res * (long double)_M_max_load_factor); + + return __res; + } + + // Return a bucket count appropriate for n elements + std::size_t + _M_bkt_for_elements(std::size_t __n) const noexcept + { return __builtin_ceil(__n / (long double)_M_max_load_factor); } + + // __n_bkt is current bucket count, __n_elt is current element count, + // and __n_ins is number of elements to be inserted. Do we need to + // increase bucket count? If so, return make_pair(true, n), where n + // is the new bucket count. If not, return make_pair(false, 0). + std::pair + _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, + std::size_t __n_ins) const noexcept + { + if (__n_elt + __n_ins >= _M_next_resize) + { + long double __min_bkts = (__n_elt + __n_ins) + / (long double)_M_max_load_factor; + if (__min_bkts >= __n_bkt) + return std::make_pair(true, + _M_next_bkt(std::max(__builtin_floor(__min_bkts) + 1, + __n_bkt * _S_growth_factor))); + + _M_next_resize + = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); + return std::make_pair(false, 0); + } + else + return std::make_pair(false, 0); + } + + typedef std::size_t _State; + + _State + _M_state() const noexcept + { return _M_next_resize; } + + void + _M_reset() noexcept + { _M_next_resize = 0; } + + void + _M_reset(_State __state) noexcept + { _M_next_resize = __state; } + + static const std::size_t _S_growth_factor = 2; + + float _M_max_load_factor; + mutable std::size_t _M_next_resize; + }; + // Base classes for std::_Hashtable. We define these base classes // because in some cases we want to do different things depending on // the value of a policy class. In some cases the policy class @@ -776,8 +909,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, typename _Traits, - bool _Constant_iterators = _Traits::__constant_iterators::value, - bool _Unique_keys = _Traits::__unique_keys::value> + bool _Constant_iterators = _Traits::__constant_iterators::value> struct _Insert; /// Specialization. @@ -786,65 +918,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, typename _Traits> struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits, true, true> + _RehashPolicy, _Traits, true> : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits> { using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>; - using value_type = typename __base_type::value_type; - using iterator = typename __base_type::iterator; - using const_iterator = typename __base_type::const_iterator; - - using __unique_keys = typename __base_type::__unique_keys; - using __hashtable = typename __base_type::__hashtable; - using __node_gen_type = typename __base_type::__node_gen_type; - - using __base_type::insert; - std::pair - insert(value_type&& __v) - { - __hashtable& __h = this->_M_conjure_hashtable(); - __node_gen_type __node_gen(__h); - return __h._M_insert(std::move(__v), __node_gen, __unique_keys()); - } - - iterator - insert(const_iterator __hint, value_type&& __v) - { - __hashtable& __h = this->_M_conjure_hashtable(); - __node_gen_type __node_gen(__h); - return __h._M_insert(__hint, std::move(__v), __node_gen, - __unique_keys()); - } - }; + using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _Traits>; - /// Specialization. - template - struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits, true, false> - : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits> - { - using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>; using value_type = typename __base_type::value_type; using iterator = typename __base_type::iterator; using const_iterator = typename __base_type::const_iterator; using __unique_keys = typename __base_type::__unique_keys; + using __ireturn_type = typename __hashtable_base::__ireturn_type; using __hashtable = typename __base_type::__hashtable; using __node_gen_type = typename __base_type::__node_gen_type; using __base_type::insert; - iterator + __ireturn_type insert(value_type&& __v) { __hashtable& __h = this->_M_conjure_hashtable(); @@ -866,9 +963,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _RehashPolicy, typename _Traits> struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits, false, _Unique_keys> + _RehashPolicy, _Traits, false> : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits> { @@ -912,28 +1009,46 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; + template + using __has_load_factor = typename _Policy::__has_load_factor; + /** * Primary class template _Rehash_base. * * Give hashtable the max_load_factor functions and reserve iff the - * rehash policy is _Prime_rehash_policy. + * rehash policy supports it. */ template + typename _RehashPolicy, typename _Traits, + typename = + __detected_or_t> struct _Rehash_base; - /// Specialization. + /// Specialization when rehash policy doesn't provide load factor management. template + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _Prime_rehash_policy, _Traits> + _H1, _H2, _Hash, _RehashPolicy, _Traits, + std::false_type> + { + }; + + /// Specialization when rehash policy provide load factor management. + template + struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, + std::true_type> { using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _Prime_rehash_policy, _Traits>; + _RehashPolicy, _Traits>; float max_load_factor() const noexcept @@ -946,7 +1061,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION max_load_factor(float __z) { __hashtable* __this = static_cast<__hashtable*>(this); - __this->__rehash_policy(_Prime_rehash_policy(__z)); + __this->__rehash_policy(_RehashPolicy(__z)); } void diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc index 092ee2852c0..5c01fa72a89 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc @@ -23,35 +23,48 @@ #include // libstdc++/26132 -void test01() -{ - bool test __attribute__((unused)) = true; - - for (float lf = 1.0; lf < 101.0; lf *= 10.0) - for (int size = 1; size <= 6561; size *= 3) - { - std::unordered_set us1; - typedef std::unordered_set::size_type size_type; - - us1.max_load_factor(10.0); - - for (int i = 0; i < size; ++i) - us1.insert(i); - - us1.max_load_factor(lf); - - for (int i = 1; i <= 6561; i *= 81) - { - const size_type n = size * 81 / i; - us1.rehash(n); - VERIFY( us1.bucket_count() > us1.size() / us1.max_load_factor() ); - VERIFY( us1.bucket_count() >= n ); - } - } -} +template + void test() + { + bool test __attribute__((unused)) = true; + + for (float lf = 1.0; lf < 101.0; lf *= 10.0) + for (int size = 1; size <= 6561; size *= 3) + { + _USet us1; + typedef typename _USet::size_type size_type; + + us1.max_load_factor(10.0); + + for (int i = 0; i < size; ++i) + us1.insert(i); + + us1.max_load_factor(lf); + + for (int i = 1; i <= 6561; i *= 81) + { + const size_type n = size * 81 / i; + us1.rehash(n); + VERIFY( us1.bucket_count() > us1.size() / us1.max_load_factor() ); + VERIFY( us1.bucket_count() >= n ); + } + } + } + +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() { - test01(); + test>(); + test>(); return 0; } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc index 8a42ed4da06..0c3b7f84167 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc @@ -18,41 +18,55 @@ // { dg-options "-std=gnu++11" } #include + #include -void test01() -{ - bool test __attribute__((unused)) = true; +template + void test() { - std::unordered_set us; - for (int i = 0; i != 100000; ++i) + bool test __attribute__((unused)) = true; { - us.insert(i); - VERIFY( us.load_factor() <= us.max_load_factor() ); + _USet us; + for (int i = 0; i != 100000; ++i) + { + us.insert(i); + VERIFY( us.load_factor() <= us.max_load_factor() ); + } } - } - { - std::unordered_set us; - us.max_load_factor(3.f); - for (int i = 0; i != 100000; ++i) { - us.insert(i); - VERIFY( us.load_factor() <= us.max_load_factor() ); + _USet us; + us.max_load_factor(3.f); + for (int i = 0; i != 100000; ++i) + { + us.insert(i); + VERIFY( us.load_factor() <= us.max_load_factor() ); + } } - } - { - std::unordered_set us; - us.max_load_factor(.3f); - for (int i = 0; i != 100000; ++i) { - us.insert(i); - VERIFY( us.load_factor() <= us.max_load_factor() ); + _USet us; + us.max_load_factor(.3f); + for (int i = 0; i != 100000; ++i) + { + us.insert(i); + VERIFY( us.load_factor() <= us.max_load_factor() ); + } } } -} + +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() { - test01(); + test>(); + test>(); 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 new file mode 100644 index 00000000000..1d01d0a19f5 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc @@ -0,0 +1,42 @@ +// 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 + +void test01() +{ + bool test __attribute__((unused)) = true; + + std::__detail::_Power2_rehash_policy policy; + VERIFY( policy._M_next_bkt(1) == 2 ); + VERIFY( policy._M_next_bkt(2) == 4 ); + VERIFY( policy._M_next_bkt(3) == 4 ); + VERIFY( policy._M_next_bkt(5) == 8 ); + VERIFY( policy._M_next_bkt(33) == 64 ); + VERIFY( policy._M_next_bkt((std::size_t(1) << (sizeof(std::size_t) * 8 - 2)) + 1) + == (std::size_t(1) << (sizeof(std::size_t) * 8 - 1)) ); +} + +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 46faa6d3bbe..2dac583598d 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 @@ -18,13 +18,15 @@ // { dg-options "-std=gnu++11" } #include + #include -void test01() +template +void test() { bool test __attribute__((unused)) = true; - std::unordered_set us; - typedef typename std::unordered_set::size_type size_type; + _USet us; + typedef typename _USet::size_type size_type; bool rehashed = false; for (int i = 0; i != 100000; ++i) { @@ -55,8 +57,20 @@ void test01() VERIFY( rehashed ); } +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() { - test01(); + test>(); + test>(); return 0; } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc index 2419af1f05b..7dcaf3958c0 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc @@ -20,94 +20,122 @@ #include #include #include + #include + #include -void test01() -{ - bool test __attribute__((unused)) = true; +template + typename _USet> + void test01() + { + bool test __attribute__((unused)) = true; - typedef std::numeric_limits nl_size_t; - std::unordered_set, std::equal_to, - __gnu_cxx::throw_allocator_limit > us; - const int nb = 100; - int scheduled_throw_counter = 0; - std::size_t thrown_exceptions = 0; - for (int i = 0; i != nb; ++i) - { - if ((float)(us.size() + 1) - / (float)us.bucket_count() >= us.max_load_factor()) - { - // We are going to need a rehash, lets introduce allocation issues: - __gnu_cxx::limit_condition::set_limit(scheduled_throw_counter++); - } - try - { - VERIFY(us.insert(i).second); - scheduled_throw_counter = 0; - } - catch (const __gnu_cxx::forced_error&) - { - ++thrown_exceptions; - --i; - } - VERIFY( us.load_factor() <= us.max_load_factor() ); - __gnu_cxx::limit_condition::set_limit(nl_size_t::max()); - } + // Make sure whatever happen we restore throw allocator limit at exit. + __gnu_cxx::limit_condition::adjustor_base adj; - VERIFY( thrown_exceptions != 0 ); - // Check that all values have been inserted: - for (int i = 0; i != nb; ++i) - { - VERIFY( us.count(i) == 1 ); - } -} + typedef std::numeric_limits nl_size_t; + _USet, std::equal_to, + __gnu_cxx::throw_allocator_limit > us; + const int nb = 100; + int scheduled_throw_counter = 0; + std::size_t thrown_exceptions = 0; + for (int i = 0; i != nb; ++i) + { + if ((float)(us.size() + 1) + / (float)us.bucket_count() >= us.max_load_factor()) + { + // We are going to need a rehash, lets introduce allocation issues: + __gnu_cxx::limit_condition::set_limit(scheduled_throw_counter++); + } + try + { + VERIFY(us.insert(i).second); + scheduled_throw_counter = 0; + } + catch (const __gnu_cxx::forced_error&) + { + ++thrown_exceptions; + --i; + } + VERIFY( us.load_factor() <= us.max_load_factor() ); + __gnu_cxx::limit_condition::set_limit(nl_size_t::max()); + } -void test02() -{ - bool test __attribute__((unused)) = true; + VERIFY( thrown_exceptions != 0 ); + // Check that all values have been inserted: + for (int i = 0; i != nb; ++i) + { + VERIFY( us.count(i) == 1 ); + } + } - typedef std::numeric_limits nl_size_t; - std::unordered_set, std::equal_to, - __gnu_cxx::throw_allocator_limit > us; - const int nb = 100; - int scheduled_throw_counter = 0; - std::size_t thrown_exceptions = 0; - for (int i = 0; i != nb; ++i) - { - if ((float)(us.size() + 2) - / (float)us.bucket_count() >= us.max_load_factor()) - { - // We are going to need a rehash, lets introduce allocation issues: - __gnu_cxx::limit_condition::set_limit(scheduled_throw_counter++); - } - try - { - std::vector v = { i, i }; - // Check the insert range robustness - us.insert(v.begin(), v.end()); - scheduled_throw_counter = 0; - } - catch (const __gnu_cxx::forced_error&) - { - ++thrown_exceptions; - --i; - } - VERIFY( us.load_factor() <= us.max_load_factor() ); - __gnu_cxx::limit_condition::set_limit(nl_size_t::max()); - } +template + typename _USet> + void test02() + { + bool test __attribute__((unused)) = true; - VERIFY( thrown_exceptions != 0 ); - // Check that all values have been inserted: - for (int i = 0; i != nb; ++i) - { - VERIFY( us.count(i) == 1 ); - } -} + // Make sure whatever happen we restore throw allocator limit at exit. + __gnu_cxx::limit_condition::adjustor_base adj; + + typedef std::numeric_limits nl_size_t; + _USet, std::equal_to, + __gnu_cxx::throw_allocator_limit > us; + const int nb = 100; + int scheduled_throw_counter = 0; + std::size_t thrown_exceptions = 0; + for (int i = 0; i != nb; ++i) + { + if ((float)(us.size() + 2) + / (float)us.bucket_count() >= us.max_load_factor()) + { + // We are going to need a rehash, lets introduce allocation issues: + __gnu_cxx::limit_condition::set_limit(scheduled_throw_counter++); + } + try + { + std::vector v = { i, i }; + // Check the insert range robustness + us.insert(v.begin(), v.end()); + scheduled_throw_counter = 0; + } + catch (const __gnu_cxx::forced_error&) + { + ++thrown_exceptions; + --i; + } + VERIFY( us.load_factor() <= us.max_load_factor() ); + __gnu_cxx::limit_condition::set_limit(nl_size_t::max()); + } + + VERIFY( thrown_exceptions != 0 ); + // Check that all values have been inserted: + for (int i = 0; i != nb; ++i) + { + VERIFY( us.count(i) == 1 ); + } + } + +template + using unordered_set_power2_rehash = + std::_Hashtable<_Value, _Value, _Alloc, + std::__detail::_Identity, + _Pred, + _Hash, + std::__detail::_Mask_range_hashing, + std::__detail::_Default_ranged_hash, + std::__detail::_Power2_rehash_policy, + std::__detail::_Hashtable_traits>; int main() { - test01(); - test02(); + test01(); + test01(); + test02(); + test02(); 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 95cc1cdc6cb..b95c86f4af4 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 @@ -22,62 +22,78 @@ #include #include -void test01() -{ - bool test __attribute__((unused)) = true; +template + typename _USet> + void test() + { + bool test __attribute__((unused)) = true; - typedef std::numeric_limits nl_size_t; - std::unordered_set, std::equal_to, - __gnu_cxx::throw_allocator_limit > us; - int val = 0; - for (; val != 100; ++val) - { - VERIFY( us.insert(val).second ); - VERIFY( us.load_factor() <= us.max_load_factor() ); - } + typedef std::numeric_limits nl_size_t; + _USet, std::equal_to, + __gnu_cxx::throw_allocator_limit > us; + int val = 0; + for (; val != 100; ++val) + { + VERIFY( us.insert(val).second ); + VERIFY( us.load_factor() <= us.max_load_factor() ); + } - float cur_max_load_factor = us.max_load_factor(); - int counter = 0; - std::size_t thrown_exceptions = 0; + float cur_max_load_factor = us.max_load_factor(); + int counter = 0; + std::size_t thrown_exceptions = 0; - // Reduce max load factor. - us.max_load_factor(us.max_load_factor() / 2); + // Reduce max load factor. + 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. - VERIFY( us.load_factor() > us.max_load_factor() ); + // At this point load factor is higher than max_load_factor because we can't + // rehash in max_load_factor call. + VERIFY( us.load_factor() > us.max_load_factor() ); - while (true) - { - __gnu_cxx::limit_condition::set_limit(counter++); - bool do_break = false; - try - { - size_t nbkts = us.bucket_count(); - // Check that unordered_set will still be correctly resized when - // needed. - VERIFY( us.insert(val++).second ); + while (true) + { + __gnu_cxx::limit_condition::limit_adjustor adjustor(counter++); + bool do_break = false; + try + { + size_t nbkts = us.bucket_count(); + // Check that unordered_set will still be correctly resized when + // needed. + VERIFY( us.insert(val++).second ); + VERIFY( us.bucket_count() != nbkts ); + VERIFY( us.load_factor() <= us.max_load_factor() ); + do_break = true; + } + catch (const __gnu_cxx::forced_error&) + { + // max load factor doesn't change. + VERIFY( us.max_load_factor() == .25f ); + ++thrown_exceptions; + } - VERIFY( us.bucket_count() != nbkts ); - VERIFY( us.load_factor() <= us.max_load_factor() ); - do_break = true; - } - catch (const __gnu_cxx::forced_error&) - { - // max load factor doesn't change. - VERIFY( us.max_load_factor() == .5f ); - ++thrown_exceptions; - } + if (do_break) + break; + } - if (do_break) - break; - } + VERIFY( thrown_exceptions > 0 ); + } - VERIFY( thrown_exceptions > 0 ); -} + +template + using unordered_set_power2_rehash = + std::_Hashtable<_Value, _Value, _Alloc, + std::__detail::_Identity, + _Pred, + _Hash, + std::__detail::_Mask_range_hashing, + std::__detail::_Default_ranged_hash, + std::__detail::_Power2_rehash_policy, + std::__detail::_Hashtable_traits>; int main() { - test01(); + test(); + test(); return 0; } diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc index a8b26754740..784ac71ec15 100644 --- a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc +++ b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc @@ -127,7 +127,27 @@ template using __umset = std::__umset_hashtable, std::allocator, - std::__uset_traits>; + std::__umset_traits>; + +template + using __uset2 = + std::_Hashtable, + std::__detail::_Identity, + std::equal_to, HashFunction, + std::__detail::_Mask_range_hashing, + std::__detail::_Default_ranged_hash, + std::__detail::_Power2_rehash_policy, + std::__uset_traits>; + +template + using __umset2 = + std::_Hashtable, + std::__detail::_Identity, + std::equal_to, HashFunction, + std::__detail::_Mask_range_hashing, + std::__detail::_Default_ranged_hash, + std::__detail::_Power2_rehash_policy, + std::__umset_traits>; int main() { @@ -181,6 +201,19 @@ int main() stop_counters(time, resource); report_performance(__FILE__, "std benches", time, resource); + start_counters(time, resource); + bench<__uset2>( + "std::unordered_set2 without hash code cached ", foos); + bench<__uset2>( + "std::unordered_set2 with hash code cached ", foos); + bench<__umset2>( + "std::unordered_multiset2 without hash code cached ", foos); + bench<__umset2>( + "std::unordered_multiset2 with hash code cached ", foos); + + stop_counters(time, resource); + report_performance(__FILE__, "std2 benches", time, resource); + bench>( "std::unordered_set default cache ", foos); bench>( diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc index 4de6598193a..44781d2fdd7 100644 --- a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc +++ b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc @@ -176,6 +176,16 @@ template std::allocator, cache>; +template + using __uset2 = + std::_Hashtable, + std::__detail::_Identity, + std::equal_to, std::hash, + std::__detail::_Mask_range_hashing, + std::__detail::_Default_ranged_hash, + std::__detail::_Power2_rehash_policy, + std::__uset_traits>; + template using __str_uset = std::__uset_hashtable, @@ -190,6 +200,16 @@ template std::allocator, cache>; +template + using __str_uset2 = + std::_Hashtable, + std::__detail::_Identity, + std::equal_to, std::hash, + std::__detail::_Mask_range_hashing, + std::__detail::_Default_ranged_hash, + std::__detail::_Power2_rehash_policy, + std::__uset_traits>; + int main() { bench<__tr1_uset>( @@ -202,6 +222,10 @@ int main() "std::unordered_set with hash code cached"); bench>( "std::unordered_set default cache"); + bench<__uset2>( + "std::unordered_set2 without hash code cached"); + bench<__uset2>( + "std::unordered_set2 with hash code cached"); bench_str<__tr1_str_uset>( "std::tr1::unordered_set without hash code cached"); bench_str<__tr1_str_uset>( @@ -210,7 +234,11 @@ int main() "std::unordered_set without hash code cached"); bench_str<__str_uset>( "std::unordered_set with hash code cached"); - bench_str>( + bench_str>( "std::unordered_set default cache"); + bench_str<__str_uset2>( + "std::unordered_set2 without hash code cached"); + bench_str<__str_uset2>( + "std::unordered_set2 with hash code cached"); return 0; } -- 2.30.2