This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by philnik on Feb 27 2022, 3:31 PM.

Diff Detail

Event Timeline

philnik created this revision.Feb 27 2022, 3:31 PM
philnik requested review of this revision.Feb 27 2022, 3:31 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 27 2022, 3:31 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik retitled this revision from [libc++][ranges] Implement ranges::minmax to [libc++][ranges] Implement ranges::minmax and ranges::minmax_element.Feb 27 2022, 3:32 PM
Quuxplusone requested changes to this revision.Feb 28 2022, 9:26 AM

The tests looked great and comprehensive... but then I took a look at the code and quickly found some missing test coverage (my "Sadly" comment).

libcxx/include/__algorithm/ranges_minmax.h
40–42

This needs a regression test. For example,

auto r = std::ranges::minmax(one, two, [](int, int) { return false; });
assert(r.min == 1);
assert(r.max == 2);

Please add similar regression tests for ranges::min and ranges::max if they don't already exist.

58–59

Sadly, I don't think we can do this. _Rp is an input_range, which means it's single-pass. You can't pass its iterators to ranges::minmax_result. You've sidestepped the guardrail by calling into __go directly instead of the constrained minmax_result::operator() — and that's fine with me — but it means that what you've got here will compile but won't work.

We should add a regression test for this. Perhaps using a completely custom input_iterator. I've thought of two test cases that use only STL facilities, but libc++ has not implemented either istream_view or move_iterator yet. Also, my move_iterator example is possibly wrong. See https://godbolt.org/z/7Kov5e6oe (and I've asked on Slack why libstdc++ barfs on the latter).

libcxx/include/__algorithm/ranges_minmax_element.h
25
32

I'd add a blank line after namespace ranges {.

40
41

Given how you use this, I think it could profitably be more like

auto __less = [&](_Ip& __it, _Ip& __jt) -> bool {
  return std::invoke(__comp, std::invoke(__proj, *__it), std::invoke(__proj, *__jt));
};

I'm ambivalent whether the params should be const _Ip&. If it's legal, then I'm leaning toward "yes."

43

Style nit.

70–71

In my head this gives the wrong answer for {1,2,4,4}; max in this case should point to the second 4, not the first 4. I may have done the mental simulation wrong, though. Please investigate and add a regression test if needed — in fact, I recommend adding a regression test either way!

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

This is unused. (If it had been used, s/NotTotallyOrdered/TotallyOrderedRVal/ on line 45. But as it is, just remove it.)

140–145

I'd like to see another test case to verify that the number stored in ret.max is actually the element e, and not proj(e). Er, actually, it would suffice to have a test case where decltype(e) != decltype(proj(e)). Which you actually have on lines 169-176 (the test involving struct S). So actually this is fine, and I wouldn't even object if you removed lines 139-144. :)

177

Please add

ret = std::ranges::minmax(b, b + 3, {}, &S::i);
assert(ret.min.i == 1);
assert(ret.max.i == 3);

so we test the iterator-sentinel version with S as well.

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

Replace these four lines with your better tests from above. Just replace MinMax with MinMaxElement in each case, obviously. :)

static_assert(HasMinMax<int (&)[10]>);
static_assert(HasMinMax<int (&&)[10]>);
static_assert(!HasMinMax<NoLessThanOp (&)[10]>);
static_assert(!HasMinMax<NotTotallyOrdered (&)[10]>);

static_assert(HasMinMax<std::initializer_list<int>>);
static_assert(!HasMinMax<std::initializer_list<NoLessThanOp>>);
static_assert(!HasMinMax<std::initializer_list<NotTotallyOrdered>>);
155

Remove this blank line. Also consider moving arr into each individual block scope (i.e. duplicate it); our style for these little block scopes is generally to make them all self-contained, not referencing (or potentially modifying) anything from the outer scope(s).
Ditto line 125.

193–196

test_iterators and test_range are called only once each. This is fine, but then they don't need to take any parameters; you can just define a resp. a2 as a local variable of test_iterators resp. test_range.
Ditto in ranges.minmax.pass.cpp.

This revision now requires changes to proceed.Feb 28 2022, 9:26 AM
philnik updated this revision to Diff 413234.Mar 5 2022, 11:19 AM
philnik marked 13 inline comments as done.
  • Address comments
