Page MenuHomePhabricator

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

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

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
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
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 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

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?

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
118

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
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 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

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.