Patchwork PR 54075 Fix hashtable::reserve

login
register
mail settings
Submitter François Dumont
Date July 25, 2012, 8:29 p.m.
Message ID <5010570E.307@gmail.com>
Download mbox | patch
Permalink /patch/173260/
State New
Headers show

Comments

François Dumont - July 25, 2012, 8:29 p.m.
Attached patch applied to trunk. I am building 4.7 branch to also apply 
the patch to this branch.

2012-07-25  François Dumont  <fdumont@gcc.gnu.org>

         PR libstdc++/54075
         * include/bits/hashtable.h
         (_Hashtable<>::_Hashtable(_InputIterator, _InputIterator,
         size_type, ...): Remove std::max usage to guarantee that hashtable
         state is consistent with hash policy state.
         (_Hashtable<>::rehash): Likewise. Set _M_prev_resize to 0 to avoid
         the hashtable to be shrinking on next insertion.
         * testsuite/23_containers/unordered_set/modifiers/reserve.cc: New.
         * 
testsuite/23_containers/unordered_multiset/modifiers/reserve.cc: New.
         * testsuite/23_containers/unordered_map/modifiers/reserve.cc: New.
         * 
testsuite/23_containers/unordered_multimap/modifiers/reserve.cc: New.

François


On 07/25/2012 04:55 PM, Jonathan Wakely wrote:
> (CC gcc-patches)
>
> On 25 July 2012 10:26, François Dumont wrote:
>> Hi
>>
>>      Here is a patch proposal for PR 54075. I also took the occasion to fix
>> something that has been delay so far which is usage of std::max to get the
>> number of buckets to use. The problem of using std::max when using the hash
>> policy is that the hashtable might be using a number of buckets inconsistent
>> with the hash policy.
>>
>> 2012-07-25  François Dumont  <fdumont@gcc.gnu.org>
>>
>>      PR libstdc++/54075
>>      * include/bits/hashtable.h
>>      (_Hashtable<>::_Hashtable(_InputIterator, _InputIterator,
>>      size_type, ...): Remove std::max usage to guaranty that hashtable
>>      state is consistent with hash policy state.
> s/guaranty/guarantee/
>
>>      (_Hashtable<>::rehash): Likewise. Set _M_prev_resize to 0 to avoid
>>      the hashtable to be shrink on next insertion.
> s/to be shrink/shrinking/
>
>>      * testsuite/23_containers/unordered_set/modifiers/reserve.cc: New.
>>      * testsuite/23_containers/unordered_multiset/modifiers/reserve.cc: New.
>>      * testsuite/23_containers/unordered_map/modifiers/reserve.cc: New.
>>      * testsuite/23_containers/unordered_multimap/modifiers/reserve.cc: New.
>>
>>      Tested under Linux x86_64.
> OK with the changelog edits above.
>
>>      I guess it will have to be apply to the 4.7 branch too, confirm please.
> Yes, I think so, it's a regression from 4.6.
>
> Thanks for dealing with it so quickly.
Jonathan Wakely - July 26, 2012, 9:11 a.m.
On 25 July 2012 21:29, François Dumont wrote:
>         (_Hashtable<>::rehash): Likewise. Set _M_prev_resize to 0 to avoid
>         the hashtable to be shrinking on next insertion.

Not "to be shrinking" just "shrinking", but nevermind.

Patch

Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 189626)
+++ include/bits/hashtable.h	(working copy)
@@ -803,11 +803,11 @@ 
 	_M_element_count(0),
 	_M_rehash_policy()
       {
-	_M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
-				   _M_rehash_policy.
-				   _M_bkt_for_elements(__detail::
-						       __distance_fw(__f,
-								     __l)));
+	_M_bucket_count =
+	  _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f,
+								       __l));
+	if (_M_bucket_count <= __bucket_hint)
+	  _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
 
 	// We don't want the rehash policy to ask for the hashtable to
 	// shrink on the first insertion so we need to reset its
@@ -1609,10 +1609,20 @@ 
     rehash(size_type __n)
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
-      _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
-			 _M_rehash_policy._M_bkt_for_elements(_M_element_count
-							      + 1)),
-		__saved_state);
+      std::size_t __buckets
+	= _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1);
+      if (__buckets <= __n)
+	__buckets = _M_rehash_policy._M_next_bkt(__n);
+
+      if (__buckets != _M_bucket_count)
+	{
+	  _M_rehash(__buckets, __saved_state);
+
+	  // We don't want the rehash policy to ask for the hashtable to shrink
+	  // on the next insertion so we need to reset its previous resize
+	  // level.
+	  _M_rehash_policy._M_prev_resize = 0;
+	}
     }
 
   template<typename _Key, typename _Value,
Index: testsuite/23_containers/unordered_multiset/modifiers/reserve.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/modifiers/reserve.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/modifiers/reserve.cc	(revision 0)
@@ -0,0 +1,48 @@ 
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2012 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 <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  const int N = 1000;
+
+  typedef std::unordered_multiset<int> MSet;
+  MSet s;
+  s.reserve(N * 2);
+
+  std::size_t bkts = s.bucket_count();
+  for (int i = 0; i != N; ++i)
+    {
+      s.insert(i);
+      s.insert(i);
+      // As long as we insert less than the reserved number of elements we
+      // shouldn't experiment any rehash.
+      VERIFY( s.bucket_count() == bkts );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/23_containers/unordered_map/modifiers/reserve.cc
===================================================================
--- testsuite/23_containers/unordered_map/modifiers/reserve.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/modifiers/reserve.cc	(revision 0)
@@ -0,0 +1,47 @@ 
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2012 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 <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  const int N = 1000;
+
+  typedef std::unordered_map<int, int> Map;
+  Map m;
+  m.reserve(N);
+
+  std::size_t bkts = m.bucket_count();
+  for (int i = 0; i != N; ++i)
+    {
+      m.insert(std::make_pair(i, i));
+      // As long as we insert less than the reserved number of elements we
+      // shouldn't experiment any rehash.
+      VERIFY( m.bucket_count() == bkts );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multimap/modifiers/reserve.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/modifiers/reserve.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/modifiers/reserve.cc	(revision 0)
@@ -0,0 +1,48 @@ 
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2012 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 <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  const int N = 1000;
+
+  typedef std::unordered_multimap<int, int> MMap;
+  MMap m;
+  m.reserve(N * 2);
+
+  std::size_t bkts = m.bucket_count();
+  for (int i = 0; i != N; ++i)
+    {
+      m.insert(std::make_pair(i, i));
+      m.insert(std::make_pair(i, i));
+      // As long as we insert less than the reserved number of elements we
+      // shouldn't experiment any rehash.
+      VERIFY( m.bucket_count() == bkts );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/23_containers/unordered_set/modifiers/reserve.cc
===================================================================
--- testsuite/23_containers/unordered_set/modifiers/reserve.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/modifiers/reserve.cc	(revision 0)
@@ -0,0 +1,47 @@ 
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2012 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 <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  const int N = 1000;
+
+  typedef std::unordered_set<int> Set;
+  Set s;
+  s.reserve(N);
+
+  std::size_t bkts = s.bucket_count();
+  for (int i = 0; i != N; ++i)
+    {
+      s.insert(i);
+      // As long as we insert less than the reserved number of elements we
+      // shouldn't experiment any rehash.
+      VERIFY( s.bucket_count() == bkts );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}