There are currently 2 thread pool implementations in LLVM (ThreadPool and orc::TaskDispatcher) for async/await-style programming, and I’d like to propose that we combine those into something more full featured and robust. The current implementation has a limitation where any task that uses the std::concurrency primitives risks causing deadlock if there are more tasks to run than threads to run them on, which somewhat undermines the purpose of having a thread pool with lots of micro-tasks:
/// It is also possible for worker threads to submit new tasks and wait for
/// them. Note that this may result in a deadlock in cases such as when a task
/// (directly or indirectly) tries to wait for its own completion, or when all
/// available threads are used up by tasks waiting for a task that has no thread
/// left to run on (this includes waiting on the returned future). It should be
/// generally safe to wait() for a group as long as groups do not form a cycle.
Thus, in particular, I want LLVM to have a library for threading with a few primary additional features to remove that issue:
- Ability to work-steal from worker threads
- Ability for worker threads to spawn new work
- Ability of any thread to schedule work to run after other tasks produce their results
- Ability for main thread to wait for results
In classic currency patterns, those would be: 1. the kernel scheduler whims 2. pthread_create 3. pthread_join 4. std::future. However, those are not compatible with a thread pool design as NVIDIA developers explain: motivation
In looking around for existing alternatives, I considered Cilk, Threading Basic Blocks, Google’s marl, Facebook’s folly fibers, and other similar designs. Those come with the upside of being symmetric so that any task can use blocking waits on any value from any other task. That however comes with the downside of not being very portable (posix deprecated swapcontext) and/or being very large projects.
I then found there is a proposal for C++26 to add just such an async/await runtime ability to libstdc++: Execution control library (since C++26) - cppreference.com
So I was look at the possibility that we could wait a decade and then be able to use the new feature, or we could implement it ourselves, or we could import a reference implementation of it now. I think that final one follows the usual trend in LLVM of features such as std::optional getting standardized and slowly replaced when they become widely available.
I found 3 libraries that appears to contain most of the features I was looking for:
- taskflow
- NVIDIA stdexec (taskflow is the backend for this)
- Facebook libunifex
The main downside to all of these being that they currently rely on co_await, which isn’t in C++17, as explained here (both the rational and the possible manual fix): libunifex/doc/overview.md at main · facebookexperimental/libunifex · GitHub
I was looking for feedback on:
- Whether folks agree LLVM should be able to use threads and especially worker pools more effectively? Particularly with the ability to add work-stealing and that has a cooperative futures object that doesn’t potentially deadlock if there are more tasks than threads
- Whether it is acceptable to use an existing library (MIT licensed), rather than designing a new one custom to LLVM? If so, which library would be preferred?
- How to bundle, vendor, or manage the external dependency? I think this is an infrequent situation, but there is already some prior art with depending on libraries such as Z3 and Polly.
- Alternative or existing proposals?