[libc++] Unroll loop in std::find_if and define other std::find variants in terms of it

[ldionne]

Summary

It was reported that libstdc++'s std::find was considerably faster than
libc++'s std::find in some cases. This was tracked down to some manual
loop unrolling being done in libstdc++'s implementation.

This patch modifies std::find_if to perform such loop unrolling, and
also modifies std::find and std::find_if_not to call std::find_if
as an implementation detail so they can take advantage of any optimization
we might do in std::find_if.

As a fly-by fix, this commit significantly improves the test coverage for
the three std::find_XXXX algorithms, which was previously insufficient to
find issues in this patch.

rdar://72436671

[ldionne]

I normally push back against this sort of manual "optimization", but in this case it seems to really make a difference for the case I was told about. We can have a discussion about whether this is an actual improvement. If we end up not taking the change, I'll at least take the test changes.

[Mordante]

In D112152#3075523, @ldionne wrote:

I normally push back against this sort of manual "optimization", but in this case it seems to really make a difference for the case I was told about. We can have a discussion about whether this is an actual improvement. If we end up not taking the change, I'll at least take the test changes.

I also would prefer a compiler can do this kind of transformation when it's beneficial.
Can you add a benchmark so we can measure the performance gains and code size changes?

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find_if.pass.cpp

62

Since the algorithm is no longer straight forward I think it would be good to validate the number of times the predicate is evaluated. Just to make sure we didn't accidentally increase the number of evaluations.

[• Quuxplusone]

libcxx/include/__algorithm/find.h

1

High-level motivation question: This performance difference that you see, is it only at -O0? I would hope that the compiler does the obvious loop unrolling at -O2 at least. I'd also be interested in seeing a Godbolt link of libc++ versus libstdc++, and perhaps even some new benchmark as part of the PR.

29

This flips the order from *first == value to value == *first. I think we're within our rights to do that, technically; but it feels gratuitous.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find_if.pass.cpp

62

+1, I think your current implementation has 4 instances of break that should be return __first, and this causes 1 extra evaluation of __pred in most cases.

[Mordante]

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find_if.pass.cpp

62

I too wondered about why not a return instead of a break. Initially I also expected one extra evaluation, but upon further studying the algorithm I _think_ it's correct. switch (__last - __first) should be larger than 3 when the for loop exits in one of the breaks.

[lebedev.ri]

FWIW, this isn't my prime areal, but i can't not comment here.
Like stated in previous review, i think this is a pretty bad idea.
Here's an incomplete list of reasons:

1. This is clearly a compiler deficiency. Fixing it will benefit everyone
2. How do you know that unrolling is always beneficial? What about -Os/-Oz? What about in-order CPU's? Why unroll 4x specifically?
3. What happens with more complex predicates? The old code had a single call, now you have how many? Will this affect (prevent) inlining in some cases?
4. The old code seems straight-forward to auto-vectorize (for certain predicates), new one, uhh.

[ldionne]

Re: all

Thanks a lot for chiming in. Morally, I share everybody's views here -- this is a compiler issue and we shouldn't be working around it in the library. This was reported to me and @fhahn asked me to look into whether it might be possible to implement this in the library. So I did, but I agree I'd rather not check this in if the compiler can be fixed instead. I'll let Florian explain what a compiler fix would involve.

libcxx/include/__algorithm/find.h

1

This is the godbolt: https://clang.godbolt.org/z/Mccs1v7Tv

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find_if.pass.cpp

62

Yeah, I could return instead of break -- but I'm pretty sure the current algorithm is correct. We'll find out when I add tests counting the number of times the predicate is called -- that's a good suggestion whatever we end up doing.

[Mordante]

If the compiler isn't smart enough, how about giving it a hint?
https://clang.llvm.org/docs/LanguageExtensions.html#loop-unrolling
Adding #pragma clang loop unroll_count(4) to our find causes the loop to unroll
https://clang.godbolt.org/z/687793Te4

[ldionne]

In D112152#3078415, @Mordante wrote:

If the compiler isn't smart enough, how about giving it a hint?
https://clang.llvm.org/docs/LanguageExtensions.html#loop-unrolling
Adding #pragma clang loop unroll_count(4) to our find causes the loop to unroll
https://clang.godbolt.org/z/687793Te4

Interesting suggestion actually! The correct comparison would be this: https://clang.godbolt.org/z/PETM1TvrG

I'll wait for @fhahn to provide more context about why we'd want to unroll in the library at all, and then I can apply your suggestions if we decide to move forward.

[fhahn]

In D112152#3078256, @ldionne wrote:

