Attached patch applied then.
I had to regorganize things a little now that some pieces have been
integrated in 71181 patch.
2016-05-24 François Dumont <fdum...@gcc.gnu.org>
* 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.
François
On 23/05/2016 13:31, Jonathan Wakely wrote:
On 17/05/16 22:28 +0200, François Dumont wrote:
On 14/05/2016 19:06, Daniel Krügler wrote:
1) The function __clp2 is declared using _GLIBCXX14_CONSTEXPR, which
means that it is an inline function if and *only* if
_GLIBCXX14_CONSTEXPR really expands to constexpr, otherwise it is
*not* inline, which is probably not intended and could easily cause
ODR problems. I suggest to mark it unconditionally as inline,
regardless of _GLIBCXX14_CONSTEXPR.
Maybe _GLIBCXX14_CONSTEXPR should take inline value previous to C++14
mode.
That's probably a good idea.
For the moment I simply added the inline as done in other situations.
OK, thanks.
2) Furthermore I suggest to declare __clp2 as noexcept - this is
(intentionally) *not* implied by constexpr.
3) Is there any reason, why _Power2_rehash_policy::_M_next_bkt
shouldn't be noexcept?
4) Similar to (3) for _Power2_rehash_policy's member functions
_M_bkt_for_elements, _M_need_rehash, _M_state, _M_reset
For noexcept I throught we were only adding it if necessary. We might
have to go through a lot of code to find all places where noexcept
could be added. Jonathan will give his feedback.
I'm in favour of adding it anywhere that that definitely can't throw.
We don't *need* to do that everywhere, but it doesn't hurt.
For the moment I have added it on all those methods.
Great.
Thanks for feedback, updated and tested patch attached.
OK for trunk - thanks!
Index: include/bits/c++config
===================================================================
--- include/bits/c++config (revision 236662)
+++ include/bits/c++config (working copy)
@@ -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
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 236662)
+++ include/bits/hashtable_policy.h (working copy)
@@ -31,6 +31,8 @@
#ifndef _HASHTABLE_POLICY_H
#define _HASHTABLE_POLICY_H 1
+#include <bits/stl_algobase.h> // for std::min.
+
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -457,6 +459,8 @@
/// 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 @@
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<size_t>(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<bool, std::size_t>
+ _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<std::size_t>(__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 @@
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,7 +918,7 @@
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>
{
@@ -793,58 +925,23 @@
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 __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _Traits>;
- using __base_type::insert;
-
- std::pair<iterator, bool>
- 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());
- }
- };
-
- /// Specialization.
- template<typename _Key, typename _Value, typename _Alloc,
- typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
- typename _RehashPolicy, typename _Traits>
- 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 @@
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash,
- typename _RehashPolicy, typename _Traits, bool _Unique_keys>
+ 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 @@
}
};
+ template<typename _Policy>
+ 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 _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash,
- typename _RehashPolicy, typename _Traits>
+ typename _RehashPolicy, typename _Traits,
+ typename =
+ __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>>
struct _Rehash_base;
- /// Specialization.
+ /// Specialization when rehash policy doesn't provide load factor management.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _Traits>
+ 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<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ 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 @@
max_load_factor(float __z)
{
__hashtable* __this = static_cast<__hashtable*>(this);
- __this->__rehash_policy(_Prime_rehash_policy(__z));
+ __this->__rehash_policy(_RehashPolicy(__z));
}
void
Index: testsuite/23_containers/unordered_set/hash_policy/26132.cc
===================================================================
--- testsuite/23_containers/unordered_set/hash_policy/26132.cc (revision 236662)
+++ testsuite/23_containers/unordered_set/hash_policy/26132.cc (working copy)
@@ -23,35 +23,48 @@
#include <testsuite_hooks.h>
// libstdc++/26132
-void test01()
-{
- bool test __attribute__((unused)) = true;
+template<typename _USet>
+ 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)
- {
- std::unordered_set<int> us1;
- typedef std::unordered_set<int>::size_type size_type;
-
- us1.max_load_factor(10.0);
+ 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;
- for (int i = 0; i < size; ++i)
- us1.insert(i);
+ us1.max_load_factor(10.0);
- us1.max_load_factor(lf);
+ for (int i = 0; i < size; ++i)
+ us1.insert(i);
- 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 );
- }
- }
-}
+ 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<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()
{
- test01();
+ test<std::unordered_set<int>>();
+ test<unordered_set_power2_rehash<int>>();
return 0;
}
Index: testsuite/23_containers/unordered_set/hash_policy/load_factor.cc
===================================================================
--- testsuite/23_containers/unordered_set/hash_policy/load_factor.cc (revision 236662)
+++ testsuite/23_containers/unordered_set/hash_policy/load_factor.cc (working copy)
@@ -18,41 +18,55 @@
// { dg-options "-std=gnu++11" }
#include <unordered_set>
+
#include <testsuite_hooks.h>
-void test01()
-{
- bool test __attribute__((unused)) = true;
+template<typename _USet>
+ void test()
{
- std::unordered_set<int> 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<int> 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<int> 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<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()
{
- test01();
+ test<std::unordered_set<int>>();
+ test<unordered_set_power2_rehash<int>>();
return 0;
}
Index: testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
===================================================================
--- testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc (nonexistent)
+++ testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc (working copy)
@@ -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
+// <http://www.gnu.org/licenses/>.
+//
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+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;
+}
Index: testsuite/23_containers/unordered_set/hash_policy/rehash.cc
===================================================================
--- testsuite/23_containers/unordered_set/hash_policy/rehash.cc (revision 236662)
+++ testsuite/23_containers/unordered_set/hash_policy/rehash.cc (working copy)
@@ -18,13 +18,15 @@
// { dg-options "-std=gnu++11" }
#include <unordered_set>
+
#include <testsuite_hooks.h>
-void test01()
+template<typename _USet>
+void test()
{
bool test __attribute__((unused)) = true;
- std::unordered_set<int> us;
- typedef typename std::unordered_set<int>::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 @@
VERIFY( rehashed );
}
+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()
{
- test01();
+ test<std::unordered_set<int>>();
+ test<unordered_set_power2_rehash<int>>();
return 0;
}
Index: testsuite/23_containers/unordered_set/insert/hash_policy.cc
===================================================================
--- testsuite/23_containers/unordered_set/insert/hash_policy.cc (revision 236662)
+++ testsuite/23_containers/unordered_set/insert/hash_policy.cc (working copy)
@@ -20,94 +20,122 @@
#include <unordered_set>
#include <vector>
#include <limits>
+
#include <ext/throw_allocator.h>
+
#include <testsuite_hooks.h>
-void test01()
-{
- bool test __attribute__((unused)) = true;
+template<template<typename _Value, typename _Hash,
+ typename _Pred, typename _Alloc>
+ typename _USet>
+ void test01()
+ {
+ bool test __attribute__((unused)) = true;
- typedef std::numeric_limits<std::size_t> nl_size_t;
- std::unordered_set<int, std::hash<int>, std::equal_to<int>,
- __gnu_cxx::throw_allocator_limit<int> > 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<std::size_t> nl_size_t;
+ _USet<int, std::hash<int>, std::equal_to<int>,
+ __gnu_cxx::throw_allocator_limit<int> > 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<std::size_t> nl_size_t;
- std::unordered_set<int, std::hash<int>, std::equal_to<int>,
- __gnu_cxx::throw_allocator_limit<int> > 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<int> 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<template<typename _Value, typename _Hash,
+ typename _Pred, typename _Alloc>
+ 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<std::size_t> nl_size_t;
+ _USet<int, std::hash<int>, std::equal_to<int>,
+ __gnu_cxx::throw_allocator_limit<int> > 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<int> 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<typename _Value, typename _Hash,
+ typename _Pred, typename _Alloc>
+ 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<false, true, true>>;
+
int main()
{
- test01();
- test02();
+ test01<std::unordered_set>();
+ test01<unordered_set_power2_rehash>();
+ test02<std::unordered_set>();
+ test02<unordered_set_power2_rehash>();
return 0;
}
Index: testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
===================================================================
--- testsuite/23_containers/unordered_set/max_load_factor/robustness.cc (revision 236662)
+++ testsuite/23_containers/unordered_set/max_load_factor/robustness.cc (working copy)
@@ -22,62 +22,78 @@
#include <ext/throw_allocator.h>
#include <testsuite_hooks.h>
-void test01()
-{
- bool test __attribute__((unused)) = true;
+template<template<typename _Value, typename _Hash,
+ typename _Pred, typename _Alloc>
+ typename _USet>
+ void test()
+ {
+ bool test __attribute__((unused)) = true;
- typedef std::numeric_limits<std::size_t> nl_size_t;
- std::unordered_set<int, std::hash<int>, std::equal_to<int>,
- __gnu_cxx::throw_allocator_limit<int> > 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<std::size_t> nl_size_t;
+ _USet<int, std::hash<int>, std::equal_to<int>,
+ __gnu_cxx::throw_allocator_limit<int> > 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<typename _Value, typename _Hash,
+ typename _Pred, typename _Alloc>
+ 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<false, true, true>>;
+
int main()
{
- test01();
+ test<std::unordered_set>();
+ test<unordered_set_power2_rehash>();
return 0;
}
Index: testsuite/performance/23_containers/insert/54075.cc
===================================================================
--- testsuite/performance/23_containers/insert/54075.cc (revision 236662)
+++ testsuite/performance/23_containers/insert/54075.cc (working copy)
@@ -127,8 +127,28 @@
using __umset = std::__umset_hashtable<Foo, HashFunction,
std::equal_to<Foo>,
std::allocator<Foo>,
- std::__uset_traits<cache>>;
+ std::__umset_traits<cache>>;
+template<bool cache>
+ using __uset2 =
+ std::_Hashtable<Foo, Foo, std::allocator<Foo>,
+ std::__detail::_Identity,
+ std::equal_to<Foo>, HashFunction,
+ std::__detail::_Mask_range_hashing,
+ std::__detail::_Default_ranged_hash,
+ std::__detail::_Power2_rehash_policy,
+ std::__uset_traits<cache>>;
+
+template<bool cache>
+ using __umset2 =
+ std::_Hashtable<Foo, Foo, std::allocator<Foo>,
+ std::__detail::_Identity,
+ std::equal_to<Foo>, HashFunction,
+ std::__detail::_Mask_range_hashing,
+ std::__detail::_Default_ranged_hash,
+ std::__detail::_Power2_rehash_policy,
+ std::__umset_traits<cache>>;
+
int main()
{
using namespace __gnu_test;
@@ -181,6 +201,19 @@
stop_counters(time, resource);
report_performance(__FILE__, "std benches", time, resource);
+ start_counters(time, resource);
+ bench<__uset2<false>>(
+ "std::unordered_set2 without hash code cached ", foos);
+ bench<__uset2<true>>(
+ "std::unordered_set2 with hash code cached ", foos);
+ bench<__umset2<false>>(
+ "std::unordered_multiset2 without hash code cached ", foos);
+ bench<__umset2<true>>(
+ "std::unordered_multiset2 with hash code cached ", foos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "std2 benches", time, resource);
+
bench<std::unordered_set<Foo, HashFunction>>(
"std::unordered_set default cache ", foos);
bench<std::unordered_multiset<Foo, HashFunction>>(
Index: testsuite/performance/23_containers/insert_erase/41975.cc
===================================================================
--- testsuite/performance/23_containers/insert_erase/41975.cc (revision 236662)
+++ testsuite/performance/23_containers/insert_erase/41975.cc (working copy)
@@ -177,6 +177,16 @@
cache>;
template<bool cache>
+ using __uset2 =
+ std::_Hashtable<int, int, std::allocator<int>,
+ std::__detail::_Identity,
+ std::equal_to<int>, std::hash<int>,
+ std::__detail::_Mask_range_hashing,
+ std::__detail::_Default_ranged_hash,
+ std::__detail::_Power2_rehash_policy,
+ std::__uset_traits<cache>>;
+
+template<bool cache>
using __str_uset =
std::__uset_hashtable<std::string, std::hash<std::string>,
std::equal_to<std::string>,
@@ -190,6 +200,16 @@
std::allocator<std::string>,
cache>;
+template<bool cache>
+ using __str_uset2 =
+ std::_Hashtable<std::string, std::string, std::allocator<std::string>,
+ std::__detail::_Identity,
+ std::equal_to<std::string>, std::hash<std::string>,
+ std::__detail::_Mask_range_hashing,
+ std::__detail::_Default_ranged_hash,
+ std::__detail::_Power2_rehash_policy,
+ std::__uset_traits<cache>>;
+
int main()
{
bench<__tr1_uset<false>>(
@@ -202,6 +222,10 @@
"std::unordered_set<int> with hash code cached");
bench<std::unordered_set<int>>(
"std::unordered_set<int> default cache");
+ bench<__uset2<false>>(
+ "std::unordered_set2<int> without hash code cached");
+ bench<__uset2<true>>(
+ "std::unordered_set2<int> with hash code cached");
bench_str<__tr1_str_uset<false>>(
"std::tr1::unordered_set<string> without hash code cached");
bench_str<__tr1_str_uset<true>>(
@@ -210,7 +234,11 @@
"std::unordered_set<string> without hash code cached");
bench_str<__str_uset<true>>(
"std::unordered_set<string> with hash code cached");
- bench_str<std::unordered_set<std::string>>(
+ bench_str<std::unordered_set<std::string>>(
"std::unordered_set<string> default cache");
+ bench_str<__str_uset2<false>>(
+ "std::unordered_set2<string> without hash code cached");
+ bench_str<__str_uset2<true>>(
+ "std::unordered_set2<string> with hash code cached");
return 0;
}
