[libc++][PSTL] Move the already implemented functions to the new dispatching scheme

[philnik]

Some fixes

[ldionne]

libcxx/include/__algorithm/pstl_any_all_none_of.h

42–44

I think you can just use std::find_if(__policy, __first, __last, __pred) here.

libcxx/include/__algorithm/pstl_backend.h

45

Also all_of and none_of?

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

19–22

You should add cancel_execution here.

26

We should include any_of.

libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h

39

Missing __cpu_backend_tag

libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h

10

_LIBCPP___ALGORITHM_PSTL_BACKENDS_FIND_IF_H => _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FIND_IF_H

libcxx/include/__algorithm/pstl_fill.h

13

You also need __algorithm/fill.h right?

libcxx/include/__algorithm/pstl_find.h

19

I don't think you need that.

[philnik]

Address comments

[philnik]

Rebased

[philnik]

Fix some stuff

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Generate files

[philnik]

• Rebased
• Try to fix CI

[philnik]

Try to fix CI

[philnik]

Order CMakeLists.txt

[philnik]

Try to fix CI

[ldionne]

Nice! LGTM once CI is green.

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

20

libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h

39

We should have a test for the CPU backend that lists all the functions it expects to provide, and make sure that they can indeed be called. Otherwise, refactorings can produce stuff like:

template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class = enable_if_t<...> >

template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, enable_if_t<..., int> = 0>

template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, enable_if_t<...> >

which are never valid overloads. This is actually quite tricky and we've been bitten by this in the past. This can be done in a separate patch, but I think it's a requirement of this approach or else we risk introducing performance regressions.

[philnik]

Try to fix CI

libcxx/include/CMakeLists.txt

set(files
   __algorithm/partition_copy.h
   __algorithm/partition_point.h
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
   __algorithm/pstl_any_all_none_of.h
   __algorithm/pstl_backend.h
   __algorithm/pstl_backends/cpu_backend.h
   __algorithm/pstl_backends/cpu_backends/backend.h
+  __algorithm/pstl_backends/cpu_backends/find_if.h
+  __algorithm/pstl_backends/cpu_backends/fill.h
   __algorithm/pstl_backends/cpu_backends/for_each.h
   __algorithm/pstl_backends/cpu_backends/serial.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
set(files
   __pstl/internal/omp/parallel_transform_reduce.h
   __pstl/internal/omp/parallel_transform_scan.h
   __pstl/internal/omp/util.h
   __pstl/internal/parallel_backend.h
   __pstl/internal/parallel_backend_omp.h
   __pstl/internal/parallel_backend_serial.h
   __pstl/internal/parallel_backend_tbb.h
   __pstl/internal/parallel_backend_utils.h
-  __pstl/internal/parallel_impl.h
   __pstl/internal/unseq_backend_simd.h
   __pstl/internal/utils.h
   __pstl_algorithm
   __pstl_memory
   __pstl_numeric
   __random/bernoulli_distribution.h
   __random/binomial_distribution.h
   __random/cauchy_distribution.h

libcxx/include/__algorithm/pstl_any_all_none_of.h

 //===----------------------------------------------------------------------===//
 //
 // 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_PSTL_ANY_ALL_NONE_OF_H
 #define _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H
 
-#include <__algorithm/any_of.h>
+#include <__algorithm/pstl_find.h>
+#include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <__pstl/internal/parallel_impl.h>
-#include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class>
+void __pstl_any_of(); // declaration needed for the frontend dispatch below
+
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Predicate,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
 any_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    return std::__terminate_on_exception([&] {
-      return __pstl::__internal::__parallel_or(
-          __pstl::__internal::__par_backend_tag{},
-          __policy,
-          __first,
-          __last,
-          [&__policy, &__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            return std::any_of(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __pred);
-          });
-    });
-  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    return __pstl::__unseq_backend::__simd_or(__first, __last - __first, __pred);
-  } else {
-    return std::any_of(__first, __last, __pred);
-  }
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_any_of),
+      [&](_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+        return std::find_if(__policy, __first, __last, __pred) != __last;
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__pred));
 }
 
+template <class>
+void __pstl_all_of(); // declaration needed for the frontend dispatch below
+
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Pred,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
 all_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_all_of),
+      [&](_ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
         return !std::any_of(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) {
           return !__pred(__value);
         });
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__pred));
 }
 
+template <class>
+void __pstl_none_of(); // declaration needed for the frontend dispatch below
+
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Pred,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
 none_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_none_of),
