This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: New hashtable power 2 rehash policy
- From: FranÃois Dumont <frs dot dumont at gmail dot com>
- To: Jonathan Wakely <jwakely at redhat dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Sat, 14 May 2016 18:13:42 +0200
- Subject: Re: New hashtable power 2 rehash policy
- Authentication-results: sourceware.org; auth=none
- References: <571B31E1 dot 6000101 at gmail dot com> <20160428102218 dot GI4241 at redhat dot com>
Le 28/04/2016 12:22, Jonathan Wakely a écrit :
On 23/04/16 10:27 +0200, François Dumont wrote:
Hi
Here is a patch to introduce a new power of 2 based rehash policy.
It enhances performance as it avoids modulo float operations. I have
updated performance benches and here is the result:
Thanks, now that we're back in stage 1 we can make this change.
2016-04-22 François Dumont <fdumont@gcc.gnu.org>
* include/bits/hashtable_policy.h
(_Prime_rehash_policy::__has_load_factor): New. Mark rehash policy
having load factor management.
(_Mask_range_hashing): New.
(_NextPower2<size_t>): New.
(_Power2_rehash_policy): New.
(_Inserts<>): Remove last template parameter _Unique_keys. Use the
same
implementation when keys are unique no matter if iterators are
constant
or not.
I found this change description confusing, because it's really using
the same implementation whether keys are unique or not, but this says
"Use the same implementation whether iterators are constant or not".
Shouldn't it be "Use the same implementation when iterators are
constant, no matter if keys are unique or not" ?
Maybe this would be clearer:
(_Inserts<>): Remove last template parameter, _Unique_keys, so
that partial specializations only depend on whether iterators are
constant or not.
Yes, sorry, I prepared this patch a long time ago and didn't reconsider
it in enough details.
+ 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); }
+ };
+
+
+ /// Helper type to compute next power of 2.
+ template<typename _SizeT,
+ std::size_t _N = sizeof(_SizeT) << 2, bool _Increment = true>
+ struct _NextPower2
+ {
+ static _SizeT
+ _Get(_SizeT __n)
+ {
+ _SizeT __next = _NextPower2<_SizeT, (_N >> 1), false>::_Get(__n);
+ __next |= __next >> _N;
+ if (_Increment)
+ ++__next;
+
+ return __next;
+ }
+ };
+
+ template<typename _SizeT>
+ struct _NextPower2<_SizeT, 1, false>
+ {
+ static _SizeT
+ _Get(_SizeT __n)
+ {
+ --__n;
+ return __n |= __n >> 1;
+ }
+ };
What's the reason to keep this recursive template instead of using a
simple function like the clp2() we discussed? A simple function (which
could be _GLIBCXX14_CONSTEXPR) compiles faster, and produces similar
object code for the default -std=gnu++14 mode. And it doesn't require
six calls to _NextPower2::_Get to calculate the result.
I though we could have a wide variety of std::size_t definition on
different platforms. If we just need to consider 32/64 bits then it is
fine. Note that I thought that gcc would optimize away the calls to
_NextPower2::_Get.
If you're worried about the final shift being unnecessary on 32-bit
you can use the preprocessor, something like:
_GLIBCXX14_CONSTEXPR
std::size_t
__clp2(std::size_t n)
{
#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;
}
I don't think we need to worry about 128-bit integers, because that
would be a ridiculous number of buckets anyway. We can just limit
__max_bkt so we don't have to deal with more than 2^63 buckets.
Adopted.
+ /// 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
+ {
+ constexpr auto __max_bkt
+ = std::size_t(1) << ((sizeof(std::size_t) << 3) - 1);
Should this be sizeof(size_t) * __CHAR_BITS__ instead of << 3 ?
Otherwise targets with char wider than 8 bits would get a smaller
maximum number of buckets, even if they have 64-bit size_t.
sizeof() returns number of char elements in the given type ? I thought
it was the number of bytes and that a byte was always 8 bits. But I know
that you know your stuff so fixed in the new patch.
So, including the suggestion above to limit it to 2^63, it would be:
constexpr size_t __max_width = std::min(sizeof(size_t), 8);
constexpr auto __max_bkt
= std::size_t(1) << (__max_width * __CHAR_BITS__ - 1);
Ok,I just had to introduce a _GLIBCXX14_USE_CONSTEXPR to be able to
define this expression as constexpr.
+
+ std::size_t __res = _NextPower2<std::size_t>::_Get(__n);
+
+ 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(0) - 1;
This can be simplified to size_t(-1), there's no need for arithmetic.
This was my mental representation of it, size_t(-1) adopted.
@@ -775,8 +907,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.
(I'm sure I've said it before, but having 10+ template parameters here
makes me sad).
Me too but there are quite some work to reduce it. It would sure be a
very interesting design change to work on.
I took the time to adapt a number of test case to also cover this new
hash policy.
New patch attached, tested under linux x86_64.
François
diff --git a/libstdc++-v3/include/bits/c++config b/libstdc++-v3/include/bits/c++config
index 57024e4..78353ae 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 2c24c19..c030eab 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 <bits/stl_algobase.h> // 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,132 @@ _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
+ std::size_t
+ __clp2(std::size_t n)
+ {
+#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
+ {
+ _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 == 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
+ { 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
+ {
+ 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
+ { return _M_next_resize; }
+
+ void
+ _M_reset() noexcept
+ { _M_next_resize = 0; }
+
+ void
+ _M_reset(_State __state)
+ { _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 +906,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 +915,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<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,
+ using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
_Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits>;
+ _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 +960,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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 +1006,46 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
};
+ 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, _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, _Prime_rehash_policy, _Traits>
+ _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 +1058,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/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index a5e6520..506ac6a 100644
--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
@@ -60,8 +60,16 @@ namespace __detail
= sizeof(__prime_list) / sizeof(unsigned long) - 1;
const unsigned long* __next_bkt =
std::lower_bound(__prime_list + 5, __prime_list + __n_primes, __n);
+
+ if (__next_bkt == __prime_list + __n_primes)
+ // 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/testsuite/23_containers/unordered_set/hash_policy/26132.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc
index 092ee28..5c01fa7 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,15 +23,16 @@
#include <testsuite_hooks.h>
// libstdc++/26132
-void test01()
+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;
+ _USet us1;
+ typedef typename _USet::size_type size_type;
us1.max_load_factor(10.0);
@@ -50,8 +51,20 @@ void test01()
}
}
+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;
}
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 8a42ed4..0c3b7f8 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,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;
+ _USet us;
for (int i = 0; i != 100000; ++i)
{
us.insert(i);
@@ -32,7 +34,7 @@ void test01()
}
}
{
- std::unordered_set<int> us;
+ _USet us;
us.max_load_factor(3.f);
for (int i = 0; i != 100000; ++i)
{
@@ -41,7 +43,7 @@ void test01()
}
}
{
- std::unordered_set<int> us;
+ _USet us;
us.max_load_factor(.3f);
for (int i = 0; i != 100000; ++i)
{
@@ -51,8 +53,20 @@ void test01()
}
}
+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;
}
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 0000000..50a9dc9
--- /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
+// <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) == 1 );
+ VERIFY( policy._M_next_bkt(2) == 2 );
+ 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 46faa6d..2dac583 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 <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 @@ void test01()
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;
}
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 2419af1..7dcaf39 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,15 +20,23 @@
#include <unordered_set>
#include <vector>
#include <limits>
+
#include <ext/throw_allocator.h>
+
#include <testsuite_hooks.h>
+template<template<typename _Value, typename _Hash,
+ typename _Pred, typename _Alloc>
+ typename _USet>
void test01()
{
bool test __attribute__((unused)) = true;
+ // 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;
- std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+ _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;
@@ -63,12 +71,18 @@ void test01()
}
}
+template<template<typename _Value, typename _Hash,
+ typename _Pred, typename _Alloc>
+ typename _USet>
void test02()
{
bool test __attribute__((unused)) = true;
+ // 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;
- std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+ _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;
@@ -105,9 +119,23 @@ void test02()
}
}
+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;
}
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..eb253a5 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,12 +22,15 @@
#include <ext/throw_allocator.h>
#include <testsuite_hooks.h>
-void test01()
+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>,
+ _USet<int, std::hash<int>, std::equal_to<int>,
__gnu_cxx::throw_allocator_limit<int> > us;
int val = 0;
for (; val != 100; ++val)
@@ -49,7 +52,7 @@ void test01()
while (true)
{
- __gnu_cxx::limit_condition::set_limit(counter++);
+ __gnu_cxx::limit_condition::limit_adjustor adjustor(counter++);
bool do_break = false;
try
{
@@ -76,8 +79,22 @@ void test01()
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;
}
diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc
index a8b2675..784ac71 100644
--- a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc
@@ -127,8 +127,28 @@ template<bool cache>
using __umset = std::__umset_hashtable<Foo, HashFunction,
std::equal_to<Foo>,
std::allocator<Foo>,
+ 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 @@ int main()
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>>(
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 4de6598..44781d2 100644
--- a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc
@@ -177,6 +177,16 @@ template<bool cache>
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 @@ template<bool cache>
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 @@ int main()
"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>>(
@@ -212,5 +236,9 @@ int main()
"std::unordered_set<string> with hash code cached");
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;
}