`<algorithm>`: `ranges::min`, `ranges::max` and `ranges::minmax` evaluate each element twice

[biart]

Describe the bug

std::ranges::min/max/minmax over a views::transform range invoke the transform roughly twice per element. libstdc++ invokes it once, and libc++'s count depends on the data. Since these overloads return range_value_t<R> by value and are constrained on indirectly_copyable_storable, one evaluation per element appears to be permitted.

Command-line test case

// cl /EHsc /std:c++latest /O2 repro.cpp
#include <algorithm>
#include <cstdio>
#include <ranges>
#include <vector>

int calls = 0;
struct Entry { double v; double get() const { ++calls; return v; } };

int main() {
    std::vector<Entry> data;
    for (int i = 1; i <= 8; ++i) data.push_back(Entry{static_cast<double>(i)});

    calls = 0;
    (void) std::ranges::min(data | std::views::transform(&Entry::get));
    std::printf("ranges::min    : %d\n", calls);   // 15

    calls = 0;
    double m = 1e300;
    for (const auto& e : data) m = (std::min)(m, e.get());
    std::printf("hand loop      : %d\n", calls);   // 8
}

Godbolt link

Observed (N = 8, so 8 is one call per element and 15 is 2N−1):

	MS STL 19.51	libstdc++	libc++
ranges::min over transform_view	15	8	<=15
ranges::max over transform_view	15	8	<=15
ranges::minmax over transform_view	22	8	22
ranges::fold_left over transform_view	8	8	8
hand-written loop	8	8	8

Expected behavior

One evaluation per element, as libstdc++ achieves.

STL version

Microsoft Visual Studio 18 (Insiders), toolset 14.51.36231, compiler 19.51.36252, x64.

Additional context

[alg.min.max]/7 constrains comparisons and applications of the projection:

Complexity: Exactly ranges::distance(r) - 1 comparisons and twice as many applications of the projection, if any.

Here the projection is identity, and I could not find any wording in [alg.min.max] or [algorithms.requirements] that constrains how many times *i may be evaluated. An implementation that stores range_value_t<R> rather than tracking an iterator would satisfy the stated complexity exactly while halving the dereferences. minmax seems to be even more permissive with its "at most" wording.

Note that [alg.min.max]/27 has similar wording on the min_element variant, except that "if any" is suspiciously missing:

Complexity: Exactly max(last - first - 1,0) comparisons and twice as many projections.

I guess the pedantic reading of this gives the reason why min_element cannot have a similar optimisation (along with minor performance and design quirks on caching reference alongside of the iterator). This is deliberately not part of this report.

Measured impact

I was trying to write a blog post advocating for C++20 ranges, and ran into unexpected performance issues when using costly transform.

With a non-trivial transform (std::cos(angle) * length), MSVC 19.51 /O2: 2.09× a hand-written loop at N = 131072, and 4.77× at N = 2048. MSVC is not able to optimise out the redundancy at /O2 /Ob3 /GL /arch:AVX2 /LTCG or with /fp:fast.

If the maintainers consider this a worthwhile change, I would be happy to prepare a pull request for std::max/min/minmax with identity projection.

[AlexGuteniev]

Looks like a duplicate of #1006

[biart]

Thanks for the pointer, it indeed seems very related.

I am trying to understand the discussion at #1006, and for now it feels that resolutions to both issues could be orthogonal:

• <algorithm>: debug checks for predicates are observable #1006 is about extra predicate invocations by the IDL=2 debug checks. This report is about extra dereferences in release builds where no debug checks run, and removing them wouldn't change the measurements.
• The call counter in the repro is only a measurement device; the motivating problem is the ~2× wall-clock cost with an expensive transform, which is why I'd frame this as QoI/performance rather than conformance.

If anything, the #1006 discussion seems to support this report: the debug checks were already removed from min/max there on the grounds that "it's a reasonable expectation for min or max to invoke the predicate only once". Here we have the similar expectation, applied to dereferences.

That said, I may well be missing context, so I rely on your expertise on how to track this. In the meanwhile, I will try to better understand both problems as well.

[biart]

Side note: I discovered that some machinery to fix this exists here:

STL/stl/inc/xutility

Line 7540 in 48570c4

concept _Prefer_iterator_copies = // When we have a choice, should we copy iterators or copy elements?

I wonder if _Prefer_iterator_copies could be safely extended to somehow guess whether dereference may be costly. (When iter_reference_t is not a reference or specifically for transformed iterators)