Small optimization of vector (or other container comparisons)

[Jonathan Wakely]

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())));
     }

Another option would be to change std::equal so that it returns treue
if the itertors to the beginning of the sequences are equal. That
needs to be done carefully though, because comparing iterators to
distinct containers is undefined. We could do it for vector::iterator
and other std::CONTAINER iterators by extracting a pointer and then
comparing pointers.

>Of course, the exact gain depends on the ratio of same vector vs 
>different vector comparisons and of the actual size of
>the vectors, but it seems to add little extra cost and the address 
>test may even also sometimes be removed by the compiler.

Yes, I don't have enough information to judge how often it will
actually be beneficial.

My guess is that for the vast majority of comparisons, the two
operands are different objects. But without realistic benchmarks I
would be concerned about making the change.

>Obviously, it is always possible for a user to do it by itself, but 
>integrating it is probably easier for the average user.....

But if we leave it to users, they can decide to do it when they know
that comparing the vector to itself is a possibility. If we do it in
the library, they can't *not* do it even if they know it's not a
possibility.

You can always use a custom comparison function if you know it's a
possibility and measurement shows it benefits your use case, and then
you can use that for things like std::map<std::vector<...>, ...> or
std::find_if.