Details
- Reviewers
• Quuxplusone var-const Mordante ldionne jdoerfert - Group Reviewers
Restricted Project - Commits
- rG58d9ab70aef3: [libc++][ranges] Implement ranges::minmax and ranges::minmax_element
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
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. |
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. |
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. |
- Address comments
@var-const maybe you should take another look. There are quite a few changes.
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:
| |
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:
| |
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? |
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 |
- Fix C++03
- Address comments
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp | ||
---|---|---|
97 | See Louis' comment |
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:
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. |
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). |
- 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 |
libcxx/benchmarks/algorithms.bench.cpp | ||
---|---|---|
360–362 | Could you try this instead? auto res = std::minmax_element(Copy.begin(), Copy.end()); benchmark::DoNotOptimize(res); |
FWIW I don't think it's worth blocking landing this algorithm on the benchmark, since the string benchmark looks normal.