6 ms·

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 o

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.

malkia 7y ago
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...
apankrat 7y ago
Re #2 - 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-completion-ports https://docs.microsoft.com/en-us/windows/win32/fileio/i-o-co...
- dblohm7 7y ago
  That's precisely how the QueueUserWorkItem API is implemented under the hood.
w0utert 7y ago
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)
- brandmeyer 7y ago
  In my case, the complexity was hidden behind the interface to the threadpool. 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.
- dragontamer 7y ago
  > use a single lock-less queue 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.
clarry 7y ago
> 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.
- dragontamer 7y ago
  Batch larger batches. 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); } 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.
  - brandmeyer 7y ago
    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.
JakobProgsch 7y ago
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.
- brandmeyer 7y ago
  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.

malkia 7y ago

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...

apankrat 7y ago

Re #2 - 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-completion-ports https://docs.microsoft.com/en-us/windows/win32/fileio/i-o-co...

dblohm7 7y ago
That's precisely how the QueueUserWorkItem API is implemented under the hood.

w0utert 7y ago

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)

brandmeyer 7y ago
In my case, the complexity was hidden behind the interface to the threadpool. 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.
dragontamer 7y ago
> use a single lock-less queue 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.

clarry 7y ago

> 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.

dragontamer 7y ago
Batch larger batches. 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); } 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.
- brandmeyer 7y ago
  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.

JakobProgsch 7y ago

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.

brandmeyer 7y ago
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.