[libc++] Implement ranges::ends_with

[var-const]

Thanks a lot, this is getting very close to LGTM. The implementation looks good (just a few formatting nitpicks), just a few minor things in tests to address plus the benchmark needs to be reworked. My sincere apologies for the very slow review (mostly due to the upcoming LLVM 17 release).

libcxx/include/__algorithm/ranges_ends_with.h

40

How about naming this function __ends_with_fn_impl_bidirectional, just for consistency with the other helpers?

68

Nit: please add a blank line before this line.

74

Nit: please add a blank line after this line.

105

Nit: can you add spaces before and after the &&? Or just clang-format these lines. If it's clang-format that produces this formatting, then never mind (although I'd be surprised).

105

Nit: the parentheses around !std::random_access_iterator<_Sent1> are unnecessary (same for the _Sent2 check).

106

Nit: std::move the iterators here as well?

118

Nit: please add a blank line after this line (to separate different functions from each other).

168

Nit: please add a blank line before this line.

libcxx/test/std/algorithms/alg.nonmodifying/alg.ends_with/ranges.ends_with.pass.cpp

43

Nit: I think we need one successful test case for each number of template arguments, so here we need to add:

static_assert(!HasEndsWithIt<int*, int*>);

(this is to "test the test", so to speak)

52

Nit: Range1 and Range2 should be forwarding references, and in the body of the concept, range1 and range2 should be forwarded. That way, it would be more similar to how the function is actually invoked.

59

Here we also need to have a successful test case for two template arguments.

60

Optional: IMO it's not necessary to test out every single not-forward-range we have, just a couple is enough (e.g. I would leave just ForwardRangeNotDerivedFrom and ForwardRangeNotSentinelSemiregular).

235

Nit: formatting needs fixing.

256

I think this should be random_access_iterator list, otherwise none of the iterator types in the list are a forward iterator so the if constexpr (std::forward_iterator...) below will never be taken.

275

Nit: s/benmark/benchmark/ (here and below).

275

+1, benchmarks should be under the benchmarks folder and use the infrastructure we're currently using (that is, Google Benchmark).

Also, we shouldn't be benchmarking the implementation details like this, partially because it's easy for the benchmark and the actual implementation to get out of sync. Rather, you can use the same input vectors for different test cases but wrap their iterators into our helper iterators, then call ends_with using the wrappers:

std::vector<int> a = /*some initializer*/;
std::vector<int> p = /*some initializer*/;

{
  std::random_access_iterator<int*> begin1(a.begin());
  std::random_access_iterator<int*> end1(a.end());
  std::random_access_iterator<int*> begin2(p.begin());
  std::random_access_iterator<int*> end2(p.end());
  std::ranges::ends_with(begin1, end1, begin2, end2);
  // ...
}
{
  std::bidirectional_iterator<int*> begin1(a.begin());
  std::bidirectional_iterator <int*> end1(a.end());
  std::bidirectional_iterator <int*> begin2(p.begin());
  std::bidirectional_iterator <int*> end2(p.end());
  std::ranges::ends_with(begin1, end1, begin2, end2);
  // ...
}

You can even test the sized optimization using sized_sentinel. Like Louis mentioned above, we unfortunately don't have a way to test for performance regressions currently, and we shouldn't try to solve that problem in this patch. Rather, it would be great if you could run the new benchmarks locally, make sure the numbers are as expected (i.e., random access iterators are faster than bidirectional iterators, etc.), then post the results in this review.

276

This should be just std::vector.

278

