[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
Andrew Gallagher andrewjcg at gmail dot com changed:
What|Removed |Added
CC||andrewjcg at gmail dot com
--- Comment #35 from Andrew Gallagher andrewjcg at gmail dot com 2012-07-24
21:45:55 UTC ---
It appears that http://gcc.gnu.org/viewcvs?root=gccview=revrev=181677 has
caused some performance regression in gcc-4.7 (or I am missing something). The
following example runs 3 times faster with gcc-4.6 than with gcc-4.7:
#include unordered_map
using namespace std;
int main() {
unordered_mapint, int m;
//m.rehash(1000);
for (int i = 0; i 1000; i++) {
m[i] = i;
}
}
Looking at a profile generated by google-perftools, it seems that most of the
time is spent in _M_rehash with gcc-4.7, as the newly rehashed size is
considerably smaller than in gcc-4.6 (perhaps due to the removal of
_M_growth_factor?), therefore it gets called a lot more often. Is this
expected behavior?
Reserve/rehash also appears to be broken. If the 'rehash' line is uncommented
in the example above, then a subsequent insert hits the check against
_M_prev_resize in _M_need_rehash and rehashes the bucket size back to a small
value.
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975 --- Comment #36 from Jonathan Wakely redi at gcc dot gnu.org 2012-07-24 21:51:23 UTC --- See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975 Paolo Carlini paolo.carlini at oracle dot com changed: What|Removed |Added Status|ASSIGNED|RESOLVED Resolution||FIXED Target Milestone|4.5.3 |4.7.0 --- Comment #34 from Paolo Carlini paolo.carlini at oracle dot com 2011-11-28 22:10:00 UTC --- Fixed for 4.7.0.
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975 --- Comment #33 from François Dumont fdumont at gcc dot gnu.org 2011-11-23 20:30:25 UTC --- Author: fdumont Date: Wed Nov 23 20:30:18 2011 New Revision: 181677 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=181677 Log: 2011-11-23 François Dumont fdum...@gcc.gnu.org PR libstdc++/41975 * include/bits/hashtable.h (_Hashtable): Major data model modification to limit performance impact of empty buckets in erase(iterator) implementation. * include/bits/hashtable_policy.h (_Hashtable_iterator, _Hashtable_const_iterator): Remove not used anymore. * include/bits/hashtable_policy.h (_Prime_rehash_policy): Remove _M_grow_factor, just use natural evolution of prime numbers. Add _M_prev_size to know when the number of buckets can be reduced. * include/bits/unordered_set.h (__unordered_set, __unordered_multiset), unordered_map.h (__unordered_map, __unordered_multimap): Change default value of cache hash code template parameter, false for integral types with noexcept hash functor, true otherwise. * include/debug/unordered_map, unordered_set: Adapt transformation from iterator/const_iterator to respectively local_iterator/const_local_iterator. * testsuite/performance/23_containers/copy_construct/unordered_set.cc: New. * testsuite/23_containers/unordered_set/instantiation_neg.cc: New. * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: New. * testsuite/23_containers/unordered_multiset/cons/copy.cc: New. * testsuite/23_containers/unordered_multiset/erase/1.cc, 24061-multiset.cc: Add checks on the number of bucket elements. * testsuite/23_containers/unordered_multiset/insert/multiset_range.cc, multiset_single.cc, multiset_single_move.cc: Likewise. Added: trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/copy.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc trunk/libstdc++-v3/testsuite/performance/23_containers/copy_construct/unordered_set.cc Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/hashtable.h trunk/libstdc++-v3/include/bits/hashtable_policy.h trunk/libstdc++-v3/include/bits/unordered_map.h trunk/libstdc++-v3/include/bits/unordered_set.h trunk/libstdc++-v3/include/debug/unordered_map trunk/libstdc++-v3/include/debug/unordered_set trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/24061-multiset.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_range.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_single.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_single_move.cc
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975 Richard Guenther rguenth at gcc dot gnu.org changed: What|Removed |Added Target Milestone|4.5.2 |4.5.3 --- Comment #32 from Richard Guenther rguenth at gcc dot gnu.org 2010-12-16 13:03:33 UTC --- GCC 4.5.2 is being released, adjusting target milestone.
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975 --- Comment #31 from Joaquín M López Muñoz joaquin at tid dot es 2010-10-06 11:10:12 UTC --- Paolo, I've read the minutes and seems no strong consensus was reached. I think it'd be useful if the issue can be reopened, at least for informative purposes, so that the committe specify whether it's in the spirit of the standard to allow low memory (singly-linked, one word per node) implementations, and if so what the likely implementations are (I understand this is Pablo's third approach). If this is the case the FCD has to be changed so as to allow erase() to throw. Otherwise implementors will know we have to resort to doubly-linked solutions.
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #30 from paolo dot carlini at oracle dot com 2010-09-21 17:55 --- More correctly (in the meanwhile went through a exchange at the beginning of this year), Howard stores the hash, which boils down to a memory requirement similar to that of the traditional doubly linked list scheme per Dinkum in the limit of high load factor, for small load factor is better because can use only one pointer instead of two for each bucket in the bucket list. All in all, if the requirements of throwing hash + erase complexity are combined, I don't think anything with a memory use similar to that of the singly linked schemes is possible. Joaquin, I think Matt would be in favor of a motion asking a re-opening of the issue in Batavia, what do you think? -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #27 from paolo dot carlini at oracle dot com 2010-09-20 17:23 --- Unless somebody posts here over the next two/three days or so *concrete* ideas of a different sort, I'm going to simply work on a doubly linked list solution, along the lines of the section iterator here: http://www.drdobbs.com/184403822 Nothing new, therefore. All the operations on iterators will become faster, not just computing the iterator returned by erase, on the other hand two pointers instead of one will be used for each element. -- paolo dot carlini at oracle dot com changed: What|Removed |Added CC||joaquin at tid dot es http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #28 from joaquin at tid dot es 2010-09-20 17:34 --- US 113, ES 2, US 118 / Issue 579 have been closed as NAD, thus let's figure out how best obtain O(1) in our implementation... Do you have a rationale for the closing of this NB comments? N3133 shows 579 unchanged. I was told that someone reported about the existence of a O(1) singly-linked list implementation in Rapperswil, but I don't have additional details. I'd wait to get the full picture before going to a doubly-linked list: the commitee had full info on the issue, so if they closed 579 as NAD they are supposed to be able to provide a rationale. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #29 from paolo dot carlini at oracle dot com 2010-09-20 17:41 --- I'm not aware of any singly linked list implementation, to be honest. I know that Dinkumware already uses doubly, and, if I'm not wrong, Howard just moved to it. I'll send you privately the rationale I have from the minutes, I'm also asking again Matt whether he has anything else to suggest, but frankly I'm rather fed up with this issue, I mean to implement something that *works*, is *conforming* and then test it in the field. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #26 from paolo dot carlini at oracle dot com 2010-08-08 15:03 --- US 113, ES 2, US 118 / Issue 579 have been closed as NAD, thus let's figure out how best obtain O(1) in our implementation... -- paolo dot carlini at oracle dot com changed: What|Removed |Added AssignedTo|unassigned at gcc dot gnu |paolo dot carlini at oracle |dot org |dot com Status|NEW |ASSIGNED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #25 from rguenth at gcc dot gnu dot org 2010-07-31 09:29 --- GCC 4.5.1 is being released, adjusting target milestone. -- rguenth at gcc dot gnu dot org changed: What|Removed |Added Target Milestone|4.5.1 |4.5.2 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #24 from rguenth at gcc dot gnu dot org 2010-04-06 11:20 --- GCC 4.5.0 is being released. Deferring to 4.5.1. -- rguenth at gcc dot gnu dot org changed: What|Removed |Added Target Milestone|4.5.0 |4.5.1 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #23 from paolo dot carlini at oracle dot com 2010-03-10 16:36 --- At the end of a further discussion today, apparently there is a strong consensus to add additional signatures returning void, Boost-style. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #17 from jzwinck at gmail dot com 2010-03-09 18:40 --- (In reply to comment #16) there is evidence (eg, the Dinkumware implementation) that returning an iterator doesn't necessarily impact performance. The GCC implementation does have poor performance. Why not leave the (performance-improving) patch in place until someone actually comes up with an implementation for GCC which does perform well? As it stands, users are left in a strange situation, being told that the performance (in GCC) is poor, but that it has to be this way because of Dinkumware (which, it's claimed, is fast). Doesn't this only serve to drive users away from GCC's implementation? To be clear, I am very much in favor of any solution which provides approximately optimal performance. Boost, for example, chose to implement a new method called erase_return_void for users who care about performance of this operation--a workaround, but with emphasis on work. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #18 from paolo dot carlini at oracle dot com 2010-03-09 18:49 --- Because would be non-conforming. In case my previous message was not clear enough, in C++1x erase will return *iterator*. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #19 from sjackman at gmail dot com 2010-03-09 19:15 --- How does the Dinkumware implementation avoid the performance hit of erase returning an iterator? -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #20 from paolo dot carlini at oracle dot com 2010-03-09 19:19 --- Nobody knows the gory details, but Plauger said that people can look into the headers of the last beta of Visual Studio... Knowledgeable people are under the impression they are using a different, double linked, implementation for the hash table, which has its own problem, still, at this point it's pretty clear that in C++1x erase will return an iterator and we have to live with that. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
-- paolo dot carlini at oracle dot com changed: What|Removed |Added AssignedTo|paolo dot carlini at oracle |unassigned at gcc dot gnu |dot com |dot org Status|REOPENED|NEW http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #21 from jzwinck at gmail dot com 2010-03-09 19:55 --- (In reply to comment #18) Because would be non-conforming. In case my previous message was not clear enough, in C++1x erase will return *iterator*. The Boost approach is still an option for GCC: let the standards mandate a suboptimal interface if they must, but provide an alternative (the one Boost calls erase_return_void). From where I sit at least, it doesn't seem infeasible for GCC to go a little bit beyond the standard in this case (again, as Boost have already elected to do). -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #22 from paolo dot carlini at oracle dot com 2010-03-09 20:15 --- As a last resort, we can imagine doing that. Would be the first case, however, to my best knowledge, that we provide a different interface controlled by a macro this way. Much better would be, and has also been mentioned today, providing two different implementations, both returning iterator and only different as regards the internal details. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #15 from paolo at gcc dot gnu dot org 2010-03-09 01:56 --- Subject: Bug 41975 Author: paolo Date: Tue Mar 9 01:56:42 2010 New Revision: 157300 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=157300 Log: 2010-03-08 Paolo Carlini paolo.carl...@oracle.com Revert: 2010-02-11 Paolo Carlini paolo.carl...@oracle.com PR libstdc++/41975, DR 579 * include/bits/hashtable.h (_Hashtable::_M_erase_node): Remove. (erase(const_iterator), erase(const_iterator, const_iterator)): Change return type to void. * include/debug/unordered_map: Adjust. * include/debug/unordered_set: Likewise. * testsuite/util/exception/safety.h: Likewise. * testsuite/23_containers/unordered_map/erase/1.cc: Likewise. * testsuite/23_containers/unordered_map/erase/24061-map.cc: Likewise. * testsuite/23_containers/unordered_set/erase/1.cc: Likewise. * testsuite/23_containers/unordered_set/erase/24061-map.cc: Likewise. * testsuite/23_containers/unordered_multimap/erase/1.cc: Likewise. * testsuite/23_containers/unordered_multimap/erase/24061-map.cc: Likewise. * testsuite/23_containers/unordered_multiset/erase/1.cc: Likewise. * testsuite/23_containers/unordered_multiset/erase/24061-map.cc: Likewise. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/hashtable.h trunk/libstdc++-v3/include/debug/unordered_map trunk/libstdc++-v3/include/debug/unordered_set trunk/libstdc++-v3/testsuite/23_containers/unordered_map/erase/1.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_map/erase/24061-map.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/1.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/24061-multimap.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/24061-multiset.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_set/erase/1.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_set/erase/24061-set.cc trunk/libstdc++-v3/testsuite/util/exception/safety.h -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #16 from paolo dot carlini at oracle dot com 2010-03-09 01:59 --- I reverted my changes and re-opened the PR: DR 579 is being resolved as NAD, because there is evidence (eg, the Dinkumware implementation) that returning an iterator doesn't necessarily impact performance. -- paolo dot carlini at oracle dot com changed: What|Removed |Added Status|RESOLVED|REOPENED Resolution|FIXED | http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
-- paolo dot carlini at oracle dot com changed: What|Removed |Added AssignedTo|unassigned at gcc dot gnu |paolo dot carlini at oracle |dot org |dot com Status|SUSPENDED |ASSIGNED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #13 from paolo at gcc dot gnu dot org 2010-02-11 18:11 --- Subject: Bug 41975 Author: paolo Date: Thu Feb 11 18:11:01 2010 New Revision: 156705 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=156705 Log: 2010-02-11 Paolo Carlini paolo.carl...@oracle.com PR libstdc++/41975, DR 579 * include/bits/hashtable.h (_Hashtable::_M_erase_node): Remove. (erase(const_iterator), erase(const_iterator, const_iterator)): Change return type to void. * include/debug/unordered_map: Adjust. * include/debug/unordered_set: Likewise. * testsuite/util/exception/safety.h: Likewise. * testsuite/23_containers/unordered_map/erase/1.cc: Likewise. * testsuite/23_containers/unordered_map/erase/24061-map.cc: Likewise. * testsuite/23_containers/unordered_set/erase/1.cc: Likewise. * testsuite/23_containers/unordered_set/erase/24061-map.cc: Likewise. * testsuite/23_containers/unordered_multimap/erase/1.cc: Likewise. * testsuite/23_containers/unordered_multimap/erase/24061-map.cc: Likewise. * testsuite/23_containers/unordered_multiset/erase/1.cc: Likewise. * testsuite/23_containers/unordered_multiset/erase/24061-map.cc: Likewise. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/hashtable.h trunk/libstdc++-v3/include/debug/unordered_map trunk/libstdc++-v3/include/debug/unordered_set trunk/libstdc++-v3/testsuite/23_containers/unordered_map/erase/1.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_map/erase/24061-map.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/1.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/24061-multimap.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/24061-multiset.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_set/erase/1.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_set/erase/24061-set.cc trunk/libstdc++-v3/testsuite/util/exception/safety.h -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #14 from paolo dot carlini at oracle dot com 2010-02-11 18:13 --- Done. -- paolo dot carlini at oracle dot com changed: What|Removed |Added Status|ASSIGNED|RESOLVED Resolution||FIXED Target Milestone|--- |4.5.0 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #12 from paolo dot carlini at oracle dot com 2010-02-09 16:09 --- Looks like there is a strong consensus in the LWG for the proposed resolution, that is returning void, and LWG 579 now is [Tentatively Ready]. We could even implement it in time for 4.5.0, but, if I'm not mistaken, the iterator range case is not trivial, let's reconsider that in a few days... -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty
--- Comment #11 from paolo dot carlini at oracle dot com 2009-12-22 10:02 --- Relevant DR reopened: http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579 Next, we should provide detailed wording... -- paolo dot carlini at oracle dot com changed: What|Removed |Added Status|NEW |SUSPENDED Summary|[C++0x] unordered_set::erase|[C++0x] [DR579] |performs worse when nearly |unordered_set::erase |empty |performs worse when nearly ||empty http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975
