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_copy.h __algorithm/pstl_fill.h __algorithm/pstl_find.h __algorithm/pstl_for_each.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 @@ -24,7 +24,16 @@ /* TODO: Documentation of how backends work -A PSTL parallel backend is a tag type to which the following functions are associated, at minimum: +PSTL algorithms are a thin API layer that forward to a backend that implements the actual operation. The backend is +selected based on the execution policy provided by the user. + +All algorithms go through the dispatching mechanism, so a backend can customize any algorithm in the PSTL in a way that +suits it. However, the only exception to this is when an algorithm can be implemented by a C function, we assume that +the C function is the most efficient way to implement it on the platform and we use that unconditionally. For example, +`std::copy(policy, ...)` will forward to `memmove` if the iterators and the copied type allow for it, regardless of +whether the backend associated to `policy` implements `__pstl_copy`. + +The following functions must be provided by all backends: template void __pstl_for_each(_Backend, _ExecutionPolicy&&, _Iterator __first, _Iterator __last, _Func __f); @@ -57,6 +66,12 @@ template bool __pstl_all_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); + template + _OutIterator __pstl_copy(_Backend, _InIterator __first, _InIterator __last, _OutIterator __result); + + template + _OutIterator __pstl_copy_n(_Backend, _InIterator __first, _Size __n, _OutIterator __result); + template bool __pstl_none_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); diff --git a/libcxx/include/__algorithm/pstl_copy.h b/libcxx/include/__algorithm/pstl_copy.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_copy.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_PSTL_FILL_H +#define _LIBCPP___ALGORITHM_PSTL_FILL_H + +#include <__algorithm/copy_n.h> +#include <__algorithm/pstl_frontend_dispatch.h> +#include <__algorithm/pstl_transform.h> +#include <__config> +#include <__functional/identity.h> +#include <__iterator/iterator_traits.h> +#include <__type_traits/is_constant_evaluated.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_INCOMLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +_LIBCPP_BEGIN_NAMESPACE_STD + +// TODO: Use the std::copy/move shenanigans to forward to std::memmove + +template +void __pstl_copy(); + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator +copy(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __result) { + return std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_copy), + [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _ForwardOutIterator __g_result) { + return std::transform(__policy, __g_first, __g_last, __g_result, __identity()); + }, + std::move(__first), + std::move(__last), + std::move(__result)); +} + +template +void __pstl_copy_n(); + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator +copy_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __result) { + return std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_copy_n), + [&](_ForwardIterator __g_first, _Size __g_n, _ForwardOutIterator __g_result) { + if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) + return std::copy(__policy, __g_first, __g_first + __g_n, __g_result); + else + return std::copy_n(__g_first, __g_n, __g_result); + }, + __first, + __n, + std::move(__result)); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_INCOMLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___ALGORITHM_PSTL_FILL_H diff --git a/libcxx/include/__pstl/internal/glue_algorithm_defs.h b/libcxx/include/__pstl/internal/glue_algorithm_defs.h --- a/libcxx/include/__pstl/internal/glue_algorithm_defs.h +++ b/libcxx/include/__pstl/internal/glue_algorithm_defs.h @@ -112,14 +112,6 @@ // [alg.copy] -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> -copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result); - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> -copy_n(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result); - template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> copy_if(_ExecutionPolicy&& __exec, diff --git a/libcxx/include/__pstl/internal/glue_algorithm_impl.h b/libcxx/include/__pstl/internal/glue_algorithm_impl.h --- a/libcxx/include/__pstl/internal/glue_algorithm_impl.h +++ b/libcxx/include/__pstl/internal/glue_algorithm_impl.h @@ -178,42 +178,6 @@ // [alg.copy] -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> -copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result) { - auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result); - - using __is_vector = typename decltype(__dispatch_tag)::__is_vector; - - return __pstl::__internal::__pattern_walk2_brick( - __dispatch_tag, - std::forward<_ExecutionPolicy>(__exec), - __first, - __last, - __result, - [](_ForwardIterator1 __begin, _ForwardIterator1 __end, _ForwardIterator2 __res) { - return __pstl::__internal::__brick_copy(__begin, __end, __res, __is_vector{}); - }); -} - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> -copy_n(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result) { - auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result); - - using __is_vector = typename decltype(__dispatch_tag)::__is_vector; - - return __pstl::__internal::__pattern_walk2_brick_n( - __dispatch_tag, - std::forward<_ExecutionPolicy>(__exec), - __first, - __n, - __result, - [](_ForwardIterator1 __begin, _Size __sz, _ForwardIterator2 __res) { - return __pstl::__internal::__brick_copy_n(__begin, __sz, __res, __is_vector{}); - }); -} - template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> copy_if(_ExecutionPolicy&& __exec, diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1789,6 +1789,7 @@ #include <__algorithm/pop_heap.h> #include <__algorithm/prev_permutation.h> #include <__algorithm/pstl_any_all_none_of.h> +#include <__algorithm/pstl_copy.h> #include <__algorithm/pstl_fill.h> #include <__algorithm/pstl_find.h> #include <__algorithm/pstl_for_each.h> diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy.pass.cpp @@ -0,0 +1,102 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// + +// template +// ForwardIterator2 copy(ExecutionPolicy&& policy, +// ForwardIterator1 first, ForwardIterator1 last, +// ForwardIterator2 result); + +#include +#include + +#include "test_macros.h" +#include "test_execution_policies.h" +#include "test_iterators.h" + +EXECUTION_POLICY_SFINAE_TEST(copy); + +static_assert(sfinae_test_copy); +static_assert(!sfinae_test_copy); + +template +struct TestInt { + template + void operator()(Policy&& policy) { + // simple test + for (const int size : {0, 1, 2, 100, 350}) { + std::vector a(size); + for (int i = 0; i != size; ++i) + a[i] = i + 1; + + std::vector out(std::size(a)); + decltype(auto) ret = + std::copy(policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), Iter2(std::data(out))); + static_assert(std::is_same_v); + assert(base(ret) == std::data(out) + std::size(out)); + for (int i = 0; i != size; ++i) + assert(out[i] == i + 1); + } + } +}; + +struct CopiedToTester { + bool copied_to = false; + CopiedToTester() = default; + CopiedToTester(const CopiedToTester&) {} + CopiedToTester& operator=(const CopiedToTester&) { + assert(!copied_to); + copied_to = true; + return *this; + } + ~CopiedToTester() = default; +}; + +template +struct TestNonTrivial { + template + void operator()(Policy&& policy) { + // simple test + for (const int size : {0, 1, 2, 100, 350}) { + std::vector a(size); + + std::vector out(std::size(a)); + auto ret = std::copy(policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), Iter2(std::data(out))); + assert(base(ret) == std::data(out) + std::size(out)); + assert(std::all_of(std::begin(out), std::end(out), [](CopiedToTester& t) { return t.copied_to; })); + assert(std::none_of(std::begin(a), std::end(a), [](CopiedToTester& t) { return t.copied_to; })); + } + } +}; + +struct TestIteratorsNonTrivial { + template + void operator()() {} +}; + +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::forward_iterator_list{}, + TestIteratorWithPolicies< types::partial_instantiation::template apply>{}); + }}); + + types::for_each( + types::forward_iterator_list{}, types::apply_type_identity{[](auto v) { + using Iter = typename decltype(v)::type; + types::for_each( + types::forward_iterator_list{}, + TestIteratorWithPolicies< types::partial_instantiation::template apply>{}); + }}); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy_n.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy_n.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 + +// + +// template +// ForwardIterator2 copy_n(ExecutionPolicy&& exec, +// ForwardIterator1 first, Size n, +// ForwardIterator2 result); + +#include +#include + +#include "test_macros.h" +#include "test_execution_policies.h" +#include "test_iterators.h" + +EXECUTION_POLICY_SFINAE_TEST(copy_n); + +static_assert(sfinae_test_copy_n); +static_assert(!sfinae_test_copy_n); + +template +struct TestInt { + template + void operator()(Policy&& policy) { + // simple test + for (const int size : {0, 1, 2, 100, 350}) { + std::vector a(size); + for (int i = 0; i != size; ++i) + a[i] = i + 1; + + std::vector out(std::size(a)); + decltype(auto) ret = std::copy_n(policy, Iter1(std::data(a)), std::size(a), Iter2(std::data(out))); + static_assert(std::is_same_v); + assert(base(ret) == std::data(out) + std::size(out)); + for (int i = 0; i != size; ++i) + assert(out[i] == i + 1); + } + } +}; + +struct CopiedToTester { + bool copied_to = false; + CopiedToTester() = default; + CopiedToTester(const CopiedToTester&) {} + CopiedToTester& operator=(const CopiedToTester&) { + assert(!copied_to); + copied_to = true; + return *this; + } + ~CopiedToTester() = default; +}; + +template +struct TestNonTrivial { + template + void operator()(Policy&& policy) { + // simple test + for (const int size : {0, 1, 2, 100, 350}) { + std::vector a(size); + + std::vector out(std::size(a)); + auto ret = std::copy_n(policy, Iter1(std::data(a)), std::size(a), Iter2(std::data(out))); + assert(base(ret) == std::data(out) + std::size(out)); + assert(std::all_of(std::begin(out), std::end(out), [](CopiedToTester& t) { return t.copied_to; })); + assert(std::none_of(std::begin(a), std::end(a), [](CopiedToTester& t) { return t.copied_to; })); + } + } +}; + +struct TestIteratorsNonTrivial { + template + void operator()() { + types::for_each(types::forward_iterator_list{}, + TestIteratorWithPolicies::template apply>{}); + } +}; + +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{}, + TestIteratorWithPolicies::template apply>{}); + }}); + types::for_each(types::forward_iterator_list{}, TestIteratorsNonTrivial{}); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/pstl.transform.unary.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/pstl.transform.unary.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/pstl.transform.unary.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/pstl.transform.unary.pass.cpp @@ -31,7 +31,7 @@ // transform algorithm that doesn't take an execution policy, which is not constrained at all. template -struct Test { +struct TestInt { template void operator()(Policy&& policy) { // simple test