Re: all

Thanks a lot for chiming in. Morally, I share everybody's views here -- this is a compiler issue and we shouldn't be working around it in the library. This was reported to me and @fhahn asked me to look into whether it might be possible to implement this in the library. So I did, but I agree I'd rather not check this in if the compiler can be fixed instead. I'll let Florian explain what a compiler fix would involve.

I think the main problem with optimising the code in LLVM at the moment is that we lose the information that all elements between begin() and end() are dereferenceable (simplified IR shown below), e.g. the IR function could get passed a garbage end pointer and only exit via the early exit. In the original C++ source, we have stronger guarantees allowing for better optimisations.

Ideally we would vectorise the search loop, but I don't think that's possible without more information in the IR. While I agree it is unfortunate that the IR seems to be missing crucial information and the compiler should do better, I don't think there's an easy fix for now.

I'd like for the Clang + libc++ package to provide the best performance for our users and surgically modifying the libc++ implementation might be the easiest first step in that direction. As @ldionne mentioned, we encountered use cases where this difference in std::find implementation is causing a 10% performance difference compared to GCC+libstdc++ for a largish application (*not* a std::find specific micro-benchmark).

As reviewers already pointed out, if we go with a source modification, the implementation should probably only kick in for data types that can be checked cheaply (e.g. integers, floats and pointers).

I am definitely also interested in working towards a way to provide deferenceability info for the begin() & end() range. (If there's already a way I missed, please let me know :)).

define i8** @src(i8** %begin, i8** %end, i8* %tgt) {
entry:
  %cmp.i.i.not8.i = icmp eq i8** %begin, %end
  br i1 %cmp.i.i.not8.i, label %exit, label %header

header:
  %ptr.iv = phi i8** [ %ptr.iv.next, %latch ], [ %begin, %entry ]
  %lv = load i8*, i8** %ptr.iv, align 8
  %cmp = icmp eq i8* %lv, %tgt
  br i1 %cmp, label %exit, label %latch

latch:
  %ptr.iv.next = getelementptr inbounds i8*, i8** %ptr.iv.1, i64 1
  %cmp.i.i.not.i = icmp eq i8** %ptr.iv.next, %end
  br i1 %cmp.i.i.not.i, label %exit, label %header

exit:
  %res.lcssa = phi i8** [ %begin, %entry ], [ %end, %latch ], [ %ptr.iv, %header ]
  ret i8** %res.lcssa
}

I also took a stab at adding a first set of benchmarks to libcxx/benchmarks/algorithms.bench.cpp , but something is not quite right I think. I'm not very familiar with the libc++ benchmarking system, so if anybody can spot any issues, please let me know.

diff --git a/libcxx/benchmarks/algorithms.bench.cpp b/libcxx/benchmarks/algorithms.bench.cpp
index 564d89d659cb..f0e610df6ba0 100644
--- a/libcxx/benchmarks/algorithms.bench.cpp
+++ b/libcxx/benchmarks/algorithms.bench.cpp
@@ -309,6 +309,48 @@ struct PopHeap {
   };
 };

+template <class ValueType, class Order>
+struct FindMid {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
+      auto I = std::find(Copy.begin(), Copy.end(), Copy[Copy.size() / 2]);
+      // Try to prevent the compiler from optimizing out std::find.
+      benchmark::DoNotOptimize(I);
+      benchmark::DoNotOptimize(Copy);
+      std::swap(*I, *Copy.begin());
+    });
+  }
+
+  bool skip() const { return Order() == ::Order::Heap; }
+
+  std::string name() const {
+    return "BM_FindMid" + ValueType::name() + Order::name() + "_" + std::to_string(Quantity);
+  };
+};
+
+template <class ValueType, class Order>
+struct FindEnd {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
+      auto I = std::find(Copy.begin(), Copy.end(), Copy.back());
+      // Try to prevent the compiler from optimizing out std::find.
+      benchmark::DoNotOptimize(I);
+      benchmark::DoNotOptimize(Copy);
+      std::swap(*I, *Copy.begin());
+    });
+  }
+
+  bool skip() const { return Order() == ::Order::Heap; }
+
+  std::string name() const {
+    return "BM_FindEnd" + ValueType::name() + Order::name() + "_" + std::to_string(Quantity);
+  };
+};
+
 } // namespace

 int main(int argc, char** argv) {
@@ -333,5 +375,7 @@ int main(int argc, char** argv) {
       Quantities);
   makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities);
   makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities);
