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

François Dumont frs.dumont@gmail.com
Thu Jan 16 13:26:00 GMT 2020


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 !



More information about the Libstdc++ mailing list