This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] PR libstdc++/83709 don't rehash if no insertion


Hi

    Bug confirmed, limited to range insertion on unordered_set and unordered_map.

    I had to specialize _M_insert_range for those containers. Now this method maintains the theoretical number of elements to insert which is used only if an insertion takes place.

    I also took this oportunity to introduce a small change in __distance_fw to report 0 only if __first == __last and do nothing in this case.

    * include/bits/hashtable_policy.h
    (__distance_fwd(_Iterator, _Iterator, input_iterator_tag)): Return 1 if
    __first != __last.
    (_Insert_base::_M_insert_range(_Ite, _Ite, _NodeGetter, true_type)): New.
    (_Insert_base::_M_insert_range(_Ite, _Ite, _NodeGetter, false_type)):
    Add false_type parameter.
    (_Insert_base::insert): Adapt.
    * include/bits/hashtable.h (_Hashtable::operator=(initializzr_list<>)):
    Adapt.
    (_Hashtable::_M_insert_unique_node): Add __n_elt parameter, defaulted
    to 1.
    (_Hashtable::_M_insert(_Arg&&, const _NodeGen&, true_type, size_t)):
    Likewise.
    (_Hashtable::_M_merge_unique): Pass target number of elements to add to
    produce only 1 rehash if necessary.
    * testsuite/23_containers/unordered_map/insert/83709.cc: New.
    * testsuite/23_containers/unordered_set/insert/83709.cc: New.

Tested under Linux x86_64 normal and debug modes.

Ok to commit ?

François


diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index e6108a6..1245d79 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -490,7 +490,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__reuse_or_alloc_node_type __roan(_M_begin(), *this);
 	_M_before_begin._M_nxt = nullptr;
 	clear();
-	this->_M_insert_range(__l.begin(), __l.end(), __roan);
+	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
 	return *this;
       }
 
@@ -678,7 +678,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // deallocate it on exception.
       iterator
       _M_insert_unique_node(size_type __bkt, __hash_code __code,
-			    __node_type* __n);
+			    __node_type* __n, size_type __n_elt = 1);
 
       // Insert node with hash code __code. Take ownership of the node,
       // deallocate it on exception.
@@ -707,12 +707,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert(_Arg&&, const _NodeGenerator&, std::true_type);
+	_M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1);
 
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
-		  std::false_type __uk)
+		  false_type __uk)
 	{
 	  return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
 			   __uk);
@@ -722,7 +722,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(const_iterator, _Arg&& __arg,
-		  const _NodeGenerator& __node_gen, std::true_type __uk)
+		  const _NodeGenerator& __node_gen, true_type __uk)
 	{
 	  return
 	    _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first;
@@ -732,7 +732,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(const_iterator, _Arg&&,
-		  const _NodeGenerator&, std::false_type);
+		  const _NodeGenerator&, false_type);
 
       size_type
       _M_erase(std::true_type, const key_type&);
@@ -884,6 +884,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
+	  auto __n_elt = __src.size();
 	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
 	    {
 	      auto __pos = __i++;
@@ -893,9 +894,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      if (_M_find_node(__bkt, __k, __code) == nullptr)
 		{
 		  auto __nh = __src.extract(__pos);
-		  _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+		  _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
 		  __nh._M_ptr = nullptr;
+		  __n_elt = 1;
 		}
+	      else if (__n_elt != 1)
+		--__n_elt;
 	    }
 	}
 
@@ -1721,12 +1725,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_insert_unique_node(size_type __bkt, __hash_code __code,
-			  __node_type* __node)
+			  __node_type* __node, size_type __n_elt)
     -> iterator
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
       std::pair<bool, std::size_t> __do_rehash
-	= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
+	= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
+					  __n_elt);
 
       __try
 	{
@@ -1824,7 +1829,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, std::true_type)
+      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type,
+		size_type __n_elt)
       -> pair<iterator, bool>
       {
 	const key_type& __k = this->_M_extract()(__v);
@@ -1836,7 +1842,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return std::make_pair(iterator(__n), false);
 
 	__n = __node_gen(std::forward<_Arg>(__v));
-	return std::make_pair(_M_insert_unique_node(__bkt, __code, __n), true);
+	return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true };
       }
 
   // Insert v unconditionally.
