On 05/08/2014 22:23, Paolo Carlini wrote:
Hi,
On 08/05/2014 10:10 PM, Jonathan Wakely wrote:
It doesn't have to be noexcept, but IMHO there is no point changing
the containers to avoid allocation unless that allows us to mark it
noexcept. If it can throw anyway, we might as well allocate the
initial buckets.
I have been following this discussion on and off. In general, I must
say that AFAIK a default constructor which doesn't allocate memory is
normally considered superior from the QoI point of view, even if isn't
noexcept. As probably I have already mentioned, a "well known" C++
library implementer used to repeat it all the time and used also to
say that our std::list implementation was very good exactly because of
that feature, *well* before the invention of noexcept. That said,
marking the constructor noexcept is of course the obvious next step, I
don't have much to say about the general development plans we have got
here.
Paolo.
Hi
Based on your feedbacks I think we should stay with just targeting
good QoI by not allocating on default construction. As I said the
noexcept qualification would need to not conform strictly to the Standard.
So here is the patch again even if a little bit simplified.
Regarding the doc I try to put information in Doxygen comments this way
we do not need to maintain another page for that.
2014-08-12 François Dumont <fdum...@gcc.gnu.org>
* include/bits/hashtable.h: Make use of the internal single bucket to
limit allocation as long as container remains empty.
* include/bits/unordered_map.h: Set default bucket hint to 0 in
constructors to avoid allocation.
* include/bits/unordered_set.h: Likewise.
* include/debug/unordered_map: Likewise.
* include/debug/unordered_set: Likewise.
* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
Returns 1 for hint 0.
* testsuite/23_containers/unordered_map/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_multimap/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_set/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_multiset/allocator/
empty_instantiation.cc: New.
Tested under Linux x86_64.
François
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 213780)
+++ include/bits/hashtable.h (working copy)
@@ -382,6 +382,17 @@
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)),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
+ _M_element_count(0),
+ _M_single_bucket(nullptr)
+ { }
+
public:
// Constructor, destructor, assignment, swap
_Hashtable(size_type __bucket_hint,
@@ -407,12 +418,12 @@
// Use delegating constructors.
explicit
_Hashtable(const allocator_type& __a)
- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
+ : _Hashtable(_H1(), _H2(), _Hash(), key_equal(),
__key_extract(), __a)
{ }
explicit
- _Hashtable(size_type __n = 10,
+ _Hashtable(size_type __n = 0,
const _H1& __hf = _H1(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -791,15 +802,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 +824,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)
@@ -1218,8 +1228,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)
@@ -130,13 +130,14 @@
/**
* @brief Default constructor creates no elements.
- * @param __n Initial number of buckets.
+ * @param __n Minimal initial number of buckets, default is 0 to avoid
+ * any allocation.
* @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 = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -842,13 +843,14 @@
/**
* @brief Default constructor creates no elements.
- * @param __n Initial number of buckets.
+ * @param __n Mnimal initial number of buckets, default 0 to avoid any
+ * allocation.
* @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 = 0,
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)
@@ -123,13 +123,14 @@
// construct/destroy/copy
/**
* @brief Default constructor creates no elements.
- * @param __n Initial number of buckets.
+ * @param __n Minimal initial number of buckets, default 0 to avoid any
+ * allocation.
* @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 = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -758,13 +759,14 @@
// construct/destroy/copy
/**
* @brief Default constructor creates no elements.
- * @param __n Initial number of buckets.
+ * @param __n Minimal initial number of buckets, default 0 to avoid any
+ * allocation.
* @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 = 0,
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)
@@ -83,7 +83,7 @@
_Base_const_local_iterator, unordered_map> const_local_iterator;
explicit
- unordered_map(size_type __n = 10,
+ unordered_map(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -496,7 +496,7 @@
_Base_const_local_iterator, unordered_multimap> const_local_iterator;
explicit
- unordered_multimap(size_type __n = 10,
+ unordered_multimap(size_type __n = 0,
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)
@@ -83,7 +83,7 @@
_Base_const_local_iterator, unordered_set> const_local_iterator;
explicit
- unordered_set(size_type __n = 10,
+ unordered_set(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -492,7 +492,7 @@
_Base_const_local_iterator, unordered_multiset> const_local_iterator;
explicit
- unordered_multiset(size_type __n = 10,
+ unordered_multiset(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: src/c++11/hashtable_c++0x.cc
===================================================================
--- src/c++11/hashtable_c++0x.cc (revision 213780)
+++ src/c++11/hashtable_c++0x.cc (working copy)
@@ -47,7 +47,7 @@
// Optimize lookups involving the first elements of __prime_list.
// (useful to speed-up, eg, constructors)
static const unsigned char __fast_bkt[12]
- = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
+ = { 1, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
if (__n <= 11)
{
Index: testsuite/23_containers/unordered_map/allocator/empty_instantiation.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/empty_instantiation.cc (revision 0)
+++ testsuite/23_containers/unordered_map/allocator/empty_instantiation.cc (working copy)
@@ -0,0 +1,98 @@
+// Copyright (C) 2013-2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_map>
+#include <testsuite_allocator.h>
+#include <testsuite_hooks.h>
+
+using namespace __gnu_test;
+typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+typedef std::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
+ alloc_type> test_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Default constructor, in fact constructor with hint using default value.
+ test_type u;
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u(1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ std::pair<int, int> ints[] {};
+ // Range constructor.
+ test_type u(ints + 0, ints + 0);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ std::pair<int, int> ints[] { { 1, 1 } };
+ // Range constructor.
+ test_type u(ints + 0, ints + 1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Initializer list constructor.
+ test_type u({});
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u({ { 1, 1 } });
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}
Index: testsuite/23_containers/unordered_multimap/allocator/empty_instantiation.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/empty_instantiation.cc (revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/empty_instantiation.cc (working copy)
@@ -0,0 +1,98 @@
+// Copyright (C) 2013-2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_map>
+#include <testsuite_allocator.h>
+#include <testsuite_hooks.h>
+
+using namespace __gnu_test;
+typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+typedef std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>,
+ alloc_type> test_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Default constructor, in fact constructor with hint using default value.
+ test_type u;
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u(1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ std::pair<int, int> ints[] {};
+ // Range constructor.
+ test_type u(ints + 0, ints + 0);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ std::pair<int, int> ints[] { { 1, 1 } };
+ // Range constructor.
+ test_type u(ints + 0, ints + 1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Initializer list constructor.
+ test_type u({});
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u({ { 1, 1 } });
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}
Index: testsuite/23_containers/unordered_multiset/allocator/empty_instantiation.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/empty_instantiation.cc (revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/empty_instantiation.cc (working copy)
@@ -0,0 +1,99 @@
+// Copyright (C) 2013-2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+#include <testsuite_allocator.h>
+#include <testsuite_hooks.h>
+
+using namespace __gnu_test;
+typedef tracker_allocator<int> alloc_type;
+typedef std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+ alloc_type> test_type;
+
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Default constructor, in fact constructor with hint using default value.
+ test_type u;
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u(1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ int ints[] {};
+ // Range constructor.
+ test_type u(ints + 0, ints + 0);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ int ints[] { 1 };
+ // Range constructor.
+ test_type u(ints + 0, ints + 1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Initializer list constructor.
+ test_type u({});
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u({ 1 });
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}
Index: testsuite/23_containers/unordered_set/allocator/empty_instantiation.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/empty_instantiation.cc (revision 0)
+++ testsuite/23_containers/unordered_set/allocator/empty_instantiation.cc (working copy)
@@ -0,0 +1,98 @@
+// Copyright (C) 2013-2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+#include <testsuite_allocator.h>
+#include <testsuite_hooks.h>
+
+using namespace __gnu_test;
+typedef tracker_allocator<int> alloc_type;
+typedef std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+ alloc_type> test_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Default constructor, in fact constructor with hint using default value.
+ test_type u;
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u(1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ int ints[] {};
+ // Range constructor.
+ test_type u(ints + 0, ints + 0);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ int ints[] { 1 };
+ // Range constructor.
+ test_type u(ints + 0, ints + 1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Initializer list constructor.
+ test_type u({});
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u({ 1 });
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}