+  makeCartesianProductBenchmark<FindMid, AllValueTypes, AllOrders>(Quantities);
+  makeCartesianProductBenchmark<FindEnd, AllValueTypes, AllOrders>(Quantities);
   benchmark::RunSpecifiedBenchmarks();
 }

[• Quuxplusone]

libcxx/include/__algorithm/find_if.h

90

Idle thought: @fhahn's commentary makes me realize that this PR is uncomfortably adjacent to the ongoing LWG(?) debate over

const char *first = "hello world";
const char *last = std::ranges::find(first, std::unreachable_sentinel, '\0');

The first question is, because unreachable_sentinel by definition can't be reached by incrementing first — does that mean that [first, unreachable_sentinel) lacks valid-range-ness in the same way as [first, first-1) or [first, nullptr) lacks valid-range-ness? in which case the above has UB?
Related but perhaps orthogonally, does that mean that find in practice should be allowed to read from elements beyond the match as long as they're still in the provided range, e.g.

int buf[100];  // uninitialized garbage
buf[0] = 42; buf[1] = 43; buf[2] = 44;
const char *last = std::find(buf, buf+100, 44);  // could this read buf[3] and thus have UB?

I think this specific PR isn't doing anything new and dangerous right now, but the commentary about "vectorization" and "information that pointers are dereferenceable" and "better optimization" seems very scary to me.

[fhahn]

libcxx/include/__algorithm/find_if.h

90

That's an interesting point! I naively assumed that both start and end iterators need to be referring to a valid range.

This observation is key to the vectorisation route I think, so if that won't hold in general then it might not be worth pursuing.

[ldionne]

I am going to abandon this patch. After consideration, I do not think that manually unrolling std::find_if like this is the way to go. Indeed, this leads to much worse code size and we really shouldn't be doing these kinds of optimizations manually, instead the compiler should learn to do it. Also, since this patch was created, we've improved std::find so that it calls memchr when it can, which is even better for both code size and speed.

I'll rebase the test improvements on top of main and upload a patch on GitHub though.

libcxx/include/__algorithm/find.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_FIND_H
 #define _LIBCPP___ALGORITHM_FIND_H
 
+#include <__algorithm/find_if.h>
 #include <__config>
+#include <__utility/forward.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Tp>
+struct __is_equal_to {
+  _Tp const& __value_;
+  template <class _Up>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
+  bool operator()(_Up&& __other) const {
+    return __value_ == _VSTD::forward<_Up>(__other);
+  }
+};
+
 template <class _InputIterator, class _Tp>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator
