3 ms·

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

by 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.
  - dragontamer 7y ago
    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.
- clarry 7y ago
  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.
  - dragontamer 7y ago
    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.

by clarry 7y ago

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.
- dragontamer 7y ago
  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.
clarry 7y ago
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.
- dragontamer 7y ago
  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.