+      [&](_ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
         return !std::any_of(__policy, __first, __last, __pred);
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__pred));
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H

libcxx/include/__algorithm/pstl_backend.h

 /*
 TODO: Documentation of how backends work
 
 A PSTL parallel backend is a tag type to which the following functions are associated, at minimum:
 
   template <class _ExecutionPolicy, class _Iterator, class _Func>
   void __pstl_for_each(_Backend, _ExecutionPolicy&&, _Iterator __first, _Iterator __last, _Func __f);
 
+  template <class _ExecutionPolicy, class _Iterator, class _Predicate>
+  _Iterator __pstl_find_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
+
 // TODO: Complete this list
 
 The following functions are optional but can be provided. If provided, they are used by the corresponding
 algorithms, otherwise they are implemented in terms of other algorithms. If none of the optional algorithms are
 implemented, all the algorithms will eventually forward to the basis algorithms listed above:
 
   template <class _ExecutionPolicy, class _Iterator, class _Size, class _Func>
   void __pstl_for_each_n(_Backend, _ExecutionPolicy&&, _Iterator __first, _Size __n, _Func __f);
 
+  template <class _ExecutionPolicy, class _Iterator, class _Predicate>
+  bool __pstl_any_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
+
+  template <class _ExecutionPolicy, class _Iterator, class _Predicate>
+  bool __pstl_all_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
+
+  template <class _ExecutionPolicy, class _Iterator, class _Predicate>
+  bool __pstl_none_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
+
+  template <class _ExecutionPolicy, class _Iterator, class _Tp>
+  void __pstl_fill(_Iterator __first, _Iterator __last, const _Tp& __value);
+
+  template <class _ExecutionPolicy, class _Iterator, class _SizeT, class _Tp>
+  void __pstl_fill_n(_Iterator __first, _SizeT __n, const _Tp& __value);
+
 // TODO: Complete this list
 
 */
 
 template <class _ExecutionPolicy>
 struct __select_backend;
 
 template <>

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

 
 #include <__config>
 
 /*
 
   // _Functor takes a subrange for [__first, __last) that should be executed in serial
   template <class _RandomAccessIterator, class _Functor>
   void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func);
 
+  // Cancel the execution of other jobs - they aren't needed anymore
+  void __cancel_execution();
+
   TODO: Document the parallel backend
 */
 
+#include <__algorithm/pstl_backends/cpu_backends/any_of.h>
+#include <__algorithm/pstl_backends/cpu_backends/fill.h>
+#include <__algorithm/pstl_backends/cpu_backends/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/for_each.h>
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h

