diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -79,6 +79,7 @@ __algorithm/pstl_backends/cpu_backends/for_each.h __algorithm/pstl_backends/cpu_backends/serial.h __algorithm/pstl_backends/cpu_backends/transform.h + __algorithm/pstl_backends/cpu_backends/transform_reduce.h __algorithm/pstl_copy.h __algorithm/pstl_fill.h __algorithm/pstl_find.h @@ -512,6 +513,8 @@ __numeric/iota.h __numeric/midpoint.h __numeric/partial_sum.h + __numeric/pstl_reduce.h + __numeric/pstl_transform_reduce.h __numeric/reduce.h __numeric/transform_exclusive_scan.h __numeric/transform_inclusive_scan.h @@ -778,6 +781,7 @@ __type_traits/nat.h __type_traits/negation.h __type_traits/noexcept_move_assign_container.h + __type_traits/operation_traits.h __type_traits/predicate_traits.h __type_traits/promote.h __type_traits/rank.h 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 @@ -28,5 +28,6 @@ #include <__algorithm/pstl_backends/cpu_backends/find_if.h> #include <__algorithm/pstl_backends/cpu_backends/for_each.h> #include <__algorithm/pstl_backends/cpu_backends/transform.h> +#include <__algorithm/pstl_backends/cpu_backends/transform_reduce.h> #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h --- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H #include <__config> +#include #if defined(_LIBCPP_HAS_NO_THREADS) || defined(_PSTL_CPU_BACKEND_SERIAL) # include <__algorithm/pstl_backends/cpu_backends/serial.h> @@ -25,6 +26,8 @@ struct __cpu_backend_tag {}; +const size_t __lane_size = 64; + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_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 --- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h @@ -53,8 +53,6 @@ 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 { 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 @@ -28,6 +28,12 @@ __f(__first, __last); } +template +_LIBCPP_HIDE_FROM_ABI _Tp +__parallel_transform_reduce(_Index __first, _Index __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduce __reduce) { + return __reduce(__first, __last, __init); +} + _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {} // TODO: Complete this list diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h @@ -0,0 +1,173 @@ +//===----------------------------------------------------------------------===// +// +// 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_TRANSFORM_REDUCE_H +#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_TRANSFORM_REDUCE_H + +#include <__algorithm/pstl_backends/cpu_backends/backend.h> +#include <__config> +#include <__iterator/iterator_traits.h> +#include <__numeric/transform_reduce.h> +#include <__type_traits/is_arithmetic.h> +#include <__type_traits/is_execution_policy.h> +#include <__type_traits/operation_traits.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_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template < + typename _DifferenceType, + typename _Tp, + typename _BinaryOperation, + typename _UnaryOperation, + __enable_if_t<__is_trivial_plus_operation<_BinaryOperation, _Tp, _Tp>::value && is_arithmetic_v<_Tp>, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Tp +__simd_transform_reduce(_DifferenceType __n, _Tp __init, _BinaryOperation, _UnaryOperation __f) noexcept { + _PSTL_PRAGMA_SIMD_REDUCTION(+ : __init) + for (_DifferenceType __i = 0; __i < __n; ++__i) + __init += __f(__i); + return __init; +} + +template < + typename _Size, + typename _Tp, + typename _BinaryOperation, + typename _UnaryOperation, + __enable_if_t::value && is_arithmetic_v<_Tp>), int> = 0> +_LIBCPP_HIDE_FROM_ABI _Tp +__simd_transform_reduce(_Size __n, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __f) noexcept { + const _Size __block_size = __lane_size / sizeof(_Tp); + if (__n > 2 * __block_size && __block_size > 1) { + alignas(__lane_size) char __lane_buffer[__lane_size]; + _Tp* __lane = reinterpret_cast<_Tp*>(__lane_buffer); + + // initializer + _PSTL_PRAGMA_SIMD + for (_Size __i = 0; __i < __block_size; ++__i) { + ::new (__lane + __i) _Tp(__binary_op(__f(__i), __f(__block_size + __i))); + } + // main loop + _Size __i = 2 * __block_size; + const _Size __last_iteration = __block_size * (__n / __block_size); + for (; __i < __last_iteration; __i += __block_size) { + _PSTL_PRAGMA_SIMD + for (_Size __j = 0; __j < __block_size; ++__j) { + __lane[__j] = __binary_op(__lane[__j], __f(__i + __j)); + } + } + // remainder + _PSTL_PRAGMA_SIMD + for (_Size __j = 0; __j < __n - __last_iteration; ++__j) { + __lane[__j] = __binary_op(__lane[__j], __f(__last_iteration + __j)); + } + // combiner + for (_Size __j = 0; __j < __block_size; ++__j) { + __init = __binary_op(__init, __lane[__j]); + } + // destroyer + _PSTL_PRAGMA_SIMD + for (_Size __j = 0; __j < __block_size; ++__j) { + __lane[__j].~_Tp(); + } + } else { + for (_Size __i = 0; __i < __n; ++__i) { + __init = __binary_op(__init, __f(__i)); + } + } + return __init; +} + +template +_LIBCPP_HIDE_FROM_ABI _Tp __pstl_transform_reduce( + __cpu_backend_tag, + _ForwardIterator1 __first1, + _ForwardIterator1 __last1, + _ForwardIterator2 __first2, + _Tp __init, + _BinaryOperation1 __reduce, + _BinaryOperation2 __transform) { + if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> && + __is_cpp17_random_access_iterator<_ForwardIterator1>::value && + __is_cpp17_random_access_iterator<_ForwardIterator2>::value) { + return std::__terminate_on_exception([&] { + return __par_backend::__parallel_transform_reduce( + __first1, + __last1, + [__first1, __first2, __transform](_ForwardIterator1 __iter) { + return __transform(*__iter, *(__first2 + (__iter - __first1))); + }, + __init, + __reduce, + [__first1, __first2, __reduce, __transform]( + _ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last, _Tp __brick_init) { + return std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>( + __cpu_backend_tag{}, + __brick_first, + __brick_last, + __first2 + (__brick_first - __first1), + __brick_init, + __reduce, + __transform); + }); + }); + } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> && + __is_cpp17_random_access_iterator<_ForwardIterator1>::value && + __is_cpp17_random_access_iterator<_ForwardIterator2>::value) { + return std::__simd_transform_reduce( + __last1 - __first1, __init, __reduce, [&](__iter_diff_t<_ForwardIterator1> __i) { + return __transform(__first1[__i], __first2[__i]); + }); + } else { + return std::transform_reduce(__first1, __last1, __first2, __init, __reduce, __transform); + } +} + +template +_LIBCPP_HIDE_FROM_ABI _Tp __pstl_transform_reduce( + __cpu_backend_tag, + _ForwardIterator __first, + _ForwardIterator __last, + _Tp __init, + _BinaryOperation __reduce, + _UnaryOperation __transform) { + if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> && + __is_cpp17_random_access_iterator<_ForwardIterator>::value) { + return std::__terminate_on_exception([&] { + return __par_backend::__parallel_transform_reduce( + __first, + __last, + [__transform](_ForwardIterator __iter) { return __transform(*__iter); }, + __init, + __reduce, + [=](_ForwardIterator __brick_first, _ForwardIterator __brick_last, _Tp __brick_init) { + return std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>( + __cpu_backend_tag{}, __brick_first, __brick_last, __brick_init, __reduce, __transform); + }); + }); + } else { + return std::transform_reduce(__first, __last, __init, __reduce, __transform); + } +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_TRANSFORM_REDUCE_H diff --git a/libcxx/include/__functional/operations.h b/libcxx/include/__functional/operations.h --- a/libcxx/include/__functional/operations.h +++ b/libcxx/include/__functional/operations.h @@ -14,6 +14,7 @@ #include <__functional/binary_function.h> #include <__functional/unary_function.h> #include <__type_traits/integral_constant.h> +#include <__type_traits/operation_traits.h> #include <__type_traits/predicate_traits.h> #include <__utility/forward.h> @@ -40,6 +41,12 @@ }; _LIBCPP_CTAD_SUPPORTED_FOR_TYPE(plus); +template +struct __is_trivial_plus_operation, _Tp, _Tp> : true_type {}; + +template +struct __is_trivial_plus_operation, _Tp, _Up> : true_type {}; + #if _LIBCPP_STD_VER >= 14 template <> struct _LIBCPP_TEMPLATE_VIS plus diff --git a/libcxx/include/__numeric/pstl_reduce.h b/libcxx/include/__numeric/pstl_reduce.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__numeric/pstl_reduce.h @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// 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___NUMERIC_PSTL_REDUCE_H +#define _LIBCPP___NUMERIC_PSTL_REDUCE_H + +#include <__config> +#include <__functional/identity.h> +#include <__numeric/pstl_transform_reduce.h> +#include <__type_traits/is_execution_policy.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if !defined(_LIBCPP_HAS_NO_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template , + enable_if_t>, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Tp +reduce(_ExecutionPolicy&& __policy, + _ForwardIterator __first, + _ForwardIterator __last, + _Tp __init, + _BinaryOperation __op = {}) { + return std::transform_reduce(__policy, __first, __last, __init, __op, __identity{}); +} + +template >, int> = 0> +_LIBCPP_HIDE_FROM_ABI __iter_value_type<_ForwardIterator> +reduce(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last) { + return std::reduce(__policy, __first, __last, __iter_value_type<_ForwardIterator>()); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___NUMERIC_PSTL_REDUCE_H diff --git a/libcxx/include/__numeric/pstl_transform_reduce.h b/libcxx/include/__numeric/pstl_transform_reduce.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__numeric/pstl_transform_reduce.h @@ -0,0 +1,99 @@ +//===----------------------------------------------------------------------===// +// +// 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___NUMERIC_PSTL_TRANSFORM_REDUCE_H +#define _LIBCPP___NUMERIC_PSTL_TRANSFORM_REDUCE_H + +#include <__algorithm/pstl_backend.h> +#include <__algorithm/pstl_frontend_dispatch.h> +#include <__config> +#include <__functional/operations.h> +#include <__numeric/transform_reduce.h> +#include <__type_traits/is_execution_policy.h> +#include <__utility/move.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_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce( + _ExecutionPolicy&& __policy, + _ForwardIterator1 __first1, + _ForwardIterator1 __last1, + _ForwardIterator2 __first2, + _Tp __init, + _BinaryOperation1 __reduce, + _BinaryOperation2 __transform) { + using _Backend = typename __select_backend<_RawPolicy>::type; + return std::__pstl_transform_reduce<_RawPolicy>( + _Backend{}, + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__init), + std::move(__reduce), + std::move(__transform)); +} + +// TODO: Should this get a customization point? +template >, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce( + _ExecutionPolicy&& __policy, + _ForwardIterator1 __first1, + _ForwardIterator1 __last1, + _ForwardIterator2 __first2, + _Tp __init) { + return std::transform_reduce(__policy, __first1, __last1, __first2, __init, plus{}, multiplies{}); +} + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce( + _ExecutionPolicy&& __policy, + _ForwardIterator __first, + _ForwardIterator __last, + _Tp __init, + _BinaryOperation __reduce, + _UnaryOperation __transform) { + using _Backend = typename __select_backend<_RawPolicy>::type; + return std::__pstl_transform_reduce<_RawPolicy>( + _Backend{}, + std::move(__first), + std::move(__last), + std::move(__init), + std::move(__reduce), + std::move(__transform)); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___NUMERIC_PSTL_TRANSFORM_REDUCE_H diff --git a/libcxx/include/__pstl/internal/glue_numeric_defs.h b/libcxx/include/__pstl/internal/glue_numeric_defs.h --- a/libcxx/include/__pstl/internal/glue_numeric_defs.h +++ b/libcxx/include/__pstl/internal/glue_numeric_defs.h @@ -16,57 +16,6 @@ #include "execution_defs.h" namespace std { -// [reduce] - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> -reduce(_ExecutionPolicy&& __exec, - _ForwardIterator __first, - _ForwardIterator __last, - _Tp __init, - _BinaryOperation __binary_op); - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> -reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init); - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, - typename iterator_traits<_ForwardIterator>::value_type> -reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last); - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce( - _ExecutionPolicy&& __exec, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _Tp __init); - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce( - _ExecutionPolicy&& __exec, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _Tp __init, - _BinaryOperation1 __binary_op1, - _BinaryOperation2 __binary_op2); - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce( - _ExecutionPolicy&& __exec, - _ForwardIterator __first, - _ForwardIterator __last, - _Tp __init, - _BinaryOperation __binary_op, - _UnaryOperation __unary_op); - // [exclusive.scan] template diff --git a/libcxx/include/__pstl/internal/glue_numeric_impl.h b/libcxx/include/__pstl/internal/glue_numeric_impl.h --- a/libcxx/include/__pstl/internal/glue_numeric_impl.h +++ b/libcxx/include/__pstl/internal/glue_numeric_impl.h @@ -19,102 +19,6 @@ namespace std { -// [reduce] - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> -reduce(_ExecutionPolicy&& __exec, - _ForwardIterator __first, - _ForwardIterator __last, - _Tp __init, - _BinaryOperation __binary_op) { - return transform_reduce( - std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, __binary_op, __pstl::__internal::__no_op()); -} - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> -reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init) { - return transform_reduce( - std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, std::plus<_Tp>(), __pstl::__internal::__no_op()); -} - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, - typename iterator_traits<_ForwardIterator>::value_type> -reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last) { - typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; - return transform_reduce( - std::forward<_ExecutionPolicy>(__exec), - __first, - __last, - _ValueType{}, - std::plus<_ValueType>(), - __pstl::__internal::__no_op()); -} - -// [transform.reduce] - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce( - _ExecutionPolicy&& __exec, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _Tp __init) { - auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2); - - typedef typename iterator_traits<_ForwardIterator1>::value_type _InputType; - return __pstl::__internal::__pattern_transform_reduce( - __dispatch_tag, - std::forward<_ExecutionPolicy>(__exec), - __first1, - __last1, - __first2, - __init, - std::plus<_InputType>(), - std::multiplies<_InputType>()); -} - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce( - _ExecutionPolicy&& __exec, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _Tp __init, - _BinaryOperation1 __binary_op1, - _BinaryOperation2 __binary_op2) { - auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2); - return __pstl::__internal::__pattern_transform_reduce( - __dispatch_tag, - std::forward<_ExecutionPolicy>(__exec), - __first1, - __last1, - __first2, - __init, - __binary_op1, - __binary_op2); -} - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce( - _ExecutionPolicy&& __exec, - _ForwardIterator __first, - _ForwardIterator __last, - _Tp __init, - _BinaryOperation __binary_op, - _UnaryOperation __unary_op) { - auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first); - return __pstl::__internal::__pattern_transform_reduce( - __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, __binary_op, __unary_op); -} - // [exclusive.scan] template diff --git a/libcxx/include/__pstl/internal/numeric_fwd.h b/libcxx/include/__pstl/internal/numeric_fwd.h --- a/libcxx/include/__pstl/internal/numeric_fwd.h +++ b/libcxx/include/__pstl/internal/numeric_fwd.h @@ -17,114 +17,6 @@ namespace __pstl { namespace __internal { -//------------------------------------------------------------------------ -// transform_reduce (version with two binary functions, according to draft N4659) -//------------------------------------------------------------------------ - -template -_Tp __brick_transform_reduce( - _RandomAccessIterator1, - _RandomAccessIterator1, - _RandomAccessIterator2, - _Tp, - _BinaryOperation1, - _BinaryOperation2, - /*__is_vector=*/std::true_type) noexcept; - -template -_Tp __brick_transform_reduce( - _ForwardIterator1, - _ForwardIterator1, - _ForwardIterator2, - _Tp, - _BinaryOperation1, - _BinaryOperation2, - /*__is_vector=*/std::false_type) noexcept; - -template -_Tp __pattern_transform_reduce( - _Tag, - _ExecutionPolicy&&, - _ForwardIterator1, - _ForwardIterator1, - _ForwardIterator2, - _Tp, - _BinaryOperation1, - _BinaryOperation2) noexcept; - -template -_Tp __pattern_transform_reduce( - __parallel_tag<_IsVector>, - _ExecutionPolicy&&, - _RandomAccessIterator1, - _RandomAccessIterator1, - _RandomAccessIterator2, - _Tp, - _BinaryOperation1, - _BinaryOperation2); - -//------------------------------------------------------------------------ -// transform_reduce (version with unary and binary functions) -//------------------------------------------------------------------------ - -template -_Tp __brick_transform_reduce( - _RandomAccessIterator, - _RandomAccessIterator, - _Tp, - _BinaryOperation, - _UnaryOperation, - /*is_vector=*/std::true_type) noexcept; - -template -_Tp __brick_transform_reduce( - _ForwardIterator, - _ForwardIterator, - _Tp, - _BinaryOperation, - _UnaryOperation, - /*is_vector=*/std::false_type) noexcept; - -template -_Tp __pattern_transform_reduce( - _Tag, _ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation, _UnaryOperation) noexcept; - -template -_Tp __pattern_transform_reduce( - __parallel_tag<_IsVector>, - _ExecutionPolicy&&, - _RandomAccessIterator, - _RandomAccessIterator, - _Tp, - _BinaryOperation, - _UnaryOperation); - //------------------------------------------------------------------------ // transform_exclusive_scan // diff --git a/libcxx/include/__pstl/internal/numeric_impl.h b/libcxx/include/__pstl/internal/numeric_impl.h --- a/libcxx/include/__pstl/internal/numeric_impl.h +++ b/libcxx/include/__pstl/internal/numeric_impl.h @@ -24,178 +24,6 @@ namespace __pstl { namespace __internal { -//------------------------------------------------------------------------ -// transform_reduce (version with two binary functions, according to draft N4659) -//------------------------------------------------------------------------ - -template -_Tp __brick_transform_reduce( - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _Tp __init, - _BinaryOperation1 __binary_op1, - _BinaryOperation2 __binary_op2, - /*is_vector=*/std::false_type) noexcept { - return std::inner_product(__first1, __last1, __first2, __init, __binary_op1, __binary_op2); -} - -template -_Tp __brick_transform_reduce( - _RandomAccessIterator1 __first1, - _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, - _Tp __init, - _BinaryOperation1 __binary_op1, - _BinaryOperation2 __binary_op2, - /*is_vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType; - return __unseq_backend::__simd_transform_reduce( - __last1 - __first1, __init, __binary_op1, [=, &__binary_op2](_DifferenceType __i) { - return __binary_op2(__first1[__i], __first2[__i]); - }); -} - -template -_Tp __pattern_transform_reduce( - _Tag, - _ExecutionPolicy&&, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _Tp __init, - _BinaryOperation1 __binary_op1, - _BinaryOperation2 __binary_op2) noexcept { - return __brick_transform_reduce( - __first1, __last1, __first2, __init, __binary_op1, __binary_op2, typename _Tag::__is_vector{}); -} - -template -_Tp __pattern_transform_reduce( - __parallel_tag<_IsVector> __tag, - _ExecutionPolicy&& __exec, - _RandomAccessIterator1 __first1, - _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, - _Tp __init, - _BinaryOperation1 __binary_op1, - _BinaryOperation2 __binary_op2) { - using __backend_tag = typename decltype(__tag)::__backend_tag; - - return __internal::__except_handler([&]() { - return __par_backend::__parallel_transform_reduce( - __backend_tag{}, - std::forward<_ExecutionPolicy>(__exec), - __first1, - __last1, - [__first1, __first2, __binary_op2](_RandomAccessIterator1 __i) mutable { - return __binary_op2(*__i, *(__first2 + (__i - __first1))); - }, - __init, - __binary_op1, // Combine - [__first1, __first2, __binary_op1, __binary_op2]( - _RandomAccessIterator1 __i, _RandomAccessIterator1 __j, _Tp __init) -> _Tp { - return __internal::__brick_transform_reduce( - __i, __j, __first2 + (__i - __first1), __init, __binary_op1, __binary_op2, _IsVector{}); - }); - }); -} - -//------------------------------------------------------------------------ -// transform_reduce (version with unary and binary functions) -//------------------------------------------------------------------------ - -template -_Tp __brick_transform_reduce( - _ForwardIterator __first, - _ForwardIterator __last, - _Tp __init, - _BinaryOperation __binary_op, - _UnaryOperation __unary_op, - /*is_vector=*/std::false_type) noexcept { - return std::transform_reduce(__first, __last, __init, __binary_op, __unary_op); -} - -template -_Tp __brick_transform_reduce( - _RandomAccessIterator __first, - _RandomAccessIterator __last, - _Tp __init, - _BinaryOperation __binary_op, - _UnaryOperation __unary_op, - /*is_vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType; - return __unseq_backend::__simd_transform_reduce( - __last - __first, __init, __binary_op, [=, &__unary_op](_DifferenceType __i) { - return __unary_op(__first[__i]); - }); -} - -template -_Tp __pattern_transform_reduce( - _Tag, - _ExecutionPolicy&&, - _ForwardIterator __first, - _ForwardIterator __last, - _Tp __init, - _BinaryOperation __binary_op, - _UnaryOperation __unary_op) noexcept { - return __internal::__brick_transform_reduce( - __first, __last, __init, __binary_op, __unary_op, typename _Tag::__is_vector{}); -} - -template -_Tp __pattern_transform_reduce( - __parallel_tag<_IsVector> __tag, - _ExecutionPolicy&& __exec, - _RandomAccessIterator __first, - _RandomAccessIterator __last, - _Tp __init, - _BinaryOperation __binary_op, - _UnaryOperation __unary_op) { - using __backend_tag = typename decltype(__tag)::__backend_tag; - - return __internal::__except_handler([&]() { - return __par_backend::__parallel_transform_reduce( - __backend_tag{}, - std::forward<_ExecutionPolicy>(__exec), - __first, - __last, - [__unary_op](_RandomAccessIterator __i) mutable { return __unary_op(*__i); }, - __init, - __binary_op, - [__unary_op, __binary_op](_RandomAccessIterator __i, _RandomAccessIterator __j, _Tp __init) { - return __internal::__brick_transform_reduce(__i, __j, __init, __binary_op, __unary_op, _IsVector{}); - }); - }); -} - //------------------------------------------------------------------------ // transform_exclusive_scan // 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 @@ -61,14 +61,6 @@ } } -template -_LIBCPP_HIDE_FROM_ABI _Tp -__parallel_transform_reduce(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _Index __first, _Index __last, - _UnaryOp, _Tp __init, _BinaryOp, _Reduce __reduce) -{ - return __reduce(__first, __last, __init); -} - template _LIBCPP_HIDE_FROM_ABI void __parallel_strict_scan(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _Index __n, _Tp __initial, 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 @@ -344,71 +344,6 @@ using is_arithmetic_plus = std::integral_constant::value && std::is_same<_BinaryOperation, std::plus<_Tp>>::value>; -template -_LIBCPP_HIDE_FROM_ABI typename std::enable_if::value, _Tp>::type -__simd_transform_reduce(_DifferenceType __n, _Tp __init, _BinaryOperation, _UnaryOperation __f) noexcept -{ - _PSTL_PRAGMA_SIMD_REDUCTION(+ : __init) - for (_DifferenceType __i = 0; __i < __n; ++__i) - __init += __f(__i); - return __init; -} - -template -_LIBCPP_HIDE_FROM_ABI typename std::enable_if::value, _Tp>::type -__simd_transform_reduce(_Size __n, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __f) noexcept -{ - const _Size __block_size = __lane_size / sizeof(_Tp); - if (__n > 2 * __block_size && __block_size > 1) - { - alignas(__lane_size) char __lane_buffer[__lane_size]; - _Tp* __lane = reinterpret_cast<_Tp*>(__lane_buffer); - - // initializer - _PSTL_PRAGMA_SIMD - for (_Size __i = 0; __i < __block_size; ++__i) - { - ::new (__lane + __i) _Tp(__binary_op(__f(__i), __f(__block_size + __i))); - } - // main loop - _Size __i = 2 * __block_size; - const _Size __last_iteration = __block_size * (__n / __block_size); - for (; __i < __last_iteration; __i += __block_size) - { - _PSTL_PRAGMA_SIMD - for (_Size __j = 0; __j < __block_size; ++__j) - { - __lane[__j] = __binary_op(__lane[__j], __f(__i + __j)); - } - } - // remainder - _PSTL_PRAGMA_SIMD - for (_Size __j = 0; __j < __n - __last_iteration; ++__j) - { - __lane[__j] = __binary_op(__lane[__j], __f(__last_iteration + __j)); - } - // combiner - for (_Size __j = 0; __j < __block_size; ++__j) - { - __init = __binary_op(__init, __lane[__j]); - } - // destroyer - _PSTL_PRAGMA_SIMD - for (_Size __j = 0; __j < __block_size; ++__j) - { - __lane[__j].~_Tp(); - } - } - else - { - for (_Size __i = 0; __i < __n; ++__i) - { - __init = __binary_op(__init, __f(__i)); - } - } - return __init; -} - // Exclusive scan for "+" and arithmetic types template diff --git a/libcxx/include/__type_traits/operation_traits.h b/libcxx/include/__type_traits/operation_traits.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__type_traits/operation_traits.h @@ -0,0 +1,22 @@ +//===----------------------------------------------------------------------===// +// +// 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___TYPE_TRAITS_OPERATION_TRAITS_H +#define _LIBCPP___TYPE_TRAITS_OPERATION_TRAITS_H + +#include <__config> +#include <__type_traits/integral_constant.h> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct __is_trivial_plus_operation : false_type {}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___TYPE_TRAITS_OPERATION_TRAITS_H diff --git a/libcxx/include/numeric b/libcxx/include/numeric --- a/libcxx/include/numeric +++ b/libcxx/include/numeric @@ -158,6 +158,8 @@ #include <__numeric/iota.h> #include <__numeric/midpoint.h> #include <__numeric/partial_sum.h> +#include <__numeric/pstl_reduce.h> +#include <__numeric/pstl_transform_reduce.h> #include <__numeric/reduce.h> #include <__numeric/transform_exclusive_scan.h> #include <__numeric/transform_inclusive_scan.h> diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -122,6 +122,7 @@ #include <__algorithm/pstl_backends/cpu_backends/for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/for_each.h'}} #include <__algorithm/pstl_backends/cpu_backends/serial.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/serial.h'}} #include <__algorithm/pstl_backends/cpu_backends/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/transform.h'}} +#include <__algorithm/pstl_backends/cpu_backends/transform_reduce.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/transform_reduce.h'}} #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}} #include <__algorithm/ranges_adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_adjacent_find.h'}} #include <__algorithm/ranges_all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_all_of.h'}} @@ -760,6 +761,7 @@ #include <__type_traits/nat.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/nat.h'}} #include <__type_traits/negation.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/negation.h'}} #include <__type_traits/noexcept_move_assign_container.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/noexcept_move_assign_container.h'}} +#include <__type_traits/operation_traits.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/operation_traits.h'}} #include <__type_traits/predicate_traits.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/predicate_traits.h'}} #include <__type_traits/promote.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/promote.h'}} #include <__type_traits/rank.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/rank.h'}} diff --git a/libcxx/test/std/algorithms/numeric.ops/reduce/pstl.reduce.pass.cpp b/libcxx/test/std/algorithms/numeric.ops/reduce/pstl.reduce.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/numeric.ops/reduce/pstl.reduce.pass.cpp @@ -0,0 +1,80 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14 + +// UNSUPPORTED: libcpp-has-no-incomplete-pstl + +// + +// template +// typename iterator_traits::value_type +// reduce(ExecutionPolicy&& exec, +// ForwardIterator first, ForwardIterator last); +// template +// T reduce(ExecutionPolicy&& exec, +// ForwardIterator first, ForwardIterator last, T init, +// BinaryOperation binary_op); + +#include +#include + +#include + +#include "test_macros.h" +#include "test_execution_policies.h" +#include "test_iterators.h" + +template +struct Test { + template + void operator()(Policy&& policy) { + for (const auto& pair : {std::pair{0, 34}, {1, 36}, {2, 39}, {100, 5184}, {350, 61809}}) { + auto [size, expected] = pair; + std::vector a(size); + for (int i = 0; i != size; ++i) + a[i] = i; + + { + decltype(auto) ret = + std::reduce(policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), 34, [](int i, int j) { + return i + j + 2; + }); + static_assert(std::is_same_v); + std::cout << ret << '\n'; + assert(ret == expected); + } + { + decltype(auto) ret = std::reduce( + policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), 34); + static_assert(std::is_same_v); + assert(ret == expected - 2 * size); + } + { + decltype(auto) ret = std::reduce( + policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a))); + static_assert(std::is_same_v); + assert(ret == expected - 2 * size - 34); + } + } + } +}; + +struct TestIterators { + template + void operator()() { + types::for_each(types::forward_iterator_list{}, + TestIteratorWithPolicies::template apply>{}); + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, TestIterators{}); + + return 0; +} diff --git a/libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.binary.pass.cpp b/libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.binary.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.binary.pass.cpp @@ -0,0 +1,93 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14 + +// UNSUPPORTED: libcpp-has-no-incomplete-pstl + +// + +// template +// T transform_reduce(ExecutionPolicy&& exec, +// ForwardIterator1 first1, ForwardIterator1 last1, +// ForwardIterator2 first2, +// T init); +// +// template +// T transform_reduce(ExecutionPolicy&& exec, +// ForwardIterator1 first1, ForwardIterator1 last1, +// ForwardIterator2 first2, +// T init, +// BinaryOperation1 binary_op1, +// BinaryOperation2 binary_op2); + +#include +#include + +#include "test_macros.h" +#include "test_execution_policies.h" +#include "test_iterators.h" + +template +struct Test { + template + void operator()(Policy&& policy) { + for (const auto& pair : {std::pair{0, 34}, {1, 33}, {2, 30}, {100, 313434}, {350, 14046934}}) { + auto [size, expected] = pair; + std::vector a(size); + std::vector b(size); + for (int i = 0; i != size; ++i) { + a[i] = i + 1; + b[i] = i - 4; + } + + decltype(auto) ret = std::transform_reduce( + policy, + Iter1(std::data(a)), + Iter1(std::data(a) + std::size(a)), + Iter2(std::data(b)), + 34, + [](int i, int j) { return i + j + 3; }, + [](int i, int j) { return i * j; }); + static_assert(std::is_same_v); + assert(ret == expected); + } + + for (const auto& pair : {std::pair{0, 34}, {1, 30}, {2, 24}, {100, 313134}, {350, 14045884}}) { + auto [size, expected] = pair; + std::vector a(size); + std::vector b(size); + for (int i = 0; i != size; ++i) { + a[i] = i + 1; + b[i] = i - 4; + } + + decltype(auto) ret = std::transform_reduce( + policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), Iter2(std::data(b)), 34); + static_assert(std::is_same_v); + assert(ret == expected); + } + } +}; + +struct TestIterators { + template + void operator()() { + types::for_each(types::forward_iterator_list{}, + TestIteratorWithPolicies::template apply>{}); + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, TestIterators{}); + + return 0; +} diff --git a/libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.unary.pass.cpp b/libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.unary.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.unary.pass.cpp @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14 + +// UNSUPPORTED: libcpp-has-no-incomplete-pstl + +// + +// template +// T transform_reduce(ExecutionPolicy&& exec, +// ForwardIterator first, ForwardIterator last, +// T init, BinaryOperation binary_op, UnaryOperation unary_op); + +#include +#include + +#include + +#include "test_macros.h" +#include "test_execution_policies.h" +#include "test_iterators.h" + +template +struct Test { + template + void operator()(Policy&& policy) { + for (const auto& pair : {std::pair{0, 34}, {1, 35}, {2, 37}, {100, 5084}, {350, 61459}}) { + auto [size, expected] = pair; + std::vector a(size); + for (int i = 0; i != size; ++i) + a[i] = i; + + decltype(auto) ret = std::transform_reduce( + policy, + Iter1(std::data(a)), + Iter1(std::data(a) + std::size(a)), + 34, + [](int i, int j) { return i + j; }, + [](int i) { return i + 1; }); + static_assert(std::is_same_v); + std::cout << ret << '\n'; + assert(ret == expected); + } + } +}; + +struct TestIterators { + template + void operator()() { + types::for_each(types::forward_iterator_list{}, + TestIteratorWithPolicies::template apply>{}); + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, TestIterators{}); + + return 0; +}