Patchwork PR 54075 Fix hashtable::reserve

login
register
mail settings
Submitter Jonathan Wakely
Date July 25, 2012, 2:55 p.m.
Message ID <CAH6eHdR1iUYopyyYhRx3rqDLi6RzAo4UaY15ZUk+rk8MABD1yw@mail.gmail.com>
Download mbox | patch
Permalink /patch/173185/
State New
Headers show

Comments

Jonathan Wakely - July 25, 2012, 2:55 p.m.
(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.
Paolo Carlini - July 26, 2012, 10:28 p.m.
On 07/25/2012 04:55 PM, Jonathan Wakely wrote:
> Yes, I think so, it's a regression from 4.6.
>
> Thanks for dealing with it so quickly.
Thanks indeed.

However, looks like we have another issue, unrelated to reserve, pure 
performance not correctness, with the sheer number of rehashes when the 
map grows. First blush doesn't seem something very too hard to fix, but 
submitters for some reason don't feel like providing a complete testcase 
for it...

Thanks again!
Paolo.

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;

+}