* [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
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).