The Chase-Lev deque is a double-ended queue (deque) designed for work-stealing schedulers. It allows a worker thread to operate on one end of the queue while other threads can steal tasks from the opposite end.
This design is optimized for task parallelism and is widely used in parallel runtimes. It operates as a shared ring buffer, that reduces memory overhead. Two roles use the buffer differently:
- the worker thread that owns it pushes tasks to the bottom and pop to the bottom (LIFO)
- the thieves steal from the top (FIFO)
The idea is that LIFO popping benefits from temporal locality (hot data) more likely to be available in the processor cache (as long as the tasks do not yield frequently, as in tokio) and improves throughput. However,
Important
The deque must handle edge cases where the worker thread and a thief simultaneously attempt to access the last task. This requires careful synchronization, typically using atomic operations and appropriate memory ordering semantics
Task interdependency and performance
When one task spawns another as a part of the computation, such as a recursive algorithm or divide and conquer, spawned tasks often access shared data or results computed by their parent task. Since the worker threads works most recently on the recently spawned task firsts, this minimize cache misses thanks to temporal locality
When instead the tasks are independent, there is no benefits instead but only a fairness problem because the worker thread always consumes most recent tasks, potentially starving the older ones