[libc++][PSTL] Implement std::copy{,_n}

[ldionne]

libcxx/include/__algorithm/pstl_copy.h

29

I think it's fine to do in a separate patch. However, I think we need to do this before we can figure out the backend story because that's definitely an additional complexity we'll want to take into account in our dispatching mechanism.

35

Let's do this consistently.

[philnik]

• Address comments
• Improve tests

[ldionne]

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy.pass.cpp

99

I see this is repeating a lot, and because of C++17 we can't use template lambas. But we can do this:

types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity([](auto It) {
  using Iter = typename decltype(It)::type;
  // the rest of your stuff
}));

// where
template <class F>
struct apply_type_identity {
  F f;
  template <class ...Args>
  auto operator()() const {
    return f(std::type_identity<Args>{}...);
  }
};

We can bikeshed about the name of apply_type_identity, I'm open to anything reasonable. IMO if we apply this throughout, it will localize the "loops" and make the testing code easier to read (and write!). WDYT?

[ldionne]

Please watch CI!

[philnik]

• Rebased
• Address comments

[philnik]

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy.pass.cpp

99

I'm not a huge fan of the name, but I can't come up with anything better.

[jloser]

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy.pass.cpp

99

I think the name is fine FWIW. Do we have a generic type for applying a generic metafunction (e.g. so a call site could look like apply<F, std::type_identity>)? The metafunction would be bound with the Args parameter pack on the call operator like it is now. Then, if you had such generic construct, you wouldn't need to name the entity apply_type_identity, it would be obvious from the callers.

[philnik]

Rebased

[philnik]

• Rebased
• Try to fix CI

[philnik]

Use new dispatching scheme

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Rebased

[ldionne]

LGTM w/ comments and CI.

libcxx/include/__algorithm/pstl_backend.h

25–26 ↗

(On Diff #521501)

Let's add something like:

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:

libcxx/include/__algorithm/pstl_copy.h

42–49

Here I would do something like

if constexpr (can-be-optimized-to-memmove(_ForwardIterator, ...)) {
  // ditch the execution policy and call the single-threaded std::copy, since we know it handles the complexity of optimizing properly
  return std::copy(__first, __last, __result);
} else {
  return std::__pstl_frontend_dispatch(...);
}

In a separate patch.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy.pass.cpp

12

This isn't used anymore, and it means the test never ran!

99

The downside of apply<F, std::type_identity> is that F here is decltype(lamda), and that doesn't work with Clang :/

So we'd have to introduce the lambda and then do decltype(x), which is not as compositional.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy_n.pass.cpp

12

x2

93

Same comment about lambdas.

[philnik]

• Address comments
• Try to fix CI

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Fix diff

[philnik]

Fix diff

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_backends/cpu_backend.h
   __algorithm/pstl_backends/cpu_backends/any_of.h
   __algorithm/pstl_backends/cpu_backends/backend.h
   __algorithm/pstl_backends/cpu_backends/fill.h
   __algorithm/pstl_backends/cpu_backends/find_if.h
   __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
   __algorithm/pstl_frontend_dispatch.h
   __algorithm/pstl_transform.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h

libcxx/include/__algorithm/pstl_copy.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_PSTL_COPY_H
+#define _LIBCPP___ALGORITHM_PSTL_COPY_H
+
+#include <__algorithm/copy_n.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>
+#include <__type_traits/is_trivially_copyable.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
+
+// TODO: Use the std::copy/move shenanigans to forward to std::memmove
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
+copy(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __result) {
+  return std::transform(__policy, __first, __last, __result, __identity());
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          class _Size,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
+copy_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __result) {
+  if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value)
+    return std::copy(__policy, __first, __first + __n, __result);
+  else
+    return std::copy_n(__first, __n, __result);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_COPY_H

libcxx/include/__pstl/internal/glue_algorithm_defs.h

search_n(_ExecutionPolicy&& __exec,
          _BinaryPredicate __pred);
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Tp>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> search_n(
     _ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value);
 
 // [alg.copy]
 
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
-copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result);
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
-copy_n(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result);
-
 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
 copy_if(_ExecutionPolicy&& __exec,
         _ForwardIterator1 __first,
         _ForwardIterator1 __last,
         _ForwardIterator2 result,
         _Predicate __pred);
 