Herald added a project: Restricted Project. · View Herald TranscriptMar 5 2022, 11:19 AM
philnik added inline comments.Mar 5 2022, 11:40 AM
libcxx/include/__algorithm/ranges_minmax_element.h
41

I think it wouldn't work if the comparator expects non-const parameters,.

70–71

This is already tested with test<It>({2, 1, 2}, 1, 2); or am I missing something?

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

There is no iterator-sentinel version for ranges::minmax? Did you mean ranges::minmax_element?

Quuxplusone requested changes to this revision.Mar 8 2022, 1:42 PM
Quuxplusone added a subscriber: BRevzin.
Quuxplusone added inline comments.
libcxx/include/__algorithm/ranges_minmax.h
66

Per @BRevzin https://cpplang.slack.com/archives/C4Q3A3XB8/p1646101005063689 , I think this needs to be

ranges::minmax_result<_Ip> __result = {*first, __result.min};

because it might not be safe to copy from *first twice. You can regression-test this with something like

std::shared_ptr<int> a[] = { std::make_shared<int>(42) };
auto [min, max] = std::ranges::minmax(std::move_iterator(a), std::move_iterator(a + 1));
assert(a[0] == nullptr);
assert(min != nullptr);
assert(max == min);
70–73

I think it's OK to read from *__first twice in this case, because if __less(*__first, __result.min) causes side effects (like moving-from), that's a bug in __less, not our problem. But I'm not sure.

104
libcxx/include/__algorithm/ranges_minmax_element.h
70–71

OK, I think you're right.
I checked out the patch and added calls to abort() on each branch of this if-tree to check coverage. That found one untested branch, which you can fix by adding this test case:

test<It>({2, 2, 1}, 2, 1);
98
This revision now requires changes to proceed.Mar 8 2022, 1:42 PM
Quuxplusone added inline comments.Mar 8 2022, 1:43 PM
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp
177

No, just forgot there wasn't one. This is fine then.

philnik updated this revision to Diff 413963.Mar 8 2022, 3:57 PM
philnik marked 7 inline comments as done.
  • Address comments
var-const requested changes to this revision.Mar 8 2022, 9:29 PM

@philnik Please update RangesAlgorithms.csv as well. Thanks!

libcxx/include/__algorithm/ranges_minmax.h
63

Do __it1 and __it2 need to be forwarded, given that they are forwarding references?

71

I have a concern similar to mismatch -- this could be a lot of copying in the worst case. Would it be worthwhile to have different implementations of the algorithm for input_range and forward_range?

77–82

Same optional suggestion re. using lambdas as in minmax_element.

libcxx/include/__algorithm/ranges_minmax_element.h
58

Very optional: I found several nested conditions with similar comparisons a little hard to keep track off. Consider streamlining some of this flow using a helper -- maybe something like:

auto __less = [&](_Ip& __it1, _Ip& __it2) -> bool {
  return std::invoke(__comp, std::invoke(__proj, *__it1), std::invoke(__proj, *__it2));
};
auto __maybe_update_min = [&__result](_Ip& __it) {
  if (__less(__it, __result.min)) {
    __result.min = __it;
  }
};
auto __maybe_update_max = [&__result](_Ip& __it) {
  if (!__less(__it, __result.max)) {
    __result.max = __it;
  }
};

ranges::minmax_result<_Ip> __result {__first, __first};
if (__first == __last || ++__first == __last)
  return __result;

if (__less(__first, __result.min))
  __result.min = __first;
else
  __result.max = __first;

while (++__first != __last) {
  _Ip __i = __first;
  if (++__first == __last) {
    __maybe_update_min(__i);
    __maybe_update_max(__i);
    return __result;
  }

  if (__less(__first, __i)) {
    __maybe_update_min(__first);
    __maybe_update_max(__i);
  } else {
    __maybe_update_min(__i);
    __maybe_update_max(__first);
  }
}
85

Would it make sense to move __first and maybe __last?

92

Question: does __r need to be forwarded, perhaps?

libcxx/include/algorithm
805

You probably also need to update the synopsis.

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

<random> is unused, right? (here and in the other test file)

32

Is "test_macros.h" used?