+//===----------------------------------------------------------------------===//
+//
+// 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_PSTL_BACKENDS_CPU_BACKEND_ANY_OF_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_ANY_OF_H
+
+#include <__algorithm/any_of.h>
+#include <__algorithm/find_if.h>
+#include <__algorithm/pstl_backends/cpu_backends/backend.h>
+#include <__atomic/atomic.h>
+#include <__config>
+#include <__functional/operations.h>
+#include <__iterator/iterator_traits.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__utility/pair.h>
+#include <__utility/terminate_on_exception.h>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+template <class _Index, class _Brick>
+_LIBCPP_HIDE_FROM_ABI bool __parallel_or(_Index __first, _Index __last, _Brick __f) {
+  std::atomic<bool> __found(false);
+  __par_backend::__parallel_for(__first, __last, [__f, &__found](_Index __i, _Index __j) {
+    if (!__found.load(std::memory_order_relaxed) && __f(__i, __j)) {
+      __found.store(true, std::memory_order_relaxed);
+      __par_backend::__cancel_execution();
+    }
+  });
+  return __found;
+}
+
+// TODO: check whether __simd_first() can be used here
+template <class _Index, class _DifferenceType, class _Pred>
+_LIBCPP_HIDE_FROM_ABI bool __simd_or(_Index __first, _DifferenceType __n, _Pred __pred) noexcept {
+  _DifferenceType __block_size = 4 < __n ? 4 : __n;
+  const _Index __last          = __first + __n;
+  while (__last != __first) {
+    int32_t __flag = 1;
+    _PSTL_PRAGMA_SIMD_REDUCTION(& : __flag)
+    for (_DifferenceType __i = 0; __i < __block_size; ++__i)
+      if (__pred(*(__first + __i)))
+        __flag = 0;
+    if (!__flag)
+      return true;
+
+    __first += __block_size;
+    if (__last - __first >= __block_size << 1) {
+      // Double the block _Size.  Any unnecessary iterations can be amortized against work done so far.
+      __block_size <<= 1;
+    } else {
+      __block_size = __last - __first;
+    }
+  }
+  return false;
+}
+
+template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
+_LIBCPP_HIDE_FROM_ABI bool
+__pstl_any_of(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    return std::__terminate_on_exception([&] {
+      return std::__parallel_or(
+          __first, __last, [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
+            return std::__pstl_any_of<__remove_parallel_policy_t<_ExecutionPolicy>>(
+                __brick_first, __brick_last, __pred);
+          });
+    });
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    return std::__simd_or(__first, __last - __first, __pred);
+  } else {
+    return std::any_of(__first, __last, __pred);
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_ANY_OF_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h

+//===----------------------------------------------------------------------===//
+//
+// 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_PSTL_BACKENDS_CPU_BACKENDS_FILL_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FILL_H
+
+#include <__algorithm/fill.h>
+#include <__algorithm/pstl_backends/cpu_backends/backend.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__utility/terminate_on_exception.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Index, class _DifferenceType, class _Tp>
+_LIBCPP_HIDE_FROM_ABI _Index
+__simd_fill_n(_Index __first, _DifferenceType __n, const _Tp& __value) noexcept
+{
+    _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
+    _PSTL_PRAGMA_SIMD
+    for (_DifferenceType __i = 0; __i < __n; ++__i)
+        __first[__i] = __value;
+    return __first + __n;
+}
+
+template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
+_LIBCPP_HIDE_FROM_ABI void
+__pstl_fill(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    std::__terminate_on_exception([&] {
+      __par_backend::__parallel_for(
+          __first, __last, [&__value](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
+            std::__pstl_fill<__remove_parallel_policy_t<_ExecutionPolicy>>(__brick_first, __brick_last, __value);
+          });
+    });
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    std::__simd_fill_n(__first, __last - __first, __value);
+  } else {
+    std::fill(__first, __last, __value);
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FILL_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h

+//===----------------------------------------------------------------------===//
+//
+// 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_PSTL_BACKENDS_CPU_BACKENDS_FIND_IF_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FIND_IF_H
+
+#include <__algorithm/find_if.h>
+#include <__algorithm/pstl_backends/cpu_backends/backend.h>
+#include <__atomic/atomic.h>
+#include <__config>
+#include <__functional/operations.h>
+#include <__iterator/iterator_traits.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__utility/pair.h>
+#include <__utility/terminate_on_exception.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Index, class _Brick, class _Compare>
+_LIBCPP_HIDE_FROM_ABI _Index
+__parallel_find(_Index __first, _Index __last, _Brick __f, _Compare __comp, bool __b_first) {
+  typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType;
+  const _DifferenceType __n      = __last - __first;
+  _DifferenceType __initial_dist = __b_first ? __n : -1;
+  std::atomic<_DifferenceType> __extremum(__initial_dist);
+  // TODO: find out what is better here: parallel_for or parallel_reduce
+  __par_backend::__parallel_for(__first, __last, [__comp, __f, __first, &__extremum](_Index __i, _Index __j) {
+    // See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of
+    // why using a shared variable scales fairly well in this situation.
+    if (__comp(__i - __first, __extremum)) {
+      _Index __res = __f(__i, __j);
+      // If not '__last' returned then we found what we want so put this to extremum
+      if (__res != __j) {
+        const _DifferenceType __k = __res - __first;
+        for (_DifferenceType __old = __extremum; __comp(__k, __old); __old = __extremum) {
+          __extremum.compare_exchange_weak(__old, __k);
+        }
+      }
+    }
+  });
+  return __extremum != __initial_dist ? __first + __extremum : __last;
+}
+
+const std::size_t __lane_size = 64;
+
+template <class _Index, class _DifferenceType, class _Compare>
+_LIBCPP_HIDE_FROM_ABI _Index
+__simd_first(_Index __first, _DifferenceType __begin, _DifferenceType __end, _Compare __comp) noexcept {
+  // Experiments show good block sizes like this
+  const _DifferenceType __block_size                        = 8;
+  alignas(__lane_size) _DifferenceType __lane[__block_size] = {0};
+  while (__end - __begin >= __block_size) {
+    _DifferenceType __found = 0;
+    _PSTL_PRAGMA_SIMD_REDUCTION(| : __found) for (_DifferenceType __i = __begin; __i < __begin + __block_size; ++__i) {
+      const _DifferenceType __t = __comp(__first, __i);
+      __lane[__i - __begin]     = __t;
+      __found |= __t;
+    }
+    if (__found) {
+      _DifferenceType __i;
+      // This will vectorize
+      for (__i = 0; __i < __block_size; ++__i) {
+        if (__lane[__i]) {
+          break;
+        }
+      }
+      return __first + __begin + __i;
+    }
+    __begin += __block_size;
+  }
+
+  // Keep remainder scalar
+  while (__begin != __end) {
+    if (__comp(__first, __begin)) {
+      return __first + __begin;
+    }
+    ++__begin;
+  }
+  return __first + __end;
+}
+
+template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
+_LIBCPP_HIDE_FROM_ABI _ForwardIterator
+__pstl_find_if(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    return std::__terminate_on_exception([&] {
+      return std::__parallel_find(
+          __first,
+          __last,
+          [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
+            return std::__pstl_find_if<__remove_parallel_policy_t<_ExecutionPolicy>>(
+                __cpu_backend_tag{}, __brick_first, __brick_last, __pred);
+          },
+          less<>{},
+          true);
+    });
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    using __diff_t = __iter_diff_t<_ForwardIterator>;
+    return std::__simd_first(__first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) {
+      return __pred(__iter[__i]);
+    });
+  } else {
+    return std::find_if(__first, __last, __pred);
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FIND_IF_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h

 
 namespace __par_backend::inline __serial_cpu_backend {
 
 template <class _RandomAccessIterator, class _Fp>
 _LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
   __f(__first, __last);
 }
 
+_LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
+
 // TODO: Complete this list
 
 } // namespace __par_backend::inline __serial_cpu_backend
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H

libcxx/include/__algorithm/pstl_fill.h

 //===----------------------------------------------------------------------===//
 //
 // 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_PSTL_FILL_H
 #define _LIBCPP___ALGORITHM_PSTL_FILL_H
 
-#include <__algorithm/fill.h>
+#include <__algorithm/fill_n.h>
+#include <__algorithm/pstl_for_each.h>
+#include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <__pstl/internal/parallel_impl.h>
-#include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class>
+void __pstl_fill(); // declaration needed for the frontend dispatch below
+
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Tp,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void
 fill(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
-  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    std::__terminate_on_exception([&] {
-      __pstl::__par_backend::__parallel_for(
-          __pstl::__internal::__par_backend_tag{},
-          __policy,
-          __first,
-          __last,
-          [&__policy, &__value](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            std::fill(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __value);
-          });
+  std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_fill),
+      [&](_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+        std::for_each(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __element) {
+          __element = __value;
         });
-  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    __pstl::__unseq_backend::__simd_fill_n(__first, __last - __first, __value);
-  } else {
-    std::fill(__first, __last, __value);
-  }
+      },
+      std::move(__first),
+      std::move(__last),
+      __value);
 }
 
