What are the benefits and drawbacks of using a work-stealing algorithm in fork-join pools?

1 Work-stealing algorithm

A work-stealing algorithm is a scheduling technique that allows a worker thread to steal subtasks from other workers when it has nothing to do. The idea is to keep all the workers busy and avoid idle time. The algorithm works as follows: each worker has a local deque (double-ended queue) where it stores its subtasks. When a worker creates new subtasks, it pushes them to the head of its deque. When a worker finishes a subtask, it pops another one from the head of its deque. When a worker's deque is empty, it tries to steal a subtask from the tail of another worker's deque.

2 Benefits of work-stealing

One of the main benefits of work-stealing is that it achieves good load balancing among the workers. Since each worker can create and execute subtasks locally, there is no need for a central coordinator or a shared queue. This reduces the overhead and the contention for accessing the shared data structures. Moreover, since each worker can steal subtasks from others, the work is distributed evenly and the idle time is minimized. Another benefit of work-stealing is that it adapts well to dynamic and irregular workloads. Since the subtasks are created and executed on demand, the algorithm can handle varying sizes and dependencies of the subtasks. The algorithm can also cope with changes in the number of workers or the availability of resources.

3 Drawbacks of work-stealing

However, work-stealing also has some drawbacks that you should be aware of. One of them is that it can cause false sharing and cache misses. False sharing occurs when two or more workers access different parts of the same cache line, causing invalidations and transfers. Cache misses occur when a worker accesses a subtask that is not in its local cache, causing delays and traffic. These problems can degrade the performance and the scalability of the algorithm. Another drawback of work-stealing is that it can introduce non-determinism and unpredictability. Since the order and the location of the subtask execution depend on the availability and the behavior of the workers, the algorithm can produce different results and timings for each run. This can make debugging and testing more difficult and require extra synchronization and communication mechanisms.

4 Best practices for work-stealing

To make the most of work-stealing, you should follow some best practices that can help you avoid or mitigate its drawbacks. One of them is to design your subtasks to be small, independent, and stateless. This way, you can reduce the false sharing and the cache misses, as well as the synchronization and the communication overhead. Another one is to use a suitable data structure for your subtasks, such as an array or a linked list, that can support efficient push, pop, and steal operations. You should also avoid using blocking or I/O operations in your subtasks, as they can prevent the workers from stealing and executing other subtasks. Finally, you should use a suitable fork-join pool configuration, such as the number and the priority of the workers, that can match your workload and your hardware.

5 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?