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

[Jonathan Wakely]

On 13/01/20 22:41 +0100, François Dumont wrote:
>On 1/10/20 11:01 PM, Jonathan Wakely wrote:
>>On 10/01/20 18:54 +0100, François Dumont wrote:
>>>Hi
>>>
>>>    Here is my attempt to improve == operator.
>>>
>>>    There is a small optimization for the std::unordered_mutiXXX 
>>>containers but the main enhancement rely on some partial template 
>>>specialization of the _Equality type. I limit it to usage of 
>>>unordered containers with std::equal_to to be sure that the 
>>>container _Equal functor is like the key type ==.
>>
>>I think we can assume that for any _Equal, not just std::equal_to:
>>http://eel.is/c++draft/unord.req#12.sentence-5
>>
>>However ...
>
>Ok but...
>
>>
>>>    Do I need to also consider user partial template 
>>>specialization of std::equal_to ? It is a well know bad practice 
>>>so I hope the Standard says that such a partial specialization 
>>>leads to undefined behavior.
>>
>>It's certainly not undefined to specialize equal_to, and I'm not sure
>>how to make your optimisations valid in that case.
>
>This proposal is indeed invalid if you use a std::equal_to partial 
>specialization, this is why I asked.
>
>>
>>Consider:
>>
>>struct X
>>{
>>  int i;
>>  int rounded() const { return i - (i % 10); }
>>  bool operator==(X x) const { return i == x.i; }
>>};
>>
>>template<> struct std::equal_to<X>
>>{
>>  bool operator()(X l, X r) const
>>  { return l.rounded() == r.rounded(); }
>>};
>>
>>template<> std::hash<X>
>>{
>>  bool operator()(X x) const { return hash<int>()(x.rounded()); }
>>};
>>
>>std::unordered_multiset<X> u{ X{10}, X{11}, X{12} };
>>std::unordered_multiset<X> v{ X{15}, X{16}, X{17} };
>>bool b1 = u == v;
>>bool b2 = std::is_permutation(u.begin(), u.end(), v.begin());
>>assert(b1 == b2);
>>
>>I think the last new specialization in your patch would be used for
>>this case, and because __x_count == v.count(*u.begin()) it will say
>>they're equal. But the is_permutation call says they're not.
>>
>>So I think the assertion would fail, but the standard says it should
>>pass. Am I mistaken?
>
>I agree, it would fail and the Standard says it should pass.
>
>So here is a new proposal. For the unique keys case I think we are 
>good, I do not see any other optimization.
>
>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.
>
>In order to detect that _Equal is the std::equal_to from 
>stl_function.h it would be great to have something like a 
>__builtin_is_system returning true for types defined in system 
>headers. For now I try to propose something similar without compiler 
>help.

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.