+template <class>
+void __pstl_fill_n(); // declaration needed for the frontend dispatch below
+
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _SizeT,
           class _Tp,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void
 fill_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _SizeT __n, const _Tp& __value) {
+  std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_fill_n),
+      [&](_ForwardIterator __first, _SizeT __n, const _Tp& __value) {
         if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value)
           std::fill(__policy, __first, __first + __n, __value);
         else
           std::fill_n(__first, __n, __value);
+      },
+      std::move(__first),
+      __n,
+      __value);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FILL_H

libcxx/include/__algorithm/pstl_find.h

 //===----------------------------------------------------------------------===//
 //
 // 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_PSTL_FIND_H
 #define _LIBCPP___ALGORITHM_PSTL_FIND_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/find.h>
+#include <__algorithm/pstl_backend.h>
+#include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
-#include <__pstl/internal/parallel_impl.h>
-#include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
-          class _Tp,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _Predicate,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
-find(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
-  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    return std::__terminate_on_exception([&] {
-      return __pstl::__internal::__parallel_find(
-          __pstl::__internal::__par_backend_tag{},
-          __policy,
-          __first,
-          __last,
-          [&__policy, &__value](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            return std::find(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __value);
-          },
-          less<>{},
-          true);
-    });
-  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    using __diff_t = __iter_diff_t<_ForwardIterator>;
-    return __pstl::__unseq_backend::__simd_first(
-        __first, __diff_t(0), __last - __first, [&__value](_ForwardIterator __iter, __diff_t __i) {
-          return __iter[__i] == __value;
-        });
-  } else {
-    return std::find(__first, __last, __value);
-  }
+find_if(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  return std::__pstl_find_if<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__pred));
 }
 
