Patchwork PR 54075 Restore 4.6 growth factor

login
register
mail settings
Submitter Jonathan Wakely
Date July 28, 2012, 9:18 p.m.
Message ID <CAH6eHdSFfjoCySVCqShSHS=8GMfsAEJOsL3J0VnsPGZ=jFC0vg@mail.gmail.com>
Download mbox | patch
Permalink /patch/173885/
State New
Headers show

Comments

Jonathan Wakely - July 28, 2012, 9:18 p.m.
Please remember to CC gcc-patches too.

On 28 July 2012 21:49, Fran├žois Dumont wrote:
> Hi
>
>     Here is the patch to restore the 4.6 growth factor of 2. I prefer to
> validate the restored behavior by adding a performance test. Without the
> patch the result was:
>
> unordered_set.cc             unordered_set 10000000 insertions  403r  329u
> 73s 402825280mem    0pf
>
> after the patch:
>
> unordered_set.cc             unordered_set 10000000 insertions  112r   86u
> 25s 402825104mem    0pf
>
> It validates the 3x times performance hint.
>
> Tested under Linux x86_64.
>
> 2012-07-28  Fran├žois Dumont  <fdumont@gcc.gnu.org>
>
>     PR libstdc++/54075
>     * include/bits/hashtable_policy.h
>     (_Prime_rehash_policy::_M_next_bkt): Add a growth factor set to 2
>     to boost growth in the number of buckets.
>     * testsuite/performance/23_containers/insert/unordered_set.cc: New.
>
> Even if it is not a Standard conformity issue I think we can apply it to the
> 4.7 branch too.

Yes, it's a performance regression, so this is OK for trunk and 4.7, thanks.

Patch

Index: include/bits/hashtable_policy.h

===================================================================
--- include/bits/hashtable_policy.h	(revision 189893)

+++ include/bits/hashtable_policy.h	(working copy)

@@ -395,6 +395,8 @@ 

 
     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
 
+    static const std::size_t _S_growth_factor = 2;

+

     float                _M_max_load_factor;
     mutable std::size_t  _M_prev_resize;
     mutable std::size_t  _M_next_resize;
@@ -415,28 +417,27 @@ 

     static const unsigned char __fast_bkt[12]
       = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
 
-    if (__n <= 11)

+    const std::size_t __grown_n = __n * _S_growth_factor;

+    if (__grown_n <= 11)

       {
 	_M_prev_resize = 0;
 	_M_next_resize
-	  = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);

-	return __fast_bkt[__n];

+	  = __builtin_ceil(__fast_bkt[__grown_n]

+			   * (long double)_M_max_load_factor);

+	return __fast_bkt[__grown_n];

       }
 
-    const unsigned long* __p

-      = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n);

+    const unsigned long* __next_bkt

+      = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes,

+			 __grown_n);

+    const unsigned long* __prev_bkt

+      = std::lower_bound(__prime_list + 1, __next_bkt, __n / _S_growth_factor);

 
-    // Shrink will take place only if the number of elements is small enough

-    // so that the prime number 2 steps before __p is large enough to still

-    // conform to the max load factor:

     _M_prev_resize
-      = __builtin_floor(*(__p - 2) * (long double)_M_max_load_factor);

-

-    // Let's guaranty that a minimal grow step of 11 is used

-    if (*__p - __n < 11)

-      __p = std::lower_bound(__p, __prime_list + _S_n_primes, __n + 11);

-    _M_next_resize = __builtin_ceil(*__p * (long double)_M_max_load_factor);

-    return *__p;

+      = __builtin_floor(*(__prev_bkt - 1) * (long double)_M_max_load_factor);

+    _M_next_resize

+      = __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);

+    return *__next_bkt;

   }
 
   // Return the smallest prime p such that alpha p >= n, where alpha
Index: testsuite/performance/23_containers/insert/unordered_set.cc

===================================================================
--- testsuite/performance/23_containers/insert/unordered_set.cc	(revision 0)

+++ testsuite/performance/23_containers/insert/unordered_set.cc	(revision 0)

@@ -0,0 +1,42 @@ 

+// 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/>.

+

+// { dg-options "-std=c++11" }

+

+#include <unordered_set>

+#include <testsuite_performance.h>

+

+int main()

+{

+  using namespace __gnu_test;

+

+  time_counter time;

+  resource_counter resource;

+

+  const int sz = 10000000;

+

+  std::unordered_set<int> s;

+  start_counters(time, resource);

+

+  for (int i = 0; i != sz ; ++i)

+    s.insert(i);

+

+  stop_counters(time, resource);

+  report_performance(__FILE__, "unordered_set 10000000 insertions",

+		     time, resource);

+  return 0;

+}