This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
New hashtable power 2 rehash policy
- From: FranÃois Dumont <frs dot dumont at gmail dot com>
- To: "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, 23 Apr 2016 10:27:13 +0200
- Subject: New hashtable power 2 rehash policy
- Authentication-results: sourceware.org; auth=none
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:
54075.cc tr1 benches 455r 446u 8s
0mem 0pf
54075.cc std benches 466r 460u 6s
0mem 0pf
54075.cc std2 benches 375r 369u 6s
0mem 0pf
std2 benches is the one using power of 2 bucket count.
Note that I made use of __detected_or_t to avoid duplicating all
the code of _Rehash_base<>.
It brings a simplification of _Insert<>, it doesn't take a
_Unique_keys template parameter anymore. It allowed to remove a
specialization.
It also improve behavior when we reach maximum number of buckets,
we won't keep on trying to increase the number as it is impossible.
Last it fixes a small problem in 54075.cc bench. We were using
__uset_traits rather than __umset_traits in definition of __umset.
Results were not the expected ones.
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.
* src/c++11/hashable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
Consider when last prime number has been reach.
* testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
New.
* testsuite/performance/23_containers/insert/54075.cc: Add bench using
the new hash policy.
* testsuite/performance/23_containers/insert_erase/41975.cc: Likewise.
Tested under linux x64_86, ok to commit ?
FranÃois
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (révision 235348)
+++ include/bits/hashtable_policy.h (copie de travail)
@@ -457,6 +457,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 +503,136 @@
mutable std::size_t _M_next_resize;
};
+ /// Range hashing function assuming that second args 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); }
+ };
+
+
+ /// 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;
+ }
+ };
+
+ /// Rehash policy providing power of 2 bucket numbers. Ease 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
+ {
+ constexpr auto __max_bkt
+ = std::size_t(1) << ((sizeof(std::size_t) << 3) - 1);
+
+ 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;
+ else
+ _M_next_resize
+ = __builtin_floor(__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
@@ -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.
@@ -785,7 +916,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>
{
@@ -792,58 +923,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();
@@ -865,9 +961,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>
{
@@ -911,28 +1007,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
@@ -945,7 +1059,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: src/c++11/hashtable_c++0x.cc
===================================================================
--- src/c++11/hashtable_c++0x.cc (révision 235348)
+++ src/c++11/hashtable_c++0x.cc (copie de travail)
@@ -60,8 +60,16 @@
= sizeof(__prime_list) / sizeof(unsigned long) - 1;
const unsigned long* __next_bkt =
std::lower_bound(__prime_list + 5, __prime_list + __n_primes, __n);
- _M_next_resize =
- __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+
+ 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(0) - 1;
+ else
+ _M_next_resize =
+ __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+
return *__next_bkt;
}
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 (copie de travail)
@@ -0,0 +1,43 @@
+// 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;
+}
Index: testsuite/performance/23_containers/insert/54075.cc
===================================================================
--- testsuite/performance/23_containers/insert/54075.cc (révision 235348)
+++ testsuite/performance/23_containers/insert/54075.cc (copie de travail)
@@ -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 (révision 235348)
+++ testsuite/performance/23_containers/insert_erase/41975.cc (copie de travail)
@@ -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,18 @@
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 +224,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 +236,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;
}