This is an archive of the discontinued LLVM Phabricator instance.

[libc++][PSTL] Copy the headers into libc++
ClosedPublic

Authored by philnik on Jan 14 2023, 6:46 PM.

Details

Reviewers
ldionne
jdoerfert
Group Reviewers
Restricted Project
Commits
rG92bd81a2be23: [libc++][PSTL] Copy the headers into libc++
Summary

We decided to integrate the PSTL into our own headers and only share the backend impletementations. This is a first step in that direction, specifically it copies the PSTL headers into the libc++ structure.

Diff Detail

Event Timeline

philnik created this revision.Jan 14 2023, 6:46 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 14 2023, 6:46 PM
Herald added subscribers: miyuki, mgrang. · View Herald Transcript
philnik retitled this revision from [libc++][PSTL][NFC] Copy the headers into libc++ to [libc++][PSTL] Copy the headers into libc++.
philnik updated this revision to Diff 489371.Jan 15 2023, 9:40 AM

Try to fix CI

philnik updated this revision to Diff 489657.Jan 16 2023, 5:41 PM

Try to fix CI

philnik updated this revision to Diff 500157.Feb 24 2023, 5:25 AM

Try to fix CI

philnik published this revision for review.Mar 13 2023, 9:39 AM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript

Thanks for the stack of patches! This is a really nice start. Before we commit to going into a specific direction, I think it is useful to lay out how we envision things being at the end, and then roughly how we're going to get there.