196

I'd add a few test cases to make sure the algorithm works correctly:

  • make sure to test both an even- and an odd-length range (since the algorithm effectively iterates in steps of two);
  • empty range;
  • single-element range;
  • sorted range (both ascending and descending);
  • all elements compare equal (this should also test that "Returns X{x, y}, where x is a copy of the leftmost element with the smallest value and y a copy of the rightmost element with the largest value in the input range").

This applies to minmax_element as well.

200

Can you add a comment explaining the main intention of this test case? It seems to be to test move_iterator behavior, but then it uses shared_ptr as well.

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

Similar to other patches: I think there needs to be a SFINAE test for every constraint (in both test files).

217

Nit: seems like an extra blank line.

221

Optional: also test with a contiguous iterator for good measure (echoing Arthur's comment from another patch)?

This revision now requires changes to proceed.Mar 8 2022, 9:29 PM
var-const added inline comments.Mar 8 2022, 9:33 PM
libcxx/include/__algorithm/ranges_minmax.h
58–59

Would it make sense to change input iterators in test_iterators.h to throw if they're read more than once?

philnik updated this revision to Diff 414063.Mar 9 2022, 4:17 AM
philnik marked 14 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_minmax.h
63

I wasn't able to produce any case where it makes a difference. The main reason these are forwarding is that iterator::operator* could return an rvalue reference. So I essentially just cast them to lvalues. There is also no guarantee that the calls will be made in a specific way.

71

I've also added two moves for the last uses of __i.

77–82

With the moves every branch is different anyways, so I don't think it makes much sense.

libcxx/include/__algorithm/ranges_minmax_element.h
85

iterators should always be cheap to copy, and ranges::minmax_element doesn't support input ranges. So I see no reason to move them.

92

Definitely not the first one, and I also don't think the second one. We still need our range for the iterators to be valid, so conceptually it doesn't make sense to forward them (and makes probably no practical difference).

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

Even and odd lengths are already covered. In ranges::minmax empty ranges aren't allowed. I added asserts. What are you looking for with a sorted range?

Quuxplusone added inline comments.Mar 9 2022, 8:54 AM
libcxx/include/__algorithm/ranges_minmax.h
63

This is detectable by the user's projection, so yes, please forward them. I think a detector would look like

int a[2] = {1, 2};
auto r = std::ranges::subrange(std::move_iterator(a), std::move_iterator(a + 2));
auto proj = [](int&&) { return 42; };  // callable only with rvalues
auto [min, max] = std::ranges::minmax(r, {}, proj);
assert(min == 1 && max == 2);

Also, what's probably muddying the issue here is that you named them __it1 and __it2 but they are not in fact iterators; they're elements/values! Please change the names to something like __a and __b. (And in general, please don't name non-iterators it. Arguably it could be short for "item," but in practice, no, it's just confusing.)

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp
227
var-const added inline comments.Mar 9 2022, 11:17 AM
libcxx/include/__algorithm/ranges_minmax.h
69

Should the rest of the function go into an else branch, to make sure it's part of if constexpr?

libcxx/include/__algorithm/ranges_minmax_element.h
85

I don't feel very strongly, but I don't think we should rely on users doing something that isn't enforced. Elsewhere we're protecting against things that are pretty unreasonable just because they're allowed. It's a good point that an iterator that's expensive to copy is more likely to be an input iterator, though.

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

This looks incorrect (it looks like the signatures of ranges::minmax_element except for the function name).

41

Can you also check that something that isn't an input_range SFINAEs away?

196

Re. sorted range -- it seems like an interesting case because min or max would be updated on every iteration.

I don't see a test for a single-element range (except the test with shared_ptr, but it's focused on a different thing).

Quuxplusone added inline comments.
libcxx/include/__algorithm/ranges_minmax_element.h
85

FWIW, if we really thought iterators/sentinels might be expensive, we might even choose to pass them by reference instead of by value. (In this specific case, we could take const _Sp&.) We're just guessing that _Sp is likely more appropriate than const _Sp& (because usually _Sp is either a pointer/iterator, or a tag type). I would not pass-by-reference just to avoid a copy of an iterator or sentinel. (But I would pass-by-reference to avoid copies of callables. Inconsistent, yes. :))

