On 1/15/20 10:52 PM, Jonathan Wakely wrote:
On 15/01/20 21:48 +0000, Jonathan Wakely wrote:
On 14/01/20 22:25 +0100, François Dumont wrote:
On 1/13/20 10:53 PM, Jonathan Wakely wrote:
On 13/01/20 22:41 +0100, François Dumont wrote:
For the multi-keys we could still avoid redundant comparisons when
_Equal is just doing == on the key type. On unordered_multiset we
could just avoids the call to is_permuation and on the
unordered_multimap we could check the is_permutation only on the
associated value rather than on the std::pair.
I don't think that's necessary, or helpful.
The idea of https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is
that you shouldn't be using _Equal at all, and therefore it doesn't
matter whether it's std::equal_to or not.
And it was indeed possible.
Nice!
PR libstdc++/91223
* include/bits/hashtable.h (_Hashtable<>): Make _Equality<> friend.
* include/bits/hashtable_policy.h: Include <bits/stl_algo.h>.
(_Equality_base): Remove.
(_Equality<>::_M_equal): Review implementation. Use
std::is_permutation.
* testsuite/23_containers/unordered_multiset/operators/1.cc
(Hash, Equal, test02, test03): New.
* testsuite/23_containers/unordered_set/operators/1.cc
(Hash, Equal, test02, test03): New.
Tested under Linux x86_64.
Ok to commit ?
Yes, OK for trunk (we're in stage4 but your patch was posted in stage3
and fixes a pretty nasty performance bug, so is OK now).
N.B. GCC has moved to Git instead of Subversion. If you don't have Git
access set up let me know and I can commit the patch for you.
I haven't done the move yet and won't be able to do it before the
week-end. So please proceed to the commit for me, thanks.
P.S. some performance numbers using the code in the bug report
(calling Nested(n+1) and Nested(n) where n is the number of levels
shown) ...
Before:
10 levels of nesting, 0.000090 seconds
20 levels of nesting, 0.082400 seconds
22 levels of nesting, 0.285758 seconds
24 levels of nesting, 1.146782 seconds
26 levels of nesting, 4.659524 seconds
28 levels of nesting, 17.739022 seconds
30 levels of nesting, 76.288977 seconds
real 1m40.204s
user 1m40.039s
sys 0m0.005s
After:
10 levels of nesting, 0.000001 seconds
20 levels of nesting, 0.000001 seconds
22 levels of nesting, 0.000001 seconds
24 levels of nesting, 0.000001 seconds
26 levels of nesting, 0.000001 seconds
28 levels of nesting, 0.000001 seconds
30 levels of nesting, 0.000001 seconds
20000 levels of nesting, 0.002905 seconds
real 0m0.002s
user 0m0.001s
sys 0m0.001s
Very nice indeed !
