[Bug libstdc++/58153] New: unordered_multimap::erase(iterator) is not constant-time when many entries have the same key
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58153 Bug ID: 58153 Summary: unordered_multimap::erase(iterator) is not constant-time when many entries have the same key Product: gcc Version: 4.8.1 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ Assignee: unassigned at gcc dot gnu.org Reporter: temporal at gmail dot com It appears that if an unordered_multimap has k entries with the same key, then erase(iter) for any of those entries is O(k) rather than constant-time. The problem is that _Hashtable::erase() searches through all nodes in the bucket looking for the one previous to the one being removed. This is reasonable for unordered_map, where buckets are expected to have no more than a couple entries. But it is surprising for unordered_multimap, whose whole purpose is to support multiple entries with the same key (and therefore the same bucket). I do not know exactly what the standard requires here, but all of the references I can find claim that erase(iter) should be average-time O(1), and none of them suggest that having a large number of entries with the same key should cause trouble. FWIW, it looks like libc++ has the same behavior. Maybe my expectations were wrong, and unordered_multimap was never meant to contain more than a couple entries per key?
[Bug libstdc++/58153] unordered_multimap::erase(iterator) is not constant-time when many entries have the same key
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58153 --- Comment #2 from Kenton Varda --- > The standard says average case O(1), worst case O(a.size()), so if every > element in the container has the same key then it's O(n). I'm not sure that follows. Yes, the standard says "worst case O(n)", but why should expect worst-case performance if I have lots of entries with the same key? In the absence of explicit language to the contrary, it seems entirely reasonable to expect unordered_multimap to perform similarly to unordered_map>, where in fact it turns out to be more like unordered_map>. I guess the real bug here is with all of the C++ reference sites that fail to mention this rather large caveat... that unordered_multimap supports duplicate keys, but only as long as there aren't "too many" duplicates. I think part of the problem might be that people are thinking: "Well, duh, hash maps perform poorly if lots of keys have the same hash!". But I don't think that's quite the same thing. Unique hash maps perform poorly in that case because it's necessary to linearly scan through many entries to find the one that matches the key. But when looking for a key in a multimap, you stop at the first match, so even if there are lots of entries with the same key, lookup can still be O(1). So, I don't think it's intrinsically true that a hashtable-based multimap should perform badly when many entries have the same key.
[Bug c++/58192] New: G++ emits incorrect code when passing enum classes as function parameters
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58192 Bug ID: 58192 Summary: G++ emits incorrect code when passing enum classes as function parameters Product: gcc Version: 4.8.1 Status: UNCONFIRMED Severity: normal Priority: P3 Component: c++ Assignee: unassigned at gcc dot gnu.org Reporter: temporal at gmail dot com Demonstration attached. It repros with g++ 4.8.1 (tested on Ubuntu and Cygwin). I think I saw similar problems with g++ 4.7.3, but this particular test case does not seem to repro with it.
[Bug c++/58192] G++ emits incorrect code when passing enum classes as function parameters
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58192 --- Comment #1 from Kenton Varda --- Created attachment 30672 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30672&action=edit Demonstration of enum class passing bug
[Bug c++/58192] G++ emits incorrect code when passing enum classes as function parameters
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58192 --- Comment #2 from Kenton Varda --- Note: Both the Ubuntu and Cygwin systems were x86_64. I don't know if the problem occurs in 32-bit mode.
[Bug c++/58192] G++ emits incorrect code when passing enum classes as function parameters
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58192 Kenton Varda changed: What|Removed |Added Attachment #30672|0 |1 is obsolete|| --- Comment #3 from Kenton Varda --- Created attachment 30673 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30673&action=edit Demonstration of enum class passing bug (v2) The first version of my demo was doing slightly weird things with unions in main(). This was vestigial code from my attempts to narrow down the bug, but wasn't actually necessary to trigger it. So, I simplified it.
[Bug libstdc++/58153] unordered_multimap::erase(iterator) is not constant-time when many entries have the same key
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58153 --- Comment #4 from Kenton Varda --- > This report entry made me wonder why iterators could not just be > pointing to the node just before the one containing the pointed to value. That's a neat idea. I think there is an obscure issue, though. If I have an iterator pointing at item N, and then I (separately) erase item N - 1, what happens to my iterator? But you bring up another, simpler point: why not just have an erase_after() method like forward_list does? That would suit my use case (although at this point I've rewritten it to do something different).
[Bug libstdc++/58153] unordered_multimap::erase(iterator) is not constant-time when many entries have the same key
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58153 --- Comment #6 from Kenton Varda --- Yep, I realize that erase_after would need to be added to the standard. I was just speculating that it may be something the standard committee should consider. I've long since solved my problem by changing my approach, so this bug is just meant to raise awareness. Feel free to ignore it if you don't think there's anything to be done.
[Bug c++/33799] Return value's destructor not executed when a local variable's destructor throws
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33799 Kenton Varda changed: What|Removed |Added CC||temporal at gmail dot com --- Comment #5 from Kenton Varda --- It's now 2013 and this issue is giving me memory leaks in real code. Will it ever be fixed?
[Bug c++/33799] Return value's destructor not executed when a local variable's destructor throws
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33799 --- Comment #7 from Kenton Varda --- > It's now 2013 so the sensible thing to do is not return by value > if your destructor can throw. That actually sounds like a pretty difficult rule to follow, unless you either ban throwing destructors altogether or ban returning by value altogether. The don't-throw-from-destructors rule is, of course, popular, but not universally agreed upon. I don't think this bug is the right place to debate it (maybe try http://goo.gl/haB5nm), but I would hope that GCC wouldn't refuse to fix a bug simply because they disagree with the coding style that triggers that bug. > FWIW Clang also behaves the same as G++ and Intel, Yes, I noticed, and Clang has also had a bug filed against them which has languished for years. Nevertheless, the behavior is wrong. > and of course calls std::terminate() in C++11 mode. Unless the destructor has noexcept(false).
[Bug c++/59426] New: __has_trivial_{copy/assign} behavior differs from documentation
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59426
Bug ID: 59426
Summary: __has_trivial_{copy/assign} behavior differs from
documentation
Product: gcc
Version: 4.8.1
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c++
Assignee: unassigned at gcc dot gnu.org
Reporter: temporal at gmail dot com
Consider this struct with deleted copy/assignment:
struct S {
S(const S&) = delete;
S& operator=(const S&) = delete;
};
GCC's __has_trivial_{copy,assign}() intrinsics return false for this type.
This is a useful answer, but appears to disagree with the documentation:
http://gcc.gnu.org/onlinedocs/gcc/Type-Traits.html
"__has_trivial_copy(type): If __is_pod (type) is true or type is a reference
type then the trait is true, else if type is a cv class or union type with a
trivial copy constructor ([class.copy]) then the trait is true, else it is
false. Requires: type shall be a complete type, (possibly cv-qualified) void,
or an array of unknown bound."
Technically, according to [class.copy], a deleted copy constructor is "trivial"
(because it is not user-provided, and none of the other exceptions apply). A
similar argument applies to assignment. Clang has chosen to implement these
intrinsics according to the docs rather than according to GCC's actual
behavior, and thus both return true for S. To avoid confusion, GCC should
update either its documentation or its implementation so that the two match.
Apparently, other compilers (Embarcadero, MSVC) implement these intrinsics as
well. I do not have access to them to test their behavior in this case.
(I originally filed a bug against Clang:
http://llvm.org/bugs/show_bug.cgi?id=18185 )
