* Re: PR 54075 Restore 4.6 growth factor
[not found] <50145054.2060102@gmail.com>
@ 2012-07-29 7:35 ` Jonathan Wakely
2012-07-29 17:38 ` François Dumont
0 siblings, 1 reply; 4+ messages in thread
From: Jonathan Wakely @ 2012-07-29 7:35 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1103 bytes --]
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.
[-- Attachment #2: hash_policy.patch --]
[-- Type: text/x-patch, Size: 3852 bytes --]
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;
+}
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: PR 54075 Restore 4.6 growth factor
2012-07-29 7:35 ` PR 54075 Restore 4.6 growth factor Jonathan Wakely
@ 2012-07-29 17:38 ` François Dumont
2012-07-29 18:08 ` Jonathan Wakely
0 siblings, 1 reply; 4+ messages in thread
From: François Dumont @ 2012-07-29 17:38 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1298 bytes --]
Patch applied. I usually CC to gcc-patches when I signal that it has
been applied. Should I send it all my patch proposals ?
François
On 07/28/2012 11:18 PM, Jonathan Wakely wrote:
> 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.
[-- Attachment #2: hash_policy.patch --]
[-- Type: text/x-patch, Size: 3749 bytes --]
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;
+}
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: PR 54075 Restore 4.6 growth factor
2012-07-29 17:38 ` François Dumont
@ 2012-07-29 18:08 ` Jonathan Wakely
2012-07-29 19:51 ` Paolo Carlini
0 siblings, 1 reply; 4+ messages in thread
From: Jonathan Wakely @ 2012-07-29 18:08 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 29 July 2012 18:15, François Dumont wrote:
> Patch applied. I usually CC to gcc-patches when I signal that it has been
> applied. Should I send it all my patch proposals ?
Yes please. The point is to allow people to review and comment before
the patch is applied, and some people only subscribe to gcc-patches
not libstdc++. The gcc-cvs and libstdc++-cvs lists provide a record
of patches that have been applied.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: PR 54075 Restore 4.6 growth factor
2012-07-29 18:08 ` Jonathan Wakely
@ 2012-07-29 19:51 ` Paolo Carlini
0 siblings, 0 replies; 4+ messages in thread
From: Paolo Carlini @ 2012-07-29 19:51 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: François Dumont, libstdc++, gcc-patches
On 07/29/2012 07:38 PM, Jonathan Wakely wrote:
> Yes please. The point is to allow people to review and comment before
> the patch is applied, and some people only subscribe to gcc-patches
> not libstdc++.
I don't have a strong opinion, but I must say that I don't understand
why those people don't subscribe to libstdc++: since we *do* have a
separate mailing list, IMO if they are interested they should. On the
other hand, if they *really* don't care (eg, some people don't even like
C++ in general ;) sending all the traffic to gcc-patches too may seem a
mild form of spamming. But, as I said, I don't have a strong opinion,
and personally I'm not terribly consistent ;)
Paolo.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2012-07-29 18:08 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <50145054.2060102@gmail.com>
2012-07-29 7:35 ` PR 54075 Restore 4.6 growth factor Jonathan Wakely
2012-07-29 17:38 ` François Dumont
2012-07-29 18:08 ` Jonathan Wakely
2012-07-29 19:51 ` Paolo Carlini
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).