[libc++][PSTL] Parallelize random_access_iterator

[gonzalobg]

Summary

P2408 requires this for C++23, but implementing it in C++20 is safe
because the only code impacted would be code that violated a
precondition of the parallel algorithm. It was P2408 intent to
enable implementations to backport this to C++20.

Closes #63447 .

[philnik]

Could you upload the patch with context (i.e. use arc or add -U9999 when generating the patch)?

It feels a bit wrong to me that we check for random_access_iterator in a classic algorithm, but I guess that is fine. Do all Cpp17RandomAccessIterators meet the random_access_iterator requirements? If yes, I'd just go with using either __has_random_access_iterator or random_access_iterator. We'd probably want to diagnose iterators which advertise themselves as such while not actually being random_access_iterators if we go that route.

libcxx/include/__algorithm/pstl_traits.h

26

This isn't actually pstl-specific, so IMO this should live in iterator_traits or something like that.

[gonzalobg]

• Generated with -U9999
• Moved utility to __iterator/concepts.h (requires random_access_iterator concept)
• Removed pstl_traits.h file

[philnik]

Thanks for the patch! LGTM.

[philnik]

Please make sure the CI is run and green before landing.

[ldionne]

libcxx/include/__algorithm/pstl_any_all_none_of.h

16 ↗

