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 << "Copyn"; }
    A( A&& ) noexcept { std::cout << "Moven"; }

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

    int x = 10;
};

int main()
{
    std::vector<A> vec( 10 );
    std::cout << "Initn";
    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?

My next step would be is to set a breakpoint in the copy constructor, then try to figure out where in the templates it gets invoked, and why. — 13 hours ago
Well, you were asking for a "why", which I can't give — I'm not an STL wizard to come up with an explanation right away. I can, however, come up with a solution: std::cout << std::ranges::max_element( vec, [] ( const auto& a, const auto& b ) { std::cout << "cmp" << std::endl; return a.x < b.x; } )->x; — 12 hours ago
Try making the move constructor noexcept. The std containers need to play safe when moving stuff. — 12 hours ago
This doesn't address the question, but nothing in this code needs the extra stuff that std::endl does. 'n' ends a line. — 12 hours ago
@Jabberwocky you probably need to add -stdlib=libc++ so that clang uses its own std lib. — 12 hours ago

score 9 · Accepted Answer · 2023-11-02 20:13:36Z

It’s what I presume is 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.

auto& __tmp = *__first; won't copy indeed, but I assume iterator is not required to return referencable value. It could possibly return a temporary. I think std::ranges::range_value_t<_Rp> accounts exactly for this in LLVM. — 11 hours ago
@Andrew That was my first instinct too but just making it std::ranges::range_value_t<_Range> __tmp = *__first; had no effect. I didn't dig deeper there. — 11 hours ago
@Andrew I've now written a bugreport. Let's see what comes out of that. — 11 hours ago

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