[libc++][ranges] Implement ranges::minmax and ranges::minmax_element

[philnik]

libcxx/include/__algorithm/ranges_minmax.h

69

I'm not a huge fan of that, but I agree that having faster compile times is more valuable than the bit of increased readability it gives to not have the else branch. Just for the record, I would definitely not want the else branch if it were a normal if.

libcxx/include/__algorithm/ranges_minmax_element.h

85

Agreed that it doesn't hurt here, but I definitely wouldn't make that a guarantee.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

196

I think I got all you requests covered now.

[var-const]

libcxx/include/__algorithm/ranges_minmax.h

69

I fully agree from the readability perspective. I would also prefer no else branch if it wasn't if constexpr.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

157

Nit: some test cases place the comment on the same line as the opening brace, and some on the next line. I don't mind either, but it should be consistent.

[philnik]

• Address comments; Fix CI

[philnik]

• Fix CI

[ldionne]

libcxx/include/__algorithm/ranges_minmax.h

57

Could you investigate whether the logic of this algorithm can be shared with the STL classic std::minmax_element? IMO this is right on the threshold where it starts making sense to share the implementation.

libcxx/include/__algorithm/ranges_minmax_element.h

85

I'm neutral. We can do it for one-liners, but we shouldn't start trying to move out of iterators whenever we can, since the benefit is likely small. It's more important that users have the mental model that iterators and sentinels must be cheap to copy, because otherwise nothing's going to work well, even if we try really hard.

[var-const]

Leaving the approval to @ldionne who had some not-yet-resolved comments.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

216

Please make sure that each test case has an associated comment.

[philnik]

• Address comments

@var-const maybe you should take another look. There are quite a few changes.

[ldionne]

Thanks a lot for the patch! I really like the new approach where we avoid duplicating the logic in minmax_element, and I think we should try to use this approach for other algorithms when the benefit outweighs the cost of doing so (which will be the case for non-trivial algos, but not for very simple ones).

Once my comments have been addressed, I think we'll be pretty much ready to ship this, but I'd still like to have a look to confirm. Thanks!

libcxx/include/__algorithm/minmax.h

13

We'll want to put the common logic in the classic header, not in the ranges header. The classic version shouldn't have a dependency on the ranges version. It might be a bit counter-intuitive because the generalized algorithm looks more like a ranges algorithm, but it's necessary if we want to avoid a dependency on ranges.

libcxx/include/__algorithm/ranges_minmax.h

52

66

I don't *think* __result is considered initialized until the semicolon, though, which means that we'd be accessing an object before it has been initialized, which is UB. Why can't we do this instead:

auto __tmp = *__first;
ranges::minmax_result<_Ip> __result = {__tmp, std::move(__tmp)};

I asked a question in the thread, waiting for an answer.

71

Could you add a short comment in the lines of // We can't copy input_iterators, so we need to use a different implementation based on stashing their value_type instead.

72

Suggestion if you don't like the decltype(__a) below:

auto __less = [&]<class _Vp>(_Vp&& __a, _Vp&& __b) -> bool { ... std::forward<_Vp>(__a) ... };

libcxx/include/__algorithm/ranges_minmax_element.h

38

This will need to be made C++03 friendly, so unfortunately you'll need to use function objects and drop the nice syntax. :(

This may mean that it's not worth refactoring the small if bits in lambdas below.

61

Per our discussion: it would be interesting to check which of the following options is best in terms of codegen:

1. Use [[unlikely]] on the if (++__first == __last) branch to tell the compiler that we rarely hit the end of the range, or
2. If we have random-access iterators, handle the case of an odd-sized range explicitly above so we can get rid of the if (++__first == __last) check in the loop altogether and always process two elements at a time, or
3. Leave the code as-is

88

I think this should be minmax_element_result, and so we're missing a minmax_result alias in ranges_minmax.h. Please add tests for both!

95

This should be returning mimmax_element_result instead. Even though it's not observable, let's do it for tidyness. Same below.

103

