Work-Stealing Thread Pools

March 2026

The Single-Queue Bottleneck

In the basic thread pool from the previous article, every task submission and every task retrieval goes through one mutex. Under low contention that is perfectly fine, but when many workers compete for the lock simultaneously, throughput drops because workers spend time spinning or sleeping on the mutex instead of executing tasks.

The problem intensifies with unbalanced workloads: if some tasks produce sub-tasks at high frequency while other workers sit idle, the single queue becomes a serialization point.

Key insight. Give each worker its own local queue. Workers push and pop from their own queue without contention. When a worker runs out of work, it steals from another worker’s queue.

How Work Stealing Works

Each worker thread owns a double-ended queue (deque). The owning thread pushes and pops from the bottom (private end), while thieves steal from the top (public end).

When a worker produces a new task (or receives one via submit()), it pushes onto the bottom of its own deque.
When a worker needs work, it pops from the bottom of its own deque (LIFO order for cache locality).
If a worker’s deque is empty, it randomly selects another worker and tries to steal from the top of that worker’s deque (FIFO order).

The owner pops from the bottom (Step 1), a thief steals from the top (Steps 2–3). The push/pop on the bottom is a fast, often lock-free operation because only the owner touches it. Contention only occurs during a steal, and steals are rare relative to local pops.

The Chase-Lev Deque

The foundational data structure for work stealing is the Chase-Lev deque, described by David Chase and Yossi Lev (2005). It provides:

push() and pop() at the bottom, called only by the owner thread.
steal() at the top, callable by any other thread.
push and pop are wait-free in the common case; steal uses a single compare-and-swap.

It uses a circular buffer (resizable array) with two atomic indices: top and bottom.

Interface

template <typename T>
class WorkStealingDeque {
public:
    explicit WorkStealingDeque(std::size_t capacity = 1024);

    // Owner only
    void push(T item);
    std::optional<T> pop();

    // Any thread
    std::optional<T> steal();

    std::size_t size() const;
};

Circular Buffer

template <typename T>
class CircularBuffer {
public:
    explicit CircularBuffer(std::size_t capacity)
        : capacity_(capacity)
        , mask_(capacity - 1)
        , buffer_(new T[capacity])
    {
        // capacity must be a power of two
        assert((capacity & (capacity - 1)) == 0);
    }

    T get(std::size_t index) const {
        return buffer_[index & mask_];
    }

    void put(std::size_t index, T value) {
        buffer_[index & mask_] = std::move(value);
    }

    // Grow the buffer, copying elements from old_top to old_bottom.
    CircularBuffer* grow(std::size_t old_top,
                         std::size_t old_bottom) {
        auto* new_buf = new CircularBuffer(capacity_ * 2);
        for (std::size_t i = old_top; i < old_bottom; ++i) {
            new_buf->put(i, get(i));
        }
        return new_buf;
    }

    std::size_t capacity() const { return capacity_; }

private:
    std::size_t capacity_;
    std::size_t mask_;
    std::unique_ptr<T[]> buffer_;
};

Core Operations

template <typename T>
class WorkStealingDeque {
    std::atomic<std::size_t> top_{0};
    std::atomic<std::size_t> bottom_{0};
    std::atomic<CircularBuffer<T>*> buffer_;

public:
    explicit WorkStealingDeque(std::size_t capacity = 1024)
        : buffer_(new CircularBuffer<T>(capacity)) {}

    ~WorkStealingDeque() {
        delete buffer_.load(std::memory_order_relaxed);
    }

    // Owner pushes at the bottom.
    void push(T item) {
        std::size_t b = bottom_.load(std::memory_order_relaxed);
        std::size_t t = top_.load(std::memory_order_acquire);
        auto* buf = buffer_.load(std::memory_order_relaxed);

        if (b - t >= buf->capacity()) {
            // Deque is full; grow.
            auto* new_buf = buf->grow(t, b);
            delete buf;
            buffer_.store(new_buf, std::memory_order_relaxed);
            buf = new_buf;
        }

        buf->put(b, std::move(item));
        std::atomic_thread_fence(std::memory_order_release);
        bottom_.store(b + 1, std::memory_order_relaxed);
    }

