A simple C++11 thread pool implementation
github.com
github.com
1) Nonuniform work sizes. Optimally scheduling the work when the sizes are nonuniform is Hard. An almost-optimal algorithm is to dispatch larger items before smaller items. This implementation dispatches work in FIFO order. While this is Not Wrong (TM), its far from optimal when the work sizes are nonuniform.
2) Small work sizes. As the size of each work item gets smaller and smaller, the proportion of the runtime cost which is spent to dispatch the work becomes larger and larger. I'm working on a system which has dozens of work items to execute, but each one is only 50-100 microseconds long. It turns out that this is an awfully inconvenient work size, and contention on a common FIFO was limiting available parallelism. I found I got nearly 50% speedup by giving each worker thread its own workqueue and round-robin dispatching among them.
3) (edited to add) They don't model fork/join parallelism well on a common pool. If work items also wait for work to complete, then the OP's implementation may deadlock them. To avoid deadlock, the join operator must be capable of executing a work item. The C++11 future API isn't rich enough to do this in user code. See also WG21 paper N3557 for more on this topic.
From the perspective of a standards body, threadpools are similar to associative data structures. There is a community of users who would like to have a one-size-fits-all implementation. But it turns out that actual workloads have wildly differing requirements. In practice, a standard library must provide several different models of a threadpool to satisfy them, or users will be forever complaining and/or rolling their own.
If you are on Windows, take a look at IOCP as a queuing mechanism.
Use one IOC port to queue work for the threads and use another IOC port to submit completed work back to whoever's listening. Worker threads then merely wait for the next completion packet, execute the work and post the packet into the second ("done") port. Dead simple and, due to how IOCP works, with very little overhead.
Strictly speaking, this is not what IOC ports are meant for, but the performance you get out of this is nothing short of amazing and the code ends up being short and simple.
[0] https://docs.microsoft.com/en-us/windows/win32/fileio/i-o-co...
This particular process wasn't the only thing in the system. I wanted the worker threads to go to sleep when there wasn't work to do.
I dare say that Multiple-producer + multiple-consumer lockless queues are not "difficult", but straight up "impossible" to write.
You MUST make a decision early on:
1. Settle on single-consumer / single-producer ("True" parallelism of 2x threads best case) on the queue, retaining the "first-in / first-out" property of the queue.
2. Decide that "first-in / first-out" is unnecessary in your use case, and generalize to multiple-producer / multiple-consumer code.
After all, it is impossible to define first-in / first-out if you cannot define an insertion order, or consuming order. If you decide on a defined insertion order, it is equivalent to deciding upon a "single" producer protected by a spinlock or mutex. (And lo-and-behold, all your code is just a very, very complex mutex). Ditto for the consumer side.
-------
You CAN write 1x consumer + 1x producer lockless queues with defined total ordering. You CAN have "many" consumers sequentially "acting" as the 1x consumer, or "many" producers "acting" as the 1x producer (by sequentially choosing one through CAS-loops or mutexes).
But I dare say, 30x consumers each being a "consumer 1 at a time" isn't really a multi-consumer queue, its a 1x consumer queue with a mutex on the front-end :-)
-------
Deciding upon a 1x producer / Multi-consumer (or the inverse: multi-producer / 1x consumer) queue is just a grossly inefficient queue.
If you cannot define the insertion order, then you cannot define the removal order. Similarly, if you cannot define the removal order, you cannot define the insertion order. You might as well "undefine the order completely" to have better performance.
-------
In any case, your assumption here has a gross amount of complexity you're ignoring. Lockless queues are NOT an item to be trifled with.
The confusion comes in because many programmers expect a strict-ordering on "work-queues", especially because many work-queues are made out of simple queues or fifos.
The big decision point for many is finally deciding, and/or realizing, that strict-ordering is not necessary in many pragmatic use cases. But this also comes with a double-edge sword: many algorithms require strict-ordering of tasks.
---------
Take a Breadth First Search, as an example. One core assumption of BFS is that the first solution you come across will be the solution closest to the root.
Ex: If searching for "Checkmate" in a chess puzzle, the BFS implementation will ALWAYS find the shortest checkmate. Lets say you're in a situation with "many checkmates", checkmate in 5-moves, checkmate in 7-moves... etc. etc. But you want to absolutely find the shortest one. BFS is clearly the answer. But ONLY if your queue is strictly FIFO.
Now if you parallelize the BFS search by replacing the true FIFO queue with a pseudo-FIFO parallel queue, its no longer guaranteed to find the shortest checkmate.
[0]: Marcos K. Aguilera, Kimberly Keeton, Stanko Novakovic, and Sharad Singhal. 2019. Designing Far Memory Data Structures: Think Outside the Box. In Proceedings of the Workshop on Hot Topics in Operating Systems (HotOS ’19). Association for Computing Machinery, New York, NY, USA, 120–126. DOI: https://doi.org/10.1145/3317550.3321433
This is where I'm at, with an application that spends most of its time task switching. Worst part is, I don't have any great ideas about how to fix it.
The easiest way is to grab multiple work items (ex: grab 100x work items) at a time. The thread will not reschedule until all 100x work items are completed.
---------
It is rare for 1x work item to map to 1x threads. Instead, calculate an estimate on a work-item's complexity (if possible), so that all threads have roughly the same amount of work going into them.
int estimatedCost = 0;
vector<WorkItem> myItems;
auto wi_iterator = workitemsList.begin();
while(estimatedCost < SOME_CONSTANT_YOU_TUNED && wi_iterator != workitemsList.end()){
myItems.push_back(*wi_iterator);
estimatedCost += estimateCost(*wi_iterator);
wi_iterator = workitemsList.erase(wi_iterator);
}
If an estimated cost is unavailable, then estimateCost(X) = 1. (100x work-items == 100 cost). I just bet that MOST cases have an estimate-cost function better than "estimateCost(X) = 1".
Run the code many times, and manually select the constant "SOME_CONSTANT_YOU_TUNED". If you're spending too much time scheduling, increase the size of the constant. If you're waiting too long on the "last threads to complete", decrease the constant.
---------
The problem is that people want a "plug and play" solution without testing or tuning, especially for a standard library. But in application-specific code, no one really cares if you have a few magic constants set for "performance reasons". I don't have any solution here for library-writers... but fortunately, most people out here are application writers and can afford this kind of tuning as part of their development process.
If the work items are atomically enqueued one at a time while there are free workers, then they will also be dequeued one at a time. This can be mitigated by enqueuing work in batches.
Workers also hold the lock for much longer, adding more contention on the FIFO.
If you're going to do that, you're usually better off just making the work items bigger on the producer side.
> This can be mitigated by enqueuing work in batches.
> Workers also hold the lock for much longer, adding more contention on the FIFO.
Fortunately, "true-FIFO" is the worst-case scenario. If you have a "Pseudo-FIFO", or "First-in USUALLY first out, but not guaranteed", you have a huge amount of flexibility with regards to avoiding contention.
The "classic" pseudo-FIFO algorithm is 1x thread-local true-FIFO per thread, with work-stealing taking from the LIFO-side from remote threads.
For example, Thread#1 push_back and pop_front on FIFO#1, which eventually runs out of work. Thread#1 now needs to grab work from another thread.
Thread#1 chooses to worksteal from say... FIFO#23. Thread#23 is still reading from pop_front side, but Thread#1 can pop_back concurrently without any contention (as long as pop_front and pop_back operate on separate cache lines).
The problem here is that Thread#1 just caused FIFO#23's data to look kinda-sorta like a stack, albeit temporarily. So you've lost the first-in-first-out guarantee. Fortunately, this isn't a major problem in many applications. (Ex: a Depth-first search becomes Depth-first when thread-local, but Breadth-first when load-balancing across cores. This is extremely good behavior in practice)
> If you're going to do that, you're usually better off just making the work items bigger on the producer side.
In my experience, that isn't always possible. A large number of problems are recursively defined, and splitting them up into tiny pieces is the most natural way of representing problems.
Take the case of parallel tree search ("mostly" depth-first search with the pseduo-FIFO defined above). Its non-obvious what the size of any node actually is! There's basically no way to predict the size of an a work-item (and we are thus left with the workEstimate(X){ return 1; } style estimate).
Other tasks (ex: Matrix Multiplication), allow for very easy tuning of work-item sizes. It all comes down to your specific application.
Or you don't make that decision. For some people, latency is more important. It really depends on your specific situation.
Async architectures seem to scale better. So maybe its worth looking into async instead of blocking to avoid task-switching.
1. there is (was?) the async future glitch in the standard where futures were generally specified to not wait for the task to finish in the destructor but the specification for async said they did. So if you just handed around futures of unknown origin you'd never know what the actual behavior was.
2. async doeesn't really specify how it works. Will there be a thread per task? Is there a maximum? Is it a fixed amount like in this implementation? Will it launch the items in the order they were queued in?
I wrote this not because I think it is somehow "correct" for the general case but because it is the simplest mental model to reason about for me. My intention was to have the most basic common denominator for what passes as a fixed size thread pool. That is also why it "isn't maintained" because it does exactly what I meant it to do and the only reason to change something about it would be to fix bugs. I could admittedly be more active in answering issues etc..
What I consider fundamental functionality is obviously also determined by the use cases I care about. Most of which at the time were of the form of expensive data parallel bulk operations to be distributed among threads in large chunks. Each item would usually take at least miliseconds, own all its data and publish the result via the future at the end. For that this model works well.
If your problem requires handling fancy dependency graphs, fine grained synchronization between threads or the work items are tiny and cache misses and queue synchronization overhead are comparatively expensive then this is not the right approach.
Intel published a bunch of helpful papers to WG21 that taught me much of the trade space, or at least served as entry points to the research. I think that their conclusions about Cilk were spot-on, in that
- Its hard to model fork/join parallelism well without language changes.
- Fork/join may not be one-size-fits-all, but it does fit a lot of problems. A well-fleshed-out work-stealing system can solve a lot of problems from a relatively simple API.
At $BigCo, we had a threadpool library with custom futures that would steal some work from the pool when the result wasn't ready. It still suffered from the performance failure modes I mentioned, but at least it wouldn't deadlock on you.
IMO, the most important action item for your library is to clearly document the deadlock risk.
I'm not sure what this is doing on HN.
using return_type = typename std::result_of<F(Args...)>::type
using return_type = decltype(f(args...));
Also the "> >" is a pre-C++11 pattern.
result_of has now been deprecated in newer C++ versions but since this advertises itself as C++11 thread pool I intend to leave it as is.
Starting the day with heavy dose of FOMO...
L39 et seq. is a lambda expression.
Native lambdas. Huh. It's like waking up to see people flying their cars to work. :)
I don't know if you should "F" necessarily but you are "MO" :-)
C++ has become a completely new language, with a large carbuncle of back compatibility attached (though they've been slowly deprecating some of that).
I like programming in modern C++ and am lucky enough to be able to compile everything std=c++17 (which we recently changed to =c++20 though support for that standard is just starting to appear). It's quite an expressive and powerful language.
Though a lot of the legacy stuff is ugly, it does give you access to older code, external libraries and the like. So you can write clear code using modern C++ and still be able to link in older code. Pretty nice.
This kind of approach is usually not what you want: either you want to spawn threads as new work arrives (when each work unit is independent of each other), or you want to have a static number of threads each doing some predefined work (ideally one per core).
Scheduling pieces of work like this is going to be terrible for cache locality and will probably result in a number of threads waiting for each other and result in underutilization of the available cores.
One thing I learned from all the issues and emails I have received about this repository over the years is that what people consider the "usual" use case of threads varies wildly. Some only care for the concurrency but not the performance, some have huge amounts of tiny work items, some have small amounts of huge work items, some have complex dependencies, some have none at all etc.
The forks don't seem to actually fix problems, they just add various features to the library, features I don't personally need. And many of the forks are also not updated in a long time.
I guess short and simple is sometimes good enough to last?
I know this would cause problems with boost, not sure about std::.
That's not a bug. The notifier can either signal the condition variable with or without the corresponding lock held and both cases are race-free. In some implementations, it may be more performant to signal the condvar with the lock still held, while in others it is more performant to signal the condvar after releasing the lock.
In this discussion "implementations" isn't referring to boost, libstdc++, or LLVM's glue library, "implementations" is referring to the underlying system libraries.
Alas, most of the implementations aren't willing to tell you which one is better.
What would the case where it's more performant to notify while holding the lock look like? Is the underlying implementation somehow able to transfer ownership of the mutex?
> There is at least one implementation that takes advantage of the requirement that a condition variable be associated with a unique lock to make fewer futex(2) calls, such that the signaling and woken thread make exactly one system call each. NPTL does this.
However, I cannot find that Q&A pairing any more. It is certainly the case on the RTOS I'm using right now that it is more optimal to signal outside the lock and rely on the fact that uncontended locking and unlocking operations don't make passes through the scheduler.
IIRC it is so hard to get it right in practice (the number of races and corner cases is staggering) that recent libc versions might have stopped doing it. I might be misremembering though.
[1] https://en.cppreference.com/w/cpp/thread/condition_variable
As a rule of thumb: its usually a bug to not hold the lock before notify(), unless you synchronize it with another condition
But yeah, in general I agree with the advice.. I'm pretty sure I've made that mistake before.
"Even if the shared variable is atomic, it must be modified under the mutex in order to correctly publish the modification to the waiting thread."
That's not normative but I can't be bothered to check the c++ standard for exact wordings. Also SuSv4 doesn't have an explicit prohibition on modifying the predicate outside a critical section. But if you do, you are truly on your own.
So simply using an atomic (even with a full release-acquire memory barrier) is not necessarily sufficient as that would only enforce the coherence but not prevent the scheduler from interrupting at the wrong moment.
All correct non-realtime uses uses of condition variables should work fine with notify called outside of the critical section.
The only case it matters is when using strict realtime scheduling (SCHED_FIFO and SCHED_RR) and it is important that higher priority threads are woken up before lower priority ones.
Side note is that I love how rust simplified that (https://docs.rs/threadpool/1.7.1/threadpool/).
The result local holds a future/task, not the result itself, and get() may force a synchronous wait, like Task#Result in .Net.
Somewhat related ramblings: I couldn't have misread the code in this way were it not for C++'s new type-inference with auto. In C#, I generally only use type-inference when first writing a statement, and then have the IDE substitute the var keyword to give a traditional 'explicit' declaration. Explicit types greatly help a codebase to be 'self-documenting'. Readability outweighs writing speed.
> A simple C++11 Thread Pool implementation
Incidentally, we build a small threadpool in the final chapter of the Rust book. Most of the implementation is described here, https://doc.rust-lang.org/nightly/book/ch20-02-multithreaded... with a bit in the following section. Here's all the code together: https://play.rust-lang.org/?version=stable&mode=debug&editio...
One difference between this pool and the library in the OP is that the OP's pool returns handles that you can use to get jobs out of the pool, whereas this one does not. You can add that functionality on top of this pool by capturing a channel, but it's nice that they have it built in. It's not needed for the example I wrote the pool of, which is handling HTTP connections, so I didn't put it in there.
Looking at this example makes me wonder if I can simplify this even further; it’d be nice to remove that ref count. Not for performance reasons, just to make there be even less code.