Also, the big downside of adding std::moves has already been illustrated, by me, literally yesterday: in D118003 I wrote a std::move that shouldn't have been there, and thus introduced a use-after-move bug. We have no good story for testing against use-after-move of iterators and sentinels. So let's be cautious in this department.

However, just changing __first into std::move(__first) sounds like a pretty harmless improvement to me. It might be faster and it will never be slower. So +1 on std::move'ing from me.
I do see how it's a slippery slope, because our STL Classic algorithms generally do not std::move iterators, and I don't think we should actually go churn up that existing code to add moves. But in new code, and specifically Ranges code where we might expect slightly-heavier-weight iterators, and specifically in this case where the function is one line long — I think we can justify std::move!

(But I'll defer to @ldionne if he has an opinion.)

philnik updated this revision to Diff 414426.Mar 10 2022, 10:48 AM
philnik marked 7 inline comments as done.
  • Rebased
  • Address comments
libcxx/include/__algorithm/ranges_minmax.h
63

I'm not adding a regression test because I think it isn't actually detectable in any sensible way. The projection has to be callable with an lvalue, because it may have the temporary as its argument.

philnik added inline comments.Mar 10 2022, 10:48 AM
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 added inline comments.Mar 10 2022, 6:10 PM
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
156

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 updated this revision to Diff 414833.Mar 12 2022, 6:38 AM
philnik marked 3 inline comments as done.
  • Address comments; Fix CI
ldionne requested changes to this revision.Mar 18 2022, 8:17 AM
ldionne added inline comments.
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.

This revision now requires changes to proceed.Mar 18 2022, 8:17 AM
var-const accepted this revision as: var-const.Mar 21 2022, 11:42 PM

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 updated this revision to Diff 418436.Mar 26 2022, 10:13 PM
philnik marked 3 inline comments as done.
  • Address comments

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

ldionne requested changes to this revision.Mar 29 2022, 7:16 AM

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 ↗(On Diff #418436)

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
78

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?

This revision now requires changes to proceed.Mar 29 2022, 7:16 AM
philnik updated this revision to Diff 419473.Mar 31 2022, 8:23 AM
philnik marked 19 inline comments as done.
  • Address comments
philnik added inline comments.Mar 31 2022, 8:23 AM
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 updated this revision to Diff 419796.Apr 1 2022, 10:27 AM
  • Fix CI; Mark LWG3180 as complete
var-const added inline comments.Apr 1 2022, 10:49 PM
libcxx/include/__algorithm/ranges_minmax.h
76

Nit: s/iteratos/iterators/.

libcxx/include/algorithm
78

Nit: s/minmas/minmax/.

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

Nit: decltype(auto).

philnik updated this revision to Diff 420054.Apr 3 2022, 8:03 AM
  • Try to fix CI
philnik updated this revision to Diff 420073.Apr 3 2022, 12:21 PM
  • Use __invoke_constexpr
philnik updated this revision to Diff 420083.Apr 3 2022, 1:26 PM
philnik marked 3 inline comments as done.
  • Fix C++03
  • Address comments
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp
97

See Louis' comment

ldionne accepted this revision.Apr 4 2022, 7:51 AM

LGTM with my comments applied. Thanks!

libcxx/include/__algorithm/minmax.h
49 ↗(On Diff #420083)

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 ↗(On Diff #420083)

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 ↗(On Diff #420083)

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 added inline comments.Apr 4 2022, 2:13 PM
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 updated this revision to Diff 421770.Apr 10 2022, 12:33 AM
philnik marked 7 inline comments as done.
  • 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 added inline comments.Apr 11 2022, 6:33 AM
libcxx/benchmarks/algorithms.bench.cpp
360–362 ↗(On Diff #421770)

Could you try this instead?

auto res = std::minmax_element(Copy.begin(), Copy.end());
benchmark::DoNotOptimize(res);
ldionne accepted this revision.Apr 13 2022, 9:39 AM

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

philnik updated this revision to Diff 422646.Apr 13 2022, 1:59 PM
  • Add generated files
This revision was not accepted when it landed; it landed in state Needs Review.Apr 14 2022, 6:37 AM
This revision was automatically updated to reflect the committed changes.