    // Owner pops from the bottom.
    std::optional<T> pop() {
        std::size_t b = bottom_.load(std::memory_order_relaxed) - 1;
        auto* buf = buffer_.load(std::memory_order_relaxed);
        bottom_.store(b, std::memory_order_relaxed);

        std::atomic_thread_fence(std::memory_order_seq_cst);

        std::size_t t = top_.load(std::memory_order_relaxed);
        if (t <= b) {
            // Non-empty.
            T item = buf->get(b);
            if (t == b) {
                // Last element: race with steal().
                if (!top_.compare_exchange_strong(
                        t, t + 1,
                        std::memory_order_seq_cst,
                        std::memory_order_relaxed)) {
                    // Lost the race to a thief.
                    bottom_.store(t + 1, std::memory_order_relaxed);
                    return std::nullopt;
                }
                bottom_.store(t + 1, std::memory_order_relaxed);
            }
            return item;
        }
        // Deque was empty.
        bottom_.store(t, std::memory_order_relaxed);
        return std::nullopt;
    }

    // Any thread steals from the top.
    std::optional<T> steal() {
        std::size_t t = top_.load(std::memory_order_acquire);
        std::atomic_thread_fence(std::memory_order_seq_cst);
        std::size_t b = bottom_.load(std::memory_order_acquire);

        if (t < b) {
            auto* buf = buffer_.load(std::memory_order_relaxed);
            T item = buf->get(t);
            if (!top_.compare_exchange_strong(
                    t, t + 1,
                    std::memory_order_seq_cst,
                    std::memory_order_relaxed)) {
                return std::nullopt;  // another thief won
            }
            return item;
        }
        return std::nullopt;
    }

    std::size_t size() const {
        std::size_t b = bottom_.load(std::memory_order_relaxed);
        std::size_t t = top_.load(std::memory_order_relaxed);
        return (b > t) ? (b - t) : 0;
    }
};

Memory ordering matters. The seq_cst fence in pop() and the matching fence in steal() prevent the owner and a thief from both successfully taking the last element. Getting the ordering wrong leads to double-consumption or lost items.

Putting It Together: A Work-Stealing Pool

#include <vector>
#include <thread>
#include <atomic>
#include <functional>
#include <random>

class WorkStealingPool {
public:
    explicit WorkStealingPool(std::size_t num_threads
                              = std::thread::hardware_concurrency())
        : stop_(false)
        , num_threads_(num_threads == 0 ? 1 : num_threads)
    {
        deques_.reserve(num_threads_);
        for (std::size_t i = 0; i < num_threads_; ++i) {
            deques_.emplace_back(
                std::make_unique<WorkStealingDeque<
                    std::function<void()>>>());
        }

        workers_.reserve(num_threads_);
        for (std::size_t i = 0; i < num_threads_; ++i) {
            workers_.emplace_back([this, i] { run(i); });
        }
    }

    WorkStealingPool(const WorkStealingPool&) = delete;
    WorkStealingPool& operator=(const WorkStealingPool&) = delete;

    void submit(std::function<void()> task) {
        // Round-robin distribution to local deques.
        std::size_t idx = next_index_.fetch_add(1,
            std::memory_order_relaxed) % num_threads_;
        deques_[idx]->push(std::move(task));
    }

    void shutdown() {
        stop_.store(true, std::memory_order_release);
        for (auto& w : workers_) {
            if (w.joinable()) w.join();
        }
    }

    ~WorkStealingPool() {
        if (!stop_.load(std::memory_order_acquire)) {
            shutdown();
        }
    }

private:
    void run(std::size_t my_index) {
        thread_local std::mt19937 rng(
            std::random_device{}());

        while (!stop_.load(std::memory_order_acquire)) {
            // 1. Try own deque first.
            auto task = deques_[my_index]->pop();
            if (task) { (*task)(); continue; }

            // 2. Try stealing from a random other worker.
            bool found = false;
            for (std::size_t attempt = 0;
                 attempt < num_threads_; ++attempt) {
                std::size_t victim =
                    rng() % num_threads_;
                if (victim == my_index) continue;
                task = deques_[victim]->steal();
                if (task) {
                    (*task)();
                    found = true;
                    break;
                }
            }

            if (!found) {
                // 3. No work anywhere; yield to reduce CPU.
                std::this_thread::yield();
            }
        }

        // Drain own deque before exiting.
        while (auto task = deques_[my_index]->pop()) {
            (*task)();
        }
    }