Nit: formatting (should be a space after for, i.e., for ().

284

Names used in tests don't have to be uglified with leading __ underscores (in fact, they shouldn't be since these are technically reserved names for the library. Even though the test is testing the library, the test itself isn't a part of the library).

289

Since these are the default values, I think they should be omitted (the predicate and the projections, that is).

[ZijunZhao]

1. reformat
2. rename helper function
3. add std::move

[ZijunZhao]

reformat

[ZijunZhao]

libcxx/test/std/algorithms/alg.nonmodifying/alg.ends_with/ranges.ends_with.pass.cpp

256

I think cpp20_input_iterator_list already contains random_access_iterator?
Why I think so is because from libcxx/test/support/test_iterators.h

using random_access_iterator_list =
    type_list<Ptr,
#if TEST_STD_VER >= 20
              contiguous_iterator<Ptr>,
#endif
              random_access_iterator<Ptr> >;

template <class Ptr>
using bidirectional_iterator_list =
    concatenate_t<random_access_iterator_list<Ptr>, type_list<bidirectional_iterator<Ptr> > >;

template <class Ptr>
using forward_iterator_list = concatenate_t<bidirectional_iterator_list<Ptr>, type_list<forward_iterator<Ptr> > >;

template <class Ptr>
using cpp17_input_iterator_list = concatenate_t<forward_iterator_list<Ptr>, type_list<cpp17_input_iterator<Ptr> > >;

#if TEST_STD_VER >= 20
template <class Ptr>
using cpp20_input_iterator_list =
    concatenate_t<forward_iterator_list<Ptr>, type_list<cpp20_input_iterator<Ptr>, cpp17_input_iterator<Ptr>>>;
#endif

[ZijunZhao]

Update HasEndsWithR test

[var-const]

libcxx/test/std/algorithms/alg.nonmodifying/alg.ends_with/ranges.ends_with.pass.cpp

53

Nit: you would also need to call std::forward<Range1>(range1) here (same for the other argument).

275

Sorry, rereading this comment, I mean random_access_iterator and bidirectional_iterator from our test_iterators.h header. Please ignore the std:: qualification, I copy-pasted it accidentally. So basically

std::vector<int> a = /*some initializer*/;
std::vector<int> p = /*some initializer*/;

{
  random_access_iterator<int*> begin1(a.begin());
  random_access_iterator<int*> end1(a.end());
  random_access_iterator<int*> begin2(p.begin());
  random_access_iterator<int*> end2(p.end());
  std::ranges::ends_with(begin1, end1, begin2, end2);
  // ...
}
{
  bidirectional_iterator<int*> begin1(a.begin());
  bidirectional_iterator<int*> end1(a.end());
  bidirectional_iterator<int*> begin2(p.begin());
  bidirectional_iterator<int*> end2(p.end());
  std::ranges::ends_with(begin1, end1, begin2, end2);
  // ...
}

[ZijunZhao]

Update benchmarks test

[ZijunZhao]

Update test

[var-const]

libcxx/benchmarks/algorithms/ranges_ends_with.bench.cpp

15

I tried out the benchmarks locally. After applying the fixes outlined above, I noticed a couple of interesting things:

1. Random access iterators end up being a little slower than bidirectional iterators, at least in my environment. This is because std::__equal_impl ends up being a little slower than std::ranges::__mismatch::__fn::__go for the same arguments. It looks like the combination of calling advance on __first1 (even though in this case it's a no-op) with the fact that equal checks __first1 == __last1 in the end inhibits some optimization. I'm reluctant to try to fix this, though, at least in this patch -- the difference is small and isn't really specific to ends_with; it might also be dependent on the compiler.

2. equal contains a powerful memcmp optimization for contiguous iterators but it doesn't get triggered currently. That's because ends_with wraps the predicate and the projections in a reference_wrapper, and the optimization only kicks in if (simplified):

__is_trivial_equality_predicate<_Pred, _Tp, _Up>::value && __is_identity<_Proj1>::value && __is_identity<_Proj2>::value

__is_trivial_equality_predicate recognizes ranges::equal_to as trivial, but not reference_wrapper<ranges::equal_to>, similarly for __is_identity.

There are a few potential solutions:

1. Modify these traits to recognize reference_wrapper.
2. Call an internal version of ranges::equal that takes functors by reference (needs to be written) or call std::__equal directly. It would also be necessary to duplicate the __unwrap_iter and __unwrap_range logic that's currently in ranges::equal.
3. Stop providing the guarantee that we never copy functors in algorithms.

I'm currently leaning towards option 1. @philnik Nikolas, what do you think?

22

Sorry, I miswrote the suggestion above, this should be

#include "test_iterators.h"

// ...

auto begin1 = random_access_iterator(a.begin());
// ...

std::random_access_iterator is a concept and as such it evaluates to a boolean. In other words, begin1, end1, begin2 and end2 end up being boolean variables, then we create zero- or one-element containers from those booleans (because they implicitly convert to integers, unfortunately), which means we ignore the size of state.range() generated by benchmark and always measure the same (meaningless) thing.

26

What we want to do is to test how the implementation of the algorithm treats different iterator categories, but at the same time we want to use the same underlying container type so that it's not a factor in our measurement (otherwise, if we compare e.g. a vector against a list, it's impossible to say how much of the performance difference is due to random-access iterator optimizations in ends_with and how much is due to the fact that vector is much more cache-friendly). Since we can make the iterator category more limited (e.g. turn a bidirectional iterator into a forward iterator) but not vice versa, that means we need to use a container with the most powerful iterator category -- so it would have to be a vector, an array or a built-in array.

If we use a container, wrap its iterators but then create a new container from those iterators, it negates the idea because the new container would have the same iterator category as before. E.g. if we create a list, wrap its (bidirectional) iterators into forward iterators, then create a new list from those forward iterators, the new list once again would have bidirectional iterators, completely negating our wrapping. In other words, you should just do

benchmark::DoNotOptimize(std::ranges::ends_with(begin1, end1, begin2, end2));

40

We would also want to test with contiguous_iterators and forward_iterators.

[philnik]

libcxx/benchmarks/algorithms/ranges_ends_with.bench.cpp

15

I think both (1) and (3) make sense. (1) Seems like a nice generalizations, but I doubt it will make much of a difference 99% of the time, and (3) seems like it simplifies some things quite a bit. I also have the suspicion that all the references in the algorithms might inhibit optimizations, but I didn't test that yet. I also don't expect most predicates and projections to be non-trivial, making this an optimization that only applies very rarely, and potentially a pessimization in some cases (although that's just conjecture on my part).

[ZijunZhao]

Update benchmark tests

[var-const]

Thank you for working on this and addressing all the feedback! LGTM with a green CI (let me know if you need any help with CI failures).

I don't know if you have commit permissions -- if not, I can help merge the patch (please provide the name and the email address to use for the author field in that case).

libcxx/benchmarks/algorithms/ranges_ends_with.bench.cpp

15

@philnik Thanks!

@ZijunZhao As discussed offline, let's implement (1) in a follow-up.

15

Nit: I don't think this header is used.

43

Nit: please add a blank line after this line.

68

Nit: extraneous blank line (here and in some other functions in this file).

95

Nit: please add a blank line after this line for consistency with other functions in this file.

[ZijunZhao]

1. add some headers in ranges_ends_with.h
2. fix nits: add/remove some blank lines
3. remove useless headers in ranges.ends_with.pass.cpp

[ZijunZhao]

Reformat

[ZijunZhao]

remove redundant headers to avoid transitive includes

[ZijunZhao]

Remove unused header files

[ZijunZhao]

Modify algorithm.inc to pass the presubmit

[ZijunZhao]

Update tests

[ZijunZhao]

change #if TEST_STD_VER > 20 to #if TEST_STD_VER >= 23

[ZijunZhao]

Correct the #if condition for ranges::starts_with() and ranges::ends_with()

[ZijunZhao]

Update algorithm.inc to pass prechecks