-find(_InputIterator __first, _InputIterator __last, const _Tp& __value_) {
-  for (; __first != __last; ++__first)
-    if (*__first == __value_)
-      break;
-  return __first;
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+_InputIterator find(_InputIterator __first, _InputIterator __last, const _Tp& __value) {
+  return _VSTD::find_if(__first, __last, __is_equal_to<_Tp>{__value});
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_FIND_H

libcxx/include/__algorithm/find_if.h

 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _InputIterator, class _Predicate>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator
-find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+_InputIterator __find_if_impl(_InputIterator __first, _InputIterator __last, _Predicate __pred,
+                              input_iterator_tag)
+{
   for (; __first != __last; ++__first)
     if (__pred(*__first))
       break;
   return __first;
 }
 
+template <class _RandomAccessIter, class _Predicate>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+_RandomAccessIter __find_if_impl(_RandomAccessIter __first, _RandomAccessIter __last, _Predicate __pred,
+                                 random_access_iterator_tag)
+{
+  using _Difference = typename iterator_traits<_RandomAccessIter>::difference_type;
+  _Difference __n = __last - __first;
+  for (_Difference __chunks = __n / 4; __chunks != 0; --__chunks) {
+    if (__pred(*__first))
+      break;
+    ++__first;
+
+    if (__pred(*__first))
+      break;
+    ++__first;
+
+    if (__pred(*__first))
+      break;
+    ++__first;
+
+    if (__pred(*__first))
+      break;
+    ++__first;
+  }
+
+  switch (__last - __first) {
+  case 3:
+    if (__pred(*__first))
+      break;
+    ++__first;
+    _LIBCPP_FALLTHROUGH();
+
+  case 2:
+    if (__pred(*__first))
+      break;
+    ++__first;
+    _LIBCPP_FALLTHROUGH();
+
+  case 1:
+    if (__pred(*__first))
+      break;
+    ++__first;
+    _LIBCPP_FALLTHROUGH();
+
+  default:
+    break;
+  }
+
+  return __first;
+}
+
+template <class _InputIterator, class _Predicate>
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
+  using _Tag = typename iterator_traits<_InputIterator>::iterator_category;
+  return _VSTD::__find_if_impl(__first, __last, __pred, _Tag());
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_FIND_IF_H

libcxx/include/__algorithm/find_if_not.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_FIND_IF_NOT_H
 #define _LIBCPP___ALGORITHM_FIND_IF_NOT_H
 
+#include <__algorithm/find_if.h>
 #include <__config>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Pred>
+struct __negate_pred {
+  _Pred& __pred_;
+  template <class _Tp>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
+  bool operator()(_Tp&& __value) const {
+    return !__pred_(_VSTD::forward<_Tp>(__value));
+  }
+};
+
 template <class _InputIterator, class _Predicate>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator
-find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
-  for (; __first != __last; ++__first)
-    if (!__pred(*__first))
-      break;
-  return __first;
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+_InputIterator find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
+  return _VSTD::find_if(__first, __last, __negate_pred<_Predicate>{__pred});
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_FIND_IF_NOT_H

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

 //   find(Iter first, Iter last, const T& value);
 
 #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, 5, 2, 4, 6};
-    int ib[] = {1, 2, 3, 4, 5, 6};
-    return    (std::find(std::begin(ia), std::end(ia), 5) == ia+2)
-           && (std::find(std::begin(ib), std::end(ib), 9) == ib+6)
-           ;
-    }
-#endif
+template <class Iter>
+TEST_CONSTEXPR_CXX17 void test_iter() {
+  int range[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 
-int main(int, char**)
+  // We don't find what we're looking for in the range
+  {
     {
-    int ia[] = {0, 1, 2, 3, 4, 5};
-    const unsigned s = sizeof(ia)/sizeof(ia[0]);
-    cpp17_input_iterator<const int*> r = std::find(cpp17_input_iterator<const int*>(ia),
-                                             cpp17_input_iterator<const int*>(ia+s), 3);
-    assert(*r == 3);
-    r = std::find(cpp17_input_iterator<const int*>(ia), cpp17_input_iterator<const int*>(ia+s), 10);
-    assert(r == cpp17_input_iterator<const int*>(ia+s));
+      Iter result = std::find(Iter(range), Iter(range), 0);
+      assert(result == Iter(range));
+    }
+    {
+      Iter result = std::find(Iter(range), Iter(std::end(range)), 999);
+      assert(result == Iter(std::end(range)));
+    }
+  }
+
+  // Tests with sub-ranges of various sizes
+  for (int size = 1; size != 10; ++size) {
+    for (int toFind = 0; toFind != size-1; ++toFind) {
+      Iter result = std::find(Iter(range), Iter(range + size), toFind);
+      assert(result == Iter(range + toFind));
+    }
+  }
+}
+
+TEST_CONSTEXPR_CXX17 bool test() {
+  test_iter<cpp17_input_iterator<int*>>();
+  test_iter<forward_iterator<int*>>();
+  test_iter<bidirectional_iterator<int*>>();
+  test_iter<random_access_iterator<int*>>();
+  return true;
+}
 
+int main(int, char**) {
+  test();
 #if TEST_STD_VER > 17
-    static_assert(test_constexpr());
+  static_assert(test());
 #endif
 
   return 0;
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find_if.pass.cpp

 
 #include <algorithm>
 #include <functional>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
-struct eq {
-    TEST_CONSTEXPR eq (int val) : v(val) {}
-    TEST_CONSTEXPR bool operator () (int v2) const { return v == v2; }
-    int v;
-    };
+struct EqualTo {
+  TEST_CONSTEXPR EqualTo(int val) : v(val) {}
+  TEST_CONSTEXPR bool operator()(int v2) const { return v == v2; }
 
-#if TEST_STD_VER > 17
-TEST_CONSTEXPR bool test_constexpr() {
-    int ia[] = {1, 3, 5, 2, 4, 6};
-    int ib[] = {1, 2, 3, 7, 5, 6};
-    eq c(4);
-    return    (std::find_if(std::begin(ia), std::end(ia), c) == ia+4)
-           && (std::find_if(std::begin(ib), std::end(ib), c) == ib+6)
-           ;
-    }
-#endif
+template <class Iter>
+TEST_CONSTEXPR_CXX17 void test_iter() {
+  int range[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 
-int main(int, char**)
+  // We don't find what we're looking for in the range
+  {
+    {
+      Iter result = std::find_if(Iter(range), Iter(range), EqualTo(0));
+      assert(result == Iter(range));
+    }
     {
-    int ia[] = {0, 1, 2, 3, 4, 5};
-    const unsigned s = sizeof(ia)/sizeof(ia[0]);
-    cpp17_input_iterator<const int*> r = std::find_if(cpp17_input_iterator<const int*>(ia),
-                                                cpp17_input_iterator<const int*>(ia+s),
-                                                eq(3));
-    assert(*r == 3);
-    r = std::find_if(cpp17_input_iterator<const int*>(ia),
-                     cpp17_input_iterator<const int*>(ia+s),
-                     eq(10));
-    assert(r == cpp17_input_iterator<const int*>(ia+s));
+      Iter result = std::find_if(Iter(range), Iter(std::end(range)), EqualTo(999));
+      assert(result == Iter(std::end(range)));
+    }
+  }
+
+  // Tests with sub-ranges of various sizes
+  for (int size = 1; size != 10; ++size) {
+    for (int toFind = 0; toFind != size-1; ++toFind) {
+      Iter result = std::find_if(Iter(range), Iter(range + size), EqualTo(toFind));
+      assert(result == Iter(range + toFind));
+    }
+  }
+}
+
+TEST_CONSTEXPR_CXX17 bool test() {
+  test_iter<cpp17_input_iterator<int*>>();
+  test_iter<forward_iterator<int*>>();
+  test_iter<bidirectional_iterator<int*>>();
+  test_iter<random_access_iterator<int*>>();
+  return true;
+}
 
+int main(int, char**) {
+  test();
 #if TEST_STD_VER > 17
-    static_assert(test_constexpr());
+  static_assert(test());
 #endif
 
   return 0;
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/find_if_not.pass.cpp

 
 #include <algorithm>
 #include <functional>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
-struct ne {
-    TEST_CONSTEXPR ne (int val) : v(val) {}
-    TEST_CONSTEXPR bool operator () (int v2) const { return v != v2; }
-    int v;
-    };
+struct DifferentFrom {
+  TEST_CONSTEXPR DifferentFrom(int val) : v(val) {}
+  TEST_CONSTEXPR bool operator()(int v2) const { return v != v2; }
 
-#if TEST_STD_VER > 17
-TEST_CONSTEXPR bool test_constexpr() {
-    int ia[] = {1, 3, 5, 2, 4, 6};
-    int ib[] = {1, 2, 3, 7, 5, 6};
-    ne c(4);
-    return    (std::find_if_not(std::begin(ia), std::end(ia), c) == ia+4)
-           && (std::find_if_not(std::begin(ib), std::end(ib), c) == ib+6)
-           ;
-    }
-#endif
+template <class Iter>
+TEST_CONSTEXPR_CXX17 void test_iter() {
+  int range[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 
-int main(int, char**)
+  // We don't find what we're looking for in the range
+  {
+    {
+      Iter result = std::find_if_not(Iter(range), Iter(range), DifferentFrom(0));
+      assert(result == Iter(range));
+    }
     {
-    int ia[] = {0, 1, 2, 3, 4, 5};
-    const unsigned s = sizeof(ia)/sizeof(ia[0]);
-    cpp17_input_iterator<const int*> r = std::find_if_not(cpp17_input_iterator<const int*>(ia),
-                                                    cpp17_input_iterator<const int*>(ia+s),
-                                                    ne(3));
-    assert(*r == 3);
-    r = std::find_if_not(cpp17_input_iterator<const int*>(ia),
-                         cpp17_input_iterator<const int*>(ia+s),
-                         ne(10));
-    assert(r == cpp17_input_iterator<const int*>(ia+s));
+      Iter result = std::find_if_not(Iter(range), Iter(std::end(range)), DifferentFrom(999));
+      assert(result == Iter(std::end(range)));
+    }
+  }
+
+  // Tests with sub-ranges of various sizes
+  for (int size = 1; size != 10; ++size) {
+    for (int toFind = 0; toFind != size-1; ++toFind) {
+      Iter result = std::find_if_not(Iter(range), Iter(range + size), DifferentFrom(toFind));
+      assert(result == Iter(range + toFind));
+    }
+  }
+}
+
+TEST_CONSTEXPR_CXX17 bool test() {
+  test_iter<cpp17_input_iterator<int*>>();
+  test_iter<forward_iterator<int*>>();
+  test_iter<bidirectional_iterator<int*>>();
+  test_iter<random_access_iterator<int*>>();
+  return true;
+}
 
+int main(int, char**) {
+  test();
 #if TEST_STD_VER > 17
-    static_assert(test_constexpr());
+  static_assert(test());
 #endif
 
   return 0;
 }