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

[François Dumont]

On 1/16/20 5:01 PM, Jonathan Wakely wrote:
> On 16/01/20 13:25 +0000, Jonathan Wakely wrote:
>> On 16/01/20 07:42 +0100, François Dumont wrote:
>>> 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.
>>
>> No problem, I can do that.
>
> Your patch is now committed to trunk. Thanks for the major
> improvement.
>
> I had a look at std::is_permutation and I think we can make some
> simplifications to the 4-argument overload, and we can share most of
> the code between the 3-arg and 4-arg overloads (once they've confirmed
> the lengths are the same they do exactly the same thing). See the
> attached patch. This should probably wait for stage1 though.
>
> I also wanted to add some comments to the _Equality::_M_equal
> specialiation for unordered_multimap/multiset to explain what the code
> was doing, and had some more ideas. See patch again.
>
> It looks like this loop can potentially visit every element of
> __other, instead of stopping at the end of the bucket:
>
> Â  typename __hashtable::const_iterator __ity(__y_n);
> Â  for (auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end)
> Â Â Â  if (--__x_count == 0)
> Â Â Â Â Â  break;
>
> Consider a case like this:
>
> unordered_multiset<int> a{1, 2, 3, 4};
> for (int i = 0; i <10000; ++i)
> Â  a.insert(1);
> unordered_multiset<int> b{1, 2, 3, 4};
> for (int i = 0; i <10000; ++i)
> Â  b.insert(2);
>
> When doing a == b we'll find 10000 elements in a with key '1',
> and find one element in b with that key. But then we iterate through
> every element in b after that one, even though they have different
> keys and are probably in different buckets.
>
> Instead of just iterating from __ity to __other.end(), can we use a
> local iterator so we stop at the end of the bucket?
>
> This seems to make the PR91263 example *very* slightly slower, but
> makes the example above significantly faster.
>
> What do you think?
>
>
The hashtable implementation is doing its best to provide good 
performances as long as the user does its part of the job. Mainly 
provide a good hash to distrubute elements smoothly throughout the 
buckets. But also avoid this kind of unordered_multiset.

If you check if you don't move out of bucket you'll have to pay for the 
bucket computation (subject of PR 68303) or perform a redundant _Equal 
to check when we left the range of equivalent elements like it used to 
be done. Current implementation leave it to the std::is_permutation to 
do that which in normal situation will be better I think.