This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] No allocation for empty unordered containers
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Jonathan Wakely <jwakely at redhat dot com>
- Cc: libstdc++ at gcc dot gnu dot org, Paolo Carlini <paolo dot carlini at oracle dot com>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 14 Aug 2014 21:22:53 +0200
- Subject: Re: [patch] No allocation for empty unordered containers
- Authentication-results: sourceware.org; auth=none
- References: <538E339A dot 3010709 at gmail dot com> <53D2C3D4 dot 8060601 at gmail dot com> <20140804114914 dot GO2361 at redhat dot com> <20140804115539 dot GP2361 at redhat dot com> <53E13810 dot 8030107 at gmail dot com> <20140805201026 dot GH6927 at redhat dot com> <53E13D4B dot 5080909 at oracle dot com> <53EA697F dot 4030407 at gmail dot com> <alpine dot DEB dot 2 dot 11 dot 1408122137280 dot 1593 at laptop-mg dot saclay dot inria dot fr> <53EA70B6 dot 20503 at gmail dot com> <20140813095026 dot GU6927 at redhat dot com>
On 13/08/2014 11:50, Jonathan Wakely wrote:
Yes you can, it's conforming to replace a (non-virtual) member function
with default arguments by two or more member functions. We do it all
the time.
See 17.6.5.5 [member.functions] p2.
You should have told it sooner ! But of course no-one is supposed
to ignore the Standard :-).
Then here is the patch to introduce default constructor with
compiler computed noexcept qualification. Note that I also made
allocator aware default constructor allocation free however noexcept
qualification has to be manually written which I find quite a burden. Do
you think we shall do so now ?
2014-08-14 François Dumont <fdumont@gcc.gnu.org>
* include/bits/hashtable_policy.h (_Prime_rehash_policy): Qualify
constructor
noexcept.
(_Hash_code_base<>): All specialization default constructible if
possible.
(_Hashtable_base<>): Likewise.
* include/bits/hashtable.h (_Hashtable<>()): Implementation defaulted.
* include/bits/unordered_map.h (unordered_map<>::unordered_map()): New,
implementation defaulted.
(unordered_multimap<>::unordered_multimap()): Likewise.
* include/bits/unordered_set.h
(unordered_set<>::unordered_set()): Likewise.
(unordered_multiset<>::unordered_multiset()): Likewise.
* include/debug/unordered_map: Likewise.
* include/debug/unordered_set: Likewise.
* testsuite/23_containers/unordered_map/allocator/noexcept.cc
(test04()): New.
* testsuite/23_containers/unordered_multimap/allocator/noexcept.cc
(test04()): New.
* testsuite/23_containers/unordered_set/allocator/noexcept.cc
(test04()): New.
* testsuite/23_containers/unordered_multiset/allocator/noexcept.cc
(test04()): New.
I am preparing a patch for profile mode so I will submit modification
for this mode with this big patch.
Tested under Linux x86_64.
Ok to commit ?
François
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 213780)
+++ include/bits/hashtable_policy.h (working copy)
@@ -460,7 +460,7 @@
/// smallest prime that keeps the load factor small enough.
struct _Prime_rehash_policy
{
- _Prime_rehash_policy(float __z = 1.0)
+ _Prime_rehash_policy(float __z = 1.0) noexcept
: _M_max_load_factor(__z), _M_next_resize(0) { }
float
@@ -1071,7 +1071,8 @@
typedef void* __hash_code;
typedef _Hash_node<_Value, false> __node_type;
- // We need the default constructor for the local iterators.
+ // We need the default constructor for the local iterators and _Hashtable
+ // default constructor.
_Hash_code_base() = default;
_Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
@@ -1161,7 +1162,8 @@
typedef std::size_t __hash_code;
typedef _Hash_node<_Value, false> __node_type;
- // We need the default constructor for the local iterators.
+ // We need the default constructor for the local iterators and _Hashtable
+ // default constructor.
_Hash_code_base() = default;
_Hash_code_base(const _ExtractKey& __ex,
@@ -1250,6 +1252,8 @@
typedef std::size_t __hash_code;
typedef _Hash_node<_Value, true> __node_type;
+ // We need the default constructor for _Hashtable default constructor.
+ _Hash_code_base() = default;
_Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
@@ -1694,6 +1698,7 @@
__hash_code, __hash_cached::value>;
protected:
+ _Hashtable_base() = default;
_Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
const _Hash& __hash, const _Equal& __eq)
: __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
@@ -1906,6 +1911,7 @@
__alloc_rebind<__node_alloc_type, __bucket_type>;
using __bucket_alloc_traits = std::allocator_traits<__bucket_alloc_type>;
+ _Hashtable_alloc() = default;
_Hashtable_alloc(const _Hashtable_alloc&) = default;
_Hashtable_alloc(_Hashtable_alloc&&) = default;
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 213780)
+++ include/bits/hashtable.h (working copy)
@@ -310,10 +310,10 @@
const_local_iterator;
private:
- __bucket_type* _M_buckets;
- size_type _M_bucket_count;
+ __bucket_type* _M_buckets = &_M_single_bucket;
+ size_type _M_bucket_count = 1;
__node_base _M_before_begin;
- size_type _M_element_count;
+ size_type _M_element_count = 0;
_RehashPolicy _M_rehash_policy;
// A single bucket used when only need for 1 bucket. Especially
@@ -322,7 +322,7 @@
// qualified.
// Note that we can't leave hashtable with 0 bucket without adding
// numerous checks in the code to avoid 0 modulus.
- __bucket_type _M_single_bucket;
+ __bucket_type _M_single_bucket = nullptr;
bool
_M_uses_single_bucket(__bucket_type* __bkts) const
@@ -382,8 +382,16 @@
void
_M_reset() noexcept;
+ _Hashtable(const _H1& __h1, const _H2& __h2, const _Hash& __h,
+ const _Equal& __eq, const _ExtractKey& __exk,
+ const allocator_type& __a)
+ : __hashtable_base(__exk, __h1, __h2, __h, __eq),
+ __hashtable_alloc(__node_alloc_type(__a))
+ { }
+
public:
// Constructor, destructor, assignment, swap
+ _Hashtable() = default;
_Hashtable(size_type __bucket_hint,
const _H1&, const _H2&, const _Hash&,
const _Equal&, const _ExtractKey&,
@@ -407,12 +415,11 @@
// Use delegating constructors.
explicit
_Hashtable(const allocator_type& __a)
- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
- __key_extract(), __a)
+ : __hashtable_alloc(__node_alloc_type(__a))
{ }
explicit
- _Hashtable(size_type __n = 10,
+ _Hashtable(size_type __n,
const _H1& __hf = _H1(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -791,15 +798,14 @@
const _H1& __h1, const _H2& __h2, const _Hash& __h,
const _Equal& __eq, const _ExtractKey& __exk,
const allocator_type& __a)
- : __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
- __hashtable_alloc(__node_alloc_type(__a)),
- _M_element_count(0),
- _M_rehash_policy()
+ : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
{
- _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
+ if (__bkt > _M_bucket_count)
+ {
+ _M_buckets = _M_allocate_buckets(__bkt);
+ _M_bucket_count = __bkt;
+ }
}
template<typename _Key, typename _Value,
@@ -814,20 +820,20 @@
const _H1& __h1, const _H2& __h2, const _Hash& __h,
const _Equal& __eq, const _ExtractKey& __exk,
const allocator_type& __a)
- : __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
- __hashtable_alloc(__node_alloc_type(__a)),
- _M_element_count(0),
- _M_rehash_policy()
+ : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
{
auto __nb_elems = __detail::__distance_fw(__f, __l);
- _M_bucket_count =
+ auto __bkt_count =
_M_rehash_policy._M_next_bkt(
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ if (__bkt_count > _M_bucket_count)
+ {
+ _M_buckets = _M_allocate_buckets(__bkt_count);
+ _M_bucket_count = __bkt_count;
+ }
+
__try
{
for (; __f != __l; ++__f)
@@ -1101,7 +1107,7 @@
__rehash_base(__ht),
__hashtable_alloc(
__node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
- _M_buckets(),
+ _M_buckets(nullptr),
_M_bucket_count(__ht._M_bucket_count),
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
@@ -1175,7 +1181,7 @@
__map_base(__ht),
__rehash_base(__ht),
__hashtable_alloc(__node_alloc_type(__a)),
- _M_buckets(),
+ _M_buckets(nullptr),
_M_bucket_count(__ht._M_bucket_count),
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
@@ -1218,8 +1224,7 @@
~_Hashtable() noexcept
{
clear();
- if (_M_buckets)
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
}
template<typename _Key, typename _Value,
Index: include/bits/unordered_map.h
===================================================================
--- include/bits/unordered_map.h (revision 213780)
+++ include/bits/unordered_map.h (working copy)
@@ -128,15 +128,18 @@
//construct/destroy/copy
+ /// Default constructor.
+ unordered_map() = default;
+
/**
* @brief Default constructor creates no elements.
- * @param __n Initial number of buckets.
+ * @param __n Minimal initial number of buckets.
* @param __hf A hash functor.
* @param __eql A key equality functor.
* @param __a An allocator object.
*/
explicit
- unordered_map(size_type __n = 10,
+ unordered_map(size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -840,15 +843,18 @@
//construct/destroy/copy
+ /// Default constructor.
+ unordered_multimap() = default;
+
/**
* @brief Default constructor creates no elements.
- * @param __n Initial number of buckets.
+ * @param __n Mnimal initial number of buckets.
* @param __hf A hash functor.
* @param __eql A key equality functor.
* @param __a An allocator object.
*/
explicit
- unordered_multimap(size_type __n = 10,
+ unordered_multimap(size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: include/bits/unordered_set.h
===================================================================
--- include/bits/unordered_set.h (revision 213780)
+++ include/bits/unordered_set.h (working copy)
@@ -121,15 +121,19 @@
//@}
// construct/destroy/copy
+
+ /// Default constructor.
+ unordered_set() = default;
+
/**
* @brief Default constructor creates no elements.
- * @param __n Initial number of buckets.
+ * @param __n Minimal initial number of buckets.
* @param __hf A hash functor.
* @param __eql A key equality functor.
* @param __a An allocator object.
*/
explicit
- unordered_set(size_type __n = 10,
+ unordered_set(size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -756,15 +760,19 @@
//@}
// construct/destroy/copy
+
+ /// Default constructor.
+ unordered_multiset() = default;
+
/**
* @brief Default constructor creates no elements.
- * @param __n Initial number of buckets.
+ * @param __n Minimal initial number of buckets.
* @param __hf A hash functor.
* @param __eql A key equality functor.
* @param __a An allocator object.
*/
explicit
- unordered_multiset(size_type __n = 10,
+ unordered_multiset(size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map (revision 213780)
+++ include/debug/unordered_map (working copy)
@@ -82,8 +82,10 @@
typedef __gnu_debug::_Safe_local_iterator<
_Base_const_local_iterator, unordered_map> const_local_iterator;
+ unordered_map() = default;
+
explicit
- unordered_map(size_type __n = 10,
+ unordered_map(size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -495,8 +497,10 @@
typedef __gnu_debug::_Safe_local_iterator<
_Base_const_local_iterator, unordered_multimap> const_local_iterator;
+ unordered_multimap() = default;
+
explicit
- unordered_multimap(size_type __n = 10,
+ unordered_multimap(size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set (revision 213780)
+++ include/debug/unordered_set (working copy)
@@ -82,8 +82,10 @@
typedef __gnu_debug::_Safe_local_iterator<
_Base_const_local_iterator, unordered_set> const_local_iterator;
+ unordered_set() = default;
+
explicit
- unordered_set(size_type __n = 10,
+ unordered_set(size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -491,8 +493,10 @@
typedef __gnu_debug::_Safe_local_iterator<
_Base_const_local_iterator, unordered_multiset> const_local_iterator;
+ unordered_multiset() = default;
+
explicit
- unordered_multiset(size_type __n = 10,
+ unordered_multiset(size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: testsuite/23_containers/unordered_map/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/noexcept.cc (revision 213780)
+++ testsuite/23_containers/unordered_map/allocator/noexcept.cc (working copy)
@@ -76,3 +76,10 @@
static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
}
+
+void test04()
+{
+ typedef std::unordered_map<int, int> test_type;
+ static_assert( noexcept( test_type() ), "Default constructor do not throw" );
+ static_assert( noexcept( test_type(test_type()) ), "Move constructor do not throw" );
+}
Index: testsuite/23_containers/unordered_multimap/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/noexcept.cc (revision 213780)
+++ testsuite/23_containers/unordered_multimap/allocator/noexcept.cc (working copy)
@@ -76,3 +76,10 @@
static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
}
+
+void test04()
+{
+ typedef std::unordered_multimap<int, int> test_type;
+ static_assert( noexcept( test_type() ), "Default constructor do not throw" );
+ static_assert( noexcept( test_type(test_type()) ), "Move constructor do not throw" );
+}
Index: testsuite/23_containers/unordered_multiset/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/noexcept.cc (revision 213780)
+++ testsuite/23_containers/unordered_multiset/allocator/noexcept.cc (working copy)
@@ -76,3 +76,10 @@
static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
}
+
+void test04()
+{
+ typedef std::unordered_multiset<int> test_type;
+ static_assert( noexcept( test_type() ), "Default constructor do not throw" );
+ static_assert( noexcept( test_type(test_type()) ), "Move constructor do not throw" );
+}
Index: testsuite/23_containers/unordered_set/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/noexcept.cc (revision 213780)
+++ testsuite/23_containers/unordered_set/allocator/noexcept.cc (working copy)
@@ -76,3 +76,10 @@
static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
}
+
+void test04()
+{
+ typedef std::unordered_set<int> test_type;
+ static_assert( noexcept( test_type() ), "Default constructor do not throw" );
+ static_assert( noexcept( test_type(test_type()) ), "Move constructor do not throw" );
+}