Small optimization of vector (or other container comparisons)

[Moritz Klammler]

On 11/17/20 2:31 PM, Jonathan Wakely via Libstdc++ wrote:
> On 16/11/20 20:08 +0100, Theodore Papadopoulo wrote:
>> Â Â Â  Hi,
>>
>> Â Â Â  Sorry if this is a naive question...
>>
>> I wonder whether it will be legal and/or interesting to modify vector
>> comparison so that it returns early when the vectors have the same
>> address
>> ie replace
>>
>> template<typename _Tp, typename _Alloc>
>> inline bool
>> Â Â Â  operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp,
>> _Alloc>& __y)
>> Â Â Â  { return (__x.size() == __y.size()
>> Â Â Â  Â Â Â Â Â  && std::equal(__x.begin(), __x.end(), __y.begin())); }
>>
>> by
>>
>> template<typename _Tp, typename _Alloc>
>> inline bool
>> Â Â Â  operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp,
>> _Alloc>& __y)
>> Â Â Â  { return (&__x==&__y) || (__x.size() == __y.size()
>> Â Â Â  Â Â Â Â Â  && std::equal(__x.begin(), __x.end(), __y.begin()))); }
> 
> N.B. this has to be std::addressof(__x) == std::addressof(__y) (but
> that's only available for C++11 and later, so it has to be
> __builtin_addressof), and should probably give a branch prediction
> hint.
> 
> Â Â Â  {
>       if (__builtin_expect(__builtin_addressof(__x)
>                            == __builtin_addressof(__y), false))
>         return true;
>       return (__x.size() == __y.size()
> Â Â Â  Â Â Â Â Â  && std::equal(__x.begin(), __x.end(), __y.begin())));
>     }

Maybe this is not a valid example but the current observed behavior is
that the assertion will pass and this change would make it fail, no?

#include <cassert>
#include <cmath>
#include <vector>

int main()
{
    const auto problematic = std::vector{1.0f, NAN, 3.0f};
    assert(problematic != problematic);
}

At least I used to (maybe incorrectly) assume that this behavior can be
relied upon.

Of course, there are types like integers, pointers and certain standard
library types like std::string which we know not to have such
problematic behavior as floating-point types do (and arbitrary
user-defined types might) so the optimization could be enabled selectively.