    std::atomic<bool> stop_;
    std::size_t num_threads_;
    std::atomic<std::size_t> next_index_{0};
    std::vector<std::unique_ptr<
        WorkStealingDeque<std::function<void()>>>> deques_;
    std::vector<std::thread> workers_;
};

When Work Stealing Helps

Work stealing is not universally better than a single shared queue. It shines in specific scenarios:

Unbalanced Workloads

When tasks spawn sub-tasks unevenly (e.g., recursive divide-and-conquer), some workers accumulate large backlogs while others run dry. Stealing redistributes work automatically.

Fork-Join Parallelism

Classic parallel algorithms like merge sort or quicksort split work recursively. The worker that initiates the split pushes sub-tasks to its own deque, maintaining cache locality. Other workers steal only when they have nothing else to do.

// Parallel fibonacci with work stealing (illustrative)
void parallel_fib(WorkStealingPool& pool, int n,
                  std::promise<long long> result) {
    if (n < 30) {
        // Base case: compute sequentially.
        result.set_value(fib_sequential(n));
        return;
    }

    std::promise<long long> p1, p2;
    auto f1 = p1.get_future();
    auto f2 = p2.get_future();

    pool.submit([&pool, n, p = std::move(p1)]() mutable {
        parallel_fib(pool, n - 1, std::move(p));
    });
    pool.submit([&pool, n, p = std::move(p2)]() mutable {
        parallel_fib(pool, n - 2, std::move(p));
    });

    result.set_value(f1.get() + f2.get());
}

When It Does Not Help

Uniform, coarse tasks. If every task takes roughly the same time, a round-robin shared queue distributes load evenly with less complexity.
Very few tasks. The overhead of per-thread deques is not justified if you only submit a handful of tasks.
High-frequency submission from one thread. A single producer flooding the pool is better served by an MPMC queue.

Reducing Contention Further

LIFO for Locality, FIFO for Stealing

The owner processes tasks in LIFO order (most recently pushed). This maximizes temporal and spatial cache locality because the most recent task likely shares data with the current task.

Thieves take from the FIFO end (oldest tasks first). Older tasks tend to represent larger, coarser units of work, so a single steal gives the thief more to do before it needs to steal again.

Exponential Backoff

Instead of std::this_thread::yield() when no work is found, use exponential backoff to reduce scheduler overhead:

void backoff_wait(unsigned& spin_count) {
    if (spin_count < 10) {
        // Busy spin with pause hint.
        for (unsigned i = 0; i < (1u << spin_count); ++i) {
#if defined(__x86_64__) || defined(_M_X64)
            __builtin_ia32_pause();
#else
            std::this_thread::yield();
#endif
        }
        ++spin_count;
    } else {
        // After many failed attempts, sleep briefly.
        std::this_thread::sleep_for(
            std::chrono::microseconds(50));
    }
}

// Reset spin_count to 0 whenever work is found.

Bounded Stealing Attempts

Rather than scanning all workers, limit stealing attempts to 2 or 3 random victims per round. If all fail, back off. This prevents a thundering herd of idle workers all trying to steal from the same busy worker.

Comparison: Shared Queue vs. Work Stealing

Property	Shared Queue	Work Stealing
Contention	All threads on one lock	Mostly lock-free local ops
Cache locality	Poor (tasks scattered)	LIFO pop preserves locality
Load balancing	Automatic (one queue)	On-demand via stealing
Complexity	Simple	Moderate (CAS, memory ordering)
Best for	Uniform, moderate tasks	Unbalanced, recursive tasks

Summary

Work stealing gives each worker a private deque, eliminating the shared-queue bottleneck.
The Chase-Lev deque provides wait-free push/pop for the owner and CAS-based steal for thieves.
LIFO pop maximizes cache locality; FIFO steal transfers coarser work chunks.
Work stealing excels at fork-join parallelism and unbalanced workloads.
For uniform tasks or simple pools, a shared queue with a mutex is often sufficient.

Next up. Shutting down a pool cleanly is harder than it sounds. The next article covers graceful shutdown: draining the queue, handling in-flight tasks, and exception safety.

← Basic Thread Pool Graceful Shutdown →