libcxx/include/__pstl/internal/glue_algorithm_impl.h

return std::search_n(
       __last,
       __count,
       __value,
       std::equal_to<typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
 // [alg.copy]
 
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
-__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 <class _ExecutionPolicy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
-__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 <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
 copy_if(_ExecutionPolicy&& __exec,
         _ForwardIterator1 __first,
         _ForwardIterator1 __last,
         _ForwardIterator2 __result,
         _Predicate __pred) {
   auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);

libcxx/include/algorithm

 #include <__algorithm/partial_sort.h>
 #include <__algorithm/partial_sort_copy.h>
 #include <__algorithm/partition.h>
 #include <__algorithm/partition_copy.h>
 #include <__algorithm/partition_point.h>
 #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>
 #include <__algorithm/pstl_transform.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
 #include <__algorithm/ranges_all_of.h>
 #include <__algorithm/ranges_any_of.h>

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// REQUIRES: with-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+//   ForwardIterator2 copy(ExecutionPolicy&& policy,
+//                         ForwardIterator1 first, ForwardIterator1 last,
+//                         ForwardIterator2 result);
+
+#include <algorithm>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(copy);
+
+static_assert(sfinae_test_copy<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_copy<std::execution::parallel_policy, int*, int*, int>);
+
+template <class Iter1, class Iter2>
+struct TestInt {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<int> a(size);
+      for (int i = 0; i != size; ++i)
+        a[i] = i + 1;
+
+      std::vector<int> 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<decltype(ret), Iter2>);
+      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 <class Iter1, class Iter2>
+struct TestNonTrivial {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<CopiedToTester> a(size);
+
+      std::vector<CopiedToTester> 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 <class Iter2>
+  void operator()() {}
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) {
+                    using Iter = typename decltype(v)::type;
+                    types::for_each(
+                        types::forward_iterator_list<int*>{},
+                        TestIteratorWithPolicies< types::partial_instantiation<TestInt, Iter>::template apply>{});
+                  }});
+
+  types::for_each(
+      types::forward_iterator_list<CopiedToTester*>{}, types::apply_type_identity{[](auto v) {
+        using Iter = typename decltype(v)::type;
+        types::for_each(
+            types::forward_iterator_list<CopiedToTester*>{},
+            TestIteratorWithPolicies< types::partial_instantiation<TestNonTrivial, Iter>::template apply>{});
+      }});
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy_n.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// REQUIRES: with-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator1, class Size, class ForwardIterator2>
+//   ForwardIterator2 copy_n(ExecutionPolicy&& exec,
+//                           ForwardIterator1 first, Size n,
+//                           ForwardIterator2 result);
+
+#include <algorithm>
+#include <vector>
+
+#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<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_copy_n<std::execution::parallel_policy, int*, int*, int>);
+
+template <class Iter1, class Iter2>
+struct TestInt {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<int> a(size);
+      for (int i = 0; i != size; ++i)
+        a[i] = i + 1;
+
+      std::vector<int> 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<decltype(ret), Iter2>);
+      assert(base(ret) == std::data(out) + std::size(out));
+      for (int i = 0; i != size; ++i)
+        assert(out[i] == i + 1);
+    }
+  }
+};
+
+struct TestIteratorsInt {
+  template <class Iter2>
+  void operator()() {
+    types::for_each(types::forward_iterator_list<int*>{},
+                    TestIteratorWithPolicies<types::partial_instantiation<TestInt, Iter2>::template apply>{});
+  }
+};
+
+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 <class Iter1, class Iter2>
+struct TestNonTrivial {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<CopiedToTester> a(size);
+
+      std::vector<CopiedToTester> 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 <class Iter2>
+  void operator()() {
+    types::for_each(types::forward_iterator_list<CopiedToTester*>{},
+                    TestIteratorWithPolicies<types::partial_instantiation<TestNonTrivial, Iter2>::template apply>{});
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorsInt{});
+  types::for_each(types::forward_iterator_list<CopiedToTester*>{}, TestIteratorsNonTrivial{});
+
+  return 0;
+}