[libc++][PSTL] Add a simple std::thread backend

[philnik]

Summary

This is just to test that the PSTL works with parallelization. This is not supposed to be a production-ready backend.

[ldionne]

I think this LGTM w/ CI passing. I'd like to see again once rebased and passing though.

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

21

__assert instead, and put this above with the other includes.

52

_LIBCPP_ASSERT

libcxx/include/__config

1274–1276

Do we still need this? If not let's remove it.

[philnik]

Address comments

libcxx/include/__config

1274–1276

It's still used by the __pstl/ headers, so I'd rather keep it for now.

[philnik]

Generate files

[philnik]

Rebased

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Different approach

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[EricWF]

The __threading header, which defines a stable API that libc++ uses to implement threading primitives. This has been used by a bunch of vendors to shim in the different implementations for their platforms.
I believe we'll want to do the same thing here.

Do we know what the full API will look like yet?

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

27

Small nit. These namespaces add a bunch of size to the mangled names. Do we need to be this descriptive?

[EricWF]

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

39

This doesn't need a capture default.

46

This can overflow in crazy large inputs, right?

I don't know that it's a problem, but I wanted to point it out.

56

Is there somewhere in the spec it says we don't want to copy the functor? That seems potentially racy?

64

What happens here if the user supplied function throws?

libcxx/src/pstl/thread_backend.cpp

19 ↗

