[libc++] Optimize for_each for segmented iterators

[philnik]

Summary

---------------------------------------------------
Benchmark                       old             new
---------------------------------------------------
bm_for_each/1               3.00 ns         2.98 ns
bm_for_each/2               4.53 ns         4.57 ns
bm_for_each/3               5.82 ns         5.82 ns
bm_for_each/4               6.94 ns         6.91 ns
bm_for_each/5               7.55 ns         7.75 ns
bm_for_each/6               7.06 ns         7.45 ns
bm_for_each/7               6.69 ns         7.14 ns
bm_for_each/8               6.86 ns         4.06 ns
bm_for_each/16              11.5 ns         5.73 ns
bm_for_each/64              43.7 ns         4.06 ns
bm_for_each/512              356 ns         7.98 ns
bm_for_each/4096            2787 ns         53.6 ns
bm_for_each/32768          20836 ns          438 ns
bm_for_each/262144        195362 ns         4945 ns
bm_for_each/1048576       685482 ns        19822 ns

[philnik]

Benchmark numbers:

---------------------------------------------------
Benchmark                       old             new
---------------------------------------------------
bm_for_each/1               3.00 ns         2.98 ns
bm_for_each/2               4.53 ns         4.57 ns
bm_for_each/3               5.82 ns         5.82 ns
bm_for_each/4               6.94 ns         6.91 ns
bm_for_each/5               7.55 ns         7.75 ns
bm_for_each/6               7.06 ns         7.45 ns
bm_for_each/7               6.69 ns         7.14 ns
bm_for_each/8               6.86 ns         4.06 ns
bm_for_each/16              11.5 ns         5.73 ns
bm_for_each/64              43.7 ns         4.06 ns
bm_for_each/512              356 ns         7.98 ns
bm_for_each/4096            2787 ns         53.6 ns
bm_for_each/32768          20836 ns          438 ns
bm_for_each/262144        195362 ns         4945 ns
bm_for_each/1048576       685482 ns        19822 ns

I think the benchmark numbers aren't in any way surprising (we can get similar numbers with similar patches for most algorithms). This patch is more focused on the actual implementation. This is only optimized for C++20-and-later as-is. The question is whether that is OK for the library. The implementation is a lot easier, but we essentially say "use the latest C++ version or you don't get nice optimizations".

[ldionne]

LGTM but I'd like to see again with the test.

libcxx/benchmarks/algorithms/for_each.bench.cpp

14

libcxx/include/__algorithm/for_each.h

1

Can we have a test that checks specifically std::for_each on a segmented iterator. Basically we can have a libcxx/test/std test that runs for_each on deque and explains that we're testing the interaction of for_each with segmented iterators. It'll be valid (but perhaps not *relevant*) for all implementations.

38

I am fine with only optimizing this in C++20. This is QOI and we should be pushing folks towards newer Standards.

[Mordante]

In D151274#4366483, @philnik wrote:

Benchmark numbers:

Can you put these numbers in the commit message? That way we can be certain they will be preserved even when Phab ever disappears.

This is only optimized for C++20-and-later as-is. The question is whether that is OK for the library. The implementation is a lot easier, but we essentially say "use the latest C++ version or you don't get nice optimizations".

I'm totally fine with that. If it's easy to backport the changes without ugly code that would be great, otherwise let's not do it.
In 10 years we still need to maintain this code and most users have probably moved to C++20 or later.

libcxx/include/__algorithm/for_each.h

38

+1

43

Seems this answers my lambda question in the other review ;-)

48

[philnik]

Address comments

[Mordante]

I'm happy, but since Louis had some remarks I leave the final approval to him.

[ldionne]

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each.pass.cpp

51

There's a lot of logic crammed into the same expression otherwise.

[philnik]

• Rebased
• Fix formatting

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Rebased

[sberg]

this causes

$ cat test.cc
#include <algorithm>
#include <deque>
void f(std::deque<int> & v) {
    std::for_each(v.begin(), v.end(), [&](int) {});
}

