cpp-work-stealing-pool

A header-only C++20 work-stealing thread pool built on a lock-free Chase-Lev deque. It supports futures, exception propagation, parallel_for, and deadlock-free nested fork/join. CI tests it with GCC and Clang under AddressSanitizer, UndefinedBehaviorSanitizer and ThreadSanitizer.

#include "wsp/thread_pool.hpp"

wsp::ThreadPool pool;                                   // one worker per core

auto f = pool.submit([](int a, int b) { return a + b; }, 20, 22);
int x = f.get();                                        // 42

pool.parallel_for<std::size_t>(0, v.size(), [&](std::size_t i) { v[i] *= 2; });

// Recursive fork/join from inside tasks: pool.wait() runs other tasks while it
// waits, so the workers never all block.
std::uint64_t fib(wsp::ThreadPool& pool, int n) {
    if (n < 20) return fib_seq(n);
    auto left = pool.submit([&pool, n] { return fib(pool, n - 1); });
    auto right = fib(pool, n - 2);
    return pool.wait(left) + right;
}

Architecture

             submit() from outside                    submit() from a worker
                     │                                          │
                     ▼                                          ▼
          ┌──────────────────────┐        ┌──────── worker k's own deque (LIFO push/pop)
          │ injection queue      │        │
          │ (mutex, FIFO)        │        ▼
          └──────────┬───────────┘   ┌─────────┐  ┌─────────┐  ┌─────────┐
                     │               │ deque 0 │  │ deque 1 │  │ deque 2 │ ...
                     └──────────────▶│ worker 0│  │ worker 1│  │ worker 2│
                                     └────┬────┘  └────▲────┘  └─────────┘
                                          │  steal()   │
                                          └────────────┘   (FIFO end: oldest = biggest task)

Where an idle worker looks for work: its own deque, then the injection queue, then a random victim's deque.

Chase-Lev deque (include/wsp/chase_lev_deque.hpp)

• The owner pushes and pops at the bottom. That needs no CAS unless it is racing thieves for the very last element.
• Thieves take from the top with a single CAS on top.
• The ring buffer grows when full. A thief may still be reading an old buffer, so old buffers are retired and kept alive until the deque is destroyed. This is a simple, safe reclamation scheme that needs no hazard pointers or epochs.
• Memory ordering follows Lê et al., Correct and Efficient Work-Stealing for Weak Memory Models (PPoPP'13), with one change: the paper's seq_cst fences are written as seq_cst loads and stores. That gives the same store→load ordering, and on x86 it is the same single xchg. ThreadSanitizer, which ignores standalone fences, can then verify the code.

Sleeping without lost wake-ups

Idle workers block on a condition variable. Waking uses a Dekker-style handshake on two seq_cst counters:

submitter	sleeper
queued_++	sleepers_++ (holding sleep_mu_)
if (sleepers_ > 0) { lock; unlock; notify_one }	wait until queued_ > 0 || stop_

Sequential consistency guarantees that at least one side sees the other's increment, so no wake-up is lost. When all workers are busy, submit() takes no lock at all on the worker-local path.

Helping wait()

When a worker calls pool.wait(future), it keeps executing queued tasks until the future is ready instead of blocking. Recursive divide-and-conquer therefore cannot deadlock, even on a single-thread pool.

Shutdown

The destructor sets stop_, and workers exit only once queued_ == 0. All outstanding work runs first, including tasks spawned during shutdown.

Build & run

cmake -S . -B build -G Ninja            # GoogleTest is fetched automatically
cmake --build build
ctest --test-dir build --output-on-failure
./build/wsp_bench
./build/parallel_quicksort

# sanitizers
cmake -S . -B build-tsan -DWSP_SANITIZER=thread  && cmake --build build-tsan && ctest --test-dir build-tsan
cmake -S . -B build-asan -DWSP_SANITIZER=address && cmake --build build-asan && ctest --test-dir build-asan

TSan on recent kernels may need sudo sysctl vm.mmap_rnd_bits=28.

Benchmarks

8-vCPU laptop VM (Docker on Windows), GCC 14 -O3. Numbers are indicative only.

fib(40)            seq    170.0 ms   pool     46.2 ms   speedup 3.68x
parallel_for 20M   seq    400.9 ms   pool    115.9 ms   speedup 3.46x
spawn 2^21 tree    central-queue  819.0 ms (2.6 Mtasks/s)   work-stealing  80.8 ms (25.9 Mtasks/s)   10.13x

std::sort (20M u32)   1782 ms
parallel_quicksort     470 ms   (3.79x)

In the spawn tree benchmark, 2 million tiny tasks each spawn two children. It isolates scheduling overhead. A classic single mutex-plus-condvar queue serializes every push and pop on one lock and one cache line. Per-worker deques keep nearly every operation core-local, which makes them about 10x faster.

Tests (tests/)

Test	What it checks
OwnerIsLifoThiefIsFifo	deque end semantics
GrowsPreservingOrder, GrowsAfterWrapAround	growth copies live elements correctly, even when they straddle the ring boundary
ConcurrentOwnerAndThievesConsumeEachItemOnce	1 owner + 4 thieves, 200k items, grows under contention, and every item is taken exactly once
NestedForkJoinDoesNotDeadlock	recursive fib on 2 workers, which needs helping-wait and exercises stealing
ParallelForRethrowsAfterAllChunksFinish	no dangling references when a chunk throws
DestructorDrainsWorkSpawnedByWork	shutdown runs tasks created during shutdown
WakesUpAfterIdle	no lost wake-ups after workers go to sleep
…	move-only callables and arguments, exception propagation, range coverage

License

MIT