[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088 --- Comment #7 from CVS Commits --- The master branch has been updated by Jonathan Wakely : https://gcc.gnu.org/g:81eab204a56dcd8acb1ca5d7df277437ca07b51a commit r12-1162-g81eab204a56dcd8acb1ca5d7df277437ca07b51a Author: Jonathan Wakely Date: Wed Jun 2 12:33:38 2021 +0100 libstdc++: Fix tests for COW std::string [PR 96088] The expected number of allocations is different when copying COW strings. Signed-off-by: Jonathan Wakely libstdc++-v3/ChangeLog: PR libstdc++/96088 * testsuite/23_containers/unordered_map/96088.cc: Adjust expected number of allocations. * testsuite/23_containers/unordered_set/96088.cc: Likewise.
[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088 François Dumont changed: What|Removed |Added Target Milestone|--- |12.0 Resolution|--- |FIXED Status|ASSIGNED|RESOLVED --- Comment #6 from François Dumont --- Fix with this commit: https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=2c43f5ec9db163696de8691eb529df06c4999bcc libstdc++: Limit allocation on iterator insertion in Hashtable [PR 96088] When inserting into unordered_multiset or unordered_multimap first instantiate the node to store and compute the hash code from it to avoid a potential intermediate key_type instantiation. When inserting into unordered_set or unordered_map check if invoking the hash functor with container key_type is noexcept and invoking the same hash functor with key part of the iterator value_type can throw. In this case create a temporary key_type instance at Hashtable level and use it to compute the hash code. This temporary instance is moved to the final storage location if needed. libstdc++-v3/ChangeLog: PR libstdc++/96088 * include/bits/hashtable_policy.h (_Select2nd): New. (_NodeBuilder<>): New. (_ReuseOrAllocNode<>::operator()): Use variadic template args. (_AllocNode<>::operator()): Likewise. * include/bits/hashtable.h (_Hashtable<>::__node_builder_t): New. (_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const _NodeGenerator&)): New. (_Hashtable<>::_S_forward_key): New. (_Hashtable<>::_M_insert): Use latter. (_Hashtable<>::_M_insert(const_iterator, _Arg&&, const _NodeGenerator&, false_type)): Instantiate node first, compute hash code second. * testsuite/23_containers/unordered_map/96088.cc: New test. * testsuite/23_containers/unordered_multimap/96088.cc: New test. * testsuite/23_containers/unordered_multiset/96088.cc: New test. * testsuite/23_containers/unordered_set/96088.cc: New test. * testsuite/util/replacement_memory_operators.h (counter::_M_increment): New. (counter::_M_decrement): New. (counter::reset()): New.
[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088 François Dumont changed: What|Removed |Added Status|UNCONFIRMED |ASSIGNED Ever confirmed|0 |1 Last reconfirmed||2020-08-04 Assignee|unassigned at gcc dot gnu.org |fdumont at gcc dot gnu.org --- Comment #5 from François Dumont --- After further investigation the unordered containers are also suffering from a problem similar to libstdc++/87194. There are several places where we constraint the iterator value_type to be an instance of container key_type forcing the compiler to generate temporaries. I'll fix that so that the nice enhancements already proposed can indeed work.
[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088 --- Comment #4 from Jonathan Wakely --- (In reply to Marc Glisse from comment #3) > > Adding hash::operator()(string_view) is an interesting idea for the > > standard though. > > Indeed. If we want to, I think it is possible to add some overloads for when > the argument is exactly const char* or string_view, which should remain > conforming and provide a significant part of the benefits. It would probably have to be: template requires same_as> size_t operator()(T) const; otherwise it can introduce ambiguities for things convertible to both string and string_view. But that annoyance aside, it seems worth exploring.
[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088 --- Comment #3 from Marc Glisse --- (In reply to Jonathan Wakely from comment #2) > Or use unordered_map, equal_to<>> which > should perform better. Good idea. > We haven't implemented http://wg21.link/p0919r3 and http://wg21.link/p1690r1 > yet, I wonder if those would help, especially if we make the internal > helpers available pre-C++20. That could allow the range insertion to use the > heteregenous lookup, to avoid creating temporaries. I'm not sure if that > would be conforming though. Heterogeneous lookup is observably different, > and not conforming in C++17. Restricting it to a few standard types like string should not be observable. > Adding hash::operator()(string_view) is an interesting idea for the > standard though. Indeed. If we want to, I think it is possible to add some overloads for when the argument is exactly const char* or string_view, which should remain conforming and provide a significant part of the benefits.
[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088 --- Comment #2 from Jonathan Wakely --- (In reply to François Dumont from comment #1) > I'll check if we can be smarter here. A nice improvement would be to change > std::hash operator signature to: > > size_t > operator()(const string_view& __str) const noexcept > > but that's a Standard modification. Or use unordered_map, equal_to<>> which should perform better. We haven't implemented http://wg21.link/p0919r3 and http://wg21.link/p1690r1 yet, I wonder if those would help, especially if we make the internal helpers available pre-C++20. That could allow the range insertion to use the heteregenous lookup, to avoid creating temporaries. I'm not sure if that would be conforming though. Heterogeneous lookup is observably different, and not conforming in C++17. Adding hash::operator()(string_view) is an interesting idea for the standard though.
[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088 --- Comment #1 from François Dumont --- The core issue here is that unordered_map key type is std::string while you insert const char* which explains the temporary. In f2 you use insert(Pair&&) method so a temporary is generated but then moved into the container. In f1 we try to check for insertion before generating the value_type and to do so we use hash that generates an additional temporary. I'll check if we can be smarter here. A nice improvement would be to change std::hash operator signature to: size_t operator()(const string_view& __str) const noexcept but that's a Standard modification.