(On Diff #540982)

Why is this include changed, since we didn't touch the contents of the file? Was the include unnecessary in the first place?

libcxx/include/__algorithm/pstl_find.h

18 ↗

(On Diff #540982)

Same comment.

libcxx/include/__algorithm/pstl_transform.h

15 ↗

(On Diff #540982)

Same comment.

libcxx/include/__iterator/concepts.h

290 ↗

(On Diff #540982)

(not attached to the diff) Can you folks think of a way to test this? I can't, but asking just in case.

[philnik]

libcxx/include/__iterator/concepts.h

290 ↗

(On Diff #540982)

We already test with C++20 iterators, which should be good enough I think. Performance can only be tested through benchmarks anyways, so I think that's out of scope for this, since we don't have any PSTL benchmarks yet. (Reminds me that we should log the result of our benchmarks...)

[gonzalobg]

libcxx/include/__iterator/concepts.h

290 ↗

(On Diff #540982)

(not attached to the diff) Can you folks think of a way to test this? I can't, but asking just in case.

I don't know how to test this (I thought quite a bit about it, but benchmarks are the only way I have to test this right now).

If someone figures out a way to test this without requiring benchmarks, that would be helpful for libstdc++ as well (I've sent a similar patch there).

[gonzalobg]

Remove unnecessary iterator/iterator_traits.h and iterator/concepts.h includes.

[gonzalobg]

Forgot to remove header from one file.

[ldionne]

Can you rebase this onto main? The diff fails to apply in the CI.

[gonzalobg]

Rebased on top of main.

[gonzalobg]

Fix fmt.

[gonzalobg]

Re-add iterator_traits to some files (required for modules).

[gonzalobg]

Re-add missing module files.

[gonzalobg]

@ldionne @philnik I've fixed all failures except for the current three. Can it be that they are caused by something that's not in my PR ?

[Mordante]

In D154305#4532745, @gonzalobg wrote:

@ldionne @philnik I've fixed all failures except for the current three. Can it be that they are caused by something that's not in my PR ?

It looks like the last build is green. Can you rebase before landing to make sure the CI is really green?

[gonzalobg]

Rebased on main.

[gonzalobg]

Name: Gonzalo Brito Gadeschi
Email: [e-mail]

[gonzalobg]

Rebased one last time.

[gonzalobg]

Fix tests after rebase.

libcxx/include/CMakeLists.txt

   __algorithm/pstl_merge.h
   __algorithm/pstl_replace.h
   __algorithm/pstl_stable_sort.h
+  __algorithm/pstl_traits.h  
   __algorithm/pstl_transform.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h

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

 #include <__algorithm/any_of.h>
 #include <__algorithm/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
+#include <__algorithm/pstl_traits.h>
 #include <__atomic/atomic.h>
 #include <__atomic/memory_order.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_HIDE_FROM_ABI bool
 __pstl_any_of(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__terminate_on_exception([&] {
       return std::__parallel_or(
           __first, __last, [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {

           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__simd_or(__first, __last - __first, __pred);
   } else {
     return std::any_of(__first, __last, __pred);

libcxx/include/__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 <__algorithm/pstl_traits.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/terminate_on_exception.h>
 

 _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> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__terminate_on_exception([&] {
       __par_backend::__parallel_for(
           __first, __last, [&__value](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {

           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__simd_fill_n(__first, __last - __first, __value);
   } else {
     std::fill(__first, __last, __value);

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

 #include <__atomic/atomic.h>
 #include <__config>
 #include <__functional/operations.h>
-#include <__iterator/iterator_traits.h>
+#include <__algorithm/pstl_traits.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/pair.h>
 #include <__utility/terminate_on_exception.h>

 _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> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__terminate_on_exception([&] {
       return std::__parallel_find(
           __first,

           true);
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_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]);

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

 #include <__algorithm/for_each.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__algorithm/pstl_traits.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/terminate_on_exception.h>
 

 _LIBCPP_HIDE_FROM_ABI void
 __pstl_for_each(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Functor __func) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__terminate_on_exception([&] {
       std::__par_backend::__parallel_for(
           __first, __last, [__func](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {

           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__simd_walk_1(__first, __last - __first, __func);
   } else {
     std::for_each(__first, __last, __func);

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

 #include <__algorithm/merge.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__algorithm/pstl_traits.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/move.h>
 #include <__utility/terminate_on_exception.h>

     _ForwardOutIterator __result,
     _Comp __comp) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                __has_random_access_iterator_category<_ForwardIterator2>::value &&
-                __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     return std::__terminate_on_exception([&] {
       __par_backend::__parallel_merge(
           __first1,

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

 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__algorithm/transform.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__algorithm/pstl_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>

     _ForwardOutIterator __result,
     _UnaryOperation __op) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value &&
-                __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     std::__terminate_on_exception([&] {
       std::__par_backend::__parallel_for(
           __first, __last, [__op, __first, __result](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {

     });
     return __result + (__last - __first);
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value &&
-                       __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     return std::__simd_walk_2(
         __first,
         __last - __first,

     _ForwardOutIterator __result,
     _BinaryOperation __op) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                __has_random_access_iterator_category<_ForwardIterator2>::value &&
-                __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     std::__terminate_on_exception([&] {
       std::__par_backend::__parallel_for(
           __first1,

     });
     return __result + (__last1 - __first1);
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                       __has_random_access_iterator_category<_ForwardIterator2>::value &&
-                       __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     return std::__simd_walk_3(
         __first1,
         __last1 - __first1,

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

 
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__algorithm/pstl_traits.h>
 #include <__numeric/transform_reduce.h>
 #include <__type_traits/is_arithmetic.h>
 #include <__type_traits/is_execution_policy.h>

     _BinaryOperation1 __reduce,
     _BinaryOperation2 __transform) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                __has_random_access_iterator_category<_ForwardIterator2>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
     return std::__terminate_on_exception([&] {
       return __par_backend::__parallel_transform_reduce(
           __first1,

           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                       __has_random_access_iterator_category<_ForwardIterator2>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
     return std::__simd_transform_reduce(
         __last1 - __first1, std::move(__init), std::move(__reduce), [&](__iter_diff_t<_ForwardIterator1> __i) {
           return __transform(__first1[__i], __first2[__i]);

     _BinaryOperation __reduce,
     _UnaryOperation __transform) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__terminate_on_exception([&] {
       return __par_backend::__parallel_transform_reduce(
           std::move(__first),

           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__simd_transform_reduce(
         __last - __first,
         std::move(__init),

libcxx/include/__algorithm/pstl_copy.h

           enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
 copy_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __result) {
-  if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value)
+  if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value)
     return std::copy(__policy, __first, __first + __n, __result);
   else
     return std::copy_n(__first, __n, __result);

libcxx/include/__algorithm/pstl_fill.h

   std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_fill_n),
       [&](_ForwardIterator __g_first, _SizeT __g_n, const _Tp& __g_value) {
-        if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value)
+        if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value)
           std::fill(__policy, __g_first, __g_first + __g_n, __g_value);
         else
           std::fill_n(__g_first, __g_n, __g_value);

libcxx/include/__algorithm/pstl_for_each.h

   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_for_each_n),
       [&](_ForwardIterator __g_first, _Size __g_size, _Function __g_func) {
-        if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value) {
+        if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
           std::for_each(__policy, std::move(__g_first), __g_first + __g_size, std::move(__g_func));
         } else {
           std::for_each_n(std::move(__g_first), __g_size, std::move(__g_func));

libcxx/include/__algorithm/pstl_traits.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_TRAITS_H
+#define _LIBCPP___ALGORITHM_PSTL_TRAITS_H
+
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
+#include <__type_traits/disjunction.h>
+#include <__type_traits/integral_constant.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Tp>
+using __has_random_access_iterator_category_or_concept
+#if _LIBCPP_STD_VER >= 20
+  = disjunction<
+    __has_random_access_iterator_category<_Tp>,
+    integral_constant<bool, random_access_iterator<_Tp>>
+  >;
+#else   // _LIBCPP_STD_VER < 20
+  = __has_random_access_iterator_category<_Tp>;
+#endif  // _LIBCPP_STD_VER
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif  // _LIBCPP___ALGORITHM_PSTL_TRAITS_H