@@ -1849,7 +1855,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_insert(const_iterator __hint, _Arg&& __v,
-		const _NodeGenerator& __node_gen, std::false_type)
+		const _NodeGenerator& __node_gen, false_type)
       -> iterator
       {
 	// First compute the hash code so that we don't do anything if it
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index ab59b61..df6a0eb 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -58,12 +58,12 @@ namespace __detail
     struct _Hashtable_base;
 
   // Helper function: return distance(first, last) for forward
-  // iterators, or 0 for input iterators.
+  // iterators, or 0/1 for input iterators.
   template<class _Iterator>
     inline typename std::iterator_traits<_Iterator>::difference_type
     __distance_fw(_Iterator __first, _Iterator __last,
 		  std::input_iterator_tag)
-    { return 0; }
+  { return __first != __last ? 1 : 0; }
 
   template<class _Iterator>
     inline typename std::iterator_traits<_Iterator>::difference_type
@@ -74,10 +74,8 @@ namespace __detail
   template<class _Iterator>
     inline typename std::iterator_traits<_Iterator>::difference_type
     __distance_fw(_Iterator __first, _Iterator __last)
-    {
-      typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
-      return __distance_fw(__first, __last, _Tag());
-    }
+    { return __distance_fw(__first, __last,
+			   std::__iterator_category(__first)); }
 
   struct _Identity
   {
@@ -820,7 +818,12 @@ namespace __detail
       template<typename _InputIterator, typename _NodeGetter>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			const _NodeGetter&);
+			const _NodeGetter&, true_type);
+
+      template<typename _InputIterator, typename _NodeGetter>
+	void
+	_M_insert_range(_InputIterator __first, _InputIterator __last,
+			const _NodeGetter&, false_type);
 
     public:
       __ireturn_type
@@ -849,7 +852,7 @@ namespace __detail
 	{
 	  __hashtable& __h = _M_conjure_hashtable();
 	  __node_gen_type __node_gen(__h);
-	  return _M_insert_range(__first, __last, __node_gen);
+	  return _M_insert_range(__first, __last, __node_gen, __unique_keys());
 	}
     };
 
@@ -862,13 +865,41 @@ namespace __detail
       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 		    _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      const _NodeGetter& __node_gen)
+		      const _NodeGetter& __node_gen, true_type)
+      {
+	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, __unique_keys(),
+			      __n_elt).second)
+	      __n_elt = 1;
+	    else if (__n_elt != 1)
+	      --__n_elt;
+	  }
+      }
+
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _RehashPolicy, typename _Traits>
+    template<typename _InputIterator, typename _NodeGetter>
+      void
+      _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
+		    _RehashPolicy, _Traits>::
+      _M_insert_range(_InputIterator __first, _InputIterator __last,
+		      const _NodeGetter& __node_gen, false_type)
       {
 	using __rehash_type = typename __hashtable::__rehash_type;
 	using __rehash_state = typename __hashtable::__rehash_state;
 	using pair_type = std::pair<bool, std::size_t>;
 
 	size_type __n_elt = __detail::__distance_fw(__first, __last);
+	if (__n_elt == 0)
+	  return;
 
 	__hashtable& __h = _M_conjure_hashtable();
 	__rehash_type& __rehash = __h._M_rehash_policy;
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/insert/83709.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/83709.cc
new file mode 100644
index 0000000..16e4f03
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/83709.cc
@@ -0,0 +1,43 @@
+// { dg-do run { target c++11 } }
+//
+// Copyright (C) 2018 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 <unordered_map>
+#include <string>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  std::unordered_map<std::string, std::string> m
+  { {"E", "E" }, { "T", "T" } };
+
+  VERIFY( m.size() == 2 );
+
+  auto bcount = m.bucket_count();
+
+  m.insert({ {"E", "E" }, { "T", "T" } });
+
+  VERIFY( m.size() == 2 );
+  VERIFY( m.bucket_count() == bcount );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/83709.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/83709.cc
new file mode 100644
index 0000000..0a5a520
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/83709.cc
@@ -0,0 +1,42 @@
+// { dg-do run { target c++11 } }
+//
+// Copyright (C) 2018 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 <unordered_set>
+#include <string>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  std::unordered_set<std::string> s { "E", "T" };
+
+  VERIFY( s.size() == 2 );
+
+  auto bcount = s.bucket_count();
+
+  s.insert({"E", "T" });
+
+  VERIFY( s.size() == 2 );
+  VERIFY( s.bucket_count() == bcount );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]