Here's a starting point. At the end, I think what we want to have is (this doesn't necessarily reflect *how* we're going to get there):

  1. No more <__pstl_algorithm> & other glue headers -- instead the PSTL versions would be defined in suitably named <__algorithm/pstl_any_of.h> headers and included directly inside <algorithm>.
  2. No more <pstl/internal/algorithm_impl.h> and <pstl/internal/algorithm_fwd.h> headers & friends -- those contain the implementation of algorithms and they would be in <__algorithm/pstl_any_of.h> & friends instead.
  3. No more <pstl/internal/glue_algorithm_defs.h> and <pstl/internal/glue_algorithm_impl.h> headers & friends -- those contain the standard facing algorithm names, which would now be directly in <__algorithm/pstl_any_of.h> & friends.
  4. The headers implementing backends are kept and we try not to make significant changes to them, if possible. This should allow keeping the backends in sync with pstl/ as needed. We might want to reorganize them under something like <__pstl_backends/{omp.h,tbb.h,serial.h,etc.}> or something similar.
  5. The configuration headers __pstl_config_site.in, pstl_config.h can be simplified to only contain the macros we actually need (pruning platforms and compilers we don't support), and then folded into __config_site and __config as appropriate.
  6. The current pstl/ has several layers of forward declarations and boilerplate, and I think we can simplify that since we don't need the flexibility of e.g. std::any_of(ExecutionPolicy, ...) being forward-declared anymore. So as you iterate to achieve the above steps (in particular 1-2-3), it would be reasonable to fold some of the layers of complexity. I see you've done that already in e.g. D143161.
  7. We should have our own tests for these algorithms and they should follow the usual libc++ testing conventions. I think we should base them on the existing pstl tests but we can add them as we iterate on steps (1-2-3).

In terms of how to get there, I think your current approach makes sense, however I would start with a clean slate. So before this patch, I would create a patch that basically removes the current integration (including the pstl test symlink) so that we start the new integration from a clean slate.

@philnik I think this properly describes what you had planned on doing (and which I agree is the right thing to do). Additional thoughts/comments?

Also CCing a few folks for awareness since they might have opinions and it would be good to get a common agreement on the direction before we start chipping away at the algorithms. @rarutyun @Mordante @var-const

bcain added a subscriber: bcain.Mar 15 2023, 8:32 AM

Thanks for the stack of patches! This is a really nice start. Before we commit to going into a specific direction, I think it is useful to lay out how we envision things being at the end, and then roughly how we're going to get there.

Here's a starting point. At the end, I think what we want to have is (this doesn't necessarily reflect *how* we're going to get there):

  1. No more <__pstl_algorithm> & other glue headers -- instead the PSTL versions would be defined in suitably named <__algorithm/pstl_any_of.h> headers and included directly inside <algorithm>.
  2. No more <pstl/internal/algorithm_impl.h> and <pstl/internal/algorithm_fwd.h> headers & friends -- those contain the implementation of algorithms and they would be in <__algorithm/pstl_any_of.h> & friends instead.
  3. No more <pstl/internal/glue_algorithm_defs.h> and <pstl/internal/glue_algorithm_impl.h> headers & friends -- those contain the standard facing algorithm names, which would now be directly in <__algorithm/pstl_any_of.h> & friends.
  4. The headers implementing backends are kept and we try not to make significant changes to them, if possible. This should allow keeping the backends in sync with pstl/ as needed. We might want to reorganize them under something like <__pstl_backends/{omp.h,tbb.h,serial.h,etc.}> or something similar.

+1 for as little divergence from upstream as possible.

  1. The configuration headers __pstl_config_site.in, pstl_config.h can be simplified to only contain the macros we actually need (pruning platforms and compilers we don't support), and then folded into __config_site and __config as appropriate.
  2. The current pstl/ has several layers of forward declarations and boilerplate, and I think we can simplify that since we don't need the flexibility of e.g. std::any_of(ExecutionPolicy, ...) being forward-declared anymore. So as you iterate to achieve the above steps (in particular 1-2-3), it would be reasonable to fold some of the layers of complexity. I see you've done that already in e.g. D143161.
  3. We should have our own tests for these algorithms and they should follow the usual libc++ testing conventions. I think we should base them on the existing pstl tests but we can add them as we iterate on steps (1-2-3).

In terms of how to get there, I think your current approach makes sense, however I would start with a clean slate. So before this patch, I would create a patch that basically removes the current integration (including the pstl test symlink) so that we start the new integration from a clean slate.

@philnik I think this properly describes what you had planned on doing (and which I agree is the right thing to do). Additional thoughts/comments?

Also CCing a few folks for awareness since they might have opinions and it would be good to get a common agreement on the direction before we start chipping away at the algorithms. @rarutyun @Mordante @var-const

I'm not too familiar with pstl so I don't have a strong opinion. What I read sounds sensible, thanks @philnik &
@ldionne for the detailed plan. I think it would be great to put some of these design ideas in a developer page for our documentation. There we can also link to the upstream projects we provide.

Not an issue for this patch series, but I wonder how we can properly sync with upstream. We've inherited the ryu algorithm for to_chars but we don't sync up with upstream MSVC STL or Ulf's GitHub.

Not an issue for this patch series, but I wonder how we can properly sync with upstream. We've inherited the ryu algorithm for to_chars but we don't sync up with upstream MSVC STL or Ulf's GitHub.

Since we own both libcxx/ and pstl/ it should be almost trivial to sync them. We have to review the PSTL patches anyways, so we just have to remember to make a follow-up patch.

Thanks for keeping me in the loop.

  1. No more <pstl/internal/algorithm_impl.h> and <pstl/internal/algorithm_fwd.h> headers & friends -- those contain the implementation of algorithms and they would be in <__algorithm/pstl_any_of.h> & friends instead.
  2. No more <pstl/internal/glue_algorithm_defs.h> and <pstl/internal/glue_algorithm_impl.h> headers & friends -- those contain the standard facing algorithm names, which would now be directly in <__algorithm/pstl_any_of.h> & friends.
  3. The headers implementing backends are kept and we try not to make significant changes to them, if possible. This should allow keeping the backends in sync with pstl/ as needed. We might want to reorganize them under something like <__pstl_backends/{omp.h,tbb.h,serial.h,etc.}> or something similar.

While I understand the approach you suggested for glue_algorithm_<fwd|impl>.h (and friends) I think that algorithm_<fwd|impl>.h (and friends) is something you probably want to keep more or less as is. They might be reorganized similar to what you suggested for __pstl_backends but in general algorithm_impl.h contains patterns, public API has mapping on. Since many different algorithms could map on single pattern it's common layer and I am not sure that you want to have that layer split between the files that correspond to public API. If I am not mistaken it might be not so simple to do that from both

  • separation perspective (you would eventually need to include those that might create undesired algorithm dependencies)
  • further synchronization with PSTL upstream perspective.

Probably the good thing to do is a renaming of algorithm_impl.h and similar ones to something that would not confuse libc++ people (e.g., __pstl[_parallel]_patterns/something).

The choice is yours, anyway.

  1. The current pstl/ has several layers of forward declarations and boilerplate, and I think we can simplify that since we don't need the flexibility of e.g. std::any_of(ExecutionPolicy, ...) being forward-declared anymore. So as you iterate to achieve the above steps (in particular 1-2-3), it would be reasonable to fold some of the layers of complexity. I see you've done that already in e.g. D143161.

The only reason why forwarding declarations were introduced is reducing the compilation time when parallel backends (i.e.., both TBB and OpenMP) are not available or if parallel policies (par, par_unseq) are disabled explicitly (if this feature is supposed to be at all. For example, with defining some macro). If you guys think that it's something that impossible in your case then you probably don't need those forward declarations. This is completely up to you, of course. I am just trying to give (or remind) more context to make a decision keeping in mind different aspects.

Thanks for keeping me in the loop.

  1. No more <pstl/internal/algorithm_impl.h> and <pstl/internal/algorithm_fwd.h> headers & friends -- those contain the implementation of algorithms and they would be in <__algorithm/pstl_any_of.h> & friends instead.
  2. No more <pstl/internal/glue_algorithm_defs.h> and <pstl/internal/glue_algorithm_impl.h> headers & friends -- those contain the standard facing algorithm names, which would now be directly in <__algorithm/pstl_any_of.h> & friends.
  3. The headers implementing backends are kept and we try not to make significant changes to them, if possible. This should allow keeping the backends in sync with pstl/ as needed. We might want to reorganize them under something like <__pstl_backends/{omp.h,tbb.h,serial.h,etc.}> or something similar.

While I understand the approach you suggested for glue_algorithm_<fwd|impl>.h (and friends) I think that algorithm_<fwd|impl>.h (and friends) is something you probably want to keep more or less as is. They might be reorganized similar to what you suggested for __pstl_backends but in general algorithm_impl.h contains patterns, public API has mapping on. Since many different algorithms could map on single pattern it's common layer and I am not sure that you want to have that layer split between the files that correspond to public API. If I am not mistaken it might be not so simple to do that from both

  • separation perspective (you would eventually need to include those that might create undesired algorithm dependencies)
  • further synchronization with PSTL upstream perspective.

Probably the good thing to do is a renaming of algorithm_impl.h and similar ones to something that would not confuse libc++ people (e.g., __pstl[_parallel]_patterns/something).

The choice is yours, anyway.

  1. The current pstl/ has several layers of forward declarations and boilerplate, and I think we can simplify that since we don't need the flexibility of e.g. std::any_of(ExecutionPolicy, ...) being forward-declared anymore. So as you iterate to achieve the above steps (in particular 1-2-3), it would be reasonable to fold some of the layers of complexity. I see you've done that already in e.g. D143161.

The only reason why forwarding declarations were introduced is reducing the compilation time when parallel backends (i.e.., both TBB and OpenMP) are not available or if parallel policies (par, par_unseq) are disabled explicitly (if this feature is supposed to be at all. For example, with defining some macro). If you guys think that it's something that impossible in your case then you probably don't need those forward declarations. This is completely up to you, of course. I am just trying to give (or remind) more context to make a decision keeping in mind different aspects.

Thanks for the additional info. I've looked a bit more through algorithm_impl.h. I think we want to keep a few of the more complex functions (and maybe move them to parallel_impl.h), but most of it just forwards to other functions. We probably want to remove these. Regarding the forward declarations, we have to always provide these overloads to be conforming. If there is no parallel backend available, the serial backend should be used instead of not providing anything. I also don't really see a use-case for disabling specific policies.

If there is no parallel backend available, the serial backend should be used instead of not providing anything. I also don't really see a use-case for disabling specific policies.

As far as I remember the it was done in libstdc++ when serial backend was not available but the idea also was to remove third-party dependencies (@rodgert could correct me if I am wrong) libstdc++ 9 just includes TBB headers by default if `#include <execution>" appears in the code: https://godbolt.org/z/MGaccsq9a

If there is any need to disable parallel policies today - I am not sure. If a good comes in my head at some point I'll let you know.

I'm not too familiar with pstl so I don't have a strong opinion. What I read sounds sensible, thanks @philnik &
@ldionne for the detailed plan. I think it would be great to put some of these design ideas in a developer page for our documentation.

@philnik Can you put this in a DesignDoc?

Since many different algorithms could map on single pattern it's common layer [...]

When we looked with @philnik, I think we did not find many patterns that were reused, which is why we came to the conclusion that having a systematic layer of patterns for all algorithms was not pulling its weigh. You know the library better, so if we misunderstood something, please let us know. If we didn't miss anything, then I do believe that keeping reusable helpers (patterns) as implementation-detail functions to be reused would be sufficient, without having to have a full layer of customization.

The only reason why forwarding declarations were introduced is reducing the compilation time when parallel backends (i.e.., both TBB and OpenMP) are not available [...]

That's interesting, I had not thought of that. However, as @philnik said, I think we'll want to go for the serial backend when we don't have anything better available, so that shouldn't be an issue.

ldionne accepted this revision.Apr 20 2023, 8:30 AM
ldionne added inline comments.
libcxx/test/libcxx/lint/lint_headers.sh.py
18 ↗(On Diff #515336)
libcxx/test/libcxx/private_headers.verify.cpp
26 ↗(On Diff #515336)
This revision is now accepted and ready to land.Apr 20 2023, 8:30 AM
philnik updated this revision to Diff 515568.Apr 20 2023, 8:34 PM
philnik marked 2 inline comments as done.
  • Address comments
  • Try to fix CI
This revision was landed with ongoing or failed builds.Apr 21 2023, 2:21 AM
This revision was automatically updated to reflect the committed changes.
libcxx/include/pstl/internal/algorithm_fwd.h