From patchwork Thu Jan 10 21:02:39 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [v3] Fix management of non empty hash functor Date: Thu, 10 Jan 2013 11:02:39 -0000 From: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 211156 Message-Id: <50EF2C6F.3050609@gmail.com> To: Paolo Carlini Cc: "libstdc++@gcc.gnu.org" , Jonathan Wakely , gcc-patches 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 * 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. > 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 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 + 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 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 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 - struct _Local_iterator_base; - /// Specialization. template 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 - using __cache_default = __not_<__and_, - is_empty<_Hash>, - integral_constant, - __detail::__is_noexcept_hash<_Tp, _Hash> >>; + using __cache_default + = __not_<__and_, + // 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>::value, + // When hash codes are cached local iterator inherits from H2 functor + // which must then be default constructible. + static_assert(__if_hash_cached>::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>::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_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_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_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 @@ -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 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 #include #include -#include +#include +#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 - 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>("std::tr1::unordered_set without hash code cached "); - bench<__tr1_uset>("std::tr1::unordered_set with hash code cached "); - bench<__tr1_umset>("std::tr1::unordered_multiset without hash code cached "); - bench<__tr1_umset>("std::tr1::unordered_multiset with hash code cached "); - bench<__uset>("std::unordered_set without hash code cached "); - bench<__uset>("std::unordered_set with hash code cached "); - bench<__umset>("std::unordered_multiset without hash code cached "); - bench<__umset>("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 ", bars); + bench>( + "std::unordered_set ", 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>( + "std::tr1::unordered_set without hash code cached ", foos); + bench<__tr1_uset>( + "std::tr1::unordered_set with hash code cached ", foos); + bench<__tr1_umset>( + "std::tr1::unordered_multiset without hash code cached ", foos); + bench<__tr1_umset>( + "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>( + "std::unordered_set without hash code cached ", foos); + bench<__uset>( + "std::unordered_set with hash code cached ", foos); + bench<__umset>( + "std::unordered_multiset without hash code cached ", foos); + bench<__umset>( + "std::unordered_multiset with hash code cached ", foos); + + stop_counters(time, resource); + report_performance(__FILE__, "std benches", time, resource); + + bench>( + "std::unordered_set default cache ", foos); + bench>( + "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 @@ // . #include -#ifdef _USE_TR1 -# include -#else -# include -#endif +#include +#include #include namespace { // Bench using an unordered_set. Hash functor for int is quite // predictable so it helps bench very specific use cases. - template - void bench() + template + void bench(const char* desc) { using namespace __gnu_test; - std::ostringstream ostr; - ostr << "unordered_set " << (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, std::equal_to, - std::allocator, - use_cache> us; -#else - std::__uset_hashtable, std::equal_to, - std::allocator, - std::__uset_traits> 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 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 - void bench_str() + template + void bench_str(const char* desc) { using namespace __gnu_test; - std::ostringstream ostr; - ostr << "unordered_set " << (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 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::equal_to, - std::allocator, - use_cache> us; -#else - std::__uset_hashtable, - std::equal_to, - std::allocator, - std::__uset_traits> us; -#endif + _ContType us; for (int i = 0; i != nb; ++i) us.insert(strs[i]); @@ -192,11 +164,53 @@ } } +template + using __uset = + std::__uset_hashtable, std::equal_to, + std::allocator, + std::__uset_traits>; + +template + using __tr1_uset = + std::tr1::__unordered_set, std::equal_to, + std::allocator, + cache>; + +template + using __str_uset = + std::__uset_hashtable, + std::equal_to, + std::allocator, + std::__uset_traits>; + +template + using __tr1_str_uset = + std::tr1::__unordered_set, + std::equal_to, + std::allocator, + cache>; + int main() { - bench(); - bench(); - bench_str(); - bench_str(); + bench<__tr1_uset>( + "std::tr1::unordered_set without hash code cached"); + bench<__tr1_uset>( + "std::tr1::unordered_set with hash code cached"); + bench<__uset>( + "std::unordered_set without hash code cached"); + bench<__uset>( + "std::unordered_set with hash code cached"); + bench>( + "std::unordered_set default cache"); + bench_str<__tr1_str_uset>( + "std::tr1::unordered_set without hash code cached"); + bench_str<__tr1_str_uset>( + "std::tr1::unordered_set with hash code cached"); + bench_str<__str_uset>( + "std::unordered_set without hash code cached"); + bench_str<__str_uset>( + "std::unordered_set with hash code cached"); + bench_str>( + "std::unordered_set 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 +// . + +#include +#include + +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::value, + // "Unexpected default cache value"); + typedef std::unordered_set 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 // . -// { dg-error "with noexcept" "" { target *-*-* } 247 } +// { dg-error "with noexcept" "" { target *-*-* } 252 } #include 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 +// . + +// { dg-error "default constructibles" "" { target *-*-* } 268 } + +#include + +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; + using hashtable = std::__uset_hashtable, + std::allocator, traits>; + + hashtable ht(10, hash(1)); +}