[PATCH] libstdc++/91223 Improve unordered containers == operator

Jonathan Wakely jwakely@redhat.com
Wed Jan 15 22:46:00 GMT 2020


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.

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



More information about the Libstdc++ mailing list