[libc++][pstl] Promote CPU backends to top-level backends (#88968)

This patch removes the two-level backend dispatching mechanism we had in
the PSTL. Instead of selecting both a PSTL backend and a

[libc++][pstl] Promote CPU backends to top-level backends (#88968)

This patch removes the two-level backend dispatching mechanism we had in
the PSTL. Instead of selecting both a PSTL backend and a PSTL CPU
backend, we now only select a top-level PSTL backend. This greatly
simplifies the PSTL configuration layer.

While this patch technically removes some flexibility from the PSTL
configuration mechanism because CPU backends are not considered
separately, it opens the door to a much more powerful configuration
mechanism based on chained backends in a follow-up patch.

This is a step towards overhauling the PSTL dispatching mechanism.

show more ...

[libc++][PSTL] Introduce cpu traits (#88134)

Currently, CPU backends in the PSTL are created by defining functions
in the __par_backend namespace. Then, the PSTL includes the CPU backend
that gets

[libc++][PSTL] Introduce cpu traits (#88134)

Currently, CPU backends in the PSTL are created by defining functions
in the __par_backend namespace. Then, the PSTL includes the CPU backend
that gets configured via CMake and gets those definitions.

This prevents CPU backends from easily co-existing and is a bit
confusing.
To solve this problem, this patch introduces the notion of __cpu_traits,
which is a cheap encapsulation of the basis operations required to
implement a CPU-based PSTL. Different backends can now define their own
tag and coexist, and the CPU-based PSTL will simply use __cpu_traits to
dispatch to the right implementation of e.g. __for_each.

Note that this patch doesn't change the actual implementation of the
backends in any way, it only modifies how that implementation is
accessed
to implement PSTL algorithms.

This patch is a step towards #88131.

show more ...

[libc++][PSTL] Add a __parallel_sort implementation to libdispatch

Reviewed By: #libc, ldionne

Spies: ldionne, libcxx-commits

Differential Revision: https://reviews.llvm.org/D155136

[libc++][PSTL] Simplify the partitioning algorithm until we have better data to know how to chunk better

The current chunking strategy is very bad for sorting, and we don't really know how to chunk

[libc++][PSTL] Simplify the partitioning algorithm until we have better data to know how to chunk better

The current chunking strategy is very bad for sorting, and we don't really know how to chunk in general. This fixes the performance problem for sorting.

Reviewed By: ldionne, #libc

Spies: libcxx-commits, krytarowski

Differential Revision: https://reviews.llvm.org/D155531

show more ...

[libc++] Make sure we use the libdispatch backend on Apple platforms

The Apple.cmake cache wasn't set up properly, so we wouldn't enable
the libdispatch backend by default on Apple platforms. This p

[libc++] Make sure we use the libdispatch backend on Apple platforms

The Apple.cmake cache wasn't set up properly, so we wouldn't enable
the libdispatch backend by default on Apple platforms. This patch
fixes the issue and adds a test.

We also need to make various drive-by fixes:
- Drop the usage of std::vector in libdispatch.h to avoid changing
the transitive includes only on Apple platforms.
- Fix includes
- Use __construct at since construct_at is unavailable in C++17
- Get rid of the (unused) __get_memory_resource function since that
adds a back-deployment requirement and we don't use it right now.
- Fix bugs in the chunking logic around boundary conditions.

Differential Revision: https://reviews.llvm.org/D155649

show more ...

[libc++][PSTL] Add a GCD backend

Reviewed By: ldionne, #libc

Spies: arichardson, mgrang, krytarowski, libcxx-commits, h-vetinari

Differential Revision: https://reviews.llvm.org/D151717