[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #50 from François Dumont --- This performance issue is a result of fixing: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975 It resulted in many more modulo operations and so expensive float divisions. I plan to commit an alternative hash policy using power of 2 number of buckets so that modulo is trivial. Bench are showing that performance are better but still not at the level of tr1 implementation on the operations you are interested in. So it is difficult to close this ticket cause performance regression is still there but it might stay this way for a long time.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #49 from Akim Demaille --- It looks like this story is missing an end.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 Akim Demaille changed: What|Removed |Added CC||akim.demaille at gmail dot com --- Comment #48 from Akim Demaille --- It looks like this history is missing an end.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #44 from François Dumont fdumont at gcc dot gnu.org 2012-11-08 20:06:08 UTC --- Author: fdumont Date: Thu Nov 8 20:06:00 2012 New Revision: 193335 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=193335 Log: 2012-11-08 François Dumont fdum...@gcc.gnu.org PR libstdc++/54075 * include/bits/hashtable.h (_Hashtable::rehash): Reset hash policy state if no rehash. * testsuite/23_containers/unordered_set/modifiers/reserve.cc (test02): New. Modified: branches/gcc-4_7-branch/libstdc++-v3/ChangeLog branches/gcc-4_7-branch/libstdc++-v3/include/bits/hashtable.h branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #45 from François Dumont fdumont at gcc dot gnu.org 2012-11-08 20:16:15 UTC --- Author: fdumont Date: Thu Nov 8 20:16:04 2012 New Revision: 193339 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=193339 Log: 2012-11-08 François Dumont fdum...@gcc.gnu.org PR libstdc++/54075 * include/bits/hashtable.h (_Hashtable::rehash): Reset hash policy state if no rehash. * testsuite/23_containers/unordered_set/modifiers/reserve.cc (test02): New. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/hashtable.h trunk/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #46 from frs.dumont at gmail dot com 2012-11-08 20:21:15 UTC --- Attached patch applied to trunk and 4.7 branch. 2012-11-08 François Dumont fdum...@gcc.gnu.org PR libstdc++/54075 * include/bits/hashtable.h (_Hashtable::rehash): Reset hash policy state if no rehash. * testsuite/23_containers/unordered_set/modifiers/reserve.cc (test02): New. François On 11/08/2012 01:58 AM, Jonathan Wakely wrote: On 7 November 2012 22:02, François Dumont wrote: Ok to commit ? If so, where ? That patch is OK for trunk and 4.7, thanks.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #47 from frs.dumont at gmail dot com 2012-11-08 21:19:05 UTC --- On 11/08/2012 03:25 AM, Paolo Carlini wrote: On 11/08/2012 02:56 AM, Paolo Carlini wrote: On the other hand, the old-old code for rehash didn't use _M_growth_factor in these computations, it just literally enforced the post-conditions of the Standard. Are we sure we aren't so to speak rehashing too much? For example, when the load factor is very low and doesn't count, it looks like a current rehash(n) accomplishes the same of an old rehash(n * 2)?!? Something seems wrong, can you double check that? In any case the comments before _M_next_bkt would need fixing. ... in other terms, I really think that the only uses of _S_growth_factor should return to be inside _M_need_rehash, because that's the function called by the inserts, when the container must automatically grow the number of buckets. Elsewhere, like the constructors, rehash, should not need to know about _S_growth_factor. Paolo. I haven't yet considered the following emails but based on those good remarks I have done the attached patch. Surprisingly it seems to have a good impact on performance even if before it testsuite/performance/23_containers/insert/unordered_set.cc was showing that new implementation was better. I have also starting to adapt tests so that it's possible to check unordered performance with std or std::tr1 implementations. Can I generalize it to other tests ? If so, is it a good approach ? François
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #40 from frs.dumont at gmail dot com 2012-11-07 22:02:56 UTC --- Here is the patch to fix the redundant rehash/reserve issue. 2012-11-07 François Dumont fdum...@gcc.gnu.org PR libstdc++/54075 * include/bits/hashtable.h (_Hashtable::rehash): Reset hash policy state if no rehash. * testsuite/23_containers/unordered_set/modifiers/reserve.cc (test02): New. I had prepared and tested it in 4.7 branch but I can apply the same on trunk. Ok to commit ? If so, where ? François On 11/06/2012 10:33 PM, paolo.carlini at oracle dot com wrote: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #39 from Paolo Carlini paolo.carlini at oracle dot com 2012-11-06 21:33:57 UTC --- Ok thanks. I guess depending on the complexity of the fixes we can apply some only to mainline first and reconsider the 4_7 branch later. Please do your best to work on both issues: we just entered Stage 3 thus no new features from now on, we are all concentrated on bug fixes until the release.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #41 from Jonathan Wakely jwakely.gcc at gmail dot com 2012-11-08 00:58:55 UTC --- On 7 November 2012 22:02, François Dumont wrote: Ok to commit ? If so, where ? That patch is OK for trunk and 4.7, thanks.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #42 from Paolo Carlini paolo.carlini at oracle dot com 2012-11-08 01:56:15 UTC --- On 11/08/2012 01:58 AM, Jonathan Wakely wrote: On 7 November 2012 22:02, François Dumont wrote: Ok to commit ? If so, where ? That patch is OK for trunk and 4.7, thanks. ... I was having a look at this code - patch per se is straightforward enough and can in any case go in now - and something is puzzling me a lot: we always compute things, in _M_next_bkt etc, in terms of __grown_n, thus __n * 2, until the final _M_rehash call. On the other hand, the old-old code for rehash didn't use _M_growth_factor in these computations, it just literally enforced the post-conditions of the Standard. Are we sure we aren't so to speak rehashing too much? For example, when the load factor is very low and doesn't count, it looks like a current rehash(n) accomplishes the same of an old rehash(n * 2)?!? Something seems wrong, can you double check that? In any case the comments before _M_next_bkt would need fixing. Thanks, Paolo.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #43 from Paolo Carlini paolo.carlini at oracle dot com 2012-11-08 02:26:12 UTC --- On 11/08/2012 02:56 AM, Paolo Carlini wrote: On the other hand, the old-old code for rehash didn't use _M_growth_factor in these computations, it just literally enforced the post-conditions of the Standard. Are we sure we aren't so to speak rehashing too much? For example, when the load factor is very low and doesn't count, it looks like a current rehash(n) accomplishes the same of an old rehash(n * 2)?!? Something seems wrong, can you double check that? In any case the comments before _M_next_bkt would need fixing. ... in other terms, I really think that the only uses of _S_growth_factor should return to be inside _M_need_rehash, because that's the function called by the inserts, when the container must automatically grow the number of buckets. Elsewhere, like the constructors, rehash, should not need to know about _S_growth_factor. Paolo.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #38 from François Dumont fdumont at gcc dot gnu.org 2012-11-06 21:22:48 UTC --- Sure, I will. However I don't expect this problem to have any relation with the performance subject of this PR.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #39 from Paolo Carlini paolo.carlini at oracle dot com 2012-11-06 21:33:57 UTC --- Ok thanks. I guess depending on the complexity of the fixes we can apply some only to mainline first and reconsider the 4_7 branch later. Please do your best to work on both issues: we just entered Stage 3 thus no new features from now on, we are all concentrated on bug fixes until the release.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 Paolo Carlini paolo.carlini at oracle dot com changed: What|Removed |Added Status|RESOLVED|REOPENED CC|fdumont at gcc dot gnu.org | Resolution|FIXED | Summary|[4.7.1] unordered_map |[4.7.1] unordered_map |insert 3x slower than 4.6.2 |insert still slower than ||4.6.2 --- Comment #35 from Paolo Carlini paolo.carlini at oracle dot com 2012-11-05 12:55:09 UTC --- Ok, let's reopen this with an adjusted Summary.
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075
Lawrence tlawrence85 at gmail dot com changed:
What|Removed |Added
CC||tlawrence85 at gmail dot
||com
--- Comment #36 from Lawrence tlawrence85 at gmail dot com 2012-11-05
22:12:12 UTC ---
It seems that this commit doesn't fully fix this issue. If you call rehash
multiple times with the same size, the second call to rehash resets
_M_prev_resize to a non-zero value in _M_next_bkt(). Here is a sample program
that shows this behavior:
#include stdio.h
#include unordered_map
int main(void) {
std::unordered_mapint, int myMap;
myMap.rehash(400);
myMap.rehash(400);
unsigned long long buckets = myMap.bucket_count();
int i = 0;
while (i 20) {
myMap.insert(std::make_pair(i, 0));
++i;
if (buckets != myMap.bucket_count()) {
printf(buckets %lu - %lu\n, buckets, myMap.bucket_count());
buckets = myMap.bucket_count();
}
}
return 0;
}
(In reply to comment #13)
Author: fdumont
Date: Thu Jul 26 12:31:50 2012
New Revision: 189889
URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=189889
Log:
2012-07-26 François Dumont fdum...@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 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.
Added:
branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/reserve.cc
branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/reserve.cc
branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/reserve.cc
branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc
Modified:
branches/gcc-4_7-branch/libstdc++-v3/ChangeLog
branches/gcc-4_7-branch/libstdc++-v3/include/bits/hashtable.h
[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 --- Comment #37 from Paolo Carlini paolo.carlini at oracle dot com 2012-11-06 00:58:37 UTC --- Francois, can you please look further into this, possibly basing on the new testcase? Thanks!
