* [patch] No allocation for empty unordered containers
@ 2014-06-03 20:44 François Dumont
2014-07-25 21:01 ` François Dumont
0 siblings, 1 reply; 15+ messages in thread
From: François Dumont @ 2014-06-03 20:44 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1773 bytes --]
Hi
Thanks to the single bucket introduced to make move semantic
noexcept we can also avoid some over allocations. Here is a patch to
avoid any allocation on default instantiation, on range constructor when
range is empty and on construction from an initialization list when this
list is empty too. I had to make all default hint value to 0 so that if
this value is used the rehash policy next bucket returns 1 bucket.
I don't know if you had in mind to noexcept qualify the default
constructor but it would mean to have a real default constructor and
another to deal with the hint which wouldn't match the Standard so no
noexcept qualification at the moment.
Tested under Linux x86_64.normal debug and profile modes.
2014-06-03 François Dumont <fdumont@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.
* include/profile/unordered_map: Likewise.
* include/profile/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.
Ok to commit ?
François
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 22878 bytes --]
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 211144)
+++ include/bits/hashtable.h (working copy)
@@ -407,12 +407,12 @@
// Use delegating constructors.
explicit
_Hashtable(const allocator_type& __a)
- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
+ : _Hashtable(0, _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())
@@ -792,14 +792,18 @@
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_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
- _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ auto __bkt_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
}
template<typename _Key, typename _Value,
@@ -815,19 +819,24 @@
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_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
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));
+
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -864,14 +873,15 @@
{
// Replacement allocator cannot free existing storage.
this->_M_deallocate_nodes(_M_begin());
- _M_before_begin._M_nxt = nullptr;
_M_deallocate_buckets();
- _M_buckets = nullptr;
+ __hashtable_base::operator=(__ht);
std::__alloc_on_copy(__this_alloc, __that_alloc);
- __hashtable_base::operator=(__ht);
- _M_bucket_count = __ht._M_bucket_count;
+ _M_buckets = &_M_single_bucket;
+ _M_bucket_count = 1;
+ _M_before_begin._M_nxt = nullptr;
_M_element_count = __ht._M_element_count;
_M_rehash_policy = __ht._M_rehash_policy;
+ _M_single_bucket = nullptr;
__try
{
_M_assign(__ht,
@@ -946,8 +956,14 @@
_M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen)
{
__bucket_type* __buckets = nullptr;
- if (!_M_buckets)
- _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+ if (_M_bucket_count != __ht._M_bucket_count)
+ {
+ // Bucket deallocation useless because per design _M_buckets
+ // can only be pointing to _M_single_bucket.
+ //_M_deallocate_buckets();
+ _M_bucket_count = __ht._M_bucket_count;
+ _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+ }
__try
{
@@ -1101,10 +1117,11 @@
__rehash_base(__ht),
__hashtable_alloc(
__node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
- _M_buckets(),
- _M_bucket_count(__ht._M_bucket_count),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(nullptr)
{
_M_assign(__ht,
[this](const __node_type* __n)
@@ -1126,14 +1143,12 @@
_M_bucket_count(__ht._M_bucket_count),
_M_before_begin(__ht._M_before_begin._M_nxt),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(__ht._M_single_bucket)
{
// Update, if necessary, buckets if __ht is using its single bucket.
if (__ht._M_uses_single_bucket())
- {
- _M_buckets = &_M_single_bucket;
- _M_single_bucket = __ht._M_single_bucket;
- }
+ _M_buckets = &_M_single_bucket;
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
@@ -1154,10 +1169,11 @@
__map_base(__ht),
__rehash_base(__ht),
__hashtable_alloc(__node_alloc_type(__a)),
- _M_buckets(),
- _M_bucket_count(__ht._M_bucket_count),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(nullptr)
{
_M_assign(__ht,
[this](const __node_type* __n)
@@ -1175,18 +1191,17 @@
__map_base(__ht),
__rehash_base(__ht),
__hashtable_alloc(__node_alloc_type(__a)),
- _M_buckets(),
- _M_bucket_count(__ht._M_bucket_count),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(nullptr)
{
if (__ht._M_node_allocator() == this->_M_node_allocator())
{
+ _M_bucket_count = __ht._M_bucket_count;
if (__ht._M_uses_single_bucket())
- {
- _M_buckets = &_M_single_bucket;
- _M_single_bucket = __ht._M_single_bucket;
- }
+ _M_single_bucket = __ht._M_single_bucket;
else
_M_buckets = __ht._M_buckets;
@@ -1195,6 +1210,7 @@
// moved.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
__ht._M_reset();
}
else
@@ -1218,8 +1234,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 211144)
+++ include/bits/unordered_map.h (working copy)
@@ -136,7 +136,7 @@
* @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())
@@ -848,7 +848,7 @@
* @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 211144)
+++ include/bits/unordered_set.h (working copy)
@@ -129,7 +129,7 @@
* @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())
@@ -764,7 +764,7 @@
* @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 211144)
+++ 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 211144)
+++ 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: include/profile/unordered_map
===================================================================
--- include/profile/unordered_map (revision 211144)
+++ include/profile/unordered_map (working copy)
@@ -77,7 +77,7 @@
typedef typename _Base::const_iterator const_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())
@@ -322,7 +322,7 @@
typedef typename _Base::const_iterator const_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/profile/unordered_set
===================================================================
--- include/profile/unordered_set (revision 211144)
+++ include/profile/unordered_set (working copy)
@@ -76,7 +76,7 @@
typedef typename _Base::const_iterator const_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())
@@ -300,7 +300,7 @@
typedef typename _Base::const_iterator const_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 211144)
+++ 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();
+}
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-06-03 20:44 [patch] No allocation for empty unordered containers François Dumont
@ 2014-07-25 21:01 ` François Dumont
2014-08-04 11:49 ` Jonathan Wakely
0 siblings, 1 reply; 15+ messages in thread
From: François Dumont @ 2014-07-25 21:01 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 2048 bytes --]
Hi
I think I never get feedback regarding this patch proposal. Note
that if accepted the doc will have to be updated regarding the default
hint value.
Thanks
On 03/06/2014 22:44, François Dumont wrote:
> Hi
>
> Thanks to the single bucket introduced to make move semantic
> noexcept we can also avoid some over allocations. Here is a patch to
> avoid any allocation on default instantiation, on range constructor
> when range is empty and on construction from an initialization list
> when this list is empty too. I had to make all default hint value to 0
> so that if this value is used the rehash policy next bucket returns 1
> bucket.
>
> I don't know if you had in mind to noexcept qualify the default
> constructor but it would mean to have a real default constructor and
> another to deal with the hint which wouldn't match the Standard so no
> noexcept qualification at the moment.
>
> Tested under Linux x86_64.normal debug and profile modes.
>
>
> 2014-06-03 François Dumont <fdumont@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.
> * include/profile/unordered_map: Likewise.
> * include/profile/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.
>
> Ok to commit ?
>
> François
>
>
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 22877 bytes --]
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 211144)
+++ include/bits/hashtable.h (working copy)
@@ -407,12 +407,12 @@
// Use delegating constructors.
explicit
_Hashtable(const allocator_type& __a)
- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
+ : _Hashtable(0, _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())
@@ -792,14 +792,18 @@
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_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
- _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ auto __bkt_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
}
template<typename _Key, typename _Value,
@@ -815,19 +819,24 @@
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_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
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));
+
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -864,14 +873,15 @@
{
// Replacement allocator cannot free existing storage.
this->_M_deallocate_nodes(_M_begin());
- _M_before_begin._M_nxt = nullptr;
_M_deallocate_buckets();
- _M_buckets = nullptr;
+ __hashtable_base::operator=(__ht);
std::__alloc_on_copy(__this_alloc, __that_alloc);
- __hashtable_base::operator=(__ht);
- _M_bucket_count = __ht._M_bucket_count;
+ _M_buckets = &_M_single_bucket;
+ _M_bucket_count = 1;
+ _M_before_begin._M_nxt = nullptr;
_M_element_count = __ht._M_element_count;
_M_rehash_policy = __ht._M_rehash_policy;
+ _M_single_bucket = nullptr;
__try
{
_M_assign(__ht,
@@ -946,8 +956,14 @@
_M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen)
{
__bucket_type* __buckets = nullptr;
- if (!_M_buckets)
- _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+ if (_M_bucket_count != __ht._M_bucket_count)
+ {
+ // Bucket deallocation useless because per design _M_buckets
+ // can only be pointing to _M_single_bucket.
+ //_M_deallocate_buckets();
+ _M_bucket_count = __ht._M_bucket_count;
+ _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+ }
__try
{
@@ -1101,10 +1117,11 @@
__rehash_base(__ht),
__hashtable_alloc(
__node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
- _M_buckets(),
- _M_bucket_count(__ht._M_bucket_count),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(nullptr)
{
_M_assign(__ht,
[this](const __node_type* __n)
@@ -1126,14 +1143,12 @@
_M_bucket_count(__ht._M_bucket_count),
_M_before_begin(__ht._M_before_begin._M_nxt),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(__ht._M_single_bucket)
{
// Update, if necessary, buckets if __ht is using its single bucket.
if (__ht._M_uses_single_bucket())
- {
- _M_buckets = &_M_single_bucket;
- _M_single_bucket = __ht._M_single_bucket;
- }
+ _M_buckets = &_M_single_bucket;
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
@@ -1154,10 +1169,11 @@
__map_base(__ht),
__rehash_base(__ht),
__hashtable_alloc(__node_alloc_type(__a)),
- _M_buckets(),
- _M_bucket_count(__ht._M_bucket_count),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(nullptr)
{
_M_assign(__ht,
[this](const __node_type* __n)
@@ -1175,18 +1191,17 @@
__map_base(__ht),
__rehash_base(__ht),
__hashtable_alloc(__node_alloc_type(__a)),
- _M_buckets(),
- _M_bucket_count(__ht._M_bucket_count),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(nullptr)
{
if (__ht._M_node_allocator() == this->_M_node_allocator())
{
+ _M_bucket_count = __ht._M_bucket_count;
if (__ht._M_uses_single_bucket())
- {
- _M_buckets = &_M_single_bucket;
- _M_single_bucket = __ht._M_single_bucket;
- }
+ _M_single_bucket = __ht._M_single_bucket;
else
_M_buckets = __ht._M_buckets;
@@ -1195,6 +1210,7 @@
// moved.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
__ht._M_reset();
}
else
@@ -1218,8 +1234,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 211144)
+++ include/bits/unordered_map.h (working copy)
@@ -136,7 +136,7 @@
* @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())
@@ -848,7 +848,7 @@
* @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 211144)
+++ include/bits/unordered_set.h (working copy)
@@ -129,7 +129,7 @@
* @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())
@@ -764,7 +764,7 @@
* @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 211144)
+++ 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 211144)
+++ 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: include/profile/unordered_map
===================================================================
--- include/profile/unordered_map (revision 211144)
+++ include/profile/unordered_map (working copy)
@@ -77,7 +77,7 @@
typedef typename _Base::const_iterator const_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())
@@ -322,7 +322,7 @@
typedef typename _Base::const_iterator const_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/profile/unordered_set
===================================================================
--- include/profile/unordered_set (revision 211144)
+++ include/profile/unordered_set (working copy)
@@ -76,7 +76,7 @@
typedef typename _Base::const_iterator const_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())
@@ -300,7 +300,7 @@
typedef typename _Base::const_iterator const_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 211144)
+++ 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();
+}
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-07-25 21:01 ` François Dumont
@ 2014-08-04 11:49 ` Jonathan Wakely
2014-08-04 11:55 ` Jonathan Wakely
0 siblings, 1 reply; 15+ messages in thread
From: Jonathan Wakely @ 2014-08-04 11:49 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 25/07/14 22:53 +0200, François Dumont wrote:
>Hi
>
> I think I never get feedback regarding this patch proposal. Note
I've been trying to weigh up the pros and cons and am unsure what's
best, but I think my preference is to have a noexcept default
constructor. Unless you hear any objections in the next 48 hours
please go ahead and commit this to trunk, thanks
>that if accepted the doc will have to be updated regarding the default
>hint value.
Good point.
>Thanks
>
>
>On 03/06/2014 22:44, François Dumont wrote:
>>Hi
>>
>> Thanks to the single bucket introduced to make move semantic
>>noexcept we can also avoid some over allocations. Here is a patch to
>>avoid any allocation on default instantiation, on range constructor
>>when range is empty and on construction from an initialization list
>>when this list is empty too. I had to make all default hint value to
>>0 so that if this value is used the rehash policy next bucket
>>returns 1 bucket.
>>
>> I don't know if you had in mind to noexcept qualify the default
>>constructor but it would mean to have a real default constructor and
>>another to deal with the hint which wouldn't match the Standard so
>>no noexcept qualification at the moment.
>>
>>Tested under Linux x86_64.normal debug and profile modes.
>>
>>
>>2014-06-03 François Dumont <fdumont@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.
>> * include/profile/unordered_map: Likewise.
>> * include/profile/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.
>>
>>Ok to commit ?
>>
>>François
>>
>>
>
>Index: include/bits/hashtable.h
>===================================================================
>--- include/bits/hashtable.h (revision 211144)
>+++ include/bits/hashtable.h (working copy)
>@@ -407,12 +407,12 @@
> // Use delegating constructors.
> explicit
> _Hashtable(const allocator_type& __a)
>- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
>+ : _Hashtable(0, _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())
>@@ -792,14 +792,18 @@
> 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_buckets(&_M_single_bucket),
>+ _M_bucket_count(1),
> _M_element_count(0),
>- _M_rehash_policy()
>+ _M_single_bucket(nullptr)
> {
>- _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
>- _M_buckets = _M_allocate_buckets(_M_bucket_count);
>+ auto __bkt_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
>+ if (_M_bucket_count != __bkt_count)
>+ {
>+ _M_bucket_count = __bkt_count;
>+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
>+ }
> }
>
> template<typename _Key, typename _Value,
>@@ -815,19 +819,24 @@
> 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_buckets(&_M_single_bucket),
>+ _M_bucket_count(1),
> _M_element_count(0),
>- _M_rehash_policy()
>+ _M_single_bucket(nullptr)
> {
> 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));
>+
>+ if (_M_bucket_count != __bkt_count)
>+ {
>+ _M_bucket_count = __bkt_count;
>+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
>+ }
>
>- _M_buckets = _M_allocate_buckets(_M_bucket_count);
> __try
> {
> for (; __f != __l; ++__f)
>@@ -864,14 +873,15 @@
> {
> // Replacement allocator cannot free existing storage.
> this->_M_deallocate_nodes(_M_begin());
>- _M_before_begin._M_nxt = nullptr;
> _M_deallocate_buckets();
>- _M_buckets = nullptr;
>+ __hashtable_base::operator=(__ht);
> std::__alloc_on_copy(__this_alloc, __that_alloc);
>- __hashtable_base::operator=(__ht);
>- _M_bucket_count = __ht._M_bucket_count;
>+ _M_buckets = &_M_single_bucket;
>+ _M_bucket_count = 1;
>+ _M_before_begin._M_nxt = nullptr;
> _M_element_count = __ht._M_element_count;
> _M_rehash_policy = __ht._M_rehash_policy;
>+ _M_single_bucket = nullptr;
> __try
> {
> _M_assign(__ht,
>@@ -946,8 +956,14 @@
> _M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen)
> {
> __bucket_type* __buckets = nullptr;
>- if (!_M_buckets)
>- _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
>+ if (_M_bucket_count != __ht._M_bucket_count)
>+ {
>+ // Bucket deallocation useless because per design _M_buckets
>+ // can only be pointing to _M_single_bucket.
>+ //_M_deallocate_buckets();
>+ _M_bucket_count = __ht._M_bucket_count;
>+ _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
>+ }
>
> __try
> {
>@@ -1101,10 +1117,11 @@
> __rehash_base(__ht),
> __hashtable_alloc(
> __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
>- _M_buckets(),
>- _M_bucket_count(__ht._M_bucket_count),
>+ _M_buckets(&_M_single_bucket),
>+ _M_bucket_count(1),
> _M_element_count(__ht._M_element_count),
>- _M_rehash_policy(__ht._M_rehash_policy)
>+ _M_rehash_policy(__ht._M_rehash_policy),
>+ _M_single_bucket(nullptr)
> {
> _M_assign(__ht,
> [this](const __node_type* __n)
>@@ -1126,14 +1143,12 @@
> _M_bucket_count(__ht._M_bucket_count),
> _M_before_begin(__ht._M_before_begin._M_nxt),
> _M_element_count(__ht._M_element_count),
>- _M_rehash_policy(__ht._M_rehash_policy)
>+ _M_rehash_policy(__ht._M_rehash_policy),
>+ _M_single_bucket(__ht._M_single_bucket)
> {
> // Update, if necessary, buckets if __ht is using its single bucket.
> if (__ht._M_uses_single_bucket())
>- {
>- _M_buckets = &_M_single_bucket;
>- _M_single_bucket = __ht._M_single_bucket;
>- }
>+ _M_buckets = &_M_single_bucket;
>
> // Update, if necessary, bucket pointing to before begin that hasn't
> // moved.
>@@ -1154,10 +1169,11 @@
> __map_base(__ht),
> __rehash_base(__ht),
> __hashtable_alloc(__node_alloc_type(__a)),
>- _M_buckets(),
>- _M_bucket_count(__ht._M_bucket_count),
>+ _M_buckets(&_M_single_bucket),
>+ _M_bucket_count(1),
> _M_element_count(__ht._M_element_count),
>- _M_rehash_policy(__ht._M_rehash_policy)
>+ _M_rehash_policy(__ht._M_rehash_policy),
>+ _M_single_bucket(nullptr)
> {
> _M_assign(__ht,
> [this](const __node_type* __n)
>@@ -1175,18 +1191,17 @@
> __map_base(__ht),
> __rehash_base(__ht),
> __hashtable_alloc(__node_alloc_type(__a)),
>- _M_buckets(),
>- _M_bucket_count(__ht._M_bucket_count),
>+ _M_buckets(&_M_single_bucket),
>+ _M_bucket_count(1),
> _M_element_count(__ht._M_element_count),
>- _M_rehash_policy(__ht._M_rehash_policy)
>+ _M_rehash_policy(__ht._M_rehash_policy),
>+ _M_single_bucket(nullptr)
> {
> if (__ht._M_node_allocator() == this->_M_node_allocator())
> {
>+ _M_bucket_count = __ht._M_bucket_count;
> if (__ht._M_uses_single_bucket())
>- {
>- _M_buckets = &_M_single_bucket;
>- _M_single_bucket = __ht._M_single_bucket;
>- }
>+ _M_single_bucket = __ht._M_single_bucket;
> else
> _M_buckets = __ht._M_buckets;
>
>@@ -1195,6 +1210,7 @@
> // moved.
> if (_M_begin())
> _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
>+
> __ht._M_reset();
> }
> else
>@@ -1218,8 +1234,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 211144)
>+++ include/bits/unordered_map.h (working copy)
>@@ -136,7 +136,7 @@
> * @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())
>@@ -848,7 +848,7 @@
> * @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 211144)
>+++ include/bits/unordered_set.h (working copy)
>@@ -129,7 +129,7 @@
> * @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())
>@@ -764,7 +764,7 @@
> * @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 211144)
>+++ 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 211144)
>+++ 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: include/profile/unordered_map
>===================================================================
>--- include/profile/unordered_map (revision 211144)
>+++ include/profile/unordered_map (working copy)
>@@ -77,7 +77,7 @@
> typedef typename _Base::const_iterator const_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())
>@@ -322,7 +322,7 @@
> typedef typename _Base::const_iterator const_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/profile/unordered_set
>===================================================================
>--- include/profile/unordered_set (revision 211144)
>+++ include/profile/unordered_set (working copy)
>@@ -76,7 +76,7 @@
> typedef typename _Base::const_iterator const_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())
>@@ -300,7 +300,7 @@
> typedef typename _Base::const_iterator const_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 211144)
>+++ 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();
>+}
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-08-04 11:49 ` Jonathan Wakely
@ 2014-08-04 11:55 ` Jonathan Wakely
[not found] ` <53E13810.8030107@gmail.com>
0 siblings, 1 reply; 15+ messages in thread
From: Jonathan Wakely @ 2014-08-04 11:55 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 04/08/14 12:49 +0100, Jonathan Wakely wrote:
>On 25/07/14 22:53 +0200, François Dumont wrote:
>>Hi
>>
>> I think I never get feedback regarding this patch proposal. Note
>
>I've been trying to weigh up the pros and cons and am unsure what's
>best, but I think my preference is to have a noexcept default
>constructor. Unless you hear any objections in the next 48 hours
>please go ahead and commit this to trunk, thanks
I hit send too soon, I meant to say that I think this change is also
needed:
>>> I don't know if you had in mind to noexcept qualify the default
>>>constructor but it would mean to have a real default constructor
>>>and another to deal with the hint which wouldn't match the
>>>Standard so no noexcept qualification at the moment.
If we don't make it noexcept then I see no point in avoiding
allocation.
(And if the functors and allocator can throw then the noexcept might
have to be condition.)
So please make sure we get that change as well during stage 1.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
[not found] ` <53E13D4B.5080909@oracle.com>
@ 2014-08-12 19:22 ` François Dumont
2014-08-12 19:39 ` Marc Glisse
0 siblings, 1 reply; 15+ messages in thread
From: François Dumont @ 2014-08-12 19:22 UTC (permalink / raw)
To: Paolo Carlini, Jonathan Wakely; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 2359 bytes --]
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 <fdumont@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
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 19231 bytes --]
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();
+}
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-08-12 19:22 ` François Dumont
@ 2014-08-12 19:39 ` Marc Glisse
2014-08-12 19:53 ` François Dumont
0 siblings, 1 reply; 15+ messages in thread
From: Marc Glisse @ 2014-08-12 19:39 UTC (permalink / raw)
To: François Dumont
Cc: Paolo Carlini, Jonathan Wakely, libstdc++, gcc-patches
On Tue, 12 Aug 2014, François Dumont wrote:
> 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.
The standard explicitly says that you may add noexcept wherever you like.
It is constexpr that we can only add in GNU mode.
--
Marc Glisse
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-08-12 19:39 ` Marc Glisse
@ 2014-08-12 19:53 ` François Dumont
2014-08-13 9:50 ` Jonathan Wakely
0 siblings, 1 reply; 15+ messages in thread
From: François Dumont @ 2014-08-12 19:53 UTC (permalink / raw)
To: libstdc++; +Cc: Paolo Carlini, Jonathan Wakely, gcc-patches
On 12/08/2014 21:39, Marc Glisse wrote:
> On Tue, 12 Aug 2014, François Dumont wrote:
>
>> 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.
>
> The standard explicitly says that you may add noexcept wherever you
> like. It is constexpr that we can only add in GNU mode.
>
That's not what I meant. For unordered containers there is no real
default constructor. it is in fact a constructor with parameters which
have all default values. This is why you can only say that it won't
throw at runtime and so you can't qualify it noexcept.
François
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-08-12 19:53 ` François Dumont
@ 2014-08-13 9:50 ` Jonathan Wakely
2014-08-14 19:23 ` François Dumont
0 siblings, 1 reply; 15+ messages in thread
From: Jonathan Wakely @ 2014-08-13 9:50 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, Paolo Carlini, gcc-patches
On 12/08/14 21:53 +0200, François Dumont wrote:
>On 12/08/2014 21:39, Marc Glisse wrote:
>>On Tue, 12 Aug 2014, François Dumont wrote:
>>
>>> 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.
>>
>>The standard explicitly says that you may add noexcept wherever you
>>like. It is constexpr that we can only add in GNU mode.
>>
> That's not what I meant. For unordered containers there is no real
>default constructor. it is in fact a constructor with parameters which
>have all default values. This is why you can only say that it won't
>throw at runtime and so you can't qualify it noexcept.
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-08-13 9:50 ` Jonathan Wakely
@ 2014-08-14 19:23 ` François Dumont
2014-08-30 18:03 ` François Dumont
` (2 more replies)
0 siblings, 3 replies; 15+ messages in thread
From: François Dumont @ 2014-08-14 19:23 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, Paolo Carlini, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1941 bytes --]
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
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 14871 bytes --]
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" );
+}
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-08-14 19:23 ` François Dumont
@ 2014-08-30 18:03 ` François Dumont
2014-09-02 10:05 ` Jonathan Wakely
2014-09-05 10:47 ` Jonathan Wakely
2014-09-09 17:29 ` Jonathan Wakely
2 siblings, 1 reply; 15+ messages in thread
From: François Dumont @ 2014-08-30 18:03 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, Paolo Carlini, gcc-patches
Any news for my patch proposals ?
Regarding documentation of default minimum number of buckets, I don't
know where it has been documented but why do we need to document it
separately ? Could it be taken care by Doxygen ? Can't it get the
default value from the code itself ? If not we could document it ourself
next to the code rather than in a distinct file.
François
On 14/08/2014 21:22, François Dumont wrote:
> 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
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-08-30 18:03 ` François Dumont
@ 2014-09-02 10:05 ` Jonathan Wakely
0 siblings, 0 replies; 15+ messages in thread
From: Jonathan Wakely @ 2014-09-02 10:05 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, Paolo Carlini, gcc-patches
On 30/08/14 20:03 +0200, François Dumont wrote:
>Any news for my patch proposals ?
>
>Regarding documentation of default minimum number of buckets, I don't
>know where it has been documented but why do we need to document it
>separately ? Could it be taken care by Doxygen ? Can't it get the
>default value from the code itself ? If not we could document it
>ourself next to the code rather than in a distinct file.
It's OK to document it with a Doxygen comment, although I think it
would be better in doc/xml/manual/containers.xml.
I'm reviewing the rest of the patch today, thanks for you patience.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-08-14 19:23 ` François Dumont
2014-08-30 18:03 ` François Dumont
@ 2014-09-05 10:47 ` Jonathan Wakely
2014-09-09 17:29 ` Jonathan Wakely
2 siblings, 0 replies; 15+ messages in thread
From: Jonathan Wakely @ 2014-09-05 10:47 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, Paolo Carlini, gcc-patches
On 14/08/14 21:22 +0200, François Dumont wrote:
> 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 ?
I don't really care about that constructor, no need to do it now.
The patch is OK to commit, thanks.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-08-14 19:23 ` François Dumont
2014-08-30 18:03 ` François Dumont
2014-09-05 10:47 ` Jonathan Wakely
@ 2014-09-09 17:29 ` Jonathan Wakely
2014-09-09 21:03 ` François Dumont
2 siblings, 1 reply; 15+ messages in thread
From: Jonathan Wakely @ 2014-09-09 17:29 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, Paolo Carlini, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 748 bytes --]
On 14/08/14 21:22 +0200, François Dumont wrote:
>I am preparing a patch for profile mode so I will submit modification
>for this mode with this big patch.
btw, François, for profile mode I think we should just do something
like this patch.
I feel quite strongly that if using Debug Mode or Profile Mode makes
your program run out of memory where it wouldn't usually fail, then
terminating is reasonable. The point of Profile Mode is not to test
abnormal execution of your program because that won't give you useful
profile information for the normal case.
It's more important for the noexcept specification to be consistent
across normal/debug/profile modes than for profile mode to fail
gracefully via bad_alloc in out-of-memory scenarios.
[-- Attachment #2: profile-noexcept.txt --]
[-- Type: text/plain, Size: 983 bytes --]
diff --git a/libstdc++-v3/include/profile/unordered_base.h b/libstdc++-v3/include/profile/unordered_base.h
index 283f87c..cd9db7e 100644
--- a/libstdc++-v3/include/profile/unordered_base.h
+++ b/libstdc++-v3/include/profile/unordered_base.h
@@ -154,7 +154,7 @@ namespace __profile
using __unique_keys = std::integral_constant<bool, _Unique_keys>;
protected:
- _Unordered_profile()
+ _Unordered_profile() noexcept
{
auto& __uc = _M_conjure();
__profcxx_hashtable_construct(&__uc, __uc.bucket_count());
@@ -162,10 +162,10 @@ namespace __profile
}
_Unordered_profile(const _Unordered_profile&)
: _Unordered_profile() { }
- _Unordered_profile(_Unordered_profile&&)
+ _Unordered_profile(_Unordered_profile&&) noexcept
: _Unordered_profile() { }
- ~_Unordered_profile() noexcept
+ ~_Unordered_profile()
{
auto& __uc = _M_conjure();
__profcxx_hashtable_destruct(&__uc, __uc.bucket_count(), __uc.size());
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-09-09 17:29 ` Jonathan Wakely
@ 2014-09-09 21:03 ` François Dumont
2014-09-09 21:31 ` Jonathan Wakely
0 siblings, 1 reply; 15+ messages in thread
From: François Dumont @ 2014-09-09 21:03 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, Paolo Carlini, gcc-patches
On 09/09/2014 19:29, Jonathan Wakely wrote:
> On 14/08/14 21:22 +0200, François Dumont wrote:
>> I am preparing a patch for profile mode so I will submit modification
>> for this mode with this big patch.
>
> btw, François, for profile mode I think we should just do something
> like this patch.
>
> I feel quite strongly that if using Debug Mode or Profile Mode makes
> your program run out of memory where it wouldn't usually fail, then
> terminating is reasonable. The point of Profile Mode is not to test
> abnormal execution of your program because that won't give you useful
> profile information for the normal case.
>
> It's more important for the noexcept specification to be consistent
> across normal/debug/profile modes than for profile mode to fail
> gracefully via bad_alloc in out-of-memory scenarios.
>
Sure, no problem. In the patch I am preparing for profile mode
failure in allocation will just mean that the involved container won't
be profiled so that I can add noexcept wherever it is needed for
consistency with normal mode. I hope to be able to submit this patch in
a week or two.
François
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [patch] No allocation for empty unordered containers
2014-09-09 21:03 ` François Dumont
@ 2014-09-09 21:31 ` Jonathan Wakely
0 siblings, 0 replies; 15+ messages in thread
From: Jonathan Wakely @ 2014-09-09 21:31 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, Paolo Carlini, gcc-patches
On 09/09/14 23:03 +0200, François Dumont wrote:
>On 09/09/2014 19:29, Jonathan Wakely wrote:
>>On 14/08/14 21:22 +0200, François Dumont wrote:
>>>I am preparing a patch for profile mode so I will submit
>>>modification for this mode with this big patch.
>>
>>btw, François, for profile mode I think we should just do something
>>like this patch.
>>
>>I feel quite strongly that if using Debug Mode or Profile Mode makes
>>your program run out of memory where it wouldn't usually fail, then
>>terminating is reasonable. The point of Profile Mode is not to test
>>abnormal execution of your program because that won't give you useful
>>profile information for the normal case.
>>
>>It's more important for the noexcept specification to be consistent
>>across normal/debug/profile modes than for profile mode to fail
>>gracefully via bad_alloc in out-of-memory scenarios.
>>
> Sure, no problem. In the patch I am preparing for profile mode
>failure in allocation will just mean that the involved container won't
>be profiled so that I can add noexcept wherever it is needed for
>consistency with normal mode. I hope to be able to submit this patch
>in a week or two.
Great - thanks for working on it.
^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2014-09-09 21:31 UTC | newest]
Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-06-03 20:44 [patch] No allocation for empty unordered containers François Dumont
2014-07-25 21:01 ` François Dumont
2014-08-04 11:49 ` Jonathan Wakely
2014-08-04 11:55 ` Jonathan Wakely
[not found] ` <53E13810.8030107@gmail.com>
[not found] ` <20140805201026.GH6927@redhat.com>
[not found] ` <53E13D4B.5080909@oracle.com>
2014-08-12 19:22 ` François Dumont
2014-08-12 19:39 ` Marc Glisse
2014-08-12 19:53 ` François Dumont
2014-08-13 9:50 ` Jonathan Wakely
2014-08-14 19:23 ` François Dumont
2014-08-30 18:03 ` François Dumont
2014-09-02 10:05 ` Jonathan Wakely
2014-09-05 10:47 ` Jonathan Wakely
2014-09-09 17:29 ` Jonathan Wakely
2014-09-09 21:03 ` François Dumont
2014-09-09 21:31 ` 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).