Why does GCC copy object for each comparison in `std::ranges::max`?

Question

Consider the following example (Godbolt):

#include <vector>
#include <iostream>
#include <ranges>
#include <algorithm>

struct A
{
    A() {}
    A( const A& ) { std::cout << "Copy\n"; }
    A( A&& ) noexcept { std::cout << "Move\n"; }

    A& operator=(const A&) { std::cout << "Copy assigned\n"; return *this; }
    A& operator=( A&& ) noexcept { std::cout << "Move assigned\n"; return *this; }

    int x = 10;
};

int main()
{
    std::vector<A> vec( 10 );
    std::cout << "Init\n";
    std::cout << std::ranges::max( vec, [] ( const auto& a, const auto& b ) { std::cout << "cmp" << std::endl; return a.x < b.x; } ).x;
}

This program compiled with GCC 13.2 (even with -O3 optimization turned on) produces the following output:

Init
Copy
Copy
cmp
Copy
cmp
Copy
cmp
Copy
cmp
Copy
cmp
Copy
cmp
Copy
cmp
Copy
cmp
Copy
cmp
10

But compiled with Clang 17 (with -stdlib=libc++ and any optimization level), it performs no copying at all (except for the returned value, as I understand it):

Init
cmp
cmp
cmp
cmp
cmp
cmp
cmp
cmp
cmp
Copy
10

If A has a costly copy-constructor, this difference will drastically decrease performance.

Is there a reason why GCC has this implementation of std::ranges::max or is it a bug?

Answer 1

It's, what I presume, a "bug" in the gcc implementation and I wrote a bugreport.

LLVM has two versions inside the operator() overload being used:

auto __first = std::ranges::begin(__r);
auto __last = std::ranges::end(__r);

_LIBCPP_ASSERT(__first != __last, "range must contain at least one element");

if constexpr (std::ranges::forward_range<_Rp>) {
    // MY COMMENT: This is what's actually being used:

    auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) {
        return std::invoke(__comp, __rhs, __lhs);
    };
    return *std::ranges::min_element(std::move(__first),
                                        std::move(__last),
                                        __comp_lhs_rhs_swapped, __proj);
} else {
    std::ranges::range_value_t<_Rp> __result = *__first;
    while (++__first != __last) {
        if (std::invoke(__comp, std::invoke(__proj, __result),
                                std::invoke(__proj, *__first)))
            __result = *__first;
    }
    return __result;
}

.. but it doesn't matter if I disable the version currently being used and instead use the while loop. It still doesn't copy.

Now for the operator() overload in GCC's case:

auto __first = std::ranges::begin(__r);
auto __last = std::ranges::end(__r);

__glibcxx_assert(__first != __last);

auto __result = *__first;        
while (++__first != __last) {
    auto __tmp = *__first;
    if (std::__invoke(__comp, std::__invoke(__proj, __result),
                              std::__invoke(__proj, __tmp)))
        __result = std::move(__tmp);
}
return __result;

The copy is here:

auto __tmp = *__first;

I assume it should be:

auto& __tmp = *__first;

because with that change, it doesn't copy anymore.

Note: I've added std:: and std::ranges:: in a couple of places to be able to use the algorithms outside their natural habitat which is inside the standard library implementations.

---

Update

The bug is now confirmed. Jonathan Wakely also replied:

[me] auto& __tmp = *__first;

[JW] That won't compile for a move_iterator or a proxy reference. I think auto&& would be OK.

[me] ...or just supplying *__first to std::__invoke

[JW] I think that would be OK too.

So, if his initial assessment is correct, it should be a low hanging fruit for someone to pick and we can hope for a fix in a near release.