$ clang++ -std=c++20 -fsyntax-only test.cc
In file included from test.cc:1:
In file included from ~/llvm/inst/bin/../include/c++/v1/algorithm:1758:
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:39:12: error: object of type '(lambda at test.cc:4:39)' cannot be assigned because its copy assignment operator is implicitly deleted
   39 |     __func = std::for_each(__lfirst, __llast, std::move(__func));
      |            ^
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each_segment.h:35:5: note: in instantiation of function template specialization 'std::for_each(std::__deque_iterator<int, int *, int &, int **, long>, std::__deque_iterator<int, int *, int &, int **, long>, (lambda at test.cc:4:39))::(anonymous class)::operator()<int *, int *>' requested here
   35 |     __func(_Traits::__local(__first), _Traits::__local(__last));
      |     ^
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:8: note: in instantiation of function template specialization 'std::__for_each_segment<std::__deque_iterator<int, int *, int &, int **, long>, (lambda at ~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:44)>' requested here
   38 |   std::__for_each_segment(__first, __last, [&](auto __lfirst, auto __llast) {
      |        ^
test.cc:4:10: note: in instantiation of function template specialization 'std::for_each<std::__deque_iterator<int, int *, int &, int **, long>, (lambda at test.cc:4:39)>' requested here
    4 |     std::for_each(v.begin(), v.end(), [&](int) {});
      |          ^
test.cc:4:39: note: lambda expression begins here
    4 |     std::for_each(v.begin(), v.end(), [&](int) {});
      |                                       ^
In file included from test.cc:1:
In file included from ~/llvm/inst/bin/../include/c++/v1/algorithm:1743:
In file included from ~/llvm/inst/bin/../include/c++/v1/__algorithm/copy.h:13:
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each_segment.h:40:3: error: no matching function for call to object of type '(lambda at ~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:44)'
   40 |   __func(_Traits::__local(__first), _Traits::__end(__sfirst));
      |   ^~~~~~
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:8: note: in instantiation of function template specialization 'std::__for_each_segment<std::__deque_iterator<int, int *, int &, int **, long>, (lambda at ~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:44)>' requested here
   38 |   std::__for_each_segment(__first, __last, [&](auto __lfirst, auto __llast) {
      |        ^
test.cc:4:10: note: in instantiation of function template specialization 'std::for_each<std::__deque_iterator<int, int *, int &, int **, long>, (lambda at test.cc:4:39)>' requested here
    4 |     std::for_each(v.begin(), v.end(), [&](int) {});
      |          ^
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:44: note: candidate template ignored: substitution failure [with __lfirst:auto = __local_iterator, __llast:auto = __local_iterator]
   38 |   std::__for_each_segment(__first, __last, [&](auto __lfirst, auto __llast) {
      |                                            ^
In file included from test.cc:1:
In file included from ~/llvm/inst/bin/../include/c++/v1/algorithm:1743:
In file included from ~/llvm/inst/bin/../include/c++/v1/__algorithm/copy.h:13:
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each_segment.h:44:5: error: no matching function for call to object of type '(lambda at ~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:44)'
   44 |     __func(_Traits::__begin(__sfirst), _Traits::__end(__sfirst));
      |     ^~~~~~
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:44: note: candidate template ignored: substitution failure [with __lfirst:auto = __local_iterator, __llast:auto = __local_iterator]
   38 |   std::__for_each_segment(__first, __last, [&](auto __lfirst, auto __llast) {
      |                                            ^
In file included from test.cc:1:
In file included from ~/llvm/inst/bin/../include/c++/v1/algorithm:1743:
In file included from ~/llvm/inst/bin/../include/c++/v1/__algorithm/copy.h:13:
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each_segment.h:48:3: error: no matching function for call to object of type '(lambda at ~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:44)'
   48 |   __func(_Traits::__begin(__sfirst), _Traits::__local(__last));
      |   ^~~~~~
~/llvm/inst/bin/../include/c++/v1/__algorithm/for_each.h:38:44: note: candidate template ignored: substitution failure [with __lfirst:auto = __local_iterator, __llast:auto = __local_iterator]
   38 |   std::__for_each_segment(__first, __last, [&](auto __lfirst, auto __llast) {
      |                                            ^
4 errors generated.

[ldionne]

We seem to be using copy assignment of the function object but that isn't a requirement of the algorithm. I think this problem is on our side. @philnik we could do something like:

diff --git a/libcxx/include/__algorithm/for_each.h b/libcxx/include/__algorithm/for_each.h
index 5e273cf1b9b1..5afd25b337e7 100644
--- a/libcxx/include/__algorithm/for_each.h
+++ b/libcxx/include/__algorithm/for_each.h
@@ -35,10 +35,11 @@ template <class _SegmentedIterator, class _Function>
   requires __is_segmented_iterator<_SegmentedIterator>::value
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Function
 for_each(_SegmentedIterator __first, _SegmentedIterator __last, _Function __func) {
+  std::__movable_box<_Function> __tmp(in_place, std::move(__func));
   std::__for_each_segment(__first, __last, [&](auto __lfirst, auto __llast) {
-    __func = std::for_each(__lfirst, __llast, std::move(__func));
+    __tmp = std::__movable_box<_Function>(in_place, std::for_each(__lfirst, __llast, std::move(*__tmp)));
   });
-  return __func;
+  return std::move(*__tmp);
 }
 #endif // _LIBCPP_STD_VER >= 20

[ldionne]

I just spoke with @philnik and we're going to revert this patch until we land D151629 and apply something like the proposed diff above. We'll also add a test to make sure we'd catch this in the future.

[ldionne]

libcxx/include/__algorithm/for_each.h

38

Let's just do it for C++ >= 23 since it will require __movable_box, which is C++23.

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each.pass.cpp

2

Not attached: We need to add a test for std::for_each where we pass a function object that isn't copy-constructible. They are supposed to work. They need to be move constructible though.

[philnik]

Address comments

[ldionne]

I think this will be LGTM after comments, but I'd like to take a quick look again.

libcxx/docs/ReleaseNotes/18.rst

56–57

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each.pass.cpp

13

This seems wrong? It was there before, but it still seems incorrect.

14

41

We need tests with 0 and 1 length sequences at the very least.

69–73

Same here, we should test a couple of different sizes of deque, in particular around the size of underlying segments. And 0 and 1.

libcxx/test/tools/clang_tidy_checks/CMakeLists.txt

12 ↗

(On Diff #557520)

I don't think this should be part of this patch.

[philnik]

Address comments

[ldionne]

libcxx/include/__algorithm/for_each.h

42

We need to test constexpr for segmented iterators (especially since we've had bugs related to that recently).

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each.pass.cpp

76

I think this range-based for-loop will break your C++03 CI run.

[philnik]

Address comments

[ldionne]

LGTM once CI is green. Thanks!

[philnik]

Try to fix CI

[philnik]

Rebased

[philnik]

Try to fix CI

[philnik]

Rebased

libcxx/benchmarks/CMakeLists.txt

 #==============================================================================
 # Register Benchmark tests
 #==============================================================================
 set(BENCHMARK_TESTS
     algorithms.partition_point.bench.cpp
     algorithms/count.bench.cpp
     algorithms/equal.bench.cpp
     algorithms/find.bench.cpp
+    algorithms/for_each.bench.cpp
     algorithms/lower_bound.bench.cpp
     algorithms/make_heap.bench.cpp
     algorithms/make_heap_then_sort_heap.bench.cpp
     algorithms/min.bench.cpp
     algorithms/min_max_element.bench.cpp
     algorithms/pop_heap.bench.cpp
     algorithms/pstl.stable_sort.bench.cpp
     algorithms/push_heap.bench.cpp

libcxx/benchmarks/algorithms/for_each.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+#include <benchmark/benchmark.h>
+#include <deque>
+
+static void bm_deque_for_each(benchmark::State& state) {
+  std::deque<char> vec1(state.range(), '1');
+  for (auto _ : state) {
+    benchmark::DoNotOptimize(vec1);
+    benchmark::DoNotOptimize(
+        std::for_each(vec1.begin(), vec1.end(), [](char& v) { v = std::clamp(v, (char)10, (char)100); }));
+  }
+}
+BENCHMARK(bm_deque_for_each)->DenseRange(1, 8)->Range(16, 1 << 20);
+
+BENCHMARK_MAIN();

libcxx/docs/ReleaseNotes/18.rst

 - P2538R1 - ADL-proof ``std::projected``
 - P2614R2 - Deprecate ``numeric_limits::has_denorm``
 - P0053R7 - C++ Synchronized Buffered Ostream (in the experimental library)
 
 
 Improvements and New Features
 -----------------------------
 
 - ``std::ranges::count`` is now optimized for ``vector<bool>::iterator``, which
   can lead up to 350x performance improvements.
 
+- ``std::for_each`` has been optimized for segmented iterators like ``std::deque::iterator`` in C++23 and
+  later, which can lead up to 40x performance improvements.
+
 - The library now provides several hardening modes under which common cases of library undefined behavior will be turned
   into a reliable program termination. The ``fast`` hardening mode enables a set of security-critical checks with
   minimal runtime overhead; the ``extensive`` hardening mode additionally enables relatively cheap checks that catch
   common logic errors but aren't necessarily security-critical; and the ``debug`` hardening mode enables all available
   checks, some of which might be very expensive. Vendors can configure which hardening mode is enabled by default with
   the ``LIBCXX_HARDENING_MODE`` variable at CMake configuration time. Users can control which hardening mode is enabled
   on a per translation unit basis using the ``_LIBCPP_HARDENING_MODE`` macro. See :ref:`the hardening documentation
   <using-hardening-modes>` for more details.

libcxx/include/__algorithm/for_each.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_FOR_EACH_H
 #define _LIBCPP___ALGORITHM_FOR_EACH_H
 
+#include <__algorithm/for_each_segment.h>
 #include <__config>
+#include <__iterator/segmented_iterator.h>
+#include <__ranges/movable_box.h>
+#include <__type_traits/enable_if.h>
+#include <__utility/in_place.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _InputIterator, class _Function>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _Function for_each(_InputIterator __first,
-                                                                                  _InputIterator __last,
-                                                                                  _Function __f) {
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Function
+for_each(_InputIterator __first, _InputIterator __last, _Function __f) {
   for (; __first != __last; ++__first)
     __f(*__first);
   return __f;
 }
 
+// __movable_box is available in C++20, but is actually a copyable-box, so optimization is only correct in C++23
+#if _LIBCPP_STD_VER >= 23
+template <class _SegmentedIterator, class _Function>
+  requires __is_segmented_iterator<_SegmentedIterator>::value
+_LIBCPP_HIDE_FROM_ABI constexpr _Function
+for_each(_SegmentedIterator __first, _SegmentedIterator __last, _Function __func) {
+  ranges::__movable_box<_Function> __wrapped_func(in_place, std::move(__func));
+  std::__for_each_segment(__first, __last, [&](auto __lfirst, auto __llast) {
+    __wrapped_func =
+        ranges::__movable_box<_Function>(in_place, std::for_each(__lfirst, __llast, std::move(*__wrapped_func)));
+  });
+  return std::move(*__wrapped_func);
+}
+#endif // _LIBCPP_STD_VER >= 23
+
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP___ALGORITHM_FOR_EACH_H

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template<InputIterator Iter, Callable<auto, Iter::reference> Function>
+//   constexpr Function   // constexpr since C++20
+//   for_each(Iter first, Iter last, Function f);
+
+#include <algorithm>
+#include <cassert>
+#include <deque>
+#if __has_include(<ranges>)
+#  include <ranges>
+#endif
+#include <vector>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+struct for_each_test {
+  TEST_CONSTEXPR for_each_test(int c) : count(c) {}
+
+  // for_each functors only have to be move constructible
+  for_each_test(const for_each_test&)            = delete;
+  for_each_test(for_each_test&&)                 = default;
+  for_each_test& operator=(const for_each_test&) = delete;
+  for_each_test& operator=(for_each_test&&)      = delete;
+
+  int count;
+  TEST_CONSTEXPR_CXX14 void operator()(int& i) {
+    ++i;
+    ++count;
+  }
+};
+
+struct Test {
+  template <class Iter>
+  TEST_CONSTEXPR_CXX20 void operator()() {
+    int sizes[] = {0, 1, 6};
+    for (const int size : sizes) {
+      int ia[]        = {0, 1, 2, 3, 4, 5};
+      for_each_test f = std::for_each(Iter(ia), Iter(ia + size), for_each_test(0));
+      assert(f.count == size);
+      for (int i = 0; i < size; ++i)
+        assert(ia[i] == static_cast<int>(i + 1));
+    }
+  }
+};
+
+TEST_CONSTEXPR_CXX20 bool test() {
+  types::for_each(types::cpp17_input_iterator_list<int*>(), Test());
+
+  // TODO: Remove the `_LIBCPP_ENABLE_EXPERIMENTAL` check once we have the FTM guarded or views::join isn't
+  // experimental anymore
+#if TEST_STD_VER >= 20 && defined(_LIBCPP_ENABLE_EXPERIMENTAL)
+  { // Make sure that the segmented iterator optimization works during constant evaluation
+    std::vector<std::vector<int>> vecs = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
+    auto v                             = std::views::join(vecs);
+    std::for_each(v.begin(), v.end(), [i = 0](int& a) mutable { assert(a == ++i); });
+  }
+#endif
+
+  return true;
+}
+
+struct deque_test {
+  std::deque<int>* d_;
+  int* i_;
+
+  deque_test(std::deque<int>& d, int& i) : d_(&d), i_(&i) {}
+
+  void operator()(int& v) {
+    assert(&(*d_)[*i_] == &v);
+    ++*i_;
+  }
+};
+
+int main(int, char**) {
+  test();
+#if TEST_STD_VER >= 20
+  static_assert(test());
+#endif
+
+  // check that segmented iterators work properly
+  int sizes[] = {0, 1, 2, 1023, 1024, 1025, 2047, 2048, 2049};
+  for (const int size : sizes) {
+    std::deque<int> d(size);
+    int index = 0;
+
+    std::for_each(d.begin(), d.end(), deque_test(d, index));
+  }
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/test.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-// <algorithm>
-
-// template<InputIterator Iter, Callable<auto, Iter::reference> Function>
-//   requires CopyConstructible<Function>
-//   constexpr Function   // constexpr after C++17
-//   for_each(Iter first, Iter last, Function f);
-
-#include <algorithm>
-#include <cassert>
-
-#include "test_macros.h"
-#include "test_iterators.h"
-
-#if TEST_STD_VER > 17
-TEST_CONSTEXPR bool test_constexpr() {
-    int ia[] = {1, 3, 6, 7};
-    int expected[] = {3, 5, 8, 9};
-
-    std::for_each(std::begin(ia), std::end(ia), [](int &a) { a += 2; });
-    return std::equal(std::begin(ia), std::end(ia), std::begin(expected))
-        ;
-    }
-#endif
-
-struct for_each_test
-{
-    for_each_test(int c) : count(c) {}
-    int count;
-    void operator()(int& i) {++i; ++count;}
-};
-
-int main(int, char**)
-{
-    int ia[] = {0, 1, 2, 3, 4, 5};
-    const unsigned s = sizeof(ia)/sizeof(ia[0]);
-    for_each_test f = std::for_each(cpp17_input_iterator<int*>(ia),
-                                    cpp17_input_iterator<int*>(ia+s),
-                                    for_each_test(0));
-    assert(f.count == s);
-    for (unsigned i = 0; i < s; ++i)
-        assert(ia[i] == static_cast<int>(i+1));
-
-#if TEST_STD_VER > 17
-    static_assert(test_constexpr());
-#endif
-
-  return 0;
-}

libcxx/utils/data/ignore_format.txt

 libcxx/include/__algorithm/binary_search.h
 libcxx/include/__algorithm/comp_ref_type.h
 libcxx/include/__algorithm/copy_backward.h
 libcxx/include/__algorithm/copy_if.h
 libcxx/include/__algorithm/copy_move_common.h
 libcxx/include/__algorithm/copy_n.h
 libcxx/include/__algorithm/equal.h
 libcxx/include/__algorithm/equal_range.h
 libcxx/include/__algorithm/fill.h
 libcxx/include/__algorithm/fill_n.h
 libcxx/include/__algorithm/find_end.h
 libcxx/include/__algorithm/find_first_of.h
-libcxx/include/__algorithm/for_each.h
 libcxx/include/__algorithm/for_each_n.h
 libcxx/include/__algorithm/generate.h
 libcxx/include/__algorithm/generate_n.h
 libcxx/include/__algorithm/half_positive.h
 libcxx/include/__algorithm/includes.h
 libcxx/include/__algorithm/in_found_result.h
 libcxx/include/__algorithm/in_fun_result.h
 libcxx/include/__algorithm/in_in_out_result.h

 libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/find_first_of_pred.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if_not.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each_n.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/ranges.for_each_n.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/ranges.for_each.pass.cpp
-libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/test.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/is_permutation.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/is_permutation_pred.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/none_of.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/ranges.none_of.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search.pass.cpp
 libcxx/test/std/algorithms/alg.nonmodifying/alg.search/search_n.pass.cpp