diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -82,6 +82,7 @@ __algorithm/pstl_backends/cpu_backends/serial.h __algorithm/pstl_backends/cpu_backends/thread.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 @@ -517,6 +518,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 @@ -787,6 +790,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_backend.h b/libcxx/include/__algorithm/pstl_backend.h --- a/libcxx/include/__algorithm/pstl_backend.h +++ b/libcxx/include/__algorithm/pstl_backend.h @@ -42,6 +42,29 @@ _OutIterator __result, _BinaryOperation __op); + template + _Tp __pstl_transform_reduce(_Backend, + _Iterator1 __first1, + _Iterator1 __last1, + _Iterator2 __first2, + _Iterator2 __last2, + _Tp __init, + _BinaryOperation1 __reduce, + _BinaryOperation2 __transform); + + template + _Tp __pstl_transform_reduce(_Backend, + _Iterator __first, + _Iterator __last, + _Tp __init, + _BinaryOperation __reduce, + _UnaryOperation __transform); + // TODO: Complete this list The following functions are optional but can be provided. If provided, they are used by the corresponding @@ -81,6 +104,12 @@ _OutIterator __result, _Comp __comp); + template + _Tp __pstl_reduce(_Backend, _Iterator __first, _Iterator __last, _Tp __init, _BinaryOperation __op); + + temlate + __iter_value_type<_Iterator> __pstl_reduce(_Backend, _Iterator __first, _Iterator __last); + // 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,6 +17,9 @@ template void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func); + template + _Tp __parallel_transform_reduce(_Iterator __first, _Iterator __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduction); + // Cancel the execution of other jobs - they aren't needed anymore void __cancel_execution(); @@ -38,10 +41,12 @@ */ #include <__algorithm/pstl_backends/cpu_backends/any_of.h> +#include <__algorithm/pstl_backends/cpu_backends/backend.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> #include <__algorithm/pstl_backends/cpu_backends/merge.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_PSTL_CPU_BACKEND_SERIAL) # include <__algorithm/pstl_backends/cpu_backends/serial.h> @@ -23,10 +24,16 @@ # pragma GCC system_header #endif +#if _LIBCPP_STD_VER >= 17 + _LIBCPP_BEGIN_NAMESPACE_STD struct __cpu_backend_tag {}; +inline constexpr size_t __lane_size = 64; + _LIBCPP_END_NAMESPACE_STD +#endif // _LIBCPP_STD_VER >= 17 + #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 @@ -11,6 +11,7 @@ #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H #include <__config> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -28,6 +29,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(std::move(__first), std::move(__last), std::move(__init)); +} + _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {} template #include <__config> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -31,6 +32,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(std::move(__first), std::move(__last), std::move(__init)); +} + _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {} template +#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/move.h> +#include <__utility/terminate_on_exception.h> +#include + +#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 < + 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(std::move(__lane[__j]), __f(__i + __j)); + } + } + // remainder + _PSTL_PRAGMA_SIMD + for (_Size __j = 0; __j < __n - __last_iteration; ++__j) { + __lane[__j] = __binary_op(std::move(__lane[__j]), __f(__last_iteration + __j)); + } + // combiner + for (_Size __j = 0; __j < __block_size; ++__j) { + __init = __binary_op(std::move(__init), std::move(__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(std::move(__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> && + __has_random_access_iterator_category<_ForwardIterator1>::value && + __has_random_access_iterator_category<_ForwardIterator2>::value) { + return std::__terminate_on_exception([&] { + return __par_backend::__parallel_transform_reduce( + __first1, + std::move(__last1), + [__first1, __first2, __transform](_ForwardIterator1 __iter) { + return __transform(*__iter, *(__first2 + (__iter - __first1))); + }, + std::move(__init), + std::move(__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, + std::move(__brick_last), + __first2 + (__brick_first - __first1), + std::move(__brick_init), + std::move(__reduce), + std::move(__transform)); + }); + }); + } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> && + __has_random_access_iterator_category<_ForwardIterator1>::value && + __has_random_access_iterator_category<_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]); + }); + } else { + return std::transform_reduce( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__init), + std::move(__reduce), + std::move(__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> && + __has_random_access_iterator_category<_ForwardIterator>::value) { + return std::__terminate_on_exception([&] { + return __par_backend::__parallel_transform_reduce( + std::move(__first), + std::move(__last), + [__transform](_ForwardIterator __iter) { return __transform(*__iter); }, + std::move(__init), + std::move(__reduce), + [=](_ForwardIterator __brick_first, _ForwardIterator __brick_last, _Tp __brick_init) { + return std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>( + __cpu_backend_tag{}, + std::move(__brick_first), + std::move(__brick_last), + std::move(__brick_init), + std::move(__reduce), + std::move(__transform)); + }); + }); + } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> && + __has_random_access_iterator_category<_ForwardIterator>::value) { + return std::__simd_transform_reduce( + __last - __first, + std::move(__init), + std::move(__reduce), + [=, &__transform](__iter_diff_t<_ForwardIterator> __i) { return __transform(__first[__i]); }); + } else { + return std::transform_reduce( + std::move(__first), std::move(__last), std::move(__init), std::move(__reduce), std::move(__transform)); + } +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _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,14 @@ }; _LIBCPP_CTAD_SUPPORTED_FOR_TYPE(plus); +template +struct __is_trivial_plus_operation, _Tp, _Tp> : true_type {}; + +#if _LIBCPP_STD_VER >= 14 +template +struct __is_trivial_plus_operation, _Tp, _Up> : true_type {}; +#endif + #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,73 @@ +//===----------------------------------------------------------------------===// +// +// 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 <__algorithm/pstl_frontend_dispatch.h> +#include <__config> +#include <__functional/identity.h> +#include <__iterator/iterator_traits.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_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +void __pstl_reduce(); + +template , + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Tp +reduce(_ExecutionPolicy&& __policy, + _ForwardIterator __first, + _ForwardIterator __last, + _Tp __init, + _BinaryOperation __op = {}) { + return std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_reduce), + [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _Tp __g_init, _BinaryOperation __g_op) { + return std::transform_reduce( + __policy, std::move(__g_first), std::move(__g_last), std::move(__g_init), std::move(__g_op), __identity{}); + }, + std::move(__first), + std::move(__last), + std::move(__init), + std::move(__op)); +} + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI __iter_value_type<_ForwardIterator> +reduce(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last) { + return std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_reduce), + [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last) { + return std::reduce(__policy, __g_first, __g_last, __iter_value_type<_ForwardIterator>()); + }, + std::move(__first), + std::move(__last)); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _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,100 @@ +//===----------------------------------------------------------------------===// +// +// 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_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce( + _ExecutionPolicy&&, + _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)); +} + +// This overload doesn't get a customization point because it's trivial to detect (through e.g. +// __is_trivial_plus_operation) when specializing the more general variant, which should always be preferred +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&&, + _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_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___NUMERIC_PSTL_TRANSFORM_REDUCE_H diff --git a/libcxx/include/__numeric/transform_reduce.h b/libcxx/include/__numeric/transform_reduce.h --- a/libcxx/include/__numeric/transform_reduce.h +++ b/libcxx/include/__numeric/transform_reduce.h @@ -26,7 +26,7 @@ _InputIterator __last, _Tp __init, _BinaryOp __b, _UnaryOp __u) { for (; __first != __last; ++__first) - __init = __b(__init, __u(*__first)); + __init = __b(std::move(__init), __u(*__first)); return __init; } @@ -36,7 +36,7 @@ _InputIterator2 __first2, _Tp __init, _BinaryOp1 __b1, _BinaryOp2 __b2) { for (; __first1 != __last1; ++__first1, (void)++__first2) - __init = __b1(__init, __b2(*__first1, *__first2)); + __init = __b1(std::move(__init), __b2(*__first1, *__first2)); return __init; } 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/__algorithm/pstl_backends/cpu_backends/backend.h b/libcxx/include/__type_traits/operation_traits.h copy from libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h copy to libcxx/include/__type_traits/operation_traits.h --- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h +++ b/libcxx/include/__type_traits/operation_traits.h @@ -6,18 +6,11 @@ // //===----------------------------------------------------------------------===// -#ifndef _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H -#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H +#ifndef _LIBCPP___TYPE_TRAITS_OPERATION_TRAITS_H +#define _LIBCPP___TYPE_TRAITS_OPERATION_TRAITS_H #include <__config> - -#if defined(_LIBCPP_PSTL_CPU_BACKEND_SERIAL) -# include <__algorithm/pstl_backends/cpu_backends/serial.h> -#elif defined(_LIBCPP_PSTL_CPU_BACKEND_THREAD) -# include <__algorithm/pstl_backends/cpu_backends/thread.h> -#else -# error "Invalid CPU backend choice" -#endif +#include <__type_traits/integral_constant.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -25,8 +18,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD -struct __cpu_backend_tag {}; +template +struct __is_trivial_plus_operation : false_type {}; _LIBCPP_END_NAMESPACE_STD -#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H +#endif // _LIBCPP___TYPE_TRAITS_OPERATION_TRAITS_H diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -351,6 +351,9 @@ module pstl_backends_cpu_backends_transform { private header "__algorithm/pstl_backends/cpu_backends/transform.h" } + module pstl_backends_cpu_backends_transform_reduce { + private header "__algorithm/pstl_backends/cpu_backends/transform_reduce.h" + } module push_heap { private header "__algorithm/push_heap.h" } module ranges_adjacent_find { private header "__algorithm/ranges_adjacent_find.h" } module ranges_all_of { private header "__algorithm/ranges_all_of.h" } @@ -1679,6 +1682,7 @@ module nat { private header "__type_traits/nat.h" } module negation { private header "__type_traits/negation.h" } module noexcept_move_assign_container { private header "__type_traits/noexcept_move_assign_container.h" } + module operation_traits { private header "__type_traits/operation_traits.h" } module predicate_traits { private header "__type_traits/predicate_traits.h" } module promote { private header "__type_traits/promote.h" } module rank { private header "__type_traits/rank.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/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp b/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp --- a/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp +++ b/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp @@ -15,6 +15,8 @@ // Make sure that the customization points get called properly when overloaded #include <__config> +#include <__iterator/iterator_traits.h> +#include <__iterator/readable_traits.h> #include struct TestPolicy {}; @@ -127,11 +129,55 @@ return {}; } +bool pstl_reduce_with_init_called = false; + +template +T __pstl_reduce(TestBackend, ForwardIterator, ForwardIterator, T, BinaryOperation) { + assert(!pstl_reduce_with_init_called); + pstl_reduce_with_init_called = true; + return {}; +} + +bool pstl_reduce_without_init_called = false; + +template +typename std::iterator_traits::value_type +__pstl_reduce(TestBackend, ForwardIterator, ForwardIterator) { + assert(!pstl_reduce_without_init_called); + pstl_reduce_without_init_called = true; + return {}; +} + +bool pstl_unary_transform_reduce_called = false; + +template +T __pstl_transform_reduce(TestBackend, ForwardIterator, ForwardIterator, T, UnaryOperation, BinaryOperation) { + assert(!pstl_unary_transform_reduce_called); + pstl_unary_transform_reduce_called = true; + return {}; +} + +bool pstl_binary_transform_reduce_called = false; + +template +typename std::iterator_traits::value_type __pstl_transform_reduce( + TestBackend, ForwardIterator1, ForwardIterator1, ForwardIterator2, T, BinaryOperation1, BinaryOperation2) { + assert(!pstl_binary_transform_reduce_called); + pstl_binary_transform_reduce_called = true; + return {}; +} + _LIBCPP_END_NAMESPACE_STD #include #include #include +#include template <> inline constexpr bool std::is_execution_policy_v = true; @@ -169,6 +215,14 @@ assert(std::pstl_unary_transform_called); (void)std::transform(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), std::begin(a), pred); assert(std::pstl_unary_transform_called); + (void)std::reduce(TestPolicy{}, std::begin(a), std::end(a), 0, pred); + assert(std::pstl_reduce_with_init_called); + (void)std::reduce(TestPolicy{}, std::begin(a), std::end(a)); + assert(std::pstl_reduce_without_init_called); + (void)std::transform_reduce(TestPolicy{}, std::begin(a), std::end(a), 0, pred, pred); + assert(std::pstl_unary_transform_reduce_called); + (void)std::transform_reduce(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), 0, pred, pred); + assert(std::pstl_binary_transform_reduce_called); return 0; } 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 @@ -125,6 +125,7 @@ #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/thread.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/thread.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'}} @@ -768,6 +769,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/libcxx/transitive_includes/cxx03.csv b/libcxx/test/libcxx/transitive_includes/cxx03.csv --- a/libcxx/test/libcxx/transitive_includes/cxx03.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx03.csv @@ -580,9 +580,17 @@ numeric cmath numeric concepts numeric cstddef +numeric cstdint +numeric cstring +numeric ctime +numeric execution numeric functional +numeric initializer_list +numeric iosfwd numeric iterator numeric limits +numeric new +numeric ratio numeric type_traits numeric version optional atomic diff --git a/libcxx/test/libcxx/transitive_includes/cxx11.csv b/libcxx/test/libcxx/transitive_includes/cxx11.csv --- a/libcxx/test/libcxx/transitive_includes/cxx11.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx11.csv @@ -581,9 +581,17 @@ numeric cmath numeric concepts numeric cstddef +numeric cstdint +numeric cstring +numeric ctime +numeric execution numeric functional +numeric initializer_list +numeric iosfwd numeric iterator numeric limits +numeric new +numeric ratio numeric type_traits numeric version optional atomic diff --git a/libcxx/test/libcxx/transitive_includes/cxx14.csv b/libcxx/test/libcxx/transitive_includes/cxx14.csv --- a/libcxx/test/libcxx/transitive_includes/cxx14.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx14.csv @@ -583,9 +583,17 @@ numeric cmath numeric concepts numeric cstddef +numeric cstdint +numeric cstring +numeric ctime +numeric execution numeric functional +numeric initializer_list +numeric iosfwd numeric iterator numeric limits +numeric new +numeric ratio numeric type_traits numeric version optional atomic diff --git a/libcxx/test/libcxx/transitive_includes/cxx17.csv b/libcxx/test/libcxx/transitive_includes/cxx17.csv --- a/libcxx/test/libcxx/transitive_includes/cxx17.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx17.csv @@ -583,9 +583,17 @@ numeric cmath numeric concepts numeric cstddef +numeric cstdint +numeric cstring +numeric ctime +numeric execution numeric functional +numeric initializer_list +numeric iosfwd numeric iterator numeric limits +numeric new +numeric ratio numeric type_traits numeric version optional atomic diff --git a/libcxx/test/libcxx/transitive_includes/cxx20.csv b/libcxx/test/libcxx/transitive_includes/cxx20.csv --- a/libcxx/test/libcxx/transitive_includes/cxx20.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx20.csv @@ -589,9 +589,17 @@ numeric cmath numeric concepts numeric cstddef +numeric cstdint +numeric cstring +numeric ctime +numeric execution numeric functional +numeric initializer_list +numeric iosfwd numeric iterator numeric limits +numeric new +numeric ratio numeric type_traits numeric version optional atomic diff --git a/libcxx/test/libcxx/transitive_includes/cxx23.csv b/libcxx/test/libcxx/transitive_includes/cxx23.csv --- a/libcxx/test/libcxx/transitive_includes/cxx23.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx23.csv @@ -399,7 +399,15 @@ numbers version numeric cmath numeric cstddef +numeric cstdint +numeric cstring +numeric ctime +numeric execution +numeric initializer_list +numeric iosfwd numeric limits +numeric new +numeric ratio numeric version optional compare optional cstddef diff --git a/libcxx/test/libcxx/transitive_includes/cxx26.csv b/libcxx/test/libcxx/transitive_includes/cxx26.csv --- a/libcxx/test/libcxx/transitive_includes/cxx26.csv +++ b/libcxx/test/libcxx/transitive_includes/cxx26.csv @@ -399,7 +399,15 @@ numbers version numeric cmath numeric cstddef +numeric cstdint +numeric cstring +numeric ctime +numeric execution +numeric initializer_list +numeric iosfwd numeric limits +numeric new +numeric ratio numeric version optional compare optional cstddef 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,73 @@ +//===----------------------------------------------------------------------===// +// +// 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 "MoveOnly.h" +#include "test_execution_policies.h" +#include "test_iterators.h" +#include "test_macros.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, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), ValueT(34), [](ValueT i, ValueT j) { + return i + j + 2; + }); + static_assert(std::is_same_v); + assert(ret == ValueT(expected)); + } + { + decltype(auto) ret = std::reduce(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), ValueT(34)); + static_assert(std::is_same_v); + assert(ret == expected - 2 * size); + } + { + decltype(auto) ret = std::reduce(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a))); + static_assert(std::is_same_v::value_type>); + assert(ret == expected - 2 * size - 34); + } + } + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, types::apply_type_identity{[](auto v) { + using Iter = typename decltype(v)::type; + types::for_each( + types::type_list{}, + TestIteratorWithPolicies::template apply>{}); + }}); + + 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,97 @@ +//===----------------------------------------------------------------------===// +// +// 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 "MoveOnly.h" +#include "test_execution_policies.h" +#include "test_iterators.h" +#include "test_macros.h" +#include "type_algorithms.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)), + ValueT(34), + [](ValueT i, ValueT j) { return i + j + 3; }, + [](ValueT i, ValueT 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); + } + } +}; + +int main(int, char**) { + types::for_each( + types::forward_iterator_list{}, types::apply_type_identity{[](auto v) { + using Iter2 = typename decltype(v)::type; + types::for_each( + types::forward_iterator_list{}, types::apply_type_identity{[](auto v2) { + using Iter1 = typename decltype(v2)::type; + types::for_each( + types::type_list{}, + TestIteratorWithPolicies::template apply>{}); + }}); + }}); + + 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,62 @@ +//===----------------------------------------------------------------------===// +// +// 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 "MoveOnly.h" +#include "test_execution_policies.h" +#include "test_iterators.h" +#include "test_macros.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)), + ValueT(34), + [](ValueT i, ValueT j) { return i + j; }, + [](ValueT i) { return i + 1; }); + static_assert(std::is_same_v); + assert(ret == expected); + } + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, types::apply_type_identity{[](auto v) { + using Iter2 = typename decltype(v)::type; + types::for_each( + types::type_list{}, + TestIteratorWithPolicies::template apply>{}); + }}); + + return 0; +}