+template <class>
+void __pstl_find_if_not();
+
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Predicate,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
-find_if(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    return std::__terminate_on_exception([&] {
-      return __pstl::__internal::__parallel_find(
-          __pstl::__internal::__par_backend_tag{},
-          __policy,
-          __first,
-          __last,
-          [&__policy, &__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            return std::find_if(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __pred);
-          },
-          less<>{},
-          true);
-    });
-  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    using __diff_t = __iter_diff_t<_ForwardIterator>;
-    return __pstl::__unseq_backend::__simd_first(
-        __first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) {
-          return __pred(__iter[__i]);
+find_if_not(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_find_if_not),
+      [&](_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+        return std::find_if(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) {
+          return !__pred(__value);
         });
-  } else {
-    return std::find_if(__first, __last, __pred);
-  }
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__pred));
 }
 
+template <class>
+void __pstl_find();
+
 template <class _ExecutionPolicy,
           class _ForwardIterator,
-          class _Predicate,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
-find_if_not(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  return std::find_if(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) {
-    return !__pred(__value);
+find(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_find),
+      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_value) {
+        return std::find_if(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __element) {
+          return __element == __g_value;
         });
+      },
+      std::move(__first),
+      std::move(__last),
+      __value);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FIND_H

libcxx/include/__algorithm/pstl_for_each.h

 #define _LIBCPP___ALGORITHM_PSTL_FOR_EACH_H
 
 #include <__algorithm/for_each.h>
 #include <__algorithm/for_each_n.h>
 #include <__algorithm/pstl_backend.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <__pstl/internal/parallel_backend.h>
-#include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__type_traits/void_t.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif

libcxx/include/__pstl/internal/parallel_backend_serial.h

public:
     _LIBCPP_HIDE_FROM_ABI _Tp*
     get() const
     {
         return __ptr_;
     }
     _LIBCPP_HIDE_FROM_ABI ~__buffer() { __allocator_.deallocate(__ptr_, __buf_size_); }
 };
 
-_LIBCPP_HIDE_FROM_ABI inline void
-__cancel_execution()
-{
-}
-
-template <class _ExecutionPolicy, class _Index, class _Fp>
-_LIBCPP_HIDE_FROM_ABI void
-__parallel_for(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _Index __first, _Index __last, _Fp __f)
-{
-    __f(__first, __last);
-}
-
 template <class _ExecutionPolicy, class _Value, class _Index, typename _RealBody, typename _Reduction>
 _LIBCPP_HIDE_FROM_ABI _Value
 __parallel_reduce(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _Index __first, _Index __last,
                   const _Value& __identity, const _RealBody& __real_body, const _Reduction&)
 {
     if (__first == __last)
     {
         return __identity;

libcxx/include/__pstl/internal/parallel_impl.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 _PSTL_PARALLEL_IMPL_H
-#define _PSTL_PARALLEL_IMPL_H
-
-#include <__atomic/atomic.h>
-#include <__atomic/memory_order.h>
-#include <__config>
-#include <__pstl/internal/parallel_backend.h>
-
-#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
-
-namespace __pstl
-{
-namespace __internal
-{
-
-//------------------------------------------------------------------------
-// parallel_find
-//-----------------------------------------------------------------------
-/** Return extremum value returned by brick f[i,j) for subranges [i,j) of [first,last)
-Each f[i,j) must return a value in [i,j). */
-template <class _BackendTag, class _ExecutionPolicy, class _Index, class _Brick, class _Compare>
-_LIBCPP_HIDE_FROM_ABI _Index
-__parallel_find(_BackendTag __tag, _ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f,
-                _Compare __comp, bool __b_first)
-{
-    typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType;
-    const _DifferenceType __n = __last - __first;
-    _DifferenceType __initial_dist = __b_first ? __n : -1;
-    std::atomic<_DifferenceType> __extremum(__initial_dist);
-    // TODO: find out what is better here: parallel_for or parallel_reduce
-    __par_backend::__parallel_for(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
-                                  [__comp, __f, __first, &__extremum](_Index __i, _Index __j)
-                                  {
-                                      // See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of
-                                      // why using a shared variable scales fairly well in this situation.
-                                      if (__comp(__i - __first, __extremum))
-                                      {
-                                          _Index __res = __f(__i, __j);
-                                          // If not '__last' returned then we found what we want so put this to extremum
-                                          if (__res != __j)
-                                          {
-                                              const _DifferenceType __k = __res - __first;
-                                              for (_DifferenceType __old = __extremum; __comp(__k, __old);
-                                                   __old = __extremum)
-                                              {
-                                                  __extremum.compare_exchange_weak(__old, __k);
-                                              }
-                                          }
-                                      }
-                                  });
-    return __extremum != __initial_dist ? __first + __extremum : __last;
-}
-
-//------------------------------------------------------------------------
-// parallel_or
-//------------------------------------------------------------------------
-//! Return true if brick f[i,j) returns true for some subrange [i,j) of [first,last)
-template <class _BackendTag, class _ExecutionPolicy, class _Index, class _Brick>
-_LIBCPP_HIDE_FROM_ABI
-bool __parallel_or(_BackendTag __tag, _ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f) {
-    std::atomic<bool> __found(false);
-    __par_backend::__parallel_for(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
-                                  [__f, &__found](_Index __i, _Index __j)
-                                  {
-                                      if (!__found.load(std::memory_order_relaxed) && __f(__i, __j))
-                                      {
-                                          __found.store(true, std::memory_order_relaxed);
-                                          __par_backend::__cancel_execution();
-                                      }
-                                  });
-    return __found;
-}
-
-} // namespace __internal
-} // namespace __pstl
-
-#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
-
-#endif /* _PSTL_PARALLEL_IMPL_H */

libcxx/include/__pstl/internal/unseq_backend_simd.h

while (__last != __first)
         else
         {
             __block_size = __last - __first;
         }
     }
     return false;
 }
 
