8 ms·

A C++17 thread pool for high-performance scientific computing

137 points by pramodbiligiri 4y ago

talolard 4y ago
It’s been a long time since I touched c++, so pardon my naïveté. I’d have assumed that optimized thread pools were a done thing. What’s new here and why was there a gap ?
- beached_whale 4y ago
  There are lots of them and many are built into the OS(e.g. GCD on mac's, Windows has a thread pool api) plus TBB on all of them...) It would be neat if the github site https://github.com/bshoshany/thread-pool https://github.com/bshoshany/thread-pool or the paper did some comparisons to the existing body out there.
- rat9988 4y ago
  Read 1.1 of the pdf: https://arxiv.org/pdf/2105.00613.pdf https://arxiv.org/pdf/2105.00613.pdf It's too long to quote. I'm too lazy to summarise.
  - 0xffff2 4y ago
    Nothing in that section explains why this is in any way new or innovative. The only interesting claim is "performance", but looking at the code, I don't see anything other than a simple naive thread-pool implementation.
- Randor 4y ago
  I looked through the code and I don't see anything new at all. Looks similar to the dozens of other thread pools I've reviewed over the years. The author is a physicist. Looks like he just decided to publish about his C++ code.
RcouF1uZ4gsC 4y ago
Looking at the code, it seems like it is more of a class project rather than a highly optimized library. It is using mutexes, condition variables, and futures to write a pretty much textbook implementation of a thread pool. However, there will be significant contention, as all the workers are reading from the same queue, and the submissions are going to the same queue. There are not multiple queues with work-stealing which is I think a minimum for a production level version of something like this. EDIT: IIRC C++ Concurrency in Action by Anthony Williams has a nice discussion of the issues of building a C++ thread pool using the C++ standard library. It does address things like contention and work-stealing.
- beached_whale 4y ago
  Sean Parent's Better Concurrency video(s) go over some of it too. Also, good series of video's
  - facontidavide 4y ago
    Video link: https://www.youtube.com/watch?v=zULU6Hhp42w https://www.youtube.com/watch?v=zULU6Hhp42w
- TillE 4y ago
  Multiple queues with work stealing is an optimization for really extreme cases (lots of tiny tasks). In most use cases, a multi-consumer lockless queue (eg, moodycamel::ConcurrentQueue) is more than adequate.
  - kazinator 4y ago
    What I'm hearing is that in most cases, any one of the reams of existing code for this is adequate.
  - thinkharderdev 4y ago
    Is it? I though that work stealing was a basic requirement for maintaining some semblance of cache locality.
deleted 4y ago
[deleted]
formerly_proven 4y ago
Code: https://github.com/bshoshany/thread-pool/blob/master/BS_thread_pool.hpp#L202 https://github.com/bshoshany/thread-pool/blob/master/BS_thre... https://github.com/bshoshany/thread-pool/blob/master/BS_thread_pool.hpp#L334 https://github.com/bshoshany/thread-pool/blob/master/BS_thre... I don't see how this is built for particularly good performance, or with many-core machines in mind.
- 908B64B197 4y ago
  Because it's not. It's an undergrad assignment basically. The writeup is nice, and it's great that it's on arxiv but it's not novel nor publishable research. The implementation that ships with a given OS is sure to run around in circles around it.
- WhitneyLand 4y ago
  A good paper will describe how the work is interesting or useful in the field and how it opens the door for future research. Here the author acknowledges that other libraries may be more performant, but describes the motivation for the work as essentially something that’s a small piece of code to maintain, and easy to use. I didn’t run the code but I read through the paper and it doesn’t seem like it’s made a convincing case for this.
- riskneutral 4y ago
  Depending on which C++17 standard libraries are being used, performance efficiency may be an issue and platform dependent.
bee_rider 4y ago
> In particular, our implementation does not utilize OpenMP or any other high-level multithreading APIs, and thus gives the programmer precise low-level control over the details of the parallelization, which permits more robust optimizations. I totally disagree with this line of thinking. The person who knows most about the hardware on which the program will be run is the person running it, not the programmer. The OpenMP API somewhat complicated in an attempt to allow the programmer to, at a high level, express ideas about data locality to the runtime. Unless we're imagining a universe in which the programmer is around to tweak their source code for every hardware platform, the idea of "giving the programmer more control" is a dead end. The programmer must be given expressiveness. Threading libraries are complicated because hardware is complicated. I mean first generation threadrippers are a little old, but they still exist: do we really want to have everybody re-write the code to handle "I have multiple packages on this node, NUMA between the dies in a given package, NUMA between the packages in the node!"
- physicsguy 4y ago
  Totally agree. Plus, OpenMP is a standard that’s grown to take into account new hardware. It works in C, C++ and Fortran, which is a huge bonus. It’s stuck around for a long time for a reason - before it and MPI were standardised, every set of processor hardware has it’s own parallelism libraries and the programmer had to learn a new set.
- pvg 4y ago
  Unless we're imagining a universe in which the programmer is around to tweak their source code for every hardware platform It doesn't have to be the whole universe just a region in which a particular kind of specialized scientific computing is done. I have not idea what this specific thing is good for but looking at it in through the lens of general purpose computing truisms probably misses more than it illuminates.
  - bee_rider 4y ago
    There's some truth there, but I think it is actually flipped. Scientific computing codes generally stick around a while (or at least they might, or at least we hope they will), they are run on complicated platforms by motivated people. There's incentive to do run-time tuning, and there's value to making them general. On the other hand, you might have things like a videogame console, where the program is tuned for a particular platform. There's plenty of room there for programmer control I think (not sure though, that isn't my field -- in the Unity/Unreal era maybe they try and make things general? But I bet the programmer can exert great control if they want).
Const-me 4y ago
Writing a thread pool which is performant and scalable is surprisingly hard, I did couple times. And now, whenever I can, I tend to avoid doing that. Instead, I prefer using the stuff already implemented by someone else, in OS userlands or runtime libraries. • C and C++ runtime libraries have OpenMP. Level of support varies across compilers but still, all mainstream ones support at least OpenMP 2.0. • .NET runtime comes with its own thread pool. The standard library provides both low-level APIs similar to the Windows’ built-in one, and higher-level things like Parallel.For remotely comparable to OpenMP. • Windows userland has another one, see CreateThreadpoolWork and SubmitThreadpoolWork APIs introduced in Vista. The API is totally different though, a programmer needs to manually submit each task to the pool. • iOS and OSX userlands also have a thread pool called Grand Central Dispatch. It’s very comparable to the Windows version.
- jltsiren 4y ago
  The main issue with OpenMP is that Apple ships a crippled version of Clang that does not support it by default. If you are developing on Mac, OpenMP should be considered an external dependency, with all the unpleasantness that means in a C++ project. If you have students writing code and the target environment is Linux, as is common in the academia, replacing OpenMP with something portable can be a good idea. Also, a thread pool that supports the equivalent of: #pragma omp parallel for schedule(static) and #pragma omp parallel for schedule(dynamic, 1) if often good enough for scientific computing. There is surprisingly little need for all the fancy things software engineers have invented because their threads have to communicate every minute.
  - physicsguy 4y ago
    Pretty much everyone in scientific computing who uses a Mac will use Homebrew or Macports to install a standard version of GCC or Clang in my experience.
- jstimpfle 4y ago
  What where your performance requirements, what where some issues that you ran into, and what did you do to improve?
kolbusa 4y ago
In my experience, EIGEN's threadpool is decent. But OpenMP (edit: I mean Intel's implementation donated to LLVM) is often faster especially if threads are allowed to be affinitized to HW processors. Another promise of OpenMP that is not made by various threadpools is cooperative execution; in threadpools tasks are usually independent. However, if any part of an app uses affinitized threads, the whole app needs to be using the same thread pool, as otherwise perf will go down. In this regard, OpenMP is less composable.
SethTro 4y ago
The paper has only a single benchmark reported from a single system where they report > In our performance test, we see a speedup of 18.2x, saturating and even surpassing this estimated theoretical upper bound. IMHO if you exceed your theoretical bound that's a sign you didn't go a good job analyzing the situation.
- Markstar 4y ago
  Yeah, I agree that they should have touched more on that. Something definitely is going on when your result exceeds what should be possible. That said, I'm currently struggling with managing threads with my algorithm, so I'm looking forward to giving this a go.
smallstepforman 4y ago
Yet again another threading implementation which ignores the Actor programming model. This must be a systemic failure in both academia for not teaching students about Actors, and the industry for barely talking about Actors. It’s like the old saying, those that dont understand Unix are doomed to reimplement it, poorly. For those readers that haven’t encountered Actors, its more than just a threading model. It allows messaging (important for interaction). An Actor is essentially a class with a std::vector<std::function void(…)> member, and a public messaging function which pushes the message with variable arguments to the queue. The message invokes the scheduler, which sequentially invokes the queued function. It eliminates locks for the client, which is the key benefit. It keeps Actors on a specific thread to use hot caches, unless work stealing moves the Actor to a free thread. The Actor abstraction is higher level than threads. I’m sure the author will come to realise the benefits of Actors once he has a decade more experience under his belt, after which just like me he’ll be disappointed at academia and the industry for not talking about the benefits of the Actor programming model. Shameless plug : my own Actor implementation, used in real world 24h/365 embedded projects: https://github.com/smallstepforman/Medo/tree/main/Actor https://github.com/smallstepforman/Medo/tree/main/Actor
- elcritch 4y ago
  Actor's are fantastic and ideal for many situations. However, this thread pool is specifically for _high performance_ computing which generally means working with shared memory. The actor paradigm generally assumes no shared memory and communications using message passing. It's harder to optimize performance and is an impedance mismatch for HPC.
  - _0w8t 4y ago
    Another important difference from the actor model is that the library uses a future interface with blocking wait to get the results. With actors there is no wait as the results are posted to the message queue of the caller. But waiting makes the usage more similar to sequential computing code. When there is an opportunity the code starts several jobs to work on presumably independent data sets, then waits for their results in a shared memory and then process them sequentially until there is another opportunity for parallel computation.
rurban 4y ago
Lots of comments but no-one found the logical error in the paper and README, which I just fixed.
Gupie 4y ago
Perhaps slightly off topic but playing with parallel numerical computations I found that C++17/20's "parallel for" loops are significantly faster than using manually created threads. https://en.cppreference.com/w/cpp/algorithm/execution_policy_tag https://en.cppreference.com/w/cpp/algorithm/execution_policy...
lionkor 4y ago
This is a very primitive implementation. I like it, and it looks good, but using mutexes and condition variables will be comparatively slow. You really want to, in theory, abuse atomics in order to "simulate" condition variables, since you avoid the possible context switch to the kernel which condition variables may have (afaik). Still cool, but I know (from building and testing my own similar implementations) like a good bit performance will be lost here due to these context switches. For an example of a more complex, but much more efficient, thread pool implementation, check out this article on thread pools in Zig [1] (the language is secondary, its mostly pseudocode). It goes over the need for an actual scheduler to make thread pools efficient. 1: https://zig.news/kprotty/resource-efficient-thread-pools-with-zig-3291 https://zig.news/kprotty/resource-efficient-thread-pools-wit...

It’s been a long time since I touched c++, so pardon my naïveté. I’d have assumed that optimized thread pools were a done thing. What’s new here and why was there a gap ?

beached_whale 4y ago
There are lots of them and many are built into the OS(e.g. GCD on mac's, Windows has a thread pool api) plus TBB on all of them...) It would be neat if the github site https://github.com/bshoshany/thread-pool https://github.com/bshoshany/thread-pool or the paper did some comparisons to the existing body out there.
rat9988 4y ago
Read 1.1 of the pdf: https://arxiv.org/pdf/2105.00613.pdf https://arxiv.org/pdf/2105.00613.pdf It's too long to quote. I'm too lazy to summarise.
- 0xffff2 4y ago
  Nothing in that section explains why this is in any way new or innovative. The only interesting claim is "performance", but looking at the code, I don't see anything other than a simple naive thread-pool implementation.
Randor 4y ago
I looked through the code and I don't see anything new at all. Looks similar to the dozens of other thread pools I've reviewed over the years. The author is a physicist. Looks like he just decided to publish about his C++ code.

RcouF1uZ4gsC 4y ago

Looking at the code, it seems like it is more of a class project rather than a highly optimized library. It is using mutexes, condition variables, and futures to write a pretty much textbook implementation of a thread pool. However, there will be significant contention, as all the workers are reading from the same queue, and the submissions are going to the same queue. There are not multiple queues with work-stealing which is I think a minimum for a production level version of something like this. EDIT: IIRC C++ Concurrency in Action by Anthony Williams has a nice discussion of the issues of building a C++ thread pool using the C++ standard library. It does address things like contention and work-stealing.

beached_whale 4y ago
Sean Parent's Better Concurrency video(s) go over some of it too. Also, good series of video's
- facontidavide 4y ago
  Video link: https://www.youtube.com/watch?v=zULU6Hhp42w https://www.youtube.com/watch?v=zULU6Hhp42w
TillE 4y ago
Multiple queues with work stealing is an optimization for really extreme cases (lots of tiny tasks). In most use cases, a multi-consumer lockless queue (eg, moodycamel::ConcurrentQueue) is more than adequate.
- kazinator 4y ago
  What I'm hearing is that in most cases, any one of the reams of existing code for this is adequate.
- thinkharderdev 4y ago
  Is it? I though that work stealing was a basic requirement for maintaining some semblance of cache locality.

deleted 4y ago

[deleted]

formerly_proven 4y ago

Code: https://github.com/bshoshany/thread-pool/blob/master/BS_thread_pool.hpp#L202 https://github.com/bshoshany/thread-pool/blob/master/BS_thre... https://github.com/bshoshany/thread-pool/blob/master/BS_thread_pool.hpp#L334 https://github.com/bshoshany/thread-pool/blob/master/BS_thre... I don't see how this is built for particularly good performance, or with many-core machines in mind.

908B64B197 4y ago
Because it's not. It's an undergrad assignment basically. The writeup is nice, and it's great that it's on arxiv but it's not novel nor publishable research. The implementation that ships with a given OS is sure to run around in circles around it.
WhitneyLand 4y ago
A good paper will describe how the work is interesting or useful in the field and how it opens the door for future research. Here the author acknowledges that other libraries may be more performant, but describes the motivation for the work as essentially something that’s a small piece of code to maintain, and easy to use. I didn’t run the code but I read through the paper and it doesn’t seem like it’s made a convincing case for this.
riskneutral 4y ago
Depending on which C++17 standard libraries are being used, performance efficiency may be an issue and platform dependent.

bee_rider 4y ago

> In particular, our implementation does not utilize OpenMP or any other high-level multithreading APIs, and thus gives the programmer precise low-level control over the details of the parallelization, which permits more robust optimizations. I totally disagree with this line of thinking. The person who knows most about the hardware on which the program will be run is the person running it, not the programmer. The OpenMP API somewhat complicated in an attempt to allow the programmer to, at a high level, express ideas about data locality to the runtime. Unless we're imagining a universe in which the programmer is around to tweak their source code for every hardware platform, the idea of "giving the programmer more control" is a dead end. The programmer must be given expressiveness. Threading libraries are complicated because hardware is complicated. I mean first generation threadrippers are a little old, but they still exist: do we really want to have everybody re-write the code to handle "I have multiple packages on this node, NUMA between the dies in a given package, NUMA between the packages in the node!"

physicsguy 4y ago
Totally agree. Plus, OpenMP is a standard that’s grown to take into account new hardware. It works in C, C++ and Fortran, which is a huge bonus. It’s stuck around for a long time for a reason - before it and MPI were standardised, every set of processor hardware has it’s own parallelism libraries and the programmer had to learn a new set.
pvg 4y ago
Unless we're imagining a universe in which the programmer is around to tweak their source code for every hardware platform It doesn't have to be the whole universe just a region in which a particular kind of specialized scientific computing is done. I have not idea what this specific thing is good for but looking at it in through the lens of general purpose computing truisms probably misses more than it illuminates.
- bee_rider 4y ago
  There's some truth there, but I think it is actually flipped. Scientific computing codes generally stick around a while (or at least they might, or at least we hope they will), they are run on complicated platforms by motivated people. There's incentive to do run-time tuning, and there's value to making them general. On the other hand, you might have things like a videogame console, where the program is tuned for a particular platform. There's plenty of room there for programmer control I think (not sure though, that isn't my field -- in the Unity/Unreal era maybe they try and make things general? But I bet the programmer can exert great control if they want).

Const-me 4y ago

Writing a thread pool which is performant and scalable is surprisingly hard, I did couple times. And now, whenever I can, I tend to avoid doing that. Instead, I prefer using the stuff already implemented by someone else, in OS userlands or runtime libraries. • C and C++ runtime libraries have OpenMP. Level of support varies across compilers but still, all mainstream ones support at least OpenMP 2.0. • .NET runtime comes with its own thread pool. The standard library provides both low-level APIs similar to the Windows’ built-in one, and higher-level things like Parallel.For remotely comparable to OpenMP. • Windows userland has another one, see CreateThreadpoolWork and SubmitThreadpoolWork APIs introduced in Vista. The API is totally different though, a programmer needs to manually submit each task to the pool. • iOS and OSX userlands also have a thread pool called Grand Central Dispatch. It’s very comparable to the Windows version.

jltsiren 4y ago
The main issue with OpenMP is that Apple ships a crippled version of Clang that does not support it by default. If you are developing on Mac, OpenMP should be considered an external dependency, with all the unpleasantness that means in a C++ project. If you have students writing code and the target environment is Linux, as is common in the academia, replacing OpenMP with something portable can be a good idea. Also, a thread pool that supports the equivalent of: #pragma omp parallel for schedule(static) and #pragma omp parallel for schedule(dynamic, 1) if often good enough for scientific computing. There is surprisingly little need for all the fancy things software engineers have invented because their threads have to communicate every minute.
- physicsguy 4y ago
  Pretty much everyone in scientific computing who uses a Mac will use Homebrew or Macports to install a standard version of GCC or Clang in my experience.
jstimpfle 4y ago
What where your performance requirements, what where some issues that you ran into, and what did you do to improve?

kolbusa 4y ago

In my experience, EIGEN's threadpool is decent. But OpenMP (edit: I mean Intel's implementation donated to LLVM) is often faster especially if threads are allowed to be affinitized to HW processors. Another promise of OpenMP that is not made by various threadpools is cooperative execution; in threadpools tasks are usually independent. However, if any part of an app uses affinitized threads, the whole app needs to be using the same thread pool, as otherwise perf will go down. In this regard, OpenMP is less composable.

SethTro 4y ago

The paper has only a single benchmark reported from a single system where they report > In our performance test, we see a speedup of 18.2x, saturating and even surpassing this estimated theoretical upper bound. IMHO if you exceed your theoretical bound that's a sign you didn't go a good job analyzing the situation.

Markstar 4y ago
Yeah, I agree that they should have touched more on that. Something definitely is going on when your result exceeds what should be possible. That said, I'm currently struggling with managing threads with my algorithm, so I'm looking forward to giving this a go.

smallstepforman 4y ago

Yet again another threading implementation which ignores the Actor programming model. This must be a systemic failure in both academia for not teaching students about Actors, and the industry for barely talking about Actors. It’s like the old saying, those that dont understand Unix are doomed to reimplement it, poorly. For those readers that haven’t encountered Actors, its more than just a threading model. It allows messaging (important for interaction). An Actor is essentially a class with a std::vector<std::function void(…)> member, and a public messaging function which pushes the message with variable arguments to the queue. The message invokes the scheduler, which sequentially invokes the queued function. It eliminates locks for the client, which is the key benefit. It keeps Actors on a specific thread to use hot caches, unless work stealing moves the Actor to a free thread. The Actor abstraction is higher level than threads. I’m sure the author will come to realise the benefits of Actors once he has a decade more experience under his belt, after which just like me he’ll be disappointed at academia and the industry for not talking about the benefits of the Actor programming model. Shameless plug : my own Actor implementation, used in real world 24h/365 embedded projects: https://github.com/smallstepforman/Medo/tree/main/Actor https://github.com/smallstepforman/Medo/tree/main/Actor

elcritch 4y ago
Actor's are fantastic and ideal for many situations. However, this thread pool is specifically for _high performance_ computing which generally means working with shared memory. The actor paradigm generally assumes no shared memory and communications using message passing. It's harder to optimize performance and is an impedance mismatch for HPC.
- _0w8t 4y ago
  Another important difference from the actor model is that the library uses a future interface with blocking wait to get the results. With actors there is no wait as the results are posted to the message queue of the caller. But waiting makes the usage more similar to sequential computing code. When there is an opportunity the code starts several jobs to work on presumably independent data sets, then waits for their results in a shared memory and then process them sequentially until there is another opportunity for parallel computation.

rurban 4y ago

Lots of comments but no-one found the logical error in the paper and README, which I just fixed.

Gupie 4y ago

Perhaps slightly off topic but playing with parallel numerical computations I found that C++17/20's "parallel for" loops are significantly faster than using manually created threads. https://en.cppreference.com/w/cpp/algorithm/execution_policy_tag https://en.cppreference.com/w/cpp/algorithm/execution_policy...

lionkor 4y ago

This is a very primitive implementation. I like it, and it looks good, but using mutexes and condition variables will be comparatively slow. You really want to, in theory, abuse atomics in order to "simulate" condition variables, since you avoid the possible context switch to the kernel which condition variables may have (afaik). Still cool, but I know (from building and testing my own similar implementations) like a good bit performance will be lost here due to these context switches. For an example of a more complex, but much more efficient, thread pool implementation, check out this article on thread pools in Zig [1] (the language is secondary, its mostly pseudocode). It goes over the need for an actual scheduler to make thread pools efficient. 1: https://zig.news/kprotty/resource-efficient-thread-pools-with-zig-3291 https://zig.news/kprotty/resource-efficient-thread-pools-wit...