It looks like the Standard gets confused between minmax_result and minmax_element_result. In the description of minmax_element (just above http://eel.is/c++draft/alg.min.max#31), it uses minmax_result as the return type of the algorithm. However, it uses minmax_element_result in the synopsis of the same algorithms (in http://eel.is/c++draft/algorithm.syn).

I'm sure this is editorial and they meant to use minmax_element_result. Can you please file a LWG issue about this? You can read how to do this near the top of https://cplusplus.github.io/LWG/lwg-active.html. Please CC me on the thread.

As far as this patch is concerned, please make sure that minmax_element is described to return minmax_element_result:

1. In the synopsis
2. In the code
3. In the test synopsis
4. In the test code for minmax_element itself

libcxx/include/algorithm

118

This applies elsewhere too, e.g. below but probably in the tests.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

2

I think you should also add an entry in robust_against_comparator_copying.pass.cpp or whatever!

52–53

Instead of just checking that those are well-formed, can you please add runtime tests below on these types?

58

Maybe?

96

I think this is actually clearer, since you're making a copy of the minmax_result, and the minmax_result itself contains a reference. This may apply elsewhere.

104–106

It looks like this is testing http://eel.is/c++draft/alg.min.max#18, please add a comment like make sure that we return {a, b} if b is not less than a.

You can then test this by:

int a = 1;
int b = 1;
auto r = ranges::minmax(a, b);
assert(&r.min == &a);
assert(&r.max == &b);

The current implementation of the test unfortunately doesn't use a strict-weak order, and so technically is IFNDR.

158

Can you please add a test to make sure that we trigger the _LIBCPP_ASSERT when we pass an empty initializer_list? You can do that by looking at what we do in other tests named assert.*.pass.cpp in the test suite. It's pretty easy to do, but you'll want to put it in a separate file because it won't run on Windows. I'd like you to check the _LIBCPP_ASSERT for ranges::minmax that takes a range.

287

I see you have tests with an input_range, but can you also add generic tests with ranges using the other archetypes like forward_iterator, bidirectional_iterator, etc?

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax_element.pass.cpp

40–41

Instead of just checking that those are well-formed, can you please add runtime tests below on these types?

45

111

I find this function name (and the one above) rather confusing, since we have 3 overloads of test in this file. Is there any reason why this isn't called test_iterators, and why the test_iterators function above (one of the first in the file) isn't redundant at this point?

[philnik]

• Address comments

[philnik]

libcxx/include/__algorithm/ranges_minmax.h

66

I think http://eel.is/c++draft/dcl.init.aggr#7 is the line in question here, and that sounds to me like the first element has to be fully initialized before the second one.

libcxx/include/__algorithm/ranges_minmax_element.h

61

https://quick-bench.com/q/ezc6hrE4rQ4Smt-XXF72ENAx3iI
It looks like using [[unlikely]] makes no difference and checking the size before the loop is slightly slower.

[philnik]

• Fix CI; Mark LWG3180 as complete

[var-const]

libcxx/include/__algorithm/ranges_minmax.h

76

Nit: s/iteratos/iterators/.

libcxx/include/algorithm

118

Nit: s/minmas/minmax/.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

97

Nit: decltype(auto).

[philnik]

• Try to fix CI

[philnik]

• Use __invoke_constexpr

[philnik]

• Fix C++03
• Address comments

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

97

See Louis' comment

[ldionne]

LGTM with my comments applied. Thanks!

libcxx/include/__algorithm/minmax.h

50

Since we start using std::invoke under the hood, this means that we would suddenly start accepting non-function-objects too as a comparator in STL classic algorithms. I don't think we want to relax the requirements like this, since it could be a portability trap for users.

Can we start static_asserting that the comparator can be called like __comp(...) in the STL algorithms?

libcxx/include/__algorithm/minmax_element.h

37

You just said during live review: I don't think I have a test to check that I'm using std::invoke for the comparator. Please add one!

libcxx/include/__algorithm/ranges_minmax.h

66

http://eel.is/c++draft/dcl.init.aggr#7 says:

The initializations of the elements of the aggregate are evaluated in the element order. That is, all value computations and side effects associated with a given element are sequenced before those of any element that follows it in order.

I am on the fence about whether this means what you think it means. In particular, if the "initializations of the elements of the aggregate are evaluated in the element order" means that the object isn't considered partially formed before the semi-colon, then the status quo works. I'll ask the question on a reflector, but until we have an answer, I think it would be safer to use this, even if it results in an additional copy:

auto __tmp = *__first;
ranges::minmax_result<_Ip> __result = {__tmp, std::move(__tmp)};

Just to unblock this review -- I'll send an email later today.

libcxx/include/__algorithm/ranges_minmax_element.h

61

Alright, in that case I don't mind leaving the code as-is, but thanks for checking. Would you mind adding your simple benchmark code to libcxx/benchmarks/algorithms.bench.cpp?

libcxx/include/type_traits

419–420

This looks like an incorrect merge conflict resolution to me.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

104–106

You're still using a comparator that isn't a strict-weak order. I think you can probably replace this by my suggestion above, which checks the same property without being IFNDR.

[ldionne]

libcxx/include/__algorithm/ranges_minmax.h

66

OK, this seems to be fine to leave as-is per the answers on https://lists.isocpp.org/core/2022/04/12238.php (this is restricted but still useful for those with access -- sorry for others).

[philnik]

• Rebased
• Address comments

libcxx/include/__algorithm/ranges_minmax_element.h

61

I added the benchmark, but I think I'm doing something wrong there. The numbers don't look correct:

BM_MinMaxElement_uint32_Random_1            1.15 ns         1.14 ns    612630528
BM_MinMaxElement_uint32_Random_4            1.81 ns         1.80 ns    387973120
BM_MinMaxElement_uint32_Random_16           1.85 ns         1.84 ns    380370944
BM_MinMaxElement_uint32_Random_64           1.06 ns         1.06 ns    659816448
BM_MinMaxElement_uint32_Random_256         0.661 ns        0.660 ns   1000079360
BM_MinMaxElement_uint32_Random_1024        0.487 ns        0.486 ns   1000079360
BM_MinMaxElement_uint32_Random_16384       0.431 ns        0.431 ns   1000079360
BM_MinMaxElement_uint32_Random_262144      0.422 ns        0.421 ns   1000079360

Only the numbers for string look normal:

BM_MinMaxElement_string_Random_1            2.36 ns         2.35 ns    299368448
BM_MinMaxElement_string_Random_4            16.7 ns         16.6 ns     42205184
BM_MinMaxElement_string_Random_16           24.6 ns         24.6 ns     28835840
BM_MinMaxElement_string_Random_64           24.4 ns         24.4 ns     29097984
BM_MinMaxElement_string_Random_256          24.4 ns         24.3 ns     29097984
BM_MinMaxElement_string_Random_1024         28.0 ns         27.9 ns     25165824
BM_MinMaxElement_string_Random_16384        31.2 ns         31.1 ns     22806528
BM_MinMaxElement_string_Random_262144       36.2 ns         36.1 ns     20709376

[ldionne]

libcxx/benchmarks/algorithms.bench.cpp

360–362

Could you try this instead?

auto res = std::minmax_element(Copy.begin(), Copy.end());
benchmark::DoNotOptimize(res);

[ldionne]

FWIW I don't think it's worth blocking landing this algorithm on the benchmark, since the string benchmark looks normal.

[philnik]

• Add generated files