(On Diff #522638)

Why are we doing void* here?

I really really hate losing the type safety.

[philnik]

In D150284#4347301, @EricWF wrote:

The __threading header, which defines a stable API that libc++ uses to implement threading primitives. This has been used by a bunch of vendors to shim in the different implementations for their platforms.
I believe we'll want to do the same thing here.

Do we know what the full API will look like yet?

We don't know exactly which parts we will require, but I don't think that's relevant for this patch. We only implement a single (primitive) backend here, which will most likely not exist for a long time in this form.

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

46

It could hypothetically overflow, but I don't think that is a problem for real code. This will also change later anyways.

56

No, but it also doesn't prevent us from calling this from multiple threads.

64

We terminate when the user throws inside a thread, so it's not relevant.

libcxx/src/pstl/thread_backend.cpp

19 ↗

(On Diff #522638)

To avoid the transitive includes. As said in the description, this is not production-ready.

[philnik]

Try to fix CI

[EricWF]

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

33

This calculation seems a bit weird to me.

We're basically saying that if no concurrency is reported, then we'll use 2 (not one) threads.
Why are we not just running the algorithm in the current thread in this case?

Either way, it seems like we should be using the calling thread to do some work rather than just waiting on the other threads to join.

51

This seems like a correctness issue we could easily find in testing, and we probably don't need a dynamic check for it here.

56

Right, but given that we just copied it. It seems wiser to also copy it as well for each thread.

[EricWF]

In D150284#4347476, @philnik wrote:

In D150284#4347301, @EricWF wrote:

The __threading header, which defines a stable API that libc++ uses to implement threading primitives. This has been used by a bunch of vendors to shim in the different implementations for their platforms.
I believe we'll want to do the same thing here.

Do we know what the full API will look like yet?

We don't know exactly which parts we will require, but I don't think that's relevant for this patch. We only implement a single (primitive) backend here, which will most likely not exist for a long time in this form.

I'm a bit worried about shipping these patches then. I normally prefer to have a bunch more certainty when committing stuff to non-experimental bits of the library. @ldionne, you're cool with this plan?

When will we know what we need?
When will the API be stable?

Because providing an API for vendors here is going to be important.

libcxx/include/__algorithm/pstl_backend.h

89

Mid-header includes are really gross. Can we avoid that?

[philnik]

In D150284#4350281, @EricWF wrote:

In D150284#4347476, @philnik wrote:

In D150284#4347301, @EricWF wrote:

The __threading header, which defines a stable API that libc++ uses to implement threading primitives. This has been used by a bunch of vendors to shim in the different implementations for their platforms.
I believe we'll want to do the same thing here.

Do we know what the full API will look like yet?

We don't know exactly which parts we will require, but I don't think that's relevant for this patch. We only implement a single (primitive) backend here, which will most likely not exist for a long time in this form.

I'm a bit worried about shipping these patches then. I normally prefer to have a bunch more certainty when committing stuff to non-experimental bits of the library. @ldionne, you're cool with this plan?

This part of the library is experimental?

When will we know what we need?
When will the API be stable?

Because providing an API for vendors here is going to be important.

I don't know exactly what you mean by "here". Do you mean as part of the std::thread backend? If yes, I very much disagree. This is already layer two of abstractions which vendors can customize. Adding a third one would just be absurd.

[philnik]

Try to fix CI

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

33

Frankly, I don't really care. As I already said, this is a shitty backend and shouldn't be used in production. This is more of a placeholder than anything else. We should implement a proper thread pool later and not instantiate threads every time an algorithm is called.

[EricWF]

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

33

OK, then I don't know that we should commit this.

What's the purpose of doing it poorly now, rather than properly later?

[philnik]

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

33

The purpose is that we can check that dispatching etc. works with multiple backends and we avoid assuming too much about what the backend does, since we would otherwise run everything on a single thread.

[EricWF]

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

33

OK, that seems like something that we don't need to check in in order for it to be initially tested.

Then, when we have a backend ready for production, we can check that in.

Or alternatively, we can check the backend in under test/ as a test header.

[philnik]

Try to fix CI

[ldionne]

In D150284#4350281, @EricWF wrote:

I'm a bit worried about shipping these patches then. I normally prefer to have a bunch more certainty when committing stuff to non-experimental bits of the library. @ldionne, you're cool with this plan?

Yes, I believe that's the best way to make progress here. We're implementing different backends to make sure that the customization points work and get a feel for how we want things to look like. However, making the backend really good would be wasted time at this point because we don't know whether we'll have to change some of the customization points. This is all guarded behind -fexperimental-library, which means that we're not actually shipping any of it by default.

Don't get me wrong, we'll make the backend(s) better before declaring this non-experimental, but right now we're trying to figure out the backend API and how to implement algorithms in terms of each other more than we're trying to create a really well optimized backend implementation.

[ldionne]

As I've said before, the goal of this backend is for us to figure out the customization points and create the plumbing for adding new CPU back-ends, and to weed out any issues we see while bringing up this "toy" backend. This is *not* the way the std::thread backend will look in the end, however it would be a waste of time to spend time optimizing it at this point since we're not certain what the CPU backend API will need to look like in the end. We suspect it'll look pretty much like the original PSTL customization points, but we might discover the need to do some things differently as we look into other backends (e.g. GCD). If that happens, any work put in making the std::thread backend good right now would potentially be wasted.

So given the spirit of this patch, I'm fine with it -- basically my bar here is:

1. I'm happy with the pluming it adds
2. The implementation looks correct and it passes tests

@EricWF Please let us know if you still see an issue with this plan.

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

30

Can you add a comment here explaining that this implementation is experimental and will be replaced by a real implementation when the library is ready for production? Just to make it clear it was never meant to be used prime time. This should be clear from the need to use -fexperimental-library, but a comment here clarifies even more, I guess.

[philnik]

• Address comments
• Try to fix CI

[ldionne]

After discussing with @EricWF, we agreed that the actually relevant part of this patch is not the implementation of the threading backend, but rather the plumbing around it (e.g the CMake configuration, the #ifdefs in pstl_backend.h, the __config_site bits, etc.). As such, I think we should rip out the .cpp file and only implement __parallel_for and __cancel_execution in a serial way here (with a comment saying it's temporary). Then, once we have the full CPU backend API checked in (e.g. __parallel_transform_reduce and friends), we can go back and create a reasonable std::thread backend implementation.

[philnik]

Address comments

[philnik]

Rebased

[ldionne]

LGTM, this addresses the issues I had discussed with @EricWF .

[EricWF]

I'm going to unblock this. Because I don't think it's harmful.

However, It's my view that ff the goal of this whole project is to nail down the underlying API and customization points, this change doesn't help reach said goal.
In my opinion, the work that should be done first here, is work that allows other users to specify their own backends.

libcxx/CMakeLists.txt

 option(LIBCXX_HAS_WIN32_THREAD_API "Ignore auto-detection and force use of win32 thread API" OFF)
 option(LIBCXX_HAS_EXTERNAL_THREAD_API
   "Build libc++ with an externalized threading API.
    This option may only be set to ON when LIBCXX_ENABLE_THREADS=ON." OFF)
 option(LIBCXX_BUILD_EXTERNAL_THREAD_LIBRARY
     "Build libc++ with an externalized threading library.
      This option may only be set to ON when LIBCXX_ENABLE_THREADS=ON" OFF)
 
+if (LIBCXX_ENABLE_THREADS)
+  set(LIBCXX_PSTL_CPU_BACKEND "std_thread" CACHE STRING "Which PSTL CPU backend to use")
+else()
+  set(LIBCXX_PSTL_CPU_BACKEND "serial" CACHE STRING "Which PSTL CPU backend to use")
+endif()
+
 # Misc options ----------------------------------------------------------------
 # FIXME: Turn -pedantic back ON. It is currently off because it warns
 # about #include_next which is used everywhere.
 option(LIBCXX_ENABLE_PEDANTIC "Compile with pedantic enabled." OFF)
 option(LIBCXX_ENABLE_WERROR "Fail and stop if a warning is triggered." OFF)
 option(LIBCXX_DISABLE_MACRO_CONFLICT_WARNINGS "Disable #warnings about conflicting macros." OFF)
 
 option(LIBCXX_GENERATE_COVERAGE "Enable generating code coverage." OFF)

 config_define_if_not(LIBCXX_ENABLE_VENDOR_AVAILABILITY_ANNOTATIONS _LIBCPP_HAS_NO_VENDOR_AVAILABILITY_ANNOTATIONS)
 config_define_if(LIBCXX_ENABLE_DEBUG_MODE _LIBCPP_ENABLE_DEBUG_MODE)
 if (LIBCXX_ENABLE_ASSERTIONS)
   config_define(1 _LIBCPP_ENABLE_ASSERTIONS_DEFAULT)
 else()
   config_define(0 _LIBCPP_ENABLE_ASSERTIONS_DEFAULT)
 endif()
 
+if (LIBCXX_PSTL_CPU_BACKEND STREQUAL "serial")
+  config_define(1 _LIBCPP_PSTL_CPU_BACKEND_SERIAL)
+elseif(LIBCXX_PSTL_CPU_BACKEND STREQUAL "std_thread")
+  config_define(1 _LIBCPP_PSTL_CPU_BACKEND_THREAD)
+else()
+  message(FATAL_ERROR "LIBCXX_PSTL_CPU_BACKEND is set to ${LIBCXX_PSTL_CPU_BACKEND}, which is not a valid backend.
+                       Valid backends are: serial, std_thread")
+endif()
+
 if (LIBCXX_ABI_DEFINES)
   set(abi_defines)
   foreach (abi_define ${LIBCXX_ABI_DEFINES})
     if (NOT abi_define MATCHES "^_LIBCPP_ABI_")
       message(SEND_ERROR "Invalid ABI macro ${abi_define} in LIBCXX_ABI_DEFINES")
     endif()
     list(APPEND abi_defines "#define ${abi_define}")
   endforeach()

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_backend.h
   __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/thread.h
   __algorithm/pstl_backends/cpu_backends/transform.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

libcxx/include/__algorithm/pstl_backend.h

 
 #  if _LIBCPP_STD_VER >= 20
 template <>
 struct __select_backend<std::execution::unsequenced_policy> {
   using type = __cpu_backend_tag;
 };
 #  endif
 
-#  if defined(_PSTL_CPU_BACKEND_SERIAL)
+#  if defined(_LIBCPP_PSTL_CPU_BACKEND_SERIAL) || defined(_LIBCPP_PSTL_CPU_BACKEND_THREAD)
+#    include <__algorithm/pstl_backends/cpu_backend.h>
 template <>
 struct __select_backend<std::execution::parallel_policy> {
   using type = __cpu_backend_tag;
 };
 
 template <>
 struct __select_backend<std::execution::parallel_unsequenced_policy> {
   using type = __cpu_backend_tag;

libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.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_BACKENDS_CPU_BACKEND_BACKEND_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H
 
 #include <__config>
 
-#if defined(_LIBCPP_HAS_NO_THREADS) || defined(_PSTL_CPU_BACKEND_SERIAL)
+#if defined(_LIBCPP_PSTL_CPU_BACKEND_SERIAL)
 #  include <__algorithm/pstl_backends/cpu_backends/serial.h>
+#elif defined(_LIBCPP_PSTL_CPU_BACKEND_THREAD)
+#  include <__algorithm/pstl_backends/cpu_backends/thread.h>
 #else
 #  error "Invalid CPU backend choice"
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 struct __cpu_backend_tag {};
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.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_BACKENDS_CPU_BACKENDS_THREAD_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_THREAD_H
+
+#include <__assert>
+#include <__config>
+#include <thread>
+#include <vector>
+
+#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
+
+namespace __par_backend::inline __thread_cpu_backend {
+
+template <class _RandomAccessIterator, class _Fp>
+_LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
+  vector<thread> __threads;
+  __threads.reserve([&]() {
+    auto __max_thread_count = thread::hardware_concurrency();
+    return __max_thread_count == 0 ? 1 : __max_thread_count;
+  }());
+
+  const auto __brick_size = ((__last - __first) / __threads.capacity()) + 1;
+
+  for (size_t __i = 0; __i != __threads.capacity(); ++__i) {
+    if (__last - __first >= __brick_size) {
+      __threads.emplace_back([&__f, __brick_first = __first, __brick_last = __first + __brick_size]() {
+        __f(__brick_first, __brick_last);
+      });
+      __first += __brick_size;
+    } else {
+      __threads.emplace_back([&__f, __brick_first = __first, __brick_last = __last]() {
+        __f(__brick_first, __brick_last);
+      });
+      __first = __last;
+    }
+  }
+  _LIBCPP_ASSERT(__first == __last, "__parallel_for didn't iterator over all elements!");
+
+  for (auto& __el : __threads) {
+    __el.join();
+  }
+}
+
+_LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
+
+} // namespace __par_backend::inline __thread_cpu_backend
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_THREAD_H

libcxx/include/__config

 #  endif
 
 // TODO(varconst): currently, there are bugs in Clang's intrinsics when handling Objective-C++ `id`, so don't use
 // compiler intrinsics in the Objective-C++ mode.
 #  ifdef __OBJC__
 #    define _LIBCPP_WORKAROUND_OBJCXX_COMPILER_INTRINSICS
 #  endif
 
 // TODO: Make this a proper configuration option
 #define _PSTL_PAR_BACKEND_SERIAL
-#define _PSTL_CPU_BACKEND_SERIAL
 
 #define _PSTL_PRAGMA(x) _Pragma(#    x)
 
 // Enable SIMD for compilers that support OpenMP 4.0
 #if (defined(_OPENMP) && _OPENMP >= 201307)
 
 #  define _PSTL_UDR_PRESENT
 #  define _PSTL_PRAGMA_SIMD _PSTL_PRAGMA(omp simd)
 #  define _PSTL_PRAGMA_DECLARE_SIMD _PSTL_PRAGMA(omp declare simd)

libcxx/include/__config_site.in

 #cmakedefine _LIBCPP_HAS_NO_FILESYSTEM_LIBRARY
 #cmakedefine _LIBCPP_HAS_NO_RANDOM_DEVICE
 #cmakedefine _LIBCPP_HAS_NO_LOCALIZATION
 #cmakedefine _LIBCPP_HAS_NO_FSTREAM
 #cmakedefine _LIBCPP_HAS_NO_WIDE_CHARACTERS
 #cmakedefine01 _LIBCPP_ENABLE_ASSERTIONS_DEFAULT
 #cmakedefine _LIBCPP_ENABLE_DEBUG_MODE
 
+// PSTL backends
+#cmakedefine _LIBCPP_PSTL_CPU_BACKEND_SERIAL
+#cmakedefine _LIBCPP_PSTL_CPU_BACKEND_THREAD
+
 // __USE_MINGW_ANSI_STDIO gets redefined on MinGW
 #ifdef __clang__
 #  pragma clang diagnostic push
 #  pragma clang diagnostic ignored "-Wmacro-redefined"
 #endif
 
 @_LIBCPP_ABI_DEFINES@
 @_LIBCPP_EXTRA_SITE_DEFINES@
 
 #ifdef __clang__
 #  pragma clang diagnostic pop
 #endif
 
 #endif // _LIBCPP___CONFIG_SITE

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/prev_permutation.h'}}
 #include <__algorithm/pstl_backends/cpu_backend.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backend.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/any_of.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/backend.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/backend.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/fill.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/find_if.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/for_each.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/serial.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/serial.h'}}
+#include <__algorithm/pstl_backends/cpu_backends/thread.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/thread.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/transform.h'}}
 #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}}
 #include <__algorithm/ranges_adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_adjacent_find.h'}}
 #include <__algorithm/ranges_all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_all_of.h'}}
 #include <__algorithm/ranges_any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_any_of.h'}}
 #include <__algorithm/ranges_binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_binary_search.h'}}
 #include <__algorithm/ranges_clamp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_clamp.h'}}
 #include <__algorithm/ranges_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy.h'}}