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

[philnik]

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.

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Rebaed

[philnik]

Rebased

[philnik]

Try to fix CI

[ldionne]

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

[Mordante]

In D141779#4189841, @ldionne wrote:

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.

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

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.

[philnik]

In D141779#4210839, @Mordante wrote:

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.

[rarutyun]

Thanks for keeping me in the loop.

In D141779#4189841, @ldionne wrote:

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.

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.

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.

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.

[philnik]

In D141779#4213395, @rarutyun wrote:

Thanks for keeping me in the loop.

In D141779#4189841, @ldionne wrote:

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.

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.

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.

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.

[rarutyun]

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.

[ldionne]

In D141779#4210839, @Mordante wrote:

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?

In D141779#4213395, @rarutyun wrote:

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.

[philnik]

Rebased

[ldionne]

libcxx/test/libcxx/lint/lint_headers.sh.py

18 ↗

(On Diff #515336)

libcxx/test/libcxx/private_headers.verify.cpp

26

[philnik]

• Address comments
• Try to fix CI

[philnik]

Rebased

[philnik]

Fix diff

libcxx/test/libcxx/private_headers.verify.cpp

for header in private_headers:
   # Skip headers that are not private yet in the modulemap
   if header in private_headers_still_public_in_modules:
     continue
 
   # Skip private headers that start with __support -- those are not in the modulemap yet
   if header.startswith('__support'):
     continue
 
-  # TODO: Stop skipping PSTL headers once their integration is finished.
+  # Skip PSTL headers. They might not be available.
   if header.startswith('__pstl'):
     continue
 
   print("{ifdef}#{indent}include <{header}> // {expected_error}@*:* {{{{use of private header from outside its module: '{header}'}}}}{endif}".format(
     ifdef='#if ' + header_restrictions[header] + '\n' if header in header_restrictions else '',
     indent='   ' if header in header_restrictions else '',
     header=header,
     expected_error='expected-error',