* [v3] Fix management of non empty hash functor
@ 2012-12-13 21:33 François Dumont
[not found] ` <50E6BA2C.2060109@oracle.com>
0 siblings, 1 reply; 5+ messages in thread
From: François Dumont @ 2012-12-13 21:33 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 2063 bytes --]
Hi
As part of a performance patch proposed in an other mailing thread
was a patch to improve management of hash functor with state. This part
is I think less sensible than the performance patch so I propose it
independently. I only would like to commit the modification on the
performance tests here if you don't mind.
Thanks to this patch caching the hash code or not doesn't depend on
the hash functor to be empty of final anymore. I only keep the default
constructible condition so that local_iterator can be default
constructible, considering it is a Standard request.
2012-12-14 François Dumont <fdumont@gcc.gnu.org>
* include/bits/hashtable_policy.h (_Local_iterator_base): Use
_Hashtable_ebo_helper to embed necessary functors into the
local_iterator. Pass information about functors involved in hash
code by copy.
* include/bits/hashtable.h (__cache_default): Cache only if the
hash functor is not noexcept qualified or if it is slow or if the
hash functor do not expose a default constructor.
* include/debug/unordered_set
(std::__debug::unordered_set<>::erase): Detect local iterators to
invalidate using contained node rather than generating a dummy
local_iterator instance.
(std::__debug::unordered_multiset<>::erase): Likewise.
* include/debug/unordered_map
(std::__debug::unordered_map<>::erase): Likewise.
(std::__debug::unordered_multimap<>::erase): Likewise.
* testsuite/performance/23_containers/insert_erase/41975.cc: Test
std::tr1 and std versions of unordered_set regardless of any
macro. Add test on default cache behavior.
* testsuite/performance/23_containers/insert/54075.cc: Likewise.
* testsuite/23_containers/unordered_set/instantiation_neg.cc:
Adapt line number.
* testsuite/23_containers/unordered_set/
not_default_constructible_hash_neg.cc: New.
* testsuite/23_containers/unordered_set/buckets/swap.cc: New.
Tested under Linux x86_64, normal and debug modes.
Ok to commit ?
François
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 36141 bytes --]
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 194488)
+++ include/bits/hashtable_policy.h (working copy)
@@ -981,9 +981,17 @@
typedef void* __hash_code;
typedef _Hash_node<_Value, false> __node_type;
- // We need the default constructor for the local iterators.
+ public:
+ // We need the following public for local iterators.
+
_Hash_code_base() = default;
+ _Hash_code_base(const _Hash_code_base&) = default;
+ std::size_t
+ _M_bucket_index(const __node_type* __p, std::size_t __n) const
+ { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
+
+ protected:
_Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
const _Hash& __h)
: _EboExtractKey(__ex), _EboHash(__h) { }
@@ -996,10 +1004,6 @@
_M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const
{ return _M_ranged_hash()(__k, __n); }
- std::size_t
- _M_bucket_index(const __node_type* __p, std::size_t __n) const
- { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
-
void
_M_store_code(__node_type*, __hash_code) const
{ }
@@ -1062,13 +1066,19 @@
hash_function() const
{ return _M_h1(); }
+ // We need the following public for the local iterators.
typedef std::size_t __hash_code;
typedef _Hash_node<_Value, false> __node_type;
- protected:
- // We need the default constructor for the local iterators.
_Hash_code_base() = default;
+ _Hash_code_base(const _Hash_code_base&) = default;
+ std::size_t
+ _M_bucket_index(const __node_type* __p,
+ std::size_t __n) const
+ { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
+
+ protected:
_Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
@@ -1082,11 +1092,6 @@
_M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const
{ return _M_h2()(__c, __n); }
- std::size_t
- _M_bucket_index(const __node_type* __p,
- std::size_t __n) const
- { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
-
void
_M_store_code(__node_type*, __hash_code) const
{ }
@@ -1148,6 +1153,10 @@
typedef std::size_t __hash_code;
typedef _Hash_node<_Value, true> __node_type;
+ // Need the following public for local iterators.
+ const _H2&
+ _M_h2() const { return _EboH2::_S_cget(*this); }
+
protected:
_Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
@@ -1195,9 +1204,6 @@
_H1&
_M_h1() { return _EboH1::_S_get(*this); }
- const _H2&
- _M_h2() const { return _EboH2::_S_cget(*this); }
-
_H2&
_M_h2() { return _EboH2::_S_get(*this); }
};
@@ -1250,12 +1256,20 @@
typename _H1, typename _H2, typename _Hash>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, true>
- : private _H2
+ : private _Hashtable_ebo_helper<0, _H2>
{
+ protected:
+ typedef _Hashtable_ebo_helper<0, _H2> _EboH2;
+ typedef _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, true> _HashCodeBase;
+
+ public:
_Local_iterator_base() = default;
- _Local_iterator_base(_Hash_node<_Value, true>* __p,
+ _Local_iterator_base(const _HashCodeBase& __base,
+ _Hash_node<_Value, true>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+ : _EboH2(__base._M_h2()),
+ _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
void
_M_incr()
@@ -1263,15 +1277,13 @@
_M_cur = _M_cur->_M_next();
if (_M_cur)
{
- std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
+ std::size_t __bkt
+ = _EboH2::_S_get(*this)(_M_cur->_M_hash_code, _M_bucket_count);
if (__bkt != _M_bucket)
_M_cur = nullptr;
}
}
- const _H2& _M_h2() const
- { return *this; }
-
_Hash_node<_Value, true>* _M_cur;
std::size_t _M_bucket;
std::size_t _M_bucket_count;
@@ -1282,13 +1294,29 @@
typename _H1, typename _H2, typename _Hash>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, false>
- : private _Hash_code_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, false>
+ : private _Hashtable_ebo_helper<0,
+ _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false>>
{
+ protected:
+ typedef _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false> _HashCodeBase;
+ typedef _Hashtable_ebo_helper<0, _HashCodeBase> _EboHashCodeBase;
+
+ std::size_t
+ _M_bucket_index(_Hash_node<_Value, false>* __cur, std::size_t __bck_count)
+ {
+ return _EboHashCodeBase::_S_get(*this)._M_bucket_index(__cur,
+ __bck_count);
+ }
+
+ public:
_Local_iterator_base() = default;
- _Local_iterator_base(_Hash_node<_Value, false>* __p,
+ _Local_iterator_base(const _HashCodeBase& __base,
+ _Hash_node<_Value, false>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+ : _EboHashCodeBase(__base),
+ _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
void
_M_incr()
@@ -1296,7 +1324,7 @@
_M_cur = _M_cur->_M_next();
if (_M_cur)
{
- std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
+ std::size_t __bkt = _M_bucket_index(_M_cur, _M_bucket_count);
if (__bkt != _M_bucket)
_M_cur = nullptr;
}
@@ -1333,6 +1361,11 @@
: public _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __cache>
{
+ private:
+ typedef _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache> _Base;
+ typedef typename _Base::_HashCodeBase _HashCodeBase;
+ public:
typedef _Value value_type;
typedef typename std::conditional<__constant_iterators,
const _Value*, _Value*>::type
@@ -1346,10 +1379,10 @@
_Local_iterator() = default;
explicit
- _Local_iterator(_Hash_node<_Value, __cache>* __p,
+ _Local_iterator(const _HashCodeBase& __hash_code_base,
+ _Hash_node<_Value, __cache>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- __cache>(__p, __bkt, __bkt_count)
+ : _Base(__hash_code_base, __p, __bkt, __bkt_count)
{ }
reference
@@ -1384,6 +1417,12 @@
: public _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __cache>
{
+ private:
+ typedef _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache> _Base;
+ typedef typename _Base::_HashCodeBase _HashCodeBase;
+
+ public:
typedef _Value value_type;
typedef const _Value* pointer;
typedef const _Value& reference;
@@ -1393,19 +1432,17 @@
_Local_const_iterator() = default;
explicit
- _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
+ _Local_const_iterator(const _HashCodeBase& __hash_code_base,
+ _Hash_node<_Value, __cache>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- __cache>(__p, __bkt, __bkt_count)
+ : _Base(__hash_code_base, __p, __bkt, __bkt_count)
{ }
_Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash,
__constant_iterators,
__cache>& __x)
- : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- __cache>(__x._M_cur, __x._M_bucket,
- __x._M_bucket_count)
+ : _Base(__x)
{ }
reference
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 194488)
+++ include/bits/hashtable.h (working copy)
@@ -39,10 +39,14 @@
_GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Tp, typename _Hash>
- using __cache_default = __not_<__and_<is_integral<_Tp>,
- is_empty<_Hash>,
- integral_constant<bool, !__is_final(_Hash)>,
- __detail::__is_noexcept_hash<_Tp, _Hash> >>;
+ using __cache_default
+ = __not_<__and_<// Do not cache for builtin types.
+ is_integral<_Tp>,
+ // Mandatory to make local_iterator default
+ // constructible.
+ is_default_constructible<_Hash>,
+ // Mandatory to have erase not throwing.
+ __detail::__is_noexcept_hash<_Tp, _Hash>>>;
/**
* Primary class template _Hashtable.
@@ -249,21 +253,21 @@
" or qualify your hash functor with noexcept");
// Following two static assertions are necessary to guarantee
- // that swapping two hashtable instances won't invalidate
- // associated local iterators.
+ // that local_iterator will be default constructible.
- // When hash codes are cached local iterator only uses H2 which
- // must then be empty.
- static_assert(__if_hash_cached<is_empty<_H2>>::value,
+ // When hash codes are cached local iterator uses H2 functor which must
+ // then be default constructible.
+ static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
"Functor used to map hash code to bucket index"
- " must be empty");
+ " must be default constructible");
// When hash codes are not cached local iterator is going to use
// __hash_code_base above to compute node bucket index so it has
- // to be empty.
- static_assert(__if_hash_not_cached<is_empty<__hash_code_base>>::value,
- "Cache the hash code or make functors involved in hash code"
- " and bucket index computation empty");
+ // to be default constructible.
+ static_assert(__if_hash_not_cached<
+ is_default_constructible<__hash_code_base>>::value,
+ "Cache the hash code or make functors involved in hash code"
+ " and bucket index computation default constructibles");
public:
template<typename _Keya, typename _Valuea, typename _Alloca,
@@ -500,30 +504,37 @@
local_iterator
begin(size_type __n)
- { return local_iterator(_M_bucket_begin(__n), __n, _M_bucket_count); }
+ {
+ return local_iterator(*this, _M_bucket_begin(__n),
+ __n, _M_bucket_count);
+ }
local_iterator
end(size_type __n)
- { return local_iterator(nullptr, __n, _M_bucket_count); }
+ { return local_iterator(*this, nullptr, __n, _M_bucket_count); }
const_local_iterator
begin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n), __n,
- _M_bucket_count); }
+ {
+ return const_local_iterator(*this, _M_bucket_begin(__n),
+ __n, _M_bucket_count);
+ }
const_local_iterator
end(size_type __n) const
- { return const_local_iterator(nullptr, __n, _M_bucket_count); }
+ { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
// DR 691.
const_local_iterator
cbegin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n), __n,
- _M_bucket_count); }
+ {
+ return const_local_iterator(*this, _M_bucket_begin(__n),
+ __n, _M_bucket_count);
+ }
const_local_iterator
cend(size_type __n) const
- { return const_local_iterator(nullptr, __n, _M_bucket_count); }
+ { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
float
load_factor() const noexcept
@@ -1141,7 +1152,7 @@
{
if (this->_M_equals(__k, __code, __p))
return __prev_p;
- if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
+ if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
break;
__prev_p = __p;
}
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map (revision 194488)
+++ include/debug/unordered_map (working copy)
@@ -364,10 +364,9 @@
{
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base::erase(__victim);
_M_check_rehashed(__bucket_count);
@@ -383,10 +382,9 @@
_Base_const_iterator __victim = __it.base();
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -410,10 +408,9 @@
._M_iterator(__last, "last"));
this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(), __last.base());
@@ -452,22 +449,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Key, typename _Tp, typename _Hash,
@@ -812,10 +793,9 @@
{
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
_Base::erase(__victim++);
++__ret;
}
@@ -830,10 +810,9 @@
_Base_const_iterator __victim = __it.base();
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -857,10 +836,9 @@
._M_iterator(__last, "last"));
this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(), __last.base());
@@ -899,22 +877,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Key, typename _Tp, typename _Hash,
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set (revision 194488)
+++ include/debug/unordered_set (working copy)
@@ -359,10 +359,9 @@
this->_M_invalidate_if(
[__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base::erase(__victim);
_M_check_rehashed(__bucket_count);
@@ -379,10 +378,9 @@
this->_M_invalidate_if(
[__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -407,10 +405,9 @@
this->_M_invalidate_if(
[__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(),
@@ -451,22 +448,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
@@ -803,10 +784,9 @@
{
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
_Base::erase(__victim++);
++__ret;
}
@@ -820,10 +800,9 @@
_Base_const_iterator __victim = __it.base();
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
return iterator(_Base::erase(__it.base()), this);
}
@@ -844,10 +823,9 @@
._M_iterator(__last, "last"));
this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
return iterator(_Base::erase(__first.base(),
__last.base()), this);
@@ -884,22 +862,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
Index: testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (revision 0)
+++ testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (revision 0)
@@ -0,0 +1,51 @@
+// { dg-do compile }
+// { dg-options "-std=c++11" }
+// { dg-require-normal-mode "" }
+
+// Copyright (C) 2012 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-error "default constructibles" "" { target *-*-* } 268 }
+
+#include <unordered_set>
+
+namespace
+{
+ struct hash
+ {
+ hash(std::size_t seed)
+ : _M_seed(seed)
+ { }
+
+ std::size_t operator() (int val) const noexcept
+ { return val ^ _M_seed; }
+
+ private:
+ std::size_t _M_seed;
+ };
+}
+
+void
+test01()
+{
+ using traits = std::__detail::_Hashtable_traits<false, true, true>;
+ using hashtable = std::__uset_hashtable<int, hash,
+ std::equal_to<int>,
+ std::allocator<int>, traits>;
+
+ hashtable ht(10, hash(1));
+}
Index: testsuite/23_containers/unordered_set/buckets/swap.cc
===================================================================
--- testsuite/23_containers/unordered_set/buckets/swap.cc (revision 0)
+++ testsuite/23_containers/unordered_set/buckets/swap.cc (revision 0)
@@ -0,0 +1,72 @@
+// { dg-options "-std=c++11" }
+
+// Copyright (C) 2012 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/>.
+
+#include <testsuite_hooks.h>
+#include <unordered_set>
+
+namespace
+{
+ struct hash
+ {
+ hash() = default;
+ hash(int modulo)
+ : _M_modulo(modulo)
+ { }
+
+ std::size_t operator() (int val) const noexcept
+ { return val % _M_modulo; }
+
+ int _M_modulo;
+ };
+}
+
+void
+test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ // static_assert(std::__cache_default<int, hash>::value,
+ // "Unexpected default cache value");
+ typedef std::unordered_set<int, hash> us_t;
+ us_t us1(10, hash(13));
+ us_t us2(10, hash(7));
+
+ VERIFY( us1.hash_function()._M_modulo == 13 );
+ VERIFY( us2.hash_function()._M_modulo == 7 );
+
+ const int nb = 5;
+ for (int i = 0; i != nb * us1.hash_function()._M_modulo; ++i)
+ us1.insert(i);
+
+ us_t::local_iterator lit = us1.begin(12);
+ us_t::local_iterator litend = us1.end(12);
+ VERIFY( std::distance(lit, litend) == nb );
+
+ us1.swap(us2);
+
+ VERIFY( us1.hash_function()._M_modulo == 7 );
+ VERIFY( us2.hash_function()._M_modulo == 13 );
+
+ VERIFY( std::distance(lit, litend) == nb );
+}
+
+int main()
+{
+ test01();
+}
Index: testsuite/23_containers/unordered_set/instantiation_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/instantiation_neg.cc (revision 194488)
+++ testsuite/23_containers/unordered_set/instantiation_neg.cc (working copy)
@@ -19,7 +19,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-// { dg-error "with noexcept" "" { target *-*-* } 247 }
+// { dg-error "with noexcept" "" { target *-*-* } 251 }
#include <unordered_set>
Index: testsuite/performance/23_containers/insert_erase/41975.cc
===================================================================
--- testsuite/performance/23_containers/insert_erase/41975.cc (revision 194488)
+++ testsuite/performance/23_containers/insert_erase/41975.cc (working copy)
@@ -18,25 +18,18 @@
// <http://www.gnu.org/licenses/>.
#include <sstream>
-#ifdef _USE_TR1
-# include <tr1/unordered_set>
-#else
-# include <unordered_set>
-#endif
+#include <tr1/unordered_set>
+#include <unordered_set>
#include <testsuite_performance.h>
namespace
{
// Bench using an unordered_set<int>. Hash functor for int is quite
// predictable so it helps bench very specific use cases.
- template<bool use_cache>
- void bench()
+ template<typename _ContType>
+ void bench(const char* desc)
{
using namespace __gnu_test;
- std::ostringstream ostr;
- ostr << "unordered_set<int> " << (use_cache ? "with" : "without")
- << " cache";
- const std::string desc = ostr.str();
time_counter time;
resource_counter resource;
@@ -44,20 +37,12 @@
const int nb = 200000;
start_counters(time, resource);
-#ifdef _USE_TR1
- std::tr1::__unordered_set<int, std::hash<int>, std::equal_to<int>,
- std::allocator<int>,
- use_cache> us;
-#else
- std::__uset_hashtable<int, std::hash<int>, std::equal_to<int>,
- std::allocator<int>,
- std::__uset_traits<use_cache>> us;
-#endif
+ _ContType us;
for (int i = 0; i != nb; ++i)
us.insert(i);
stop_counters(time, resource);
- ostr.str("");
+ std::ostringstream ostr;
ostr << desc << ": first insert";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
@@ -110,14 +95,10 @@
// Bench using unordered_set<string> that show how important it is to cache
// hash code as computing string hash code is quite expensive compared to
// computing it for int.
- template<bool use_cache>
- void bench_str()
+ template<typename _ContType>
+ void bench_str(const char* desc)
{
using namespace __gnu_test;
- std::ostringstream ostr;
- ostr << "unordered_set<string> " << (use_cache ? "with" : "without")
- << " cache";
- const std::string desc = ostr.str();
time_counter time;
resource_counter resource;
@@ -125,6 +106,7 @@
const int nb = 200000;
// First generate once strings that are going to be used throughout the
// bench:
+ std::ostringstream ostr;
std::vector<std::string> strs;
strs.reserve(nb);
for (int i = 0; i != nb; ++i)
@@ -136,17 +118,7 @@
start_counters(time, resource);
-#ifdef _USE_TR1
- std::tr1::__unordered_set<std::string, std::hash<std::string>,
- std::equal_to<std::string>,
- std::allocator<std::string>,
- use_cache> us;
-#else
- std::__uset_hashtable<std::string, std::hash<std::string>,
- std::equal_to<std::string>,
- std::allocator<std::string>,
- std::__uset_traits<use_cache>> us;
-#endif
+ _ContType us;
for (int i = 0; i != nb; ++i)
us.insert(strs[i]);
@@ -192,11 +164,53 @@
}
}
+template<bool cache>
+ using __uset =
+ std::__uset_hashtable<int, std::hash<int>, std::equal_to<int>,
+ std::allocator<int>,
+ std::__uset_traits<cache>>;
+
+template<bool cache>
+ using __tr1_uset =
+ std::tr1::__unordered_set<int, std::hash<int>, std::equal_to<int>,
+ std::allocator<int>,
+ cache>;
+
+template<bool cache>
+ using __str_uset =
+ std::__uset_hashtable<std::string, std::hash<std::string>,
+ std::equal_to<std::string>,
+ std::allocator<std::string>,
+ std::__uset_traits<cache>>;
+
+template<bool cache>
+ using __tr1_str_uset =
+ std::tr1::__unordered_set<std::string, std::hash<std::string>,
+ std::equal_to<std::string>,
+ std::allocator<std::string>,
+ cache>;
+
int main()
{
- bench<false>();
- bench<true>();
- bench_str<false>();
- bench_str<true>();
+ bench<__tr1_uset<false>>(
+ "std::tr1::unordered_set<int> without hash code cached");
+ bench<__tr1_uset<true>>(
+ "std::tr1::unordered_set<int> with hash code cached");
+ bench<__uset<false>>(
+ "std::unordered_set<int> without hash code cached");
+ bench<__uset<true>>(
+ "std::unordered_set<int> with hash code cached");
+ bench<std::unordered_set<int>>(
+ "std::unordered_set<int> default cache");
+ bench_str<__tr1_str_uset<false>>(
+ "std::tr1::unordered_set<string> without hash code cached");
+ bench_str<__tr1_str_uset<true>>(
+ "std::tr1::unordered_set<string> with hash code cached");
+ bench_str<__str_uset<false>>(
+ "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>>(
+ "std::unordered_set<string> default cache");
return 0;
}
Index: testsuite/performance/23_containers/insert/54075.cc
===================================================================
--- testsuite/performance/23_containers/insert/54075.cc (revision 194488)
+++ testsuite/performance/23_containers/insert/54075.cc (working copy)
@@ -15,14 +15,18 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
+// { dg-add-options no_pch }
// { dg-options "-std=c++11" }
#include <testsuite_performance.h>
#include <random>
#include <sstream>
#include <tr1/unordered_set>
-#include<unordered_set>
+#include <unordered_set>
+#define USE_MY_FOO 1
+
+#if USE_MY_FOO
struct Foo
{
typedef std::random_device::result_type _Type;
@@ -54,36 +58,57 @@
{ return t.hash(); }
};
+#else
+
+struct Foo
+{
+ int bar;
+ int baz;
+ int meh;
+ Foo()
+ {
+ bar = random(); baz = random(); meh = random();
+ }
+ Foo(const Foo&) = default;
+ size_t hash() const noexcept { return bar^baz^meh; }
+ inline bool operator==(const Foo& other) const {
+ return other.bar == bar && other.baz == baz && other.meh == meh;
+ }
+};
+
+struct HashFunction
+{
+ template<typename T>
+ size_t operator()(const T& t) const noexcept {
+ return t.hash();
+ }
+};
+
+#endif
+
+const int sz = 300000;
+
template<typename _ContType>
- void bench(const char* container_desc)
+void bench(const char* container_desc, const Foo* foos)
{
using namespace __gnu_test;
+ _ContType s;
+
time_counter time;
resource_counter resource;
-
- const int sz = 300000;
-
- Foo foos[sz];
- {
- std::random_device randev;
- for (int i = 0; i != sz; ++i)
- foos[i].init(randev);
- }
-
- _ContType s;
start_counters(time, resource);
for (int i = 0; i != sz ; ++i)
- s.insert(foos[i]);
+ s.insert(foos[i]);
stop_counters(time, resource);
std::ostringstream ostr;
- ostr << container_desc << sz << " Foo insertions";
+ ostr << container_desc << sz << " Foo insertions, "
+ << s.size() << " inserted";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
// Try to insert again to check performance of collision detection
-
const int nb_loop = 10;
start_counters(time, resource);
@@ -121,12 +146,48 @@
int main()
{
- bench<__tr1_uset<false>>("std::tr1::unordered_set without hash code cached ");
- bench<__tr1_uset<true>>("std::tr1::unordered_set with hash code cached ");
- bench<__tr1_umset<false>>("std::tr1::unordered_multiset without hash code cached ");
- bench<__tr1_umset<true>>("std::tr1::unordered_multiset with hash code cached ");
- bench<__uset<false>>("std::unordered_set without hash code cached ");
- bench<__uset<true>>("std::unordered_set with hash code cached ");
- bench<__umset<false>>("std::unordered_multiset without hash code cached ");
- bench<__umset<true>>("std::unordered_multiset with hash code cached ");
+ using namespace __gnu_test;
+
+ Foo foos[sz];
+#if USE_MY_FOO
+ {
+ std::random_device randev;
+ for (int i = 0; i != sz; ++i)
+ foos[i].init(randev);
+ }
+#endif
+
+ time_counter time;
+ resource_counter resource;
+ start_counters(time, resource);
+
+ bench<__tr1_uset<false>>(
+ "std::tr1::unordered_set without hash code cached ", foos);
+ bench<__tr1_uset<true>>(
+ "std::tr1::unordered_set with hash code cached ", foos);
+ bench<__tr1_umset<false>>(
+ "std::tr1::unordered_multiset without hash code cached ", foos);
+ bench<__tr1_umset<true>>(
+ "std::tr1::unordered_multiset with hash code cached ", foos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "tr1 benches", time, resource);
+
+ start_counters(time, resource);
+ bench<__uset<false>>(
+ "std::unordered_set without hash code cached ", foos);
+ bench<__uset<true>>(
+ "std::unordered_set with hash code cached ", foos);
+ bench<__umset<false>>(
+ "std::unordered_multiset without hash code cached ", foos);
+ bench<__umset<true>>(
+ "std::unordered_multiset with hash code cached ", foos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "std benches", time, resource);
+
+ bench<std::unordered_set<Foo, HashFunction>>(
+ "std::unordered_set default cache ", foos);
+ bench<std::unordered_multiset<Foo, HashFunction>>(
+ "std::unordered_multiset default cache ", foos);
}
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [v3] Fix management of non empty hash functor
[not found] ` <50E6BA2C.2060109@oracle.com>
@ 2013-01-10 21:02 ` François Dumont
2013-01-28 15:43 ` Jonathan Wakely
0 siblings, 1 reply; 5+ messages in thread
From: François Dumont @ 2013-01-10 21:02 UTC (permalink / raw)
To: Paolo Carlini; +Cc: libstdc++, Jonathan Wakely, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 4236 bytes --]
Hi
Here is an other version of this patch. Indeed there were no need
to expose many stuff public. Inheriting from _Hash_code_base is fine, it
is not final and it deals with EBO itself. I only kept usage of
_Hashtable_ebo_helper when embedding H2 functor. As it is an extension
we could have impose it not to be final but it doesn't cost a lot to
deal with it. Finally I only needed a single friend declaration to get
access to the H2 part of _Hash_code_base.
I didn't touch the default cache policy for the moment except
reducing constraints on the hash functor. I prefer to submit an other
patch to change when we cache or not depending on the hash functor
expected performance.
I also took the time to replace some typedef expressions with using
ones. I really know what is the rule about using one or the other but I
remembered that Benjamin spent quite some time changing typedef in using
so I prefer to stick to this approach in this file, even if there are
still some typedef left.
Tested under linux x86_64 normal and debug modes.
2013-01-10 François Dumont <fdumont@gcc.gnu.org>
* include/bits/hashtable_policy.h (_Local_iterator_base): Use
_Hashtable_ebo_helper to embed necessary functors into the
local_iterator when necessary. Pass information about functors
involved in hash code by copy.
* include/bits/hashtable.h (__cache_default): Do not cache for
builtin integral types unless the hash functor is not noexcept
qualified or is not default constructible. Adapt static assertions
and local iteraror instantiations.
* include/debug/unordered_set
(std::__debug::unordered_set<>::erase): Detect local iterators to
invalidate using contained node rather than generating a dummy
local_iterator instance.
(std::__debug::unordered_multiset<>::erase): Likewise.
* include/debug/unordered_map
(std::__debug::unordered_map<>::erase): Likewise.
(std::__debug::unordered_multimap<>::erase): Likewise.
* testsuite/performance/23_containers/insert_erase/41975.cc: Test
std::tr1 and std versions of unordered_set regardless of any
macro. Add test on default cache behavior.
* testsuite/performance/23_containers/insert/54075.cc: Likewise.
* testsuite/23_containers/unordered_set/instantiation_neg.cc:
Adapt line number.
* testsuite/23_containers/unordered_set/
not_default_constructible_hash_neg.cc: New.
* testsuite/23_containers/unordered_set/buckets/swap.cc: New.
If you agree with the patch tell me where and when to apply it.
François
On 01/04/2013 12:17 PM, Paolo Carlini wrote:
> Hi,
>
> On 12/13/2012 10:32 PM, François Dumont wrote:
>> Hi
>>
>> As part of a performance patch proposed in an other mailing
>> thread was a patch to improve management of hash functor with state.
>> This part is I think less sensible than the performance patch so I
>> propose it independently. I only would like to commit the
>> modification on the performance tests here if you don't mind.
>>
>> Thanks to this patch caching the hash code or not doesn't depend
>> on the hash functor to be empty of final anymore. I only keep the
>> default constructible condition so that local_iterator can be default
>> constructible, considering it is a Standard request.
> I'm finally having a closer look at this work of yours (sorry aboutt
> the delay!) and I think we want something similar for 4.8.0. However,
> to be honest, I'm not convinced we are implementing the general idea
> in the best way, in particular I don't like the much more complex
> access control structure, _Hash_code_base loses encapsulation, etc.
> Did you consider maybe adding friend declarations in a few places?
>
> Jon, do you have suggestiong? The idea of managing to get rid of the
> empty & !final requirement for dispatching seems right to me.
>
> By the way, I'm also not convinced that is_integral is the right
> category, I think is_scalar for example is better: pointers are common
> and very similar in terms of std::hash, likewise floating point
> quantities (with the possible exception of long double, but I don't
> think we should spend time on it).
>
> Paolo.
>
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 43209 bytes --]
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 195097)
+++ include/bits/hashtable_policy.h (working copy)
@@ -1,6 +1,6 @@
// Internal policy header for unordered_set and unordered_map -*- C++ -*-
-// Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc.
+// Copyright (C) 2010-2013 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
@@ -202,7 +202,7 @@
template<typename _Value, bool _Cache_hash_code>
struct _Node_iterator_base
{
- typedef _Hash_node<_Value, _Cache_hash_code> __node_type;
+ using __node_type = _Hash_node<_Value, _Cache_hash_code>;
__node_type* _M_cur;
@@ -282,7 +282,7 @@
struct _Node_const_iterator
: public _Node_iterator_base<_Value, __cache>
{
- private:
+ private:
using __base_type = _Node_iterator_base<_Value, __cache>;
using __node_type = typename __base_type::__node_type;
@@ -941,6 +941,17 @@
};
/**
+ * Primary class template _Local_iterator_base.
+ *
+ * Base class for local iterators, used to iterate within a bucket
+ * but not between buckets.
+ */
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash,
+ bool __cache_hash_code>
+ struct _Local_iterator_base;
+
+ /**
* Primary class template _Hash_code_base.
*
* Encapsulates two policy issues that aren't quite orthogonal.
@@ -974,8 +985,8 @@
private _Hashtable_ebo_helper<1, _Hash>
{
private:
- typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
- typedef _Hashtable_ebo_helper<1, _Hash> _EboHash;
+ using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
+ using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>;
protected:
typedef void* __hash_code;
@@ -986,7 +997,7 @@
_Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
const _Hash& __h)
- : _EboExtractKey(__ex), _EboHash(__h) { }
+ : __ebo_extract_key(__ex), __ebo_hash(__h) { }
__hash_code
_M_hash_code(const _Key& __key) const
@@ -1017,16 +1028,16 @@
protected:
const _ExtractKey&
- _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
_ExtractKey&
- _M_extract() { return _EboExtractKey::_S_get(*this); }
+ _M_extract() { return __ebo_extract_key::_S_get(*this); }
const _Hash&
- _M_ranged_hash() const { return _EboHash::_S_cget(*this); }
+ _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
_Hash&
- _M_ranged_hash() { return _EboHash::_S_get(*this); }
+ _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
};
// No specialization for ranged hash function while caching hash codes.
@@ -1041,7 +1052,7 @@
/// Specialization: hash function and range-hashing function, no
/// caching of hash codes.
- /// Provides typedef and accessor required by TR1.
+ /// Provides typedef and accessor required by C++ 11.
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
@@ -1051,9 +1062,9 @@
private _Hashtable_ebo_helper<2, _H2>
{
private:
- typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
- typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
- typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
+ using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
+ using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
+ using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
public:
typedef _H1 hasher;
@@ -1062,17 +1073,17 @@
hash_function() const
{ return _M_h1(); }
+ protected:
typedef std::size_t __hash_code;
typedef _Hash_node<_Value, false> __node_type;
- protected:
// We need the default constructor for the local iterators.
_Hash_code_base() = default;
_Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
- : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
+ : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
__hash_code
_M_hash_code(const _Key& __k) const
@@ -1104,27 +1115,27 @@
}
const _ExtractKey&
- _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
_ExtractKey&
- _M_extract() { return _EboExtractKey::_S_get(*this); }
+ _M_extract() { return __ebo_extract_key::_S_get(*this); }
const _H1&
- _M_h1() const { return _EboH1::_S_cget(*this); }
+ _M_h1() const { return __ebo_h1::_S_cget(*this); }
_H1&
- _M_h1() { return _EboH1::_S_get(*this); }
+ _M_h1() { return __ebo_h1::_S_get(*this); }
const _H2&
- _M_h2() const { return _EboH2::_S_cget(*this); }
+ _M_h2() const { return __ebo_h2::_S_cget(*this); }
_H2&
- _M_h2() { return _EboH2::_S_get(*this); }
+ _M_h2() { return __ebo_h2::_S_get(*this); }
};
/// Specialization: hash function and range-hashing function,
/// caching hash codes. H is provided but ignored. Provides
- /// typedef and accessor required by TR1.
+ /// typedef and accessor required by C++ 11.
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
@@ -1134,10 +1145,14 @@
private _Hashtable_ebo_helper<2, _H2>
{
private:
- typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
- typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
- typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
+ // Gives access to _M_h2() to the local iterator implementation.
+ friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
+ _Default_ranged_hash, true>;
+ using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
+ using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
+ using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
+
public:
typedef _H1 hasher;
@@ -1145,14 +1160,14 @@
hash_function() const
{ return _M_h1(); }
+ protected:
typedef std::size_t __hash_code;
typedef _Hash_node<_Value, true> __node_type;
- protected:
_Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
- : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
+ : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
__hash_code
_M_hash_code(const _Key& __k) const
@@ -1184,22 +1199,22 @@
}
const _ExtractKey&
- _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
_ExtractKey&
- _M_extract() { return _EboExtractKey::_S_get(*this); }
+ _M_extract() { return __ebo_extract_key::_S_get(*this); }
const _H1&
- _M_h1() const { return _EboH1::_S_cget(*this); }
+ _M_h1() const { return __ebo_h1::_S_cget(*this); }
_H1&
- _M_h1() { return _EboH1::_S_get(*this); }
+ _M_h1() { return __ebo_h1::_S_get(*this); }
const _H2&
- _M_h2() const { return _EboH2::_S_cget(*this); }
+ _M_h2() const { return __ebo_h2::_S_cget(*this); }
_H2&
- _M_h2() { return _EboH2::_S_get(*this); }
+ _M_h2() { return __ebo_h2::_S_get(*this); }
};
/**
@@ -1234,28 +1249,25 @@
};
- /**
- * Primary class template _Local_iterator_base.
- *
- * Base class for local iterators, used to iterate within a bucket
- * but not between buckets.
- */
- template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash,
- bool __cache_hash_code>
- struct _Local_iterator_base;
-
/// Specialization.
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, true>
- : private _H2
+ : private _Hashtable_ebo_helper<0, _H2>
{
+ protected:
+ using __base_type = _Hashtable_ebo_helper<0, _H2>;
+ using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, true>;
+
+ public:
_Local_iterator_base() = default;
- _Local_iterator_base(_Hash_node<_Value, true>* __p,
+ _Local_iterator_base(const __hash_code_base& __base,
+ _Hash_node<_Value, true>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+ : __base_type(__base._M_h2()),
+ _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
void
_M_incr()
@@ -1263,15 +1275,14 @@
_M_cur = _M_cur->_M_next();
if (_M_cur)
{
- std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
+ std::size_t __bkt
+ = __base_type::_S_get(*this)(_M_cur->_M_hash_code,
+ _M_bucket_count);
if (__bkt != _M_bucket)
_M_cur = nullptr;
}
}
- const _H2& _M_h2() const
- { return *this; }
-
_Hash_node<_Value, true>* _M_cur;
std::size_t _M_bucket;
std::size_t _M_bucket_count;
@@ -1285,10 +1296,17 @@
: private _Hash_code_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, false>
{
+ protected:
+ using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false>;
+
+ public:
_Local_iterator_base() = default;
- _Local_iterator_base(_Hash_node<_Value, false>* __p,
+ _Local_iterator_base(const __hash_code_base& __base,
+ _Hash_node<_Value, false>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+ : __hash_code_base(__base),
+ _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
void
_M_incr()
@@ -1333,6 +1351,11 @@
: public _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __cache>
{
+ private:
+ using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+ public:
typedef _Value value_type;
typedef typename std::conditional<__constant_iterators,
const _Value*, _Value*>::type
@@ -1345,11 +1368,10 @@
_Local_iterator() = default;
- explicit
- _Local_iterator(_Hash_node<_Value, __cache>* __p,
+ _Local_iterator(const __hash_code_base& __base,
+ _Hash_node<_Value, __cache>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- __cache>(__p, __bkt, __bkt_count)
+ : __base_type(__base, __p, __bkt, __bkt_count)
{ }
reference
@@ -1384,6 +1406,12 @@
: public _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __cache>
{
+ private:
+ using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+
+ public:
typedef _Value value_type;
typedef const _Value* pointer;
typedef const _Value& reference;
@@ -1392,20 +1420,17 @@
_Local_const_iterator() = default;
- explicit
- _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
+ _Local_const_iterator(const __hash_code_base& __base,
+ _Hash_node<_Value, __cache>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- __cache>(__p, __bkt, __bkt_count)
+ : __base_type(__base, __p, __bkt, __bkt_count)
{ }
_Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash,
__constant_iterators,
__cache>& __x)
- : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- __cache>(__x._M_cur, __x._M_bucket,
- __x._M_bucket_count)
+ : __base_type(__x)
{ }
reference
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 195097)
+++ include/bits/hashtable.h (working copy)
@@ -1,6 +1,6 @@
// hashtable.h header -*- C++ -*-
-// Copyright (C) 2007-2012 Free Software Foundation, Inc.
+// Copyright (C) 2007-2013 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
@@ -39,10 +39,15 @@
_GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Tp, typename _Hash>
- using __cache_default = __not_<__and_<is_integral<_Tp>,
- is_empty<_Hash>,
- integral_constant<bool, !__is_final(_Hash)>,
- __detail::__is_noexcept_hash<_Tp, _Hash> >>;
+ using __cache_default
+ = __not_<__and_<// Do not cache for builtin integral types having trivial
+ // hasher.
+ is_integral<_Tp>,
+ // Mandatory to make local_iterator default
+ // constructible.
+ is_default_constructible<_Hash>,
+ // Mandatory to have erase not throwing.
+ __detail::__is_noexcept_hash<_Tp, _Hash>>>;
/**
* Primary class template _Hashtable.
@@ -249,21 +254,21 @@
" or qualify your hash functor with noexcept");
// Following two static assertions are necessary to guarantee
- // that swapping two hashtable instances won't invalidate
- // associated local iterators.
+ // that local_iterator will be default constructible.
- // When hash codes are cached local iterator only uses H2 which
- // must then be empty.
- static_assert(__if_hash_cached<is_empty<_H2>>::value,
+ // When hash codes are cached local iterator inherits from H2 functor
+ // which must then be default constructible.
+ static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
"Functor used to map hash code to bucket index"
- " must be empty");
+ " must be default constructible");
- // When hash codes are not cached local iterator is going to use
- // __hash_code_base above to compute node bucket index so it has
- // to be empty.
- static_assert(__if_hash_not_cached<is_empty<__hash_code_base>>::value,
- "Cache the hash code or make functors involved in hash code"
- " and bucket index computation empty");
+ // When hash codes are not cached local iterator inherits from
+ // __hash_code_base above to compute node bucket index so it has to be
+ // default constructible.
+ static_assert(__if_hash_not_cached<
+ is_default_constructible<__hash_code_base>>::value,
+ "Cache the hash code or make functors involved in hash code"
+ " and bucket index computation default constructibles");
public:
template<typename _Keya, typename _Valuea, typename _Alloca,
@@ -500,30 +505,37 @@
local_iterator
begin(size_type __n)
- { return local_iterator(_M_bucket_begin(__n), __n, _M_bucket_count); }
+ {
+ return local_iterator(*this, _M_bucket_begin(__n),
+ __n, _M_bucket_count);
+ }
local_iterator
end(size_type __n)
- { return local_iterator(nullptr, __n, _M_bucket_count); }
+ { return local_iterator(*this, nullptr, __n, _M_bucket_count); }
const_local_iterator
begin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n), __n,
- _M_bucket_count); }
+ {
+ return const_local_iterator(*this, _M_bucket_begin(__n),
+ __n, _M_bucket_count);
+ }
const_local_iterator
end(size_type __n) const
- { return const_local_iterator(nullptr, __n, _M_bucket_count); }
+ { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
// DR 691.
const_local_iterator
cbegin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n), __n,
- _M_bucket_count); }
+ {
+ return const_local_iterator(*this, _M_bucket_begin(__n),
+ __n, _M_bucket_count);
+ }
const_local_iterator
cend(size_type __n) const
- { return const_local_iterator(nullptr, __n, _M_bucket_count); }
+ { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
float
load_factor() const noexcept
@@ -1141,7 +1153,7 @@
{
if (this->_M_equals(__k, __code, __p))
return __prev_p;
- if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
+ if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
break;
__prev_p = __p;
}
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map (revision 195097)
+++ include/debug/unordered_map (working copy)
@@ -1,7 +1,6 @@
// Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
-// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
-// Free Software Foundation, Inc.
+// Copyright (C) 2003-2013 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
@@ -364,10 +363,9 @@
{
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base::erase(__victim);
_M_check_rehashed(__bucket_count);
@@ -383,10 +381,9 @@
_Base_const_iterator __victim = __it.base();
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -410,10 +407,9 @@
._M_iterator(__last, "last"));
this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(), __last.base());
@@ -452,22 +448,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Key, typename _Tp, typename _Hash,
@@ -812,10 +792,9 @@
{
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
_Base::erase(__victim++);
++__ret;
}
@@ -830,10 +809,9 @@
_Base_const_iterator __victim = __it.base();
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -857,10 +835,9 @@
._M_iterator(__last, "last"));
this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(), __last.base());
@@ -899,22 +876,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Key, typename _Tp, typename _Hash,
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set (revision 195097)
+++ include/debug/unordered_set (working copy)
@@ -1,7 +1,6 @@
// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
-// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
-// Free Software Foundation, Inc.
+// Copyright (C) 2003-2013 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
@@ -359,10 +358,9 @@
this->_M_invalidate_if(
[__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base::erase(__victim);
_M_check_rehashed(__bucket_count);
@@ -379,10 +377,9 @@
this->_M_invalidate_if(
[__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -407,10 +404,9 @@
this->_M_invalidate_if(
[__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(),
@@ -451,22 +447,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
@@ -803,10 +783,9 @@
{
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
_Base::erase(__victim++);
++__ret;
}
@@ -820,10 +799,9 @@
_Base_const_iterator __victim = __it.base();
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
return iterator(_Base::erase(__it.base()), this);
}
@@ -844,10 +822,9 @@
._M_iterator(__last, "last"));
this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
return iterator(_Base::erase(__first.base(),
__last.base()), this);
@@ -884,22 +861,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
Index: testsuite/performance/23_containers/insert/54075.cc
===================================================================
--- testsuite/performance/23_containers/insert/54075.cc (revision 195097)
+++ testsuite/performance/23_containers/insert/54075.cc (working copy)
@@ -1,4 +1,4 @@
-// Copyright (C) 2012 Free Software Foundation, Inc.
+// Copyright (C) 2012-2013 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
@@ -21,10 +21,14 @@
#include <random>
#include <sstream>
#include <tr1/unordered_set>
-#include<unordered_set>
+#include <unordered_set>
+#define USE_MY_FOO 1
+
struct Foo
{
+#if USE_MY_FOO
+
typedef std::random_device::result_type _Type;
_Type bar;
_Type baz;
@@ -38,6 +42,18 @@
meh = randev();
}
+#else
+
+ int bar;
+ int baz;
+ int meh;
+
+ Foo()
+ { bar = random(); baz = random(); meh = random(); }
+ Foo(const Foo&) = default;
+
+#endif
+
std::size_t
hash() const noexcept
{ return std::size_t(bar ^ baz ^ meh); }
@@ -54,36 +70,30 @@
{ return t.hash(); }
};
+const int sz = 300000;
+
template<typename _ContType>
- void bench(const char* container_desc)
+ void
+ bench(const char* container_desc, const typename _ContType::value_type* foos)
{
using namespace __gnu_test;
+ _ContType s;
+
time_counter time;
resource_counter resource;
-
- const int sz = 300000;
-
- Foo foos[sz];
- {
- std::random_device randev;
- for (int i = 0; i != sz; ++i)
- foos[i].init(randev);
- }
-
- _ContType s;
start_counters(time, resource);
for (int i = 0; i != sz ; ++i)
- s.insert(foos[i]);
+ s.insert(foos[i]);
stop_counters(time, resource);
std::ostringstream ostr;
- ostr << container_desc << sz << " Foo insertions";
+ ostr << container_desc << sz << " insertion attempts, "
+ << s.size() << " inserted";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
// Try to insert again to check performance of collision detection
-
const int nb_loop = 10;
start_counters(time, resource);
@@ -94,7 +104,7 @@
stop_counters(time, resource);
ostr.str("");
ostr << container_desc << nb_loop << " times insertion of "
- << sz << " Foo";
+ << sz << " elements";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
}
@@ -121,12 +131,58 @@
int main()
{
- bench<__tr1_uset<false>>("std::tr1::unordered_set without hash code cached ");
- bench<__tr1_uset<true>>("std::tr1::unordered_set with hash code cached ");
- bench<__tr1_umset<false>>("std::tr1::unordered_multiset without hash code cached ");
- bench<__tr1_umset<true>>("std::tr1::unordered_multiset with hash code cached ");
- bench<__uset<false>>("std::unordered_set without hash code cached ");
- bench<__uset<true>>("std::unordered_set with hash code cached ");
- bench<__umset<false>>("std::unordered_multiset without hash code cached ");
- bench<__umset<true>>("std::unordered_multiset with hash code cached ");
+ using namespace __gnu_test;
+
+ {
+ int bars[sz];
+ for (int i = 0; i != sz; ++i)
+ bars[i] = i;
+ bench<std::tr1::unordered_set<int>>(
+ "std::tr1::unordered_set<int> ", bars);
+ bench<std::unordered_set<int>>(
+ "std::unordered_set<int> ", bars);
+ }
+
+ Foo foos[sz];
+#if USE_MY_FOO
+ {
+ std::random_device randev;
+ for (int i = 0; i != sz; ++i)
+ foos[i].init(randev);
+ }
+#endif
+
+ time_counter time;
+ resource_counter resource;
+ start_counters(time, resource);
+
+ bench<__tr1_uset<false>>(
+ "std::tr1::unordered_set without hash code cached ", foos);
+ bench<__tr1_uset<true>>(
+ "std::tr1::unordered_set with hash code cached ", foos);
+ bench<__tr1_umset<false>>(
+ "std::tr1::unordered_multiset without hash code cached ", foos);
+ bench<__tr1_umset<true>>(
+ "std::tr1::unordered_multiset with hash code cached ", foos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "tr1 benches", time, resource);
+
+ start_counters(time, resource);
+ bench<__uset<false>>(
+ "std::unordered_set without hash code cached ", foos);
+ bench<__uset<true>>(
+ "std::unordered_set with hash code cached ", foos);
+ bench<__umset<false>>(
+ "std::unordered_multiset without hash code cached ", foos);
+ bench<__umset<true>>(
+ "std::unordered_multiset with hash code cached ", foos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "std benches", time, resource);
+
+ bench<std::unordered_set<Foo, HashFunction>>(
+ "std::unordered_set default cache ", foos);
+ bench<std::unordered_multiset<Foo, HashFunction>>(
+ "std::unordered_multiset default cache ", foos);
}
Index: testsuite/performance/23_containers/insert_erase/41975.cc
===================================================================
--- testsuite/performance/23_containers/insert_erase/41975.cc (revision 195097)
+++ testsuite/performance/23_containers/insert_erase/41975.cc (working copy)
@@ -1,6 +1,6 @@
// { dg-options "-std=gnu++0x" }
-// Copyright (C) 2011 Free Software Foundation, Inc.
+// Copyright (C) 2011-2013 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
@@ -18,25 +18,18 @@
// <http://www.gnu.org/licenses/>.
#include <sstream>
-#ifdef _USE_TR1
-# include <tr1/unordered_set>
-#else
-# include <unordered_set>
-#endif
+#include <tr1/unordered_set>
+#include <unordered_set>
#include <testsuite_performance.h>
namespace
{
// Bench using an unordered_set<int>. Hash functor for int is quite
// predictable so it helps bench very specific use cases.
- template<bool use_cache>
- void bench()
+ template<typename _ContType>
+ void bench(const char* desc)
{
using namespace __gnu_test;
- std::ostringstream ostr;
- ostr << "unordered_set<int> " << (use_cache ? "with" : "without")
- << " cache";
- const std::string desc = ostr.str();
time_counter time;
resource_counter resource;
@@ -44,20 +37,12 @@
const int nb = 200000;
start_counters(time, resource);
-#ifdef _USE_TR1
- std::tr1::__unordered_set<int, std::hash<int>, std::equal_to<int>,
- std::allocator<int>,
- use_cache> us;
-#else
- std::__uset_hashtable<int, std::hash<int>, std::equal_to<int>,
- std::allocator<int>,
- std::__uset_traits<use_cache>> us;
-#endif
+ _ContType us;
for (int i = 0; i != nb; ++i)
us.insert(i);
stop_counters(time, resource);
- ostr.str("");
+ std::ostringstream ostr;
ostr << desc << ": first insert";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
@@ -110,14 +95,10 @@
// Bench using unordered_set<string> that show how important it is to cache
// hash code as computing string hash code is quite expensive compared to
// computing it for int.
- template<bool use_cache>
- void bench_str()
+ template<typename _ContType>
+ void bench_str(const char* desc)
{
using namespace __gnu_test;
- std::ostringstream ostr;
- ostr << "unordered_set<string> " << (use_cache ? "with" : "without")
- << " cache";
- const std::string desc = ostr.str();
time_counter time;
resource_counter resource;
@@ -125,6 +106,7 @@
const int nb = 200000;
// First generate once strings that are going to be used throughout the
// bench:
+ std::ostringstream ostr;
std::vector<std::string> strs;
strs.reserve(nb);
for (int i = 0; i != nb; ++i)
@@ -136,17 +118,7 @@
start_counters(time, resource);
-#ifdef _USE_TR1
- std::tr1::__unordered_set<std::string, std::hash<std::string>,
- std::equal_to<std::string>,
- std::allocator<std::string>,
- use_cache> us;
-#else
- std::__uset_hashtable<std::string, std::hash<std::string>,
- std::equal_to<std::string>,
- std::allocator<std::string>,
- std::__uset_traits<use_cache>> us;
-#endif
+ _ContType us;
for (int i = 0; i != nb; ++i)
us.insert(strs[i]);
@@ -192,11 +164,53 @@
}
}
+template<bool cache>
+ using __uset =
+ std::__uset_hashtable<int, std::hash<int>, std::equal_to<int>,
+ std::allocator<int>,
+ std::__uset_traits<cache>>;
+
+template<bool cache>
+ using __tr1_uset =
+ std::tr1::__unordered_set<int, std::hash<int>, std::equal_to<int>,
+ std::allocator<int>,
+ cache>;
+
+template<bool cache>
+ using __str_uset =
+ std::__uset_hashtable<std::string, std::hash<std::string>,
+ std::equal_to<std::string>,
+ std::allocator<std::string>,
+ std::__uset_traits<cache>>;
+
+template<bool cache>
+ using __tr1_str_uset =
+ std::tr1::__unordered_set<std::string, std::hash<std::string>,
+ std::equal_to<std::string>,
+ std::allocator<std::string>,
+ cache>;
+
int main()
{
- bench<false>();
- bench<true>();
- bench_str<false>();
- bench_str<true>();
+ bench<__tr1_uset<false>>(
+ "std::tr1::unordered_set<int> without hash code cached");
+ bench<__tr1_uset<true>>(
+ "std::tr1::unordered_set<int> with hash code cached");
+ bench<__uset<false>>(
+ "std::unordered_set<int> without hash code cached");
+ bench<__uset<true>>(
+ "std::unordered_set<int> with hash code cached");
+ bench<std::unordered_set<int>>(
+ "std::unordered_set<int> default cache");
+ bench_str<__tr1_str_uset<false>>(
+ "std::tr1::unordered_set<string> without hash code cached");
+ bench_str<__tr1_str_uset<true>>(
+ "std::tr1::unordered_set<string> with hash code cached");
+ bench_str<__str_uset<false>>(
+ "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>>(
+ "std::unordered_set<string> default cache");
return 0;
}
Index: testsuite/23_containers/unordered_set/buckets/swap.cc
===================================================================
--- testsuite/23_containers/unordered_set/buckets/swap.cc (revision 0)
+++ testsuite/23_containers/unordered_set/buckets/swap.cc (revision 0)
@@ -0,0 +1,72 @@
+// { dg-options "-std=c++11" }
+
+// Copyright (C) 2013 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/>.
+
+#include <testsuite_hooks.h>
+#include <unordered_set>
+
+namespace
+{
+ struct hash
+ {
+ hash() = default;
+ hash(int modulo)
+ : _M_modulo(modulo)
+ { }
+
+ std::size_t operator() (int val) const noexcept
+ { return val % _M_modulo; }
+
+ int _M_modulo;
+ };
+}
+
+void
+test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ // static_assert(std::__cache_default<int, hash>::value,
+ // "Unexpected default cache value");
+ typedef std::unordered_set<int, hash> us_t;
+ us_t us1(10, hash(13));
+ us_t us2(10, hash(7));
+
+ VERIFY( us1.hash_function()._M_modulo == 13 );
+ VERIFY( us2.hash_function()._M_modulo == 7 );
+
+ const int nb = 5;
+ for (int i = 0; i != nb * us1.hash_function()._M_modulo; ++i)
+ us1.insert(i);
+
+ us_t::local_iterator lit = us1.begin(12);
+ us_t::local_iterator litend = us1.end(12);
+ VERIFY( std::distance(lit, litend) == nb );
+
+ us1.swap(us2);
+
+ VERIFY( us1.hash_function()._M_modulo == 7 );
+ VERIFY( us2.hash_function()._M_modulo == 13 );
+
+ VERIFY( std::distance(lit, litend) == nb );
+}
+
+int main()
+{
+ test01();
+}
Index: testsuite/23_containers/unordered_set/instantiation_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/instantiation_neg.cc (revision 195097)
+++ testsuite/23_containers/unordered_set/instantiation_neg.cc (working copy)
@@ -2,7 +2,7 @@
// { dg-options "-std=gnu++0x" }
// { dg-require-normal-mode "" }
-// Copyright (C) 2011, 2012 Free Software Foundation, Inc.
+// Copyright (C) 2011-2013 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
@@ -19,7 +19,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-// { dg-error "with noexcept" "" { target *-*-* } 247 }
+// { dg-error "with noexcept" "" { target *-*-* } 252 }
#include <unordered_set>
Index: testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (revision 0)
+++ testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (revision 0)
@@ -0,0 +1,51 @@
+// { dg-do compile }
+// { dg-options "-std=c++11" }
+// { dg-require-normal-mode "" }
+
+// Copyright (C) 2013 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-error "default constructibles" "" { target *-*-* } 268 }
+
+#include <unordered_set>
+
+namespace
+{
+ struct hash
+ {
+ hash(std::size_t seed)
+ : _M_seed(seed)
+ { }
+
+ std::size_t operator() (int val) const noexcept
+ { return val ^ _M_seed; }
+
+ private:
+ std::size_t _M_seed;
+ };
+}
+
+void
+test01()
+{
+ using traits = std::__detail::_Hashtable_traits<false, true, true>;
+ using hashtable = std::__uset_hashtable<int, hash,
+ std::equal_to<int>,
+ std::allocator<int>, traits>;
+
+ hashtable ht(10, hash(1));
+}
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [v3] Fix management of non empty hash functor
2013-01-10 21:02 ` François Dumont
@ 2013-01-28 15:43 ` Jonathan Wakely
2013-01-28 21:08 ` François Dumont
0 siblings, 1 reply; 5+ messages in thread
From: Jonathan Wakely @ 2013-01-28 15:43 UTC (permalink / raw)
To: François Dumont; +Cc: Paolo Carlini, libstdc++, gcc-patches
On 10 January 2013 21:02, François Dumont wrote:
> Hi
>
> Here is an other version of this patch. Indeed there were no need to
> expose many stuff public. Inheriting from _Hash_code_base is fine, it is not
> final and it deals with EBO itself. I only kept usage of
> _Hashtable_ebo_helper when embedding H2 functor. As it is an extension we
> could have impose it not to be final but it doesn't cost a lot to deal with
> it. Finally I only needed a single friend declaration to get access to the
> H2 part of _Hash_code_base.
OK.
> I didn't touch the default cache policy for the moment except reducing
> constraints on the hash functor. I prefer to submit an other patch to change
> when we cache or not depending on the hash functor expected performance.
OK. The reduced constraints are good. Does this actually affect
performance? In my tests it doesn't, so I assume we still need to
change the caching decision to notice any performance improvements?
(Do the performance benchmarks actually tell us anything useful?
When I run them I get such varying results it doesn't seem to be reliable.)
> I also took the time to replace some typedef expressions with using
> ones. I really know what is the rule about using one or the other but I
> remembered that Benjamin spent quite some time changing typedef in using so
> I prefer to stick to this approach in this file, even if there are still
> some typedef left.
OK, that doesn't make any difference so isn't important which is used.
> Tested under linux x86_64 normal and debug modes.
>
> 2013-01-10 François Dumont <fdumont@gcc.gnu.org>
>
>
> * include/bits/hashtable_policy.h (_Local_iterator_base): Use
> _Hashtable_ebo_helper to embed necessary functors into the
> local_iterator when necessary. Pass information about functors
Repeating "necessary" seems unnecessary here :)
> involved in hash code by copy.
> * include/bits/hashtable.h (__cache_default): Do not cache for
> builtin integral types unless the hash functor is not noexcept
> qualified or is not default constructible. Adapt static assertions
> and local iteraror instantiations.
^^ "iteraror"
+ // When hash codes are not cached local iterator inherits from
+ // __hash_code_base above to compute node bucket index so it has to be
+ // default constructible.
+ static_assert(__if_hash_not_cached<
+ is_default_constructible<__hash_code_base>>::value,
+ "Cache the hash code or make functors involved in hash code"
+ " and bucket index computation default constructibles");
"constructible" not "constructibles"
This is OK for trunk, but not 4.7
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [v3] Fix management of non empty hash functor
2013-01-28 15:43 ` Jonathan Wakely
@ 2013-01-28 21:08 ` François Dumont
2013-01-28 21:12 ` Jonathan Wakely
0 siblings, 1 reply; 5+ messages in thread
From: François Dumont @ 2013-01-28 21:08 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: Paolo Carlini, libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 3384 bytes --]
Attached patch applied.
2013-01-28 François Dumont <fdumont@gcc.gnu.org>
* include/bits/hashtable_policy.h (_Local_iterator_base): Use
_Hashtable_ebo_helper to embed functors into the local_iterator
when necessary. Pass information about functors involved in hash
code by copy.
* include/bits/hashtable.h (__cache_default): Do not cache for
builtin integral types unless the hash functor is not noexcept
qualified or is not default constructible. Adapt static assertions
and local iterator instantiations.
* include/debug/unordered_set
(std::__debug::unordered_set<>::erase): Detect local iterators to
invalidate using contained node rather than generating a dummy
local_iterator instance.
(std::__debug::unordered_multiset<>::erase): Likewise.
* include/debug/unordered_map
(std::__debug::unordered_map<>::erase): Likewise.
(std::__debug::unordered_multimap<>::erase): Likewise.
* testsuite/performance/23_containers/insert_erase/41975.cc: Test
std::tr1 and std versions of unordered_set regardless of any
macro. Add test on default cache behavior.
* testsuite/performance/23_containers/insert/54075.cc: Likewise.
* testsuite/23_containers/unordered_set/instantiation_neg.cc:
Adapt line number.
* testsuite/23_containers/unordered_set/
not_default_constructible_hash_neg.cc: New.
* testsuite/23_containers/unordered_set/buckets/swap.cc: New.
On 01/28/2013 04:42 PM, Jonathan Wakely wrote:
> On 10 January 2013 21:02, François Dumont wrote:
>> Hi
>>
>> Here is an other version of this patch. Indeed there were no need to
>> expose many stuff public. Inheriting from _Hash_code_base is fine, it is not
>> final and it deals with EBO itself. I only kept usage of
>> _Hashtable_ebo_helper when embedding H2 functor. As it is an extension we
>> could have impose it not to be final but it doesn't cost a lot to deal with
>> it. Finally I only needed a single friend declaration to get access to the
>> H2 part of _Hash_code_base.
> OK.
>
>> I didn't touch the default cache policy for the moment except reducing
>> constraints on the hash functor. I prefer to submit an other patch to change
>> when we cache or not depending on the hash functor expected performance.
> OK. The reduced constraints are good. Does this actually affect
> performance? In my tests it doesn't, so I assume we still need to
> change the caching decision to notice any performance improvements?
No performance gain plan with that patch indeed. It just restore support
for non-empty hash functor that used to work with previous
implementation. There is also no performance test impacted by the
modification of the default cache behavior so it is not surprised that
you noticed nothing.
>
> (Do the performance benchmarks actually tell us anything useful?
> When I run them I get such varying results it doesn't seem to be reliable.)
Last time I run the tests it was showing when not caching was better
than caching. I have even added a bench on the unordered containers
directly to show what are the performance of default behavior. For the
moment, for the Foo type used in 54075.cc, the default behavior is not
the best one. But I will submit a patch for that soon with a hash traits
telling if it is fast or not, like we already talk about.
François
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 42401 bytes --]
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 195515)
+++ include/bits/hashtable_policy.h (working copy)
@@ -1,6 +1,6 @@
// Internal policy header for unordered_set and unordered_map -*- C++ -*-
-// Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc.
+// Copyright (C) 2010-2013 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
@@ -202,7 +202,7 @@
template<typename _Value, bool _Cache_hash_code>
struct _Node_iterator_base
{
- typedef _Hash_node<_Value, _Cache_hash_code> __node_type;
+ using __node_type = _Hash_node<_Value, _Cache_hash_code>;
__node_type* _M_cur;
@@ -282,7 +282,7 @@
struct _Node_const_iterator
: public _Node_iterator_base<_Value, __cache>
{
- private:
+ private:
using __base_type = _Node_iterator_base<_Value, __cache>;
using __node_type = typename __base_type::__node_type;
@@ -941,6 +941,17 @@
};
/**
+ * Primary class template _Local_iterator_base.
+ *
+ * Base class for local iterators, used to iterate within a bucket
+ * but not between buckets.
+ */
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash,
+ bool __cache_hash_code>
+ struct _Local_iterator_base;
+
+ /**
* Primary class template _Hash_code_base.
*
* Encapsulates two policy issues that aren't quite orthogonal.
@@ -974,8 +985,8 @@
private _Hashtable_ebo_helper<1, _Hash>
{
private:
- typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
- typedef _Hashtable_ebo_helper<1, _Hash> _EboHash;
+ using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
+ using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>;
protected:
typedef void* __hash_code;
@@ -986,7 +997,7 @@
_Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
const _Hash& __h)
- : _EboExtractKey(__ex), _EboHash(__h) { }
+ : __ebo_extract_key(__ex), __ebo_hash(__h) { }
__hash_code
_M_hash_code(const _Key& __key) const
@@ -1017,16 +1028,16 @@
protected:
const _ExtractKey&
- _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
_ExtractKey&
- _M_extract() { return _EboExtractKey::_S_get(*this); }
+ _M_extract() { return __ebo_extract_key::_S_get(*this); }
const _Hash&
- _M_ranged_hash() const { return _EboHash::_S_cget(*this); }
+ _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
_Hash&
- _M_ranged_hash() { return _EboHash::_S_get(*this); }
+ _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
};
// No specialization for ranged hash function while caching hash codes.
@@ -1041,7 +1052,7 @@
/// Specialization: hash function and range-hashing function, no
/// caching of hash codes.
- /// Provides typedef and accessor required by TR1.
+ /// Provides typedef and accessor required by C++ 11.
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
@@ -1051,9 +1062,9 @@
private _Hashtable_ebo_helper<2, _H2>
{
private:
- typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
- typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
- typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
+ using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
+ using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
+ using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
public:
typedef _H1 hasher;
@@ -1062,17 +1073,17 @@
hash_function() const
{ return _M_h1(); }
+ protected:
typedef std::size_t __hash_code;
typedef _Hash_node<_Value, false> __node_type;
- protected:
// We need the default constructor for the local iterators.
_Hash_code_base() = default;
_Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
- : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
+ : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
__hash_code
_M_hash_code(const _Key& __k) const
@@ -1104,27 +1115,27 @@
}
const _ExtractKey&
- _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
_ExtractKey&
- _M_extract() { return _EboExtractKey::_S_get(*this); }
+ _M_extract() { return __ebo_extract_key::_S_get(*this); }
const _H1&
- _M_h1() const { return _EboH1::_S_cget(*this); }
+ _M_h1() const { return __ebo_h1::_S_cget(*this); }
_H1&
- _M_h1() { return _EboH1::_S_get(*this); }
+ _M_h1() { return __ebo_h1::_S_get(*this); }
const _H2&
- _M_h2() const { return _EboH2::_S_cget(*this); }
+ _M_h2() const { return __ebo_h2::_S_cget(*this); }
_H2&
- _M_h2() { return _EboH2::_S_get(*this); }
+ _M_h2() { return __ebo_h2::_S_get(*this); }
};
/// Specialization: hash function and range-hashing function,
/// caching hash codes. H is provided but ignored. Provides
- /// typedef and accessor required by TR1.
+ /// typedef and accessor required by C++ 11.
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
@@ -1134,10 +1145,14 @@
private _Hashtable_ebo_helper<2, _H2>
{
private:
- typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
- typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
- typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
+ // Gives access to _M_h2() to the local iterator implementation.
+ friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
+ _Default_ranged_hash, true>;
+ using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
+ using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
+ using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
+
public:
typedef _H1 hasher;
@@ -1145,14 +1160,14 @@
hash_function() const
{ return _M_h1(); }
+ protected:
typedef std::size_t __hash_code;
typedef _Hash_node<_Value, true> __node_type;
- protected:
_Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
- : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
+ : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
__hash_code
_M_hash_code(const _Key& __k) const
@@ -1184,22 +1199,22 @@
}
const _ExtractKey&
- _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
_ExtractKey&
- _M_extract() { return _EboExtractKey::_S_get(*this); }
+ _M_extract() { return __ebo_extract_key::_S_get(*this); }
const _H1&
- _M_h1() const { return _EboH1::_S_cget(*this); }
+ _M_h1() const { return __ebo_h1::_S_cget(*this); }
_H1&
- _M_h1() { return _EboH1::_S_get(*this); }
+ _M_h1() { return __ebo_h1::_S_get(*this); }
const _H2&
- _M_h2() const { return _EboH2::_S_cget(*this); }
+ _M_h2() const { return __ebo_h2::_S_cget(*this); }
_H2&
- _M_h2() { return _EboH2::_S_get(*this); }
+ _M_h2() { return __ebo_h2::_S_get(*this); }
};
/**
@@ -1234,28 +1249,25 @@
};
- /**
- * Primary class template _Local_iterator_base.
- *
- * Base class for local iterators, used to iterate within a bucket
- * but not between buckets.
- */
- template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash,
- bool __cache_hash_code>
- struct _Local_iterator_base;
-
/// Specialization.
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, true>
- : private _H2
+ : private _Hashtable_ebo_helper<0, _H2>
{
+ protected:
+ using __base_type = _Hashtable_ebo_helper<0, _H2>;
+ using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, true>;
+
+ public:
_Local_iterator_base() = default;
- _Local_iterator_base(_Hash_node<_Value, true>* __p,
+ _Local_iterator_base(const __hash_code_base& __base,
+ _Hash_node<_Value, true>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+ : __base_type(__base._M_h2()),
+ _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
void
_M_incr()
@@ -1263,15 +1275,14 @@
_M_cur = _M_cur->_M_next();
if (_M_cur)
{
- std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
+ std::size_t __bkt
+ = __base_type::_S_get(*this)(_M_cur->_M_hash_code,
+ _M_bucket_count);
if (__bkt != _M_bucket)
_M_cur = nullptr;
}
}
- const _H2& _M_h2() const
- { return *this; }
-
_Hash_node<_Value, true>* _M_cur;
std::size_t _M_bucket;
std::size_t _M_bucket_count;
@@ -1285,10 +1296,17 @@
: private _Hash_code_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, false>
{
+ protected:
+ using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false>;
+
+ public:
_Local_iterator_base() = default;
- _Local_iterator_base(_Hash_node<_Value, false>* __p,
+ _Local_iterator_base(const __hash_code_base& __base,
+ _Hash_node<_Value, false>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+ : __hash_code_base(__base),
+ _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
void
_M_incr()
@@ -1333,6 +1351,11 @@
: public _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __cache>
{
+ private:
+ using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+ public:
typedef _Value value_type;
typedef typename std::conditional<__constant_iterators,
const _Value*, _Value*>::type
@@ -1345,11 +1368,10 @@
_Local_iterator() = default;
- explicit
- _Local_iterator(_Hash_node<_Value, __cache>* __p,
+ _Local_iterator(const __hash_code_base& __base,
+ _Hash_node<_Value, __cache>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- __cache>(__p, __bkt, __bkt_count)
+ : __base_type(__base, __p, __bkt, __bkt_count)
{ }
reference
@@ -1384,6 +1406,12 @@
: public _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __cache>
{
+ private:
+ using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+
+ public:
typedef _Value value_type;
typedef const _Value* pointer;
typedef const _Value& reference;
@@ -1392,20 +1420,17 @@
_Local_const_iterator() = default;
- explicit
- _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
+ _Local_const_iterator(const __hash_code_base& __base,
+ _Hash_node<_Value, __cache>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- __cache>(__p, __bkt, __bkt_count)
+ : __base_type(__base, __p, __bkt, __bkt_count)
{ }
_Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash,
__constant_iterators,
__cache>& __x)
- : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
- __cache>(__x._M_cur, __x._M_bucket,
- __x._M_bucket_count)
+ : __base_type(__x)
{ }
reference
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 195515)
+++ include/bits/hashtable.h (working copy)
@@ -1,6 +1,6 @@
// hashtable.h header -*- C++ -*-
-// Copyright (C) 2007-2012 Free Software Foundation, Inc.
+// Copyright (C) 2007-2013 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
@@ -39,10 +39,15 @@
_GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Tp, typename _Hash>
- using __cache_default = __not_<__and_<is_integral<_Tp>,
- is_empty<_Hash>,
- integral_constant<bool, !__is_final(_Hash)>,
- __detail::__is_noexcept_hash<_Tp, _Hash> >>;
+ using __cache_default
+ = __not_<__and_<// Do not cache for builtin integral types having trivial
+ // hasher.
+ is_integral<_Tp>,
+ // Mandatory to make local_iterator default
+ // constructible.
+ is_default_constructible<_Hash>,
+ // Mandatory to have erase not throwing.
+ __detail::__is_noexcept_hash<_Tp, _Hash>>>;
/**
* Primary class template _Hashtable.
@@ -249,21 +254,21 @@
" or qualify your hash functor with noexcept");
// Following two static assertions are necessary to guarantee
- // that swapping two hashtable instances won't invalidate
- // associated local iterators.
+ // that local_iterator will be default constructible.
- // When hash codes are cached local iterator only uses H2 which
- // must then be empty.
- static_assert(__if_hash_cached<is_empty<_H2>>::value,
+ // When hash codes are cached local iterator inherits from H2 functor
+ // which must then be default constructible.
+ static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
"Functor used to map hash code to bucket index"
- " must be empty");
+ " must be default constructible");
- // When hash codes are not cached local iterator is going to use
- // __hash_code_base above to compute node bucket index so it has
- // to be empty.
- static_assert(__if_hash_not_cached<is_empty<__hash_code_base>>::value,
- "Cache the hash code or make functors involved in hash code"
- " and bucket index computation empty");
+ // When hash codes are not cached local iterator inherits from
+ // __hash_code_base above to compute node bucket index so it has to be
+ // default constructible.
+ static_assert(__if_hash_not_cached<
+ is_default_constructible<__hash_code_base>>::value,
+ "Cache the hash code or make functors involved in hash code"
+ " and bucket index computation default constructibles");
public:
template<typename _Keya, typename _Valuea, typename _Alloca,
@@ -500,30 +505,37 @@
local_iterator
begin(size_type __n)
- { return local_iterator(_M_bucket_begin(__n), __n, _M_bucket_count); }
+ {
+ return local_iterator(*this, _M_bucket_begin(__n),
+ __n, _M_bucket_count);
+ }
local_iterator
end(size_type __n)
- { return local_iterator(nullptr, __n, _M_bucket_count); }
+ { return local_iterator(*this, nullptr, __n, _M_bucket_count); }
const_local_iterator
begin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n), __n,
- _M_bucket_count); }
+ {
+ return const_local_iterator(*this, _M_bucket_begin(__n),
+ __n, _M_bucket_count);
+ }
const_local_iterator
end(size_type __n) const
- { return const_local_iterator(nullptr, __n, _M_bucket_count); }
+ { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
// DR 691.
const_local_iterator
cbegin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n), __n,
- _M_bucket_count); }
+ {
+ return const_local_iterator(*this, _M_bucket_begin(__n),
+ __n, _M_bucket_count);
+ }
const_local_iterator
cend(size_type __n) const
- { return const_local_iterator(nullptr, __n, _M_bucket_count); }
+ { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
float
load_factor() const noexcept
@@ -1141,7 +1153,7 @@
{
if (this->_M_equals(__k, __code, __p))
return __prev_p;
- if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
+ if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
break;
__prev_p = __p;
}
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map (revision 195515)
+++ include/debug/unordered_map (working copy)
@@ -361,10 +361,9 @@
{
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base::erase(__victim);
_M_check_rehashed(__bucket_count);
@@ -380,10 +379,9 @@
_Base_const_iterator __victim = __it.base();
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -407,10 +405,9 @@
._M_iterator(__last, "last"));
this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(), __last.base());
@@ -449,22 +446,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Key, typename _Tp, typename _Hash,
@@ -807,10 +788,9 @@
{
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
_Base::erase(__victim++);
++__ret;
}
@@ -825,10 +805,9 @@
_Base_const_iterator __victim = __it.base();
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -852,10 +831,9 @@
._M_iterator(__last, "last"));
this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(), __last.base());
@@ -894,22 +872,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Key, typename _Tp, typename _Hash,
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set (revision 195515)
+++ include/debug/unordered_set (working copy)
@@ -356,10 +356,9 @@
this->_M_invalidate_if(
[__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base::erase(__victim);
_M_check_rehashed(__bucket_count);
@@ -376,10 +375,9 @@
this->_M_invalidate_if(
[__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -404,10 +402,9 @@
this->_M_invalidate_if(
[__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(),
@@ -448,22 +445,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
@@ -798,10 +779,9 @@
{
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
_Base::erase(__victim++);
++__ret;
}
@@ -815,10 +795,9 @@
_Base_const_iterator __victim = __it.base();
this->_M_invalidate_if([__victim](_Base_const_iterator __it)
{ return __it == __victim; });
- _Base_const_local_iterator __local_victim = _S_to_local(__victim);
this->_M_invalidate_local_if(
- [__local_victim](_Base_const_local_iterator __it)
- { return __it == __local_victim; });
+ [__victim](_Base_const_local_iterator __it)
+ { return __it._M_cur == __victim._M_cur; });
return iterator(_Base::erase(__it.base()), this);
}
@@ -839,10 +818,9 @@
._M_iterator(__last, "last"));
this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
{ return __it == __tmp; });
- _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
this->_M_invalidate_local_if(
- [__local_tmp](_Base_const_local_iterator __it)
- { return __it == __local_tmp; });
+ [__tmp](_Base_const_local_iterator __it)
+ { return __it._M_cur == __tmp._M_cur; });
}
return iterator(_Base::erase(__first.base(),
__last.base()), this);
@@ -879,22 +857,6 @@
if (__prev_count != this->bucket_count())
_M_invalidate_locals();
}
-
- static _Base_local_iterator
- _S_to_local(_Base_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_local_iterator(__it._M_cur, 0, 0);
- }
-
- static _Base_const_local_iterator
- _S_to_local(_Base_const_iterator __it)
- {
- // The returned local iterator will not be incremented so we don't
- // need to compute __it's node bucket
- return _Base_const_local_iterator(__it._M_cur, 0, 0);
- }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
Index: testsuite/performance/23_containers/insert_erase/41975.cc
===================================================================
--- testsuite/performance/23_containers/insert_erase/41975.cc (revision 195515)
+++ testsuite/performance/23_containers/insert_erase/41975.cc (working copy)
@@ -1,6 +1,6 @@
// { dg-options "-std=gnu++0x" }
-// Copyright (C) 2011 Free Software Foundation, Inc.
+// Copyright (C) 2011-2013 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
@@ -18,25 +18,18 @@
// <http://www.gnu.org/licenses/>.
#include <sstream>
-#ifdef _USE_TR1
-# include <tr1/unordered_set>
-#else
-# include <unordered_set>
-#endif
+#include <tr1/unordered_set>
+#include <unordered_set>
#include <testsuite_performance.h>
namespace
{
// Bench using an unordered_set<int>. Hash functor for int is quite
// predictable so it helps bench very specific use cases.
- template<bool use_cache>
- void bench()
+ template<typename _ContType>
+ void bench(const char* desc)
{
using namespace __gnu_test;
- std::ostringstream ostr;
- ostr << "unordered_set<int> " << (use_cache ? "with" : "without")
- << " cache";
- const std::string desc = ostr.str();
time_counter time;
resource_counter resource;
@@ -44,20 +37,12 @@
const int nb = 200000;
start_counters(time, resource);
-#ifdef _USE_TR1
- std::tr1::__unordered_set<int, std::hash<int>, std::equal_to<int>,
- std::allocator<int>,
- use_cache> us;
-#else
- std::__uset_hashtable<int, std::hash<int>, std::equal_to<int>,
- std::allocator<int>,
- std::__uset_traits<use_cache>> us;
-#endif
+ _ContType us;
for (int i = 0; i != nb; ++i)
us.insert(i);
stop_counters(time, resource);
- ostr.str("");
+ std::ostringstream ostr;
ostr << desc << ": first insert";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
@@ -110,14 +95,10 @@
// Bench using unordered_set<string> that show how important it is to cache
// hash code as computing string hash code is quite expensive compared to
// computing it for int.
- template<bool use_cache>
- void bench_str()
+ template<typename _ContType>
+ void bench_str(const char* desc)
{
using namespace __gnu_test;
- std::ostringstream ostr;
- ostr << "unordered_set<string> " << (use_cache ? "with" : "without")
- << " cache";
- const std::string desc = ostr.str();
time_counter time;
resource_counter resource;
@@ -125,6 +106,7 @@
const int nb = 200000;
// First generate once strings that are going to be used throughout the
// bench:
+ std::ostringstream ostr;
std::vector<std::string> strs;
strs.reserve(nb);
for (int i = 0; i != nb; ++i)
@@ -136,17 +118,7 @@
start_counters(time, resource);
-#ifdef _USE_TR1
- std::tr1::__unordered_set<std::string, std::hash<std::string>,
- std::equal_to<std::string>,
- std::allocator<std::string>,
- use_cache> us;
-#else
- std::__uset_hashtable<std::string, std::hash<std::string>,
- std::equal_to<std::string>,
- std::allocator<std::string>,
- std::__uset_traits<use_cache>> us;
-#endif
+ _ContType us;
for (int i = 0; i != nb; ++i)
us.insert(strs[i]);
@@ -192,11 +164,53 @@
}
}
+template<bool cache>
+ using __uset =
+ std::__uset_hashtable<int, std::hash<int>, std::equal_to<int>,
+ std::allocator<int>,
+ std::__uset_traits<cache>>;
+
+template<bool cache>
+ using __tr1_uset =
+ std::tr1::__unordered_set<int, std::hash<int>, std::equal_to<int>,
+ std::allocator<int>,
+ cache>;
+
+template<bool cache>
+ using __str_uset =
+ std::__uset_hashtable<std::string, std::hash<std::string>,
+ std::equal_to<std::string>,
+ std::allocator<std::string>,
+ std::__uset_traits<cache>>;
+
+template<bool cache>
+ using __tr1_str_uset =
+ std::tr1::__unordered_set<std::string, std::hash<std::string>,
+ std::equal_to<std::string>,
+ std::allocator<std::string>,
+ cache>;
+
int main()
{
- bench<false>();
- bench<true>();
- bench_str<false>();
- bench_str<true>();
+ bench<__tr1_uset<false>>(
+ "std::tr1::unordered_set<int> without hash code cached");
+ bench<__tr1_uset<true>>(
+ "std::tr1::unordered_set<int> with hash code cached");
+ bench<__uset<false>>(
+ "std::unordered_set<int> without hash code cached");
+ bench<__uset<true>>(
+ "std::unordered_set<int> with hash code cached");
+ bench<std::unordered_set<int>>(
+ "std::unordered_set<int> default cache");
+ bench_str<__tr1_str_uset<false>>(
+ "std::tr1::unordered_set<string> without hash code cached");
+ bench_str<__tr1_str_uset<true>>(
+ "std::tr1::unordered_set<string> with hash code cached");
+ bench_str<__str_uset<false>>(
+ "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>>(
+ "std::unordered_set<string> default cache");
return 0;
}
Index: testsuite/performance/23_containers/insert/54075.cc
===================================================================
--- testsuite/performance/23_containers/insert/54075.cc (revision 195515)
+++ testsuite/performance/23_containers/insert/54075.cc (working copy)
@@ -1,4 +1,4 @@
-// Copyright (C) 2012 Free Software Foundation, Inc.
+// Copyright (C) 2012-2013 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
@@ -21,10 +21,14 @@
#include <random>
#include <sstream>
#include <tr1/unordered_set>
-#include<unordered_set>
+#include <unordered_set>
+#define USE_MY_FOO 1
+
struct Foo
{
+#if USE_MY_FOO
+
typedef std::random_device::result_type _Type;
_Type bar;
_Type baz;
@@ -38,6 +42,18 @@
meh = randev();
}
+#else
+
+ int bar;
+ int baz;
+ int meh;
+
+ Foo()
+ { bar = random(); baz = random(); meh = random(); }
+ Foo(const Foo&) = default;
+
+#endif
+
std::size_t
hash() const noexcept
{ return std::size_t(bar ^ baz ^ meh); }
@@ -54,36 +70,30 @@
{ return t.hash(); }
};
+const int sz = 300000;
+
template<typename _ContType>
- void bench(const char* container_desc)
+ void
+ bench(const char* container_desc, const typename _ContType::value_type* foos)
{
using namespace __gnu_test;
+ _ContType s;
+
time_counter time;
resource_counter resource;
-
- const int sz = 300000;
-
- Foo foos[sz];
- {
- std::random_device randev;
- for (int i = 0; i != sz; ++i)
- foos[i].init(randev);
- }
-
- _ContType s;
start_counters(time, resource);
for (int i = 0; i != sz ; ++i)
- s.insert(foos[i]);
+ s.insert(foos[i]);
stop_counters(time, resource);
std::ostringstream ostr;
- ostr << container_desc << sz << " Foo insertions";
+ ostr << container_desc << sz << " insertion attempts, "
+ << s.size() << " inserted";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
// Try to insert again to check performance of collision detection
-
const int nb_loop = 10;
start_counters(time, resource);
@@ -94,7 +104,7 @@
stop_counters(time, resource);
ostr.str("");
ostr << container_desc << nb_loop << " times insertion of "
- << sz << " Foo";
+ << sz << " elements";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
}
@@ -121,12 +131,58 @@
int main()
{
- bench<__tr1_uset<false>>("std::tr1::unordered_set without hash code cached ");
- bench<__tr1_uset<true>>("std::tr1::unordered_set with hash code cached ");
- bench<__tr1_umset<false>>("std::tr1::unordered_multiset without hash code cached ");
- bench<__tr1_umset<true>>("std::tr1::unordered_multiset with hash code cached ");
- bench<__uset<false>>("std::unordered_set without hash code cached ");
- bench<__uset<true>>("std::unordered_set with hash code cached ");
- bench<__umset<false>>("std::unordered_multiset without hash code cached ");
- bench<__umset<true>>("std::unordered_multiset with hash code cached ");
+ using namespace __gnu_test;
+
+ {
+ int bars[sz];
+ for (int i = 0; i != sz; ++i)
+ bars[i] = i;
+ bench<std::tr1::unordered_set<int>>(
+ "std::tr1::unordered_set<int> ", bars);
+ bench<std::unordered_set<int>>(
+ "std::unordered_set<int> ", bars);
+ }
+
+ Foo foos[sz];
+#if USE_MY_FOO
+ {
+ std::random_device randev;
+ for (int i = 0; i != sz; ++i)
+ foos[i].init(randev);
+ }
+#endif
+
+ time_counter time;
+ resource_counter resource;
+ start_counters(time, resource);
+
+ bench<__tr1_uset<false>>(
+ "std::tr1::unordered_set without hash code cached ", foos);
+ bench<__tr1_uset<true>>(
+ "std::tr1::unordered_set with hash code cached ", foos);
+ bench<__tr1_umset<false>>(
+ "std::tr1::unordered_multiset without hash code cached ", foos);
+ bench<__tr1_umset<true>>(
+ "std::tr1::unordered_multiset with hash code cached ", foos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "tr1 benches", time, resource);
+
+ start_counters(time, resource);
+ bench<__uset<false>>(
+ "std::unordered_set without hash code cached ", foos);
+ bench<__uset<true>>(
+ "std::unordered_set with hash code cached ", foos);
+ bench<__umset<false>>(
+ "std::unordered_multiset without hash code cached ", foos);
+ bench<__umset<true>>(
+ "std::unordered_multiset with hash code cached ", foos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "std benches", time, resource);
+
+ bench<std::unordered_set<Foo, HashFunction>>(
+ "std::unordered_set default cache ", foos);
+ bench<std::unordered_multiset<Foo, HashFunction>>(
+ "std::unordered_multiset default cache ", foos);
}
Index: testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (revision 0)
+++ testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (revision 0)
@@ -0,0 +1,51 @@
+// { dg-do compile }
+// { dg-options "-std=c++11" }
+// { dg-require-normal-mode "" }
+
+// Copyright (C) 2013 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-error "default constructibles" "" { target *-*-* } 268 }
+
+#include <unordered_set>
+
+namespace
+{
+ struct hash
+ {
+ hash(std::size_t seed)
+ : _M_seed(seed)
+ { }
+
+ std::size_t operator() (int val) const noexcept
+ { return val ^ _M_seed; }
+
+ private:
+ std::size_t _M_seed;
+ };
+}
+
+void
+test01()
+{
+ using traits = std::__detail::_Hashtable_traits<false, true, true>;
+ using hashtable = std::__uset_hashtable<int, hash,
+ std::equal_to<int>,
+ std::allocator<int>, traits>;
+
+ hashtable ht(10, hash(1));
+}
Index: testsuite/23_containers/unordered_set/buckets/swap.cc
===================================================================
--- testsuite/23_containers/unordered_set/buckets/swap.cc (revision 0)
+++ testsuite/23_containers/unordered_set/buckets/swap.cc (revision 0)
@@ -0,0 +1,72 @@
+// { dg-options "-std=c++11" }
+
+// Copyright (C) 2013 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/>.
+
+#include <testsuite_hooks.h>
+#include <unordered_set>
+
+namespace
+{
+ struct hash
+ {
+ hash() = default;
+ hash(int modulo)
+ : _M_modulo(modulo)
+ { }
+
+ std::size_t operator() (int val) const noexcept
+ { return val % _M_modulo; }
+
+ int _M_modulo;
+ };
+}
+
+void
+test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ // static_assert(std::__cache_default<int, hash>::value,
+ // "Unexpected default cache value");
+ typedef std::unordered_set<int, hash> us_t;
+ us_t us1(10, hash(13));
+ us_t us2(10, hash(7));
+
+ VERIFY( us1.hash_function()._M_modulo == 13 );
+ VERIFY( us2.hash_function()._M_modulo == 7 );
+
+ const int nb = 5;
+ for (int i = 0; i != nb * us1.hash_function()._M_modulo; ++i)
+ us1.insert(i);
+
+ us_t::local_iterator lit = us1.begin(12);
+ us_t::local_iterator litend = us1.end(12);
+ VERIFY( std::distance(lit, litend) == nb );
+
+ us1.swap(us2);
+
+ VERIFY( us1.hash_function()._M_modulo == 7 );
+ VERIFY( us2.hash_function()._M_modulo == 13 );
+
+ VERIFY( std::distance(lit, litend) == nb );
+}
+
+int main()
+{
+ test01();
+}
Index: testsuite/23_containers/unordered_set/instantiation_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/instantiation_neg.cc (revision 195515)
+++ testsuite/23_containers/unordered_set/instantiation_neg.cc (working copy)
@@ -2,7 +2,7 @@
// { dg-options "-std=gnu++0x" }
// { dg-require-normal-mode "" }
-// Copyright (C) 2011, 2012 Free Software Foundation, Inc.
+// Copyright (C) 2011-2013 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
@@ -19,7 +19,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-// { dg-error "with noexcept" "" { target *-*-* } 247 }
+// { dg-error "with noexcept" "" { target *-*-* } 252 }
#include <unordered_set>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [v3] Fix management of non empty hash functor
2013-01-28 21:08 ` François Dumont
@ 2013-01-28 21:12 ` Jonathan Wakely
0 siblings, 0 replies; 5+ messages in thread
From: Jonathan Wakely @ 2013-01-28 21:12 UTC (permalink / raw)
To: François Dumont; +Cc: Paolo Carlini, libstdc++, gcc-patches
On 28 January 2013 21:08, François Dumont wrote:
>>
>> (Do the performance benchmarks actually tell us anything useful?
>> When I run them I get such varying results it doesn't seem to be
>> reliable.)
>
> Last time I run the tests it was showing when not caching was better than
> caching.
Yes, I've definitely seen real advantage from not caching (but that
was in my own tests, not the performance testsuite.)
> I have even added a bench on the unordered containers directly to
> show what are the performance of default behavior. For the moment, for the
> Foo type used in 54075.cc, the default behavior is not the best one. But I
> will submit a patch for that soon with a hash traits telling if it is fast
> or not, like we already talk about.
Great, thanks.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2013-01-28 21:12 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-12-13 21:33 [v3] Fix management of non empty hash functor François Dumont
[not found] ` <50E6BA2C.2060109@oracle.com>
2013-01-10 21:02 ` François Dumont
2013-01-28 15:43 ` Jonathan Wakely
2013-01-28 21:08 ` François Dumont
2013-01-28 21:12 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).