> Not sure but there may be two bugs in the code. The use of notify on the condition outside of the mutex lock.
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.
I understand the case where it's more performant to notify outside of the lock, so that the notified thread doesn't wake up and immediately block again waiting for the notifying thread to release the lock.
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?
I must admit that I could be mistaken. There was a stack overflow question about this very topic wherein an NPTL implementer spoke up and claimed the following (any errors in this are the fault of my own recollection):
> 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.
You are thinking of FUTEX_*_REQUEUE (see the man page for details). It will move (some of) the waiters from the condvar futex to the mutex futex. IIRC, the optimization is called wait morphing.
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.
Per [1] the lock does not need to be held when calling notify. In the 17 standard this is §33.5 but I can't quite parse out the real requirements there.
In this case I think it should be ok because !this->tasks.empty() is part of the predicate, and will be true after a new item is enqueued (and before notify is called). So if the producer is interrupted between releasing the mutex and calling notify, the consumer would not call wait.
But yeah, in general I agree with the advice.. I'm pretty sure I've made that mistake before.
It depends on if the predicate can (also) be changed without the lock being held, as otherwise the release/acquire ordering semantics are not guaranteed. So long as items are only every enqueued with the lock held, it should be ok.
"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.
It is because condition variables have no state, i.e. calling signal without waiters is equivalent to doing nothing and does not affect a future wait. The concern is that a thread is switched out after it checks the condition but before it calls wait, and in that moment the condition variable is signaled. The thread then calls wait and is not awoken (potentially never to be awoken). If the predicate is not altered without the mutex and the waiting thread has the mutex at the time it checks the predicate (this latter part is a must in all cases), then it is guaranteed the predicate will remain unmet at least until the thread has switched to a waiting state.
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.
The exception I guess is when paired with a condition variable, since CV waits are not guaranteed spurious and necessarily must be combined with another condition. The caveat being that the variable being tested upon wake must not be modified without the lock held (presumably to prevent reordering).
> its usually a bug to not hold the lock before notify()
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.
The C++ spec simplifies what is basically an abstraction over the posix layer. I dug into this very deeply a long time ago, there’s a lot nuance there and documentation is confusing: https://github.com/neosmart/pevents/issues/2
The 'simple' adjective is vastly abused - in majority of cases code behind 'simple' project isn't simple - like in this case a person without mid-advanced knowledge about threading / binding / synchronisation / generic programming will have a problem to grasp what's going on in the implementation.
No it's not. It looks like it on the surface, but real world usage will run into the blocking `get()` methods blocking threads on the thread pool leading to deadlocks or low throughput. What C++ needs is a well thought out design of how to transfer values in a purely asynchronous manner (like Rust futures, JavaScript promises, etc).
The thread pool normally just allows you to execute code (think void() lambdas). Returning values to the caller isn’t something they normally do, but is normally managed by higher level concurrency libraries like facebooks folly or libq (among others).
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.
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.
It's not maintained but it sure does work well. I've been throwing all kinds of workloads at it, always works like a charm.
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?
It's been so long since I've programmed in C++ that I can't even read this code. Last time I wrote an anonymous function I had to use boost::lambda, now there's an override for [] on line 39? And wtf is the arrow operator doing out there in space on line 19?
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.
Threadpools are rabbit-hole problems. They seem structurally simple at first, but they also have some unexpected failure modes. There are two that I'm aware of, and there are almost certainly more.
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.
Just curious, but is there a reason why you didn’t just use a single lock-less queue? Per-thread work queues sounds like a perfectly serviceable solution but I can imagine it an advantage to hide that added complexity behind a lock-less queue (which could in fact be implemented using multiple queues internally, but I think that’s just one of multiple ways to implement such a thing)
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.
Not sure if I'm following. In many (most?) multiple-producer/multiple-consumer cases it is completely irrelevant if the work-queue guarantees a strict insertion/removal order, as long as the queue is 'fair' (time in queue is distributed evenly over all work items). If that's all you need, a lock-free implementation using atomic operations does not have to be complicated, or what am I missing here?
A "work-queue" doesn't have strict ordering in many multithreaded programs. But a "queue" or "fifo" is expected to have a strict ordering.
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.
Actually, this is very feasible by overprovisioning to get enough padding to use the approach described in Section 5.3 of [0]. That way you get a really fast fast-path.
[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
But also, coordination with the OS and thread pools from other processes - e.g. GrandCentral / dispatch. If you have multiple apps using that same thread pool they need to be aware of that, and the OS seems like what should be managing these...
> 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.
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.
Pre-calculating an estimate to the work-item's complexity helps solve problem#1, while batching work-items together into the vector<WorkItem> list solves problem#2.
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.
You're effectively solving the problem of small work items by making them larger. Alas, doing so in the workers introduces new failure modes.
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.
Yes, you're correct! This is definitely a difficult problem with many nuances.
> 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.
Work items in my case are packets from the network. There's not much I can do to batch them; perhaps increase socket buffer sizes, but that comes with its own problems, and doesn't help when the peer is waiting for a response instead of flooding more packets in.
Instead of 16x consumer threads serving 16x producer threads, you probably would be more efficient with 8x consumer threads serving 24x producer threads. Or some other asymetrical arrangement. Its the classic "latency vs throughput" tradeoff, you decide that higher-latency is acceptable to increase throughput.
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.
I'm the original author of that github repo and I agree with all of this. The original reason why I wrote it was to familiarize myself with the then new features in the C++11 standard. Particularly I liked the simplicity of std::async but didn't like that:
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.
I also liked the simplicity of the std::async interface. But since the first few implementations just created a whole thread to execute them, I haven't ever used it. NPTL is pretty efficient at spawning and shutting down threads, but I still wouldn't spin up an entire thread unless the unit of work was several milliseconds at least.
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.
Fundamentally concepts are enjoyed by most everyone, including those who are learning about them the first time, especially when they're explained clearly.
It's a neat trick I hadn't seen before, but it doesn't seem particularly advanced. There are all kinds of things in the STL that I don't remember or care about until I actually need them.
You definitely have a different interpretation of "Hello World" than most people. There is some pretty sophisticated syntax happening in this short example. If I were to do a real hello world, it would be more high-level and a lot shorter, but also not as useful as this example.
On a somewhat tangential note, for C++ threading, Intel TBB is the best thing after sliced bread. Can't recommend it enough. It's just plain amazing. Very advanced. Complete with a flow-graph implementation. Should be part of the toolkit of every serious programmer (on par with C++ standard library).
The queue is a single contention point which will have a considerable overhead unless the work takes a long time to execute (ie, enqueue is infrequent).
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.
> This kind of approach is usually not what you want
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.
65 comments
[ 3.8 ms ] story [ 114 ms ] threadI 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.
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?
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.
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.
Pre-calculating an estimate to the work-item's complexity helps solve problem#1, while batching work-items together into the vector<WorkItem> list solves problem#2.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.
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.
I made a few changes to it to make it more flexible in terms of when it starts, stops, and restarts:
https://github.com/seung-lab/euclidean-distance-transform-3d...
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.