diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -73,6 +73,8 @@ __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 @@ -538,7 +540,6 @@ __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 diff --git a/libcxx/include/__algorithm/pstl_any_all_none_of.h b/libcxx/include/__algorithm/pstl_any_all_none_of.h --- a/libcxx/include/__algorithm/pstl_any_all_none_of.h +++ b/libcxx/include/__algorithm/pstl_any_all_none_of.h @@ -9,11 +9,10 @@ #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> @@ -27,50 +26,66 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +void __pstl_any_of(); // declaration needed for the frontend dispatch below + template >, int> = 0> + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, 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 +void __pstl_all_of(); // declaration needed for the frontend dispatch below + template >, int> = 0> + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, int> = 0> _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool all_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) { - return !std::any_of(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) { - return !__pred(__value); - }); + 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 +void __pstl_none_of(); // declaration needed for the frontend dispatch below + template >, int> = 0> + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, int> = 0> _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool none_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) { - return !std::any_of(__policy, __first, __last, __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 diff --git a/libcxx/include/__algorithm/pstl_backend.h b/libcxx/include/__algorithm/pstl_backend.h --- a/libcxx/include/__algorithm/pstl_backend.h +++ b/libcxx/include/__algorithm/pstl_backend.h @@ -29,6 +29,9 @@ template void __pstl_for_each(_Backend, _ExecutionPolicy&&, _Iterator __first, _Iterator __last, _Func __f); + template + _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 @@ -38,6 +41,21 @@ template void __pstl_for_each_n(_Backend, _ExecutionPolicy&&, _Iterator __first, _Size __n, _Func __f); + template + bool __pstl_any_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); + + template + bool __pstl_all_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); + + template + bool __pstl_none_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); + + template + void __pstl_fill(_Iterator __first, _Iterator __last, const _Tp& __value); + + template + void __pstl_fill_n(_Iterator __first, _SizeT __n, const _Tp& __value); + // TODO: Complete this list */ diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backend.h b/libcxx/include/__algorithm/pstl_backends/cpu_backend.h --- a/libcxx/include/__algorithm/pstl_backends/cpu_backend.h +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backend.h @@ -17,9 +17,15 @@ template 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 diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h @@ -0,0 +1,83 @@ +//===----------------------------------------------------------------------===// +// +// 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 +_LIBCPP_HIDE_FROM_ABI bool __parallel_or(_Index __first, _Index __last, _Brick __f) { + std::atomic __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 +_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 +_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 diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h @@ -0,0 +1,57 @@ +//===----------------------------------------------------------------------===// +// +// 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 +_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 +_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 diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h @@ -0,0 +1,120 @@ +//===----------------------------------------------------------------------===// +// +// 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 +_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 +_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 +_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 diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h --- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h @@ -27,6 +27,8 @@ __f(__first, __last); } +_LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {} + // TODO: Complete this list } // namespace __par_backend::inline __serial_cpu_backend diff --git a/libcxx/include/__algorithm/pstl_fill.h b/libcxx/include/__algorithm/pstl_fill.h --- a/libcxx/include/__algorithm/pstl_fill.h +++ b/libcxx/include/__algorithm/pstl_fill.h @@ -9,11 +9,11 @@ #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> @@ -26,43 +26,50 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +void __pstl_fill(); // declaration needed for the frontend dispatch below + template >, int> = 0> + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, 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); - }); - }); - } 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::__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; + }); + }, + std::move(__first), + std::move(__last), + __value); } +template +void __pstl_fill_n(); // declaration needed for the frontend dispatch below + template >, int> = 0> + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, int> = 0> _LIBCPP_HIDE_FROM_ABI void fill_n(_ExecutionPolicy&& __policy, _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::__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 diff --git a/libcxx/include/__algorithm/pstl_find.h b/libcxx/include/__algorithm/pstl_find.h --- a/libcxx/include/__algorithm/pstl_find.h +++ b/libcxx/include/__algorithm/pstl_find.h @@ -11,9 +11,9 @@ #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> @@ -28,77 +28,57 @@ template >, int> = 0> + class _Predicate, + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, 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 +void __pstl_find_if_not(); + template >, int> = 0> + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, 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 +void __pstl_find(); + template >, int> = 0> + class _Tp, + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, 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 diff --git a/libcxx/include/__algorithm/pstl_for_each.h b/libcxx/include/__algorithm/pstl_for_each.h --- a/libcxx/include/__algorithm/pstl_for_each.h +++ b/libcxx/include/__algorithm/pstl_for_each.h @@ -15,8 +15,6 @@ #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> diff --git a/libcxx/include/__pstl/internal/parallel_backend_serial.h b/libcxx/include/__pstl/internal/parallel_backend_serial.h --- a/libcxx/include/__pstl/internal/parallel_backend_serial.h +++ b/libcxx/include/__pstl/internal/parallel_backend_serial.h @@ -45,18 +45,6 @@ _LIBCPP_HIDE_FROM_ABI ~__buffer() { __allocator_.deallocate(__ptr_, __buf_size_); } }; -_LIBCPP_HIDE_FROM_ABI inline void -__cancel_execution() -{ -} - -template -_LIBCPP_HIDE_FROM_ABI void -__parallel_for(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _Index __first, _Index __last, _Fp __f) -{ - __f(__first, __last); -} - template _LIBCPP_HIDE_FROM_ABI _Value __parallel_reduce(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _Index __first, _Index __last, diff --git a/libcxx/include/__pstl/internal/parallel_impl.h b/libcxx/include/__pstl/internal/parallel_impl.h deleted file mode 100644 --- a/libcxx/include/__pstl/internal/parallel_impl.h +++ /dev/null @@ -1,88 +0,0 @@ -// -*- 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 -_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 -_LIBCPP_HIDE_FROM_ABI -bool __parallel_or(_BackendTag __tag, _ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f) { - std::atomic __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 */ diff --git a/libcxx/include/__pstl/internal/unseq_backend_simd.h b/libcxx/include/__pstl/internal/unseq_backend_simd.h --- a/libcxx/include/__pstl/internal/unseq_backend_simd.h +++ b/libcxx/include/__pstl/internal/unseq_backend_simd.h @@ -95,52 +95,6 @@ return false; } -template -_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 _LIBCPP_HIDE_FROM_ABI std::pair<_Index1, _Index2> __simd_first(_Index1 __first1, _DifferenceType __n, _Index2 __first2, _Pred __pred) noexcept @@ -320,17 +274,6 @@ } } -template -_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 _LIBCPP_HIDE_FROM_ABI _Index __simd_generate_n(_Index __first, _DifferenceType __size, _Generator __g) noexcept