Lockless Work-Stealing Queues in Modern Game Engines

Modern game engines rely on lockless work-stealing job queues to maximize multi-core CPU utilization without the latency penalties of operating-system-level thread synchronization. This article explores the architecture behind these systems, detailing the foundational Chase-Lev work-stealing deque, atomic memory ordering, cache-line optimization, and techniques for mitigating race conditions across arbitrary worker threads.

The Work-Stealing Architecture

In a work-stealing scheduler, each CPU worker thread manages its own private queue of tasks. When a thread exhausts its local work, it becomes a "thief" and attempts to steal tasks from the queues of other worker threads.

To make this efficient and lock-free, engineers predominantly implement variants of the Chase-Lev work-stealing deque (double-ended queue). The deque operates with asymmetric access patterns:

  • The Owner Thread (LIFO): The worker that owns the queue pushes and pops tasks from the bottom of the deque. Operating as a Last-In, First-Out (LIFO) stack preserves cache locality, as newly spawned sub-tasks often access data hot in the CPU L1/L2 caches.
  • The Stealing Threads (FIFO): Concurrent thieves pop tasks from the top of the deque using a First-In, First-Out (FIFO) access pattern. Thieves take older tasks—often high-level tasks that represent larger branches of the workload graph—reducing the overall number of steals required.

Because the owner and the thieves operate on opposite ends of the deque, contention is minimized. Synchronization is strictly required only when the deque contains one item or when the queue becomes empty.

Managing Concurrency with Atomic Indices

A lockless deque is typically implemented over a circular array managed by two atomic indices: top and bottom.

  1. Push Operation (Owner Only):
    • The owner reads bottom and top.
    • If the buffer is not full, the owner stores the task at buffer[bottom].
    • The owner increments bottom with a store-release operation (std::memory_order_release), ensuring the task data is globally visible before the increment is published.
  2. Pop Operation (Owner Only):
    • The owner decrements bottom with sequential consistency or acquire/release barriers.
    • If top < bottom, multiple items remain. The owner retrieves the task at bottom without contending with thieves.
    • If top == bottom, exactly one item remains, creating a race condition with any potential thief attempting to read that same task. The owner executes an atomic Compare-And-Swap (CAS) to update top to top + 1. If the CAS succeeds, the owner claims the task. If it fails, a thief stole it first, and the owner resets bottom = top + 1.
  3. Steal Operation (Any Arbitrary Core):
    • A thief reads top with acquire semantics (std::memory_order_acquire).
    • The thief reads bottom with acquire semantics.
    • If top < bottom, tasks are available. The thief reads the task at buffer[top].
    • The thief executes a CAS on top (compare_exchange_strong), attempting to advance it to top + 1. If the CAS succeeds, the steal is complete; if it fails, another thread won the race, and the thief retries or targets another core.

Memory Ordering and Barrier Placement

To prevent CPU instruction reordering and compiler optimizations from corrupting state, engineers utilize C++11 atomic memory orders rather than heavy sequentially consistent operations:

  • Acquire-Release Semantics: Pushing tasks uses memory_order_release to ensure that task payload data is written to memory before the bottom pointer updates. Stealing and popping read the index with memory_order_acquire to guarantee they do not read stale task data.
  • Sequential Consistency at the Boundary: The singular edge-case—when the queue transitions from one item to zero—often requires an explicit full memory barrier (atomic_thread_fence(memory_order_seq_cst)) or a sequentially consistent CAS to ensure that the owner's decrement of bottom and the thief's increment of top are strictly synchronized across all CPU store buffers.

Cache-Conscious Design and False Sharing

High-frequency atomic exchanges can invalidate CPU cache lines, leading to cache-coherency bottlenecks known as false sharing. Engineers apply specific layout constraints to prevent this:

  • Cache-Line Padding: The top and bottom atomic integers must reside on separate cache lines (typically 64 or 128 bytes apart) using alignas(std::hardware_destructive_interference_size). This prevents the owner thread updating bottom from invalidating the cache line containing top, which thieves are actively monitoring.
  • Task Storage Separation: The pointers or inline task descriptors inside the circular buffer array are kept in a contiguous memory block separated from the control indices.

Mitigating Dynamic Allocation and the ABA Problem

In performance-critical game engines, unbounded queues that dynamically allocate memory at runtime introduce unacceptable latency.

  • Bounded Power-of-Two Rings: Queues are often fixed at compile-time to power-of-two sizes (e.g., 1024 or 4096 elements). This simplifies index wrapping via a bitwise AND (index & (capacity - 1)) instead of modulo operations.
  • 64-Bit Monotonic Counters: Instead of wrapping the top and bottom variables directly, engineers allow 64-bit unsigned integers to increment monotonically without wrapping. The circular buffer index is derived solely during array indexing. Because a 64-bit integer will not overflow within centuries under continuous operation, the ABA problem—where a pointer is swapped back to an identical address while another thread is mid-operation—is mathematically eliminated without needing tagged pointers or garbage collection schemes like hazard pointers.