This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by philnik on May 2 2023, 4:40 PM.

Diff Detail

Event Timeline

philnik created this revision.May 2 2023, 4:40 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 2 2023, 4:40 PM
philnik requested review of this revision.May 2 2023, 4:40 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 2 2023, 4:40 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik retitled this revision from [libc++][PSTL] Implement std::copy{,_n,_if} to [libc++][PSTL] Implement std::copy{,_n}.May 2 2023, 4:40 PM
ldionne added inline comments.May 3 2023, 8:32 AM
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 updated this revision to Diff 519095.May 3 2023, 8:59 AM
philnik marked an inline comment as done.
  • Address comments
  • Improve tests
ldionne accepted this revision.May 3 2023, 2:02 PM
ldionne added inline comments.
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?

This revision is now accepted and ready to land.May 3 2023, 2:02 PM

Please watch CI!

philnik updated this revision to Diff 519704.May 4 2023, 5:41 PM
philnik marked an inline comment as done.
  • Rebased
  • Address comments
philnik added inline comments.May 4 2023, 5:48 PM
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 added a subscriber: jloser.May 4 2023, 6:18 PM
jloser added inline comments.
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 updated this revision to Diff 520367.May 8 2023, 7:25 AM
  • Rebased
  • Try to fix CI
philnik updated this revision to Diff 521451.May 11 2023, 2:38 PM

Use new dispatching scheme

philnik requested review of this revision.May 11 2023, 3:28 PM

LGTM w/ comments and CI.

libcxx/include/__algorithm/pstl_backend.h
25–26

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.

ldionne accepted this revision.May 12 2023, 10:43 AM
This revision is now accepted and ready to land.May 12 2023, 10:43 AM
philnik updated this revision to Diff 521727.May 12 2023, 11:15 AM
philnik marked 4 inline comments as done.
  • Address comments
  • Try to fix CI
This revision was automatically updated to reflect the committed changes.
philnik reopened this revision.May 15 2023, 10:34 AM
This revision is now accepted and ready to land.May 15 2023, 10:34 AM
This revision was landed with ongoing or failed builds.May 15 2023, 2:47 PM
This revision was automatically updated to reflect the committed changes.