-template <class _Index, class _DifferenceType, class _Compare>
-_LIBCPP_HIDE_FROM_ABI _Index
-__simd_first(_Index __first, _DifferenceType __begin, _DifferenceType __end, _Compare __comp) noexcept
-{
-    // Experiments show good block sizes like this
-    const _DifferenceType __block_size = 8;
-    alignas(__lane_size) _DifferenceType __lane[__block_size] = {0};
-    while (__end - __begin >= __block_size)
-    {
-        _DifferenceType __found = 0;
-            _PSTL_PRAGMA_SIMD_REDUCTION(|
-                                        : __found) for (_DifferenceType __i = __begin; __i < __begin + __block_size;
-                                                        ++__i)
-        {
-            const _DifferenceType __t = __comp(__first, __i);
-            __lane[__i - __begin] = __t;
-            __found |= __t;
-        }
-        if (__found)
-        {
-            _DifferenceType __i;
-            // This will vectorize
-            for (__i = 0; __i < __block_size; ++__i)
-            {
-                if (__lane[__i])
-                {
-                    break;
-                }
-            }
-            return __first + __begin + __i;
-        }
-        __begin += __block_size;
-    }
-
-    //Keep remainder scalar
-    while (__begin != __end)
-    {
-        if (__comp(__first, __begin))
-        {
-            return __first + __begin;
-        }
-        ++__begin;
-    }
-    return __first + __end;
-}
-
 template <class _Index1, class _DifferenceType, class _Index2, class _Pred>
 _LIBCPP_HIDE_FROM_ABI std::pair<_Index1, _Index2>
 __simd_first(_Index1 __first1, _DifferenceType __n, _Index2 __first2, _Pred __pred) noexcept
 {
     const _Index1 __last1 = __first1 + __n;
     const _Index2 __last2 = __first2 + __n;
     // Experiments show good block sizes like this
     const _DifferenceType __block_size = 8;
for (_DifferenceType __i = 0; __i < __n; ++__i)
         else
         {
             __out_false[__cnt_false] = __first[__i];
             ++__cnt_false;
         }
     }
 }
 
-template <class _Index, class _DifferenceType, class _Tp>
-_LIBCPP_HIDE_FROM_ABI _Index
-__simd_fill_n(_Index __first, _DifferenceType __n, const _Tp& __value) noexcept
-{
-    _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
-    _PSTL_PRAGMA_SIMD
-    for (_DifferenceType __i = 0; __i < __n; ++__i)
-        __first[__i] = __value;
-    return __first + __n;
-}
-
 template <class _Index, class _DifferenceType, class _Generator>
 _LIBCPP_HIDE_FROM_ABI _Index
 __simd_generate_n(_Index __first, _DifferenceType __size, _Generator __g) noexcept
 {
     _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
     _PSTL_PRAGMA_SIMD
     for (_DifferenceType __i = 0; __i < __size; ++__i)
         __first[__i] = __g();