[Hashtable,2/6] Avoid over-sizing container
diff mbox series

Message ID f838feda-70e8-4052-e433-985082b63894@gmail.com
State New
Headers show
Series
  • Untitled series #143415
Related show

Commit Message

François Dumont Nov. 17, 2019, 8:56 p.m. UTC
This patch avoids over-sizing of the container by rather considering the 
bucket count hint or potential reservation.

It concerns only the non-multi containers.

     * include/bits/hashtable.h
     (_Hashtable<>(_InputIterator, _InputIterator, size_t, const _H1&,
     const _H2&, const _Hash&, const _Equal&, const _ExtractKey&,
     const allocator_type&, __unique_keys_t)): New.
     (_Hashtable<>(_InputIterator, _InputIterator, size_t, const _H1&,
     const _H2&, const _Hash&, const _Equal&, const _ExtractKey&,
     const allocator_type&, __multi_keys_t)): New.
     (_Hashtable<>(_InputIterator, _InputIterator, size_t, const _H1&,
     const _H2&, const _Hash&, const _Equal&, const _ExtractKey&,
     const allocator_type&)): Delegate to latters.
     (operator=(initializer_list<value_type>)): Rehash if too small.
     (_M_insert(_Arg&&, const _NodeGenerator&, __unique_keys_t)): Remove
     size_t len parameter.
     * include/bits/hashtable_policy.h (_Insert_base<>::_M_insert_range):
     Do not try to get input range distance.
     * testsuite/23_containers/unordered_set/cons/bucket_hint.cc: New.
     * testsuite/23_containers/unordered_set/modifiers/insert.cc: New.

Tested under Linux x86_64.

François

Patch
diff mbox series

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index a685c20376f..5f785d4904d 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -463,17 +463,26 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__hashtable_alloc(__node_alloc_type(__a))
       { }
 
-    public:
-      // Constructor, destructor, assignment, swap
-      _Hashtable() = default;
-      _Hashtable(size_type __bkt_count_hint,
+      template<typename _InputIterator>
+	_Hashtable(_InputIterator __first, _InputIterator __last,
+		   size_type __bkt_count_hint,
 		   const _H1&, const _H2&, const _Hash&,
 		   const _Equal&, const _ExtractKey&,
-		 const allocator_type&);
+		   const allocator_type&,
+		   __unique_keys_t);
 
       template<typename _InputIterator>
 	_Hashtable(_InputIterator __first, _InputIterator __last,
 		   size_type __bkt_count_hint,
+		   const _H1&, const _H2&, const _Hash&,
+		   const _Equal&, const _ExtractKey&,
+		   const allocator_type&,
+		   __multi_keys_t);
+
+    public:
+      // Constructor, destructor, assignment, swap
+      _Hashtable() = default;
+      _Hashtable(size_type __bkt_count_hint,
 		 const _H1&, const _H2&, const _Hash&,
 		 const _Equal&, const _ExtractKey&,
 		 const allocator_type&);
@@ -487,6 +496,16 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable(_Hashtable&&, const allocator_type&);
 
       // Use delegating constructors.
+      template<typename _InputIterator>
+	_Hashtable(_InputIterator __first, _InputIterator __last,
+		   size_type __bkt_count_hint,
+		   const _H1& __h1, const _H2& __h2, const _Hash& __h,
+		   const _Equal& __eq, const _ExtractKey& __exk,
+		   const allocator_type& __a)
+	: _Hashtable(__first, __last, __bkt_count_hint,
+		     __h1, __h2, __h, __eq, __exk, __a, __unique_keys{})
+	{ }
+
       explicit
       _Hashtable(const allocator_type& __a)
       : __hashtable_alloc(__node_alloc_type(__a))
@@ -543,6 +562,14 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
 	_M_before_begin._M_nxt = nullptr;
 	clear();
+
+	// We consider that all elements of __l are going to be inserted.
+	auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
+
+	// Do not shrink to keep potential user reservation.
+	if (_M_bucket_count < __l_bkt_count)
+	  rehash(__l_bkt_count);
+
 	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
 	return *this;
       }
@@ -763,7 +790,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert(_Arg&&, const _NodeGenerator&, __unique_keys_t, size_type = 1);
+	_M_insert(_Arg&&, const _NodeGenerator&, __unique_keys_t);
 
       template<typename _Arg, typename _NodeGenerator>
 	iterator
@@ -1062,7 +1089,25 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		 size_type __bkt_count_hint,
 		 const _H1& __h1, const _H2& __h2, const _Hash& __h,
 		 const _Equal& __eq, const _ExtractKey& __exk,
-		 const allocator_type& __a)
+		 const allocator_type& __a, __unique_keys_t)
+      : _Hashtable(__bkt_count_hint, __h1, __h2, __h, __eq, __exk, __a)
+      {
+	for (; __f != __l; ++__f)
+	  this->insert(*__f);
+      }
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    template<typename _InputIterator>
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+      _Hashtable(_InputIterator __f, _InputIterator __l,
+		 size_type __bkt_count_hint,
+		 const _H1& __h1, const _H2& __h2, const _Hash& __h,
+		 const _Equal& __eq, const _ExtractKey& __exk,
+		 const allocator_type& __a, __multi_keys_t)
       : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
       {
 	auto __nb_elems = __detail::__distance_fw(__f, __l);
@@ -1830,7 +1875,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen,
-		__unique_keys_t __uks, size_type __n_elt)
+		__unique_keys_t __uks)
       -> pair<iterator, bool>
       {
 	const key_type& __k = this->_M_extract()(__v);
@@ -1841,8 +1886,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return { iterator(__node), false };
 
 	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
-	auto __pos
-	  = _M_insert_node(__uks, __bkt, __code, __node._M_node, __n_elt);
+	auto __pos = _M_insert_node(__uks, __bkt, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index f6c40be3b91..f330f7f811b 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -883,18 +883,9 @@  namespace __detail
       _M_insert_range(_InputIterator __first, _InputIterator __last,
 		      const _NodeGetter& __node_gen, __unique_keys_t __uks)
       {
-	size_type __n_elt = __detail::__distance_fw(__first, __last);
-	if (__n_elt == 0)
-	  return;
-
 	__hashtable& __h = _M_conjure_hashtable();
 	for (; __first != __last; ++__first)
-	  {
-	    if (__h._M_insert(*__first, __node_gen, __uks, __n_elt).second)
-	      __n_elt = 1;
-	    else if (__n_elt != 1)
-	      --__n_elt;
-	  }
+	  __h._M_insert(*__first, __node_gen, __uks);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/bucket_hint.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/bucket_hint.cc
new file mode 100644
index 00000000000..ebbaee7b4e0
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/bucket_hint.cc
@@ -0,0 +1,63 @@ 
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2019 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/>.
+
+#include <vector>
+#include <forward_list>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  std::unordered_set<int> a;
+  a.reserve(2);
+
+  std::unordered_set<int> b({ 0, 1, 0, 1, 0, 1, 0, 1 }, a.bucket_count());
+  VERIFY( b.bucket_count() == a.bucket_count() );
+}
+
+void test02()
+{
+  std::unordered_set<int> a;
+  a.reserve(2);
+
+  std::vector<int> v { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 };
+
+  std::unordered_set<int> b(v.begin(), v.end(), a.bucket_count());
+  VERIFY( b.bucket_count() == a.bucket_count() );
+}
+
+void test03()
+{
+  std::unordered_set<int> a;
+  a.reserve(2);
+
+  std::forward_list<int> fl { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 };
+
+  std::unordered_set<int> b(fl.begin(), fl.end(), a.bucket_count());
+  VERIFY( b.bucket_count() == a.bucket_count() );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert.cc
new file mode 100644
index 00000000000..d373eea2991
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert.cc
@@ -0,0 +1,66 @@ 
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2019 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/>.
+
+#include <vector>
+#include <forward_list>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  std::unordered_set<int> a;
+  a.reserve(2);
+
+  auto bkt_count = a.bucket_count();
+  a.insert({ 0, 1, 0, 1, 0, 1, 0, 1 });
+  VERIFY( a.bucket_count() == bkt_count );
+}
+
+void test02()
+{
+  std::unordered_set<int> a;
+  a.reserve(2);
+
+  std::vector<int> v { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 };
+
+  auto bkt_count = a.bucket_count();
+  a.insert(v.begin(), v.end());
+  VERIFY( a.bucket_count() == bkt_count );
+}
+
+void test03()
+{
+  std::unordered_set<int> a;
+  a.reserve(2);
+
+  std::forward_list<int> fl { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 };
+
+  auto bkt_count = a.bucket_count();
+  a.insert(fl.begin(), fl.end());
+  VERIFY( a.bucket_count() == bkt_count );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}