Job Systems
from Scratch

01Why a game engine needs a job system

A 60 fps game has 16.6 milliseconds to update the world, simulate physics, run animation, cull the scene, build a few thousand draw calls, and stream textures off disk. The PS5 and Xbox Series have eight CPU cores; a gaming PC commonly has six to sixteen. Put all of that work on one core and it overflows the 16.6 ms budget, so the game drops to 30 fps while the other cores sit idle. The job of a job system is to spread that work across every core the machine has.

Spreading the work across cores is harder than it sounds: threads have to coordinate, memory access has to stay cache-friendly, and a naïve solution that hands work to other threads can run slower than the single-threaded version it replaced. A job system is the layer that handles that for the rest of the engine.

The fixed-thread era is over

In the mid-2000s, when consoles first shipped with multiple cores, engines were typically refactored along subsystem lines. One thread for the renderer, one for physics, one for audio, one for everything else. Bungie's Halo: Reach worked this way, with unique threads for rendering, audio and simulation^[3]. It is intuitive because it maps onto the way the engine is already organized. It also stops scaling once every subsystem has a thread, because there is no next subsystem to assign. Worse, the load on each subsystem shifts from frame to frame: a frame heavy on physics leaves the render thread idle, a frame heavy on rendering leaves the physics thread idle, and each frame takes as long as its busiest thread. Bungie's own summary was that static per-thread load balancing "meant suboptimal workload distribution"^[3].

The breakthrough, which the industry settled on between roughly 2009 and 2015, was to stop splitting by subsystem and start splitting by data. Instead of one fat physics thread that integrates every rigid body, you have a thousand small jobs, each of which integrates ten bodies. Throw all thousand jobs at a pool of workers, let the workers grab them as they finish whatever they were doing, and every core stays busy. The abstract of Tatarchuk's GDC 2015 talk on the Destiny renderer states it directly: "to optimally take advantage of all available resources, a game engine must be designed from the ground up for job-based multithreading"^[3].

The widget below contrasts the two models on a synthetic frame of 24 ms of total work. The "fixed threads" mode runs a render thread, a physics thread, and a gameplay thread, each with its own fixed workload. The "job system" mode splits the same work into small jobs for a pool of workers. Compare when each mode finishes the frame:

02A short history of getting parallel

The design most engines use today took shape over about three decades. A short tour:

Each step assumed the ones before it: the scheduling theory (1994–95), the deque (2005), the data-layout discipline (2009), shipped engine designs (2015), and a standard-library vocabulary (2024).

03The naïve worker pool

Start with the simplest thing that could possibly work. N worker threads, one shared queue of work, and a mutex protecting the queue. Each worker loops: grab the mutex, pop a job, drop the mutex, run the job. When the queue is empty, the worker sleeps on a condition variable until somebody adds work.

// A simple thread pool: N worker threads share one job queue,
// protected by a mutex. The usual first design.
class NaivePool {
  // The lock that protects the queue and isRunning. One thread holds it at a time.
  std::mutex                          queueLock;

  // Lets idle workers sleep until somebody calls notify_one().
  // We wake them when a new job arrives or when shutting down.
  std::condition_variable             workAvailable;

  // The queue of jobs. Each job is a callable with no arguments.
  std::queue<std::function<void()>>   jobQueue;

  // One std::thread per worker. They all run workerLoop().
  std::vector<std::thread>            workerThreads;

  // Cleared, under queueLock, by the destructor to tell workers to exit.
  bool                                isRunning = true;

public:
  // Spawn `workerCount` threads. Each enters workerLoop() immediately.
  explicit NaivePool(int workerCount) {
    for (int i = 0; i < workerCount; i++)
      workerThreads.emplace_back([this] { workerLoop(); });
  }

  ~NaivePool() {
    {
      // Clear the flag under the lock: a worker between its check and its
      // wait() would otherwise miss both the flag and the notify.
      std::lock_guard lock(queueLock);
      isRunning = false;
    }
    workAvailable.notify_all();                  // wake every sleeper so it can exit
    for (std::thread& worker : workerThreads) worker.join();
  }

  // Add a job to the queue and wake one sleeping worker.
  void submit(std::function<void()> job) {
    {
      // Take the lock just long enough to push. Releasing it inside
      // the braces lets workers actually pop the job we just added.
      std::lock_guard lock(queueLock);           // every submitter contends here
      jobQueue.push(std::move(job));
    }
    // Wake one worker. If multiple are sleeping, only one needs to run.
    workAvailable.notify_one();
  }

private:
  // Every worker runs this loop until shutdown.
  void workerLoop() {
    for (;;) {
      std::function<void()> nextJob;
      {
        std::unique_lock lock(queueLock);        // every worker also contends here
        // Sleep until there's work to do, or we're shutting down.
        // wait() releases the lock while sleeping and re-acquires it
        // before returning, so the checks below are always safe.
        workAvailable.wait(lock, [this] {
          return !jobQueue.empty() || !isRunning;
        });
        if (!isRunning) return;                  // shutdown: still-queued jobs are dropped
        nextJob = std::move(jobQueue.front());
        jobQueue.pop();
      }                                          // release the lock before running the job
      nextJob();                                 // run outside the lock so other workers can fetch theirs
    }
  }
};

This works. It's about 70 lines of C++ (plus <condition_variable>, <functional>, <mutex>, <queue>, <thread> and <vector>), it's correct, and it gives a real speedup on, say, four cores running 100 ms of mostly-independent work. It is also where most first attempts stop, and it stops scaling quickly. The rest of this tutorial is about why.

Three things go wrong as you scale

1. Lock contention. Every worker grabs the queue's mutex on every job. At 16 workers and a million tiny jobs per second, the lock can become the bottleneck, and the workers spend much of their time waiting in line to look at the queue.
2. Cache-line ping-pong. The mutex word, the queue's head and tail, and the condition variable's wait list are written by every push and pop, from every core. Each write needs the cache line holding that data in the writing core's cache, so those lines bounce between cores. §5 shows the mechanism.
3. It can't express dependencies. Real frame work has structure: animation runs after physics, render runs after visibility culling. With a flat queue and nothing else, a job that needs another job's result has to block until it finishes, and a blocked thread is a wasted core.

Each of these problems has a fix, and the next sections take them one at a time. By the end the global lock is gone from the hot path, each worker has its own queue so cores rarely touch the same line, and dependencies are first-class.

04Threads versus tasks

Beginner code often conflates two separate ideas.

A thread is an execution context: a stack, a program counter, and a slot in the operating system's scheduler. Creating and joining one on Linux costs on the order of 10 microseconds (9 µs on an Intel Skylake server and 20 µs on AMD Rome in Lemire's measurement^[15]). Each one reserves address space for its stack (1 MiB by default on Windows, 8 MiB with a typical Linux default), and once you have more threads than cores, the kernel has to context-switch between them, which costs on the order of a microsecond per switch, more once you count the cache pollution that follows. So you want few threads.

A task (or job) is a unit of work: a function and its inputs. Creating one costs little more than filling in a small struct, so you can afford many tasks.

Unity's manual states it directly: the job system "ensures that there are only enough threads to match the capacity of the CPU cores"^[8]. Naughty Dog runs six worker threads on PS4, pinned one per core, and then puts a hundred and sixty fibers on top of them to hold the work^[2]. Both engines are following the same rule.

In our scheduler:

We reserve one logical core for the main thread and the OS. Everything else becomes a worker. On an 8-core machine that's 7 worker threads plus the main thread, so 8 threads total but only 7 of them are dedicated to jobs.

Once you separate the two concepts, a few other things become obvious. Tasks are cheap to make, so you should make a lot of them: granularity matters, and we'll quantify it in §7. Tasks don't need their own stack: they borrow the worker's stack while they run, so a task can fit in a few dozen bytes (Molecular Matters sizes its jobs to one 64-byte cache line^[7]) instead of a megabyte.

05Cache lines and the false-sharing trap

When a multi-core program runs slower than the single-core version, common causes are lock contention, oversubscription, memory bandwidth, and false sharing. False sharing is one of the more surprising of these, and one of the easier ones to fix once you know the shape.

Caches don't fetch one byte at a time. They fetch a whole cache line, typically 64 bytes on x86-64 (Intel and AMD, including the Zen 2 silicon in the PS5 and Xbox Series X) and 128 bytes on Apple's M-series chips^[12]. Two variables that sit within 64 bytes of each other can end up on the same cache line. Now imagine two threads, each writing to one of those variables. The variables are independent, but the cache line is one unit, and the cache-coherence protocol (a MESI variant on x86) tracks ownership per line^[13]:

1. Core 0 writes to variable a. The line is loaded into Core 0's L1, marked as Modified.
2. Core 1 wants to write to variable b. The line is in Core 0's L1, so Core 1 has to invalidate Core 0's copy, then pull the line over to its own L1.
3. Core 0 writes a again, so the line moves back to Core 0's L1.
4. This repeats for as long as both threads keep writing.

The line pings between the cores' caches even though the data they touch is logically independent. Hence "false sharing": the sharing looks like sharing only to the cache, not to the programmer.

Run the demo. The top row has two counters packed adjacently in a struct; both threads write to it. The bottom row has the same counters, padded to live on separate cache lines. Same code, same workload, different memory layout:

The fix

Make sure data that is touched by different threads sits on different cache lines. In C++17 the standard provides a portable constant for the right alignment:

// std::hardware_destructive_interference_size (in <new>) is the implementation's
// recommended minimum offset between two concurrently written objects.
// It's the toolchain's pick: 64 on x86-64. GCC's generic AArch64 value is 256,
// to cover every Arm line size (Apple Silicon's lines are 128 bytes).
constexpr size_t cacheLineBytes = std::hardware_destructive_interference_size;

// Per-worker statistics, one instance per worker. The owner bumps
// jobsCompleted; a thief bumps jobsStolen when it takes one of this worker's
// jobs, so the two counters are written from different cores.
struct WorkerStats {
  // alignas tells the compiler to start this member on a fresh cache line,
  // inserting padding bytes before it if needed. It also raises the struct's
  // alignment, so neighbouring workers' stats in an array never share a line.
  alignas(cacheLineBytes) std::atomic<int64_t> jobsCompleted;

  // This counter lives on its own cache line too, so a thief's writes
  // here don't invalidate the owner's copy of jobsCompleted.
  alignas(cacheLineBytes) std::atomic<int64_t> jobsStolen;
};
// sizeof(WorkerStats) is now 128 bytes on x86, not 16: a little memory per
// worker to keep two cores from fighting over one line on the hot path.

The alignas declaration tells the compiler to start each member on a fresh cache line, padding with empty bytes if necessary. It costs memory: a struct that "should" be 16 bytes grows to 128. On a hot path that two cores write, those bytes are cheap next to the coherence traffic they remove. One caveat is heap allocation: before C++17, new and std::allocator didn't honor alignments above alignof(std::max_align_t) (usually 16), so a heap array of these structs could still straddle lines. C++17's aligned new fixed that.

06Lock-free queues

Now we go back to the queue. We have N workers and we want them to push and pop concurrently without a mutex. The phrase to look up is lock-free queue: a queue built from atomic read-modify-write operations such as compare-and-swap (CAS) instead of locks, with the guarantee that a stalled thread can't stop the others from making progress. Done right, multiple workers make progress simultaneously instead of serializing through a critical section. Production examples include moodycamel's ConcurrentQueue^[42].

The classic design is Dmitry Vyukov's bounded MPMC queue^[16]: a fixed-size array where each slot has a sequence counter, and one CAS per enqueue or dequeue. Vyukov notes it is "not lockfree in the official meaning" (a stalled producer can block consumers waiting on that specific slot), but it is widely used, Rust's crossbeam ArrayQueue among others, because the fast path touches two cache lines and takes no lock.

Each slot tracks its own version (the sequence number). Producers race for the slot whose sequence equals the current tail. Whoever wins the CAS writes the payload and bumps the sequence to mark the slot full; whoever loses gets the new tail back from its failed CAS and tries the next slot. Consumers race symmetrically on the head.

Run the queue below. Producers (purple) push payloads; consumers (green) pull them. Sequence numbers on each slot flip from "ready to write" to "ready to read" and back:

An MPMC queue is the right structure when you have a true many-to-many relationship. In a job system you mostly don't. The usual pattern:

• One queue (a deque, really) per worker thread.
• The owning worker is the only producer and almost always the only consumer.
• Other workers occasionally steal from the deque when they run out of their own work.

That structure is a work-stealing deque; the Chase-Lev deque is the standard lock-free implementation, and it's the topic of the next section. The MPMC queue earns its keep in the global submission path (the main thread handing top-level work to the scheduler) where many threads might be producers and the cost of contention is amortized over a coarse-grained event.

07Work stealing

A single global queue, even a lock-free one, is still one contention point for N workers. Bitsquid shipped exactly that and argued it was fine at their granularity (at most 5 × thread-count tasks per heavy job) until core counts passed about 32^[41]. As jobs get smaller and cores more numerous, the alternative is a queue per worker.

That works fine when the work is balanced. It falls apart the moment one worker finishes early and the others are still backed up: worker A is idle, worker B has a queue of fifty jobs, and they can't help each other. We need a way for idle workers to pull work from busy ones.

Work stealing, the strategy Cilk put on a provable footing in 1995^[5], solves this by making the per-worker queue a deque with asymmetric access:

• The owner pushes and pops at the bottom of its deque. This is the fast path; almost always uncontended.
• A thief (another worker that ran out of work) steals from the top. This is the slow path; contention here is rare but it still has to be correct.

Owner operations are LIFO (last-in, first-out), which keeps a worker's hot data in its L1. Thief operations are FIFO (first-in, first-out), which tends to grab older, larger jobs that are more likely to contain further sub-work for the thief to subsume. The standard lock-free implementation is the Chase-Lev deque^[6]. The original paper assumes sequential consistency; Lê et al. (2013) give C11 memory orderings for it, proven correct on ARM and POWER, and that is the version to implement^[18].

The widget shows the steals as they happen:

The "work-first" principle

Frigo, Leiserson, and Randall's PLDI 1998 paper on the Cilk-5 scheduler^[19] articulates the design principle that makes work-stealing schedulers fast, not just correct: optimize the path where no stealing happens. They call this the work-first principle. Since steals are rare in a well-balanced computation, the common case is "owner pops a job from its own deque and runs it." That path should cost something close to a function call.

Concretely, in our scheduler:

• The owner's push is a plain store into the slot plus a release store of the bottom index; no read-modify-write. Its pop writes the bottom index, then needs one full seq_cst fence before reading the top (store-then-load is the one reordering even x86 allows), and a CAS only when it races a thief for the last element.
• The thief's steal is a single CAS on the top counter.
• The deque storage is owned by one worker (no cross-thread allocation in the fast path).

An uncontended push costs about as much as a couple of ordinary stores; an uncontended pop adds the full fence, on the order of tens of cycles on x86. A steal costs more because its CAS has to pull the top counter's cache line from another core, typically on the order of a hundred cycles or more. As long as steals are a small fraction of operations, the fast path dominates the average. Reinalter's Molecular Matters series^[7] walks through a complete C++ implementation with timings; it's worth reading after this section.

How granular is granular?

One question that comes up every time you build a work-stealing scheduler: how big should each job be? Too small and you spend more time managing the queue than running the work. Too big and you can't load-balance because there aren't enough jobs to steal.

The Cilk-5 paper's design principle is that the spawn fast-path should cost only a small multiple of an ordinary function call so that spawn overhead doesn't dominate the work. The practical version: each job should do at least one to two orders of magnitude more work than your queue operations take. If push/pop is around 10 ns, aim for at least 1 µs of work per job. At that ratio, a 16.6 ms frame can schedule on the order of ten thousand jobs without spending serious time on the queue itself; Naughty Dog reported roughly 800 to 1,000 jobs per frame in The Last of Us Remastered^[2]. Unity's documentation points the same way: a batchSize of 32 to 128 for cheap per-element work, and as low as 1 when each element is expensive^[8].

08Dependencies as a DAG

Real frame work has structure. Visibility culling has to finish before draw-call building can start. Animation has to finish before skinning. Audio listener position depends on the player's transform, which is updated by gameplay. The graph of which job depends on which is a directed acyclic graph (DAG), and a real scheduler has to honor it.

A sketch of a typical frame's job graph (the same graph as the "typical frame" preset in the demo further down):

The graph fans out early. A fixed-thread design runs each box on its assigned thread, so ready boxes that share a thread wait for each other; a job system can run every ready box on any free core.

Three ways to express dependencies

Different engines pick different syntax for the same idea. The mechanics map onto a small handful of primitives:

1. Counters (Naughty Dog). Each job decrements a shared atomic counter when it finishes. A waiting job parks its fiber until the counter reaches the value it waits for, usually zero^[2]. The counter is the dependency primitive, and waiting is explicit in the job's code.
2. Handles (Unity). Every Schedule() call returns a JobHandle. You pass it into the next Schedule() call as a dependency, or combine several handles with JobHandle.CombineDependencies(a, b, c). The scheduler tracks the resulting DAG and runs each job once its predecessors complete^[8].
3. Continuations (Unreal Tasks, C++26 senders). Each task carries a list of prerequisite tasks. When a prerequisite completes, it decrements a counter on its dependents; whichever decrements to zero gets enqueued. Expressed this way, no worker blocks waiting for a prerequisite^[9].

Handles and continuations come down to the same bookkeeping: each task counts its unresolved prerequisites, each finishing prerequisite decrements its dependents' counts, and whichever count reaches zero is enqueued. Naughty Dog's counters invert it: the waiter parks on a count of outstanding jobs, which is affordable because a parked fiber doesn't tie up a worker (§9).

In code, the heart of a dependency-tracking scheduler is about a dozen lines:

// A Task is a node in the dependency DAG. Three fields:
//   1. The callable to run (its "body").
//   2. How many holds still keep it from running.
//   3. Which other tasks are waiting on this one.
struct Task {
  std::function<void()>   body;
  std::atomic<int>        openHolds;    // unfinished prereqs + 1 (the builder's)
  std::vector<Task*>      dependents;   // who depends on us
};

// Drops one hold. fetch_sub returns the value BEFORE the decrement, so a
// return of 1 means this call took the count to 0. Exactly one caller (the
// builder or the last prereq to finish) sees that, and only it enqueues.
void releaseHold(Task* task) {
  if (task->openHolds.fetch_sub(1, std::memory_order_acq_rel) == 1)
    pushToReadyQueue(task);             // nothing left to wait for: run it
}

// Contract: the builder creates every task with openHolds = (its prereq
// count) + 1 and fills in every dependents list first, then calls this once
// per task. The extra hold stops a fast prereq from releasing a task twice.
void submitWhenReady(Task* task) {
  releaseHold(task);                    // drop the builder's hold
}

// A worker calls this when it pops a task from a queue.
void runTask(Task* task) {
  task->body();                         // the actual work
  // acq_rel: the release half publishes this body's writes, and the acquire
  // half lets the last decrementer see every prereq's writes.
  for (Task* dependent : task->dependents)
    releaseHold(dependent);
}

Three fields per task and three short functions. The extra builder hold matters: without it, a prerequisite that finishes while the graph is still being wired can release a dependent early, or release it twice. §10 adds the worker pool, the work-stealing deques, and a small lock per task so a task can be linked to a prerequisite that is already running.

Build a small graph and run it through the scheduler:

09Fibers and why Naughty Dog uses them

So far our scheduler is built on threads alone. There's a problem with that model, and it shows up the first time you write a job that wants to wait for another job to finish in the middle of its own work.

Imagine a job that builds a draw list. Halfway through, it needs the result of a culling job that's currently running on another worker. What should it do?

• Block on a condition variable. The worker sits idle waiting for the culling job, even though the queue is full of other work, so its core is wasted.
• Spin-wait. The worker burns CPU (and its SMT sibling's share of the core) watching a flag, which wastes the core just as thoroughly.
• Run other jobs while waiting. The worker pops and runs other jobs until the counter clears; Molecular Matters' Wait() works this way^[7], as does §10's wait(). The core stays busy, but the waiting job's frame stays underneath whatever runs on top of it, so it can't resume until that nested work unwinds, and deep nesting can overflow the stack.
• Use continuation-passing. Restructure the draw-list job into two jobs: the part before the wait, and a continuation that runs when culling finishes. Works, but it's invasive to the caller and you can't suspend in the middle of a complex function.

None of those is what Naughty Dog reached for. They wanted to write code like this:

void buildDrawList() {
  prepareCommandBuffer();
  JobCounter* cullingDone = scheduleCulling();
  waitForCounter(cullingDone, 0);   // reads like a blocking wait; with fibers it isn't
  encodeVisibleObjects();
}

"Wait for the counter" looks blocking, but they wanted it to not waste the worker. Their answer was fibers: lightweight user-mode threads that you switch by hand, in user space, with no kernel involvement.

What is a fiber

A fiber is a stack and a saved register state. Switching from fiber A to fiber B means: save A's CPU registers onto A's stack, load B's registers from B's stack, jump to where B was suspended. The OS doesn't know. With hand-written assembly, the switch is on the order of tens of cycles; Boost.Fiber documents "less than a hundred"^[23]. Compare a thread context switch, which crosses the user-kernel boundary and costs roughly a microsecond, more once you count the TLB and cache penalty on wake-up.

On Windows, fibers are an OS API (ConvertThreadToFiber, CreateFiber, SwitchToFiber), implemented in user mode: the kernel doesn't schedule them^[21]. Elsewhere you can use Boost.Context (mostly hand-written assembly per ABI) or write the switch yourself in a few dozen lines of assembly per platform. Marl, Google's open-source job system^[22], has implementations for x86, x64, aarch64, mips, ppc, riscv, and more in its osfiber_asm_*.S files.

The Naughty Dog architecture

Putting it all together, Gyrling's GDC 2015 talk describes:

• 6 worker threads, pinned one per PS4 core. The threads are the execution units.
• 160 fibers total: 128 with 64 KiB stacks for ordinary jobs, 32 with 512 KiB stacks for jobs that need more stack.
• 3 priority queues (low, normal, high). No work-stealing in the classical Cilk sense; the queues are global.
• Atomic counters are the synchronization primitive. waitForCounter(n) doesn't block the worker; it parks the current fiber on the counter and switches to another fiber. When the counter drops to n, the parked fiber becomes runnable again^[2].

The result is that jobs can wait inline, in normal-looking code, without wasting workers: a worker waiting on a job never blocks on an OS primitive; it switches fibers.

Step through a fiber switch:

Fibers versus C++20 coroutines

A natural question in 2026: why not C++20 coroutines instead of fibers? The two differ in where the suspended state lives.

• Stackful (fibers). Each fiber has a real stack of fixed size. Any function can suspend the fiber, no matter how deep. Switching is fast but the stack is allocated up front^[23].
• Stackless (C++20 coroutines). The compiler transforms the coroutine function into a state machine. Only that function can suspend; if you want a callee to suspend, you have to mark it a coroutine too, and so on up the chain. Each coroutine frame holds only the state that lives across a suspension point, and it is heap-allocated unless the compiler can elide the allocation.

For a game engine job system, the choice usually comes down to: do you want to be able to call waitForCounter() from anywhere in a job's call stack? Fibers say yes; coroutines say only from coroutine-marked frames. Naughty Dog's engine, FiberTaskingLib and Marl use fibers for this reason: engines have a lot of code that wasn't written with suspension in mind, and making every frame on the path a coroutine is invasive.

10A working scheduler, in your language

Below is a complete, working scheduler in two languages: modern C++ (20) and Rust. The C++ version is about 230 lines and uses no dependencies beyond the standard library; the Rust version is about 190 lines, also stdlib-only. Both implement the same design: a fixed pool of OS-thread workers, a work-stealing deque per worker, an injection queue for tasks submitted from other threads, dependency tracking with the hold counts from §8, and a wait() that runs tasks until everything submitted has finished. Idle workers sleep on a condition variable. There are no fibers; the callout below lists what else is left out. The C++ deque is the lock-free bounded Chase-Lev design with Lê et al.'s orderings; the Rust deque keeps a mutex per worker for brevity (crossbeam-deque is the lock-free equivalent).

Pick a language. Read the comments; every interesting line has one.

// ───────────────────────────────────────────────────────────
// scheduler.cpp · work-stealing job system with DAG support
// Compile: g++ -std=c++20 -O2 -pthread -c scheduler.cpp
// (a library: link it with a main() like the usage notes at the end)
// ───────────────────────────────────────────────────────────
#include <algorithm>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <cstddef>
#include <cstdint>
#include <deque>
#include <functional>
#include <initializer_list>
#include <memory>
#include <mutex>
#include <random>
#include <thread>
#include <vector>

namespace mpg {

// 64 bytes is the x86 line size. It's hardcoded because GCC warns when
// std::hardware_destructive_interference_size appears in a header (its
// value can change with -mtune). Apple Silicon lines are 128 bytes.
constexpr std::size_t kCacheLine = 64;

struct Task {
  std::function<void()> body;
  // Starts at 1: the submitter's own hold, dropped at the end of submit(),
  // so no prerequisite can release the task while submit() is still linking it.
  std::atomic<int>      openPrereqs{1};
  std::mutex            dependentsLock;  // guards dependents and done together
  std::vector<Task*>    dependents;      // tasks waiting on this one
  bool                  done = false;    // set once, under dependentsLock
};

// A bounded ring-buffer deque, owned by one worker.
// Owner pushes/pops at bottom; thieves CAS-steal at top.
// Orderings follow Lê et al.'s C11 Chase-Lev deque, minus the resizing.
class Deque {
  static constexpr std::int64_t kCapacity = 1024;             // per worker
  alignas(kCacheLine) std::atomic<std::int64_t> top{0};       // thieves CAS it
  alignas(kCacheLine) std::atomic<std::int64_t> bottom{0};    // only the owner writes it
  // Atomic slots: a slow thief can read a slot the owner is refilling after
  // a wraparound. Its CAS then fails, but the read must not be a data race.
  alignas(kCacheLine) std::atomic<Task*> buffer[kCapacity]{};
public:
  bool push(Task* task) {                                      // owner only
    std::int64_t bottomIndex = bottom.load(std::memory_order_relaxed);
    std::int64_t topIndex = top.load(std::memory_order_acquire);
    if (bottomIndex - topIndex >= kCapacity) return false;     // full
    buffer[bottomIndex % kCapacity].store(task, std::memory_order_relaxed);
    // Release: a thief whose acquire load sees the new bottom also sees the
    // slot, and everything the submitter wrote into *task before pushing it.
    bottom.store(bottomIndex + 1, std::memory_order_release);
    return true;
  }

  Task* popOwner() {                                           // owner only: the fast path
    std::int64_t bottomIndex = bottom.load(std::memory_order_relaxed) - 1;
    bottom.store(bottomIndex, std::memory_order_relaxed);       // reserve the bottom slot
    // Full fence: thieves must see the reservation before we read top, or
    // the owner and a thief could both take the last task. Store-then-load
    // is the one reordering x86 allows, so this is a real MFENCE even there.
    std::atomic_thread_fence(std::memory_order_seq_cst);
    std::int64_t topIndex = top.load(std::memory_order_relaxed);
    if (topIndex > bottomIndex) {                               // empty: undo the reservation
      bottom.store(bottomIndex + 1, std::memory_order_relaxed);
      return nullptr;
    }
    Task* task = buffer[bottomIndex % kCapacity].load(std::memory_order_relaxed);
    if (topIndex != bottomIndex) return task;                   // 2+ left: no thief can reach this one
    // Last task: race any thief for it with the same CAS a thief uses.
    bool won = top.compare_exchange_strong(topIndex, topIndex + 1,
        std::memory_order_seq_cst, std::memory_order_relaxed);
    bottom.store(bottomIndex + 1, std::memory_order_relaxed);   // empty either way
    return won ? task : nullptr;
  }

  Task* steal() {                                              // other threads: the slow path
    std::int64_t topIndex = top.load(std::memory_order_acquire);
    // Pairs with the fence in popOwner(): read top before bottom.
    std::atomic_thread_fence(std::memory_order_seq_cst);
    std::int64_t bottomIndex = bottom.load(std::memory_order_acquire);
    if (topIndex >= bottomIndex) return nullptr;                // empty
    Task* task = buffer[topIndex % kCapacity].load(std::memory_order_relaxed);
    // Claim slot topIndex. Failure means the owner or another thief got it.
    if (!top.compare_exchange_strong(topIndex, topIndex + 1,
            std::memory_order_seq_cst, std::memory_order_relaxed))
      return nullptr;
    return task;
  }
};

class Scheduler {
  std::vector<std::unique_ptr<Deque>> deques;       // one per worker
  std::vector<std::thread>            workers;
  // Only a deque's owner may push to it, so tasks submitted from other
  // threads (the main thread) go here instead. A mutex is fine on this
  // coarse path; a Vyukov MPMC queue (§6) is the lock-free swap-in.
  std::mutex                          injectLock;
  std::deque<Task*>                   injectQueue;
  std::atomic<bool>                   running{true};
  std::atomic<int>                    inFlight{0};  // submitted, not yet finished
  std::mutex                          sleepLock;
  std::condition_variable             wakeSignal;

  // Which scheduler and deque this thread works for; null / -1 elsewhere.
  static thread_local const Scheduler* workerOwner;
  static thread_local int              workerIndex;

public:
  explicit Scheduler(int workerCount = -1) {
    if (workerCount < 0)   // eq. 1: leave one core for the main thread and the OS
      workerCount = std::max(1, (int)std::thread::hardware_concurrency() - 1);
    for (int i = 0; i < workerCount; i++) deques.push_back(std::make_unique<Deque>());
    for (int i = 0; i < workerCount; i++) workers.emplace_back([this, i] { workerLoop(i); });
  }

  ~Scheduler() {                   // call wait() first: workers don't drain on exit
    running.store(false, std::memory_order_release);
    wakeSignal.notify_all();
    for (std::thread& worker : workers) worker.join();
  }

  // Create a task that runs after every task in prereqs, which may still be
  // queued or running. The caller owns the result; delete it after wait().
  Task* submit(std::function<void()> body, std::initializer_list<Task*> prereqs = {}) {
    Task* task = new Task();
    task->body = std::move(body);
    inFlight.fetch_add(1, std::memory_order_relaxed);
    for (Task* prereq : prereqs) {
      // Checking done and linking happen under one lock, so the prereq
      // can't finish in between and miss this dependent.
      std::lock_guard lock(prereq->dependentsLock);
      if (!prereq->done) {
        task->openPrereqs.fetch_add(1, std::memory_order_relaxed);
        prereq->dependents.push_back(task);
      }
    }
    releaseHold(task);             // drop the submitter's hold
    return task;
  }

  void wait() {                    // help run tasks until everything submitted finished
    while (inFlight.load(std::memory_order_acquire) > 0) {
      if (Task* task = findWork(-1)) runTask(task);
      else std::this_thread::yield();
    }
  }

private:
  // Every hold (the submitter's, one per unfinished prereq) is dropped once.
  // Exactly one caller sees the count go 1 -> 0, and only that one enqueues.
  void releaseHold(Task* task) {
    if (task->openPrereqs.fetch_sub(1, std::memory_order_acq_rel) == 1) enqueue(task);
  }

  void enqueue(Task* task) {
    // A worker pushes onto its own deque (LIFO, cache-hot). Other threads,
    // and a worker whose deque is full, use the injection queue.
    bool ownDeque = workerOwner == this && deques[workerIndex]->push(task);
    if (!ownDeque) {
      std::lock_guard lock(injectLock);
      injectQueue.push_back(task);
    }
    wakeSignal.notify_one();
  }

  Task* findWork(int myIndex) {
    if (myIndex >= 0)
      if (Task* task = deques[myIndex]->popOwner()) return task;   // own work first
    {
      std::lock_guard lock(injectLock);
      if (!injectQueue.empty()) {
        Task* task = injectQueue.front();
        injectQueue.pop_front();
        return task;
      }
    }
    // Random victims spread thieves out instead of piling onto one deque.
    thread_local std::mt19937 rng{std::random_device{}()};
    std::uniform_int_distribution<int> pickVictim(0, (int)deques.size() - 1);
    for (int attempt = 0; attempt < (int)deques.size() * 2; attempt++) {
      int victim = pickVictim(rng);
      if (victim == myIndex) continue;
      if (Task* task = deques[victim]->steal()) return task;
    }
    return nullptr;
  }

  void runTask(Task* task) {
    task->body();
    {
      std::lock_guard lock(task->dependentsLock);
      task->done = true;           // from here on, submit() won't link to us
    }
    // done is set, so nothing appends to dependents any more: read it unlocked.
    for (Task* dependent : task->dependents) releaseHold(dependent);
    inFlight.fetch_sub(1, std::memory_order_acq_rel);
  }

  void workerLoop(int myIndex) {
    workerOwner = this;
    workerIndex = myIndex;
    while (running.load(std::memory_order_acquire)) {
      if (Task* task = findWork(myIndex)) { runTask(task); continue; }
      // Nothing to do: sleep until enqueue() signals. The timeout covers a
      // push that lands between findWork() failing and wait_for() starting.
      std::unique_lock lock(sleepLock);
      wakeSignal.wait_for(lock, std::chrono::microseconds(100));
    }
  }
};

thread_local const Scheduler* Scheduler::workerOwner = nullptr;
thread_local int              Scheduler::workerIndex = -1;

} // namespace mpg

// ── usage ────────────────────────────────────────────────
// mpg::Scheduler scheduler;
// auto* a = scheduler.submit([] { /* work */ });
// auto* b = scheduler.submit([] { /* work */ }, {a});  // b runs after a
// auto* c = scheduler.submit([] { /* work */ }, {a, b});
// scheduler.wait();
// delete a; delete b; delete c;   // or recycle them from a pool

// ───────────────────────────────────────────────────────────
// scheduler.rs · work-stealing job system with DAG support
// Compile: rustc -O --crate-type=lib scheduler.rs
// ───────────────────────────────────────────────────────────
use std::cell::Cell;
use std::collections::hash_map::RandomState;
use std::collections::VecDeque;
use std::hash::BuildHasher;
use std::sync::atomic::{AtomicBool, AtomicI32, Ordering};
use std::sync::{Arc, Condvar, Mutex};
use std::thread;
use std::time::Duration;

pub type Body = Box<dyn FnOnce() + Send>;

pub struct Task {
    body: Mutex<Option<Body>>,    // taken once, by whichever thread runs the task
    // Starts at 1: the submitter's own hold, dropped at the end of submit(),
    // so no prerequisite can release the task while submit() is still linking it.
    open_prereqs: AtomicI32,
    dependents: Mutex<Dependents>, // the list and the done flag, under one lock
}

struct Dependents {
    tasks: Vec<Arc<Task>>,         // tasks waiting on this one
    done: bool,                    // set once, under the lock
}

// Per-worker deque. Owner: push_back / pop_back (LIFO).
// Thief: pop_front (FIFO). A mutex per deque keeps this short; the
// lock-free Chase-Lev version is crossbeam-deque (what Rayon uses).
struct WorkerDeque {
    tasks: Mutex<VecDeque<Arc<Task>>>,
}

impl WorkerDeque {
    fn new() -> Self { Self { tasks: Mutex::new(VecDeque::new()) } }
    fn push(&self, task: Arc<Task>) { self.tasks.lock().unwrap().push_back(task); }
    fn pop_owner(&self) -> Option<Arc<Task>> { self.tasks.lock().unwrap().pop_back() }
    fn steal(&self) -> Option<Arc<Task>> { self.tasks.lock().unwrap().pop_front() }
}

// State the workers and the Scheduler handle share.
struct Shared {
    deques: Vec<WorkerDeque>,              // one per worker
    // Tasks submitted from threads that aren't workers (the main thread).
    inject_queue: Mutex<VecDeque<Arc<Task>>>,
    running: AtomicBool,
    in_flight: AtomicI32,                  // submitted, not yet finished
    sleep_lock: Mutex<()>,
    wake_signal: Condvar,
}

thread_local! {
    // Which scheduler and deque this thread works for; None elsewhere.
    static WORKER: Cell<Option<(*const Shared, usize)>> = const { Cell::new(None) };
    // xorshift state for picking steal victims, seeded per thread.
    static RNG_STATE: Cell<u64> = Cell::new(RandomState::new().hash_one(0u8) | 1);
}

fn random_below(bound: usize) -> usize {
    RNG_STATE.with(|state| {
        let mut x = state.get();
        x ^= x << 13; x ^= x >> 7; x ^= x << 17;   // xorshift64: cheap, good enough here
        state.set(x);
        (x % bound as u64) as usize
    })
}

impl Shared {
    // Every hold (the submitter's, one per unfinished prereq) is dropped once.
    // Exactly one caller sees the count go 1 -> 0, and only that one enqueues.
    fn release_hold(&self, task: Arc<Task>) {
        if task.open_prereqs.fetch_sub(1, Ordering::AcqRel) == 1 { self.enqueue(task); }
    }

    fn enqueue(&self, task: Arc<Task>) {
        // A worker pushes onto its own deque; other threads use the injection queue.
        match WORKER.with(|worker| worker.get()) {
            Some((owner, index)) if std::ptr::eq(owner, self) => self.deques[index].push(task),
            _ => self.inject_queue.lock().unwrap().push_back(task),
        }
        self.wake_signal.notify_one();
    }

    fn find_work(&self, my_index: Option<usize>) -> Option<Arc<Task>> {
        if let Some(index) = my_index {
            if let Some(task) = self.deques[index].pop_owner() { return Some(task); }  // own work first
        }
        if let Some(task) = self.inject_queue.lock().unwrap().pop_front() { return Some(task); }
        // Random victims spread thieves out instead of piling onto one deque.
        for _attempt in 0..self.deques.len() * 2 {
            let victim = random_below(self.deques.len());
            if Some(victim) == my_index { continue; }
            if let Some(task) = self.deques[victim].steal() { return Some(task); }
        }
        None
    }

    fn run_task(&self, task: Arc<Task>) {
        let body = task.body.lock().unwrap().take();
        if let Some(body) = body { body(); }
        let dependents = {
            let mut dependents = task.dependents.lock().unwrap();
            dependents.done = true;        // from here on, submit() won't link to us
            std::mem::take(&mut dependents.tasks)
        };
        for dependent in dependents { self.release_hold(dependent); }
        self.in_flight.fetch_sub(1, Ordering::AcqRel);
    }
}

pub struct Scheduler {
    shared: Arc<Shared>,
    workers: Vec<thread::JoinHandle<()>>,
}

impl Scheduler {
    pub fn new(worker_count: usize) -> Self {
        let worker_count = worker_count.max(1);
        let shared = Arc::new(Shared {
            deques: (0..worker_count).map(|_| WorkerDeque::new()).collect(),
            inject_queue: Mutex::new(VecDeque::new()),
            running: AtomicBool::new(true),
            in_flight: AtomicI32::new(0),
            sleep_lock: Mutex::new(()),
            wake_signal: Condvar::new(),
        });
        let workers = (0..worker_count)
            .map(|index| {
                let shared = Arc::clone(&shared);
                thread::spawn(move || worker_loop(&shared, index))
            })
            .collect();
        Self { shared, workers }
    }

    // Create a task that runs after every task in prereqs, which may still be
    // queued or running.
    pub fn submit(&self, body: Body, prereqs: &[Arc<Task>]) -> Arc<Task> {
        let task = Arc::new(Task {
            body: Mutex::new(Some(body)),
            open_prereqs: AtomicI32::new(1),
            dependents: Mutex::new(Dependents { tasks: Vec::new(), done: false }),
        });
        self.shared.in_flight.fetch_add(1, Ordering::Relaxed);
        for prereq in prereqs {
            // Checking done and linking happen under one lock, so the prereq
            // can't finish in between and miss this dependent.
            let mut dependents = prereq.dependents.lock().unwrap();
            if !dependents.done {
                task.open_prereqs.fetch_add(1, Ordering::Relaxed);
                dependents.tasks.push(Arc::clone(&task));
            }
        }
        self.shared.release_hold(Arc::clone(&task));   // drop the submitter's hold
        task
    }

    pub fn wait(&self) {             // help run tasks until everything submitted finished
        while self.shared.in_flight.load(Ordering::Acquire) > 0 {
            match self.shared.find_work(None) {
                Some(task) => self.shared.run_task(task),
                None => thread::yield_now(),
            }
        }
    }
}

impl Drop for Scheduler {
    fn drop(&mut self) {             // call wait() first: workers don't drain on exit
        self.shared.running.store(false, Ordering::Release);
        self.shared.wake_signal.notify_all();
        for worker in self.workers.drain(..) { let _ = worker.join(); }
    }
}

fn worker_loop(shared: &Shared, my_index: usize) {
    WORKER.with(|worker| worker.set(Some((shared as *const Shared, my_index))));
    while shared.running.load(Ordering::Acquire) {
        if let Some(task) = shared.find_work(Some(my_index)) { shared.run_task(task); continue; }
        // Nothing to do: sleep until enqueue() signals. The timeout covers a
        // push that lands between find_work() failing and wait_timeout() starting.
        let lock = shared.sleep_lock.lock().unwrap();
        let _ = shared.wake_signal.wait_timeout(lock, Duration::from_micros(100)).unwrap();
    }
}

// ── usage ────────────────────────────────────────────────
// let scheduler = Scheduler::new(7);
// let a = scheduler.submit(Box::new(|| { /* work */ }), &[]);
// let b = scheduler.submit(Box::new(|| { /* work */ }), &[a.clone()]);  // b runs after a
// let c = scheduler.submit(Box::new(|| { /* work */ }), &[a, b]);
// scheduler.wait();

11Try it yourself

The playground below runs a JavaScript model of the scheduler above: a greedy scheduler that hands each ready task to the first free worker and advances simulated time, so the timeline shows where parallelism runs out. It models the dependency tracking, not the deques or the stealing. The library is exposed as MPGJobs; you can build task graphs, run them, and see the worker timeline for the result. Hit Run (or Ctrl+Enter / Cmd+Enter) to execute. Output prints below; the worker timeline is drawn on the right.

Edit anything. Drop the worker count to 1 (a single-threaded version) and the frame stretches out. Bump it to 8 and the frame shrinks until the critical path sets the length. Try a chain of 30 dependent jobs and you'll see that adding workers doesn't help past the critical-path length.

12How Unity does it

Unity's C# job system, released in 2018, is a thin managed layer over the native job system Unity uses for its own engine code^[8]. Three pieces matter to a user of it.

The job interfaces

You implement a job by writing a struct with one method. The struct is the body; the fields are the inputs and outputs. Unity copies the struct into the scheduler, so jobs can't capture references the way a closure would.

• IJob: one unit of work, runs once on a worker.
• IJobParallelFor: N independent iterations; the scheduler picks a batch size and hands out ranges to workers.
• IJobFor: like IJobParallelFor, but the same job can run on the calling thread, sequentially on one worker, or in parallel batches.
• IJobChunk / IJobEntity: ECS-specific; iterates over archetype chunks. Used inside DOTS / Entities packages.

using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;

[BurstCompile]
struct UpdateParticles : IJobParallelFor {
    public NativeArray<float3> positions;
    [ReadOnly] public NativeArray<float3> velocities;
    public float dt;

    public void Execute(int index) {
        positions[index] += velocities[index] * dt;
    }
}

// At call site:
var job   = new UpdateParticles { positions = pos, velocities = vel, dt = 0.016f };
var handle = job.Schedule(pos.Length, 64);   // one Execute(index) per particle, batchSize=64
handle.Complete();                          // block until done; call it as late as possible

Three things to notice

1. Handles are dependencies. Schedule returns a JobHandle. Pass it into the next Schedule call to express "this depends on that." JobHandle.CombineDependencies(a, b, c) gives you a handle that's satisfied when all three are. The result is the same DAG you'd build with our prereqs array^[8].

2. The safety system catches data races at schedule time. Every NativeArray tracks which jobs read or write it. If you try to schedule a job that writes to a container that another scheduled job is also writing, Unity throws an exception with a clear message before either job runs. The AtomicSafetyHandle checks are compiled in only when ENABLE_UNITY_COLLECTIONS_CHECKS is defined, which by default means the Editor, so player builds skip them^[8]. For programmers new to multithreading this is the most useful part of the system, because it turns a race that might corrupt data silently into an exception at schedule time.

3. Burst is a separate piece. [BurstCompile] hands the job's struct to Unity's Burst compiler, which translates a restricted dialect of C# called HPC# (high-performance C#) through LLVM into target-specific machine code, vectorized where the loop allows^[24]. The Unity.Mathematics vector types (float4, float3, int4) are designed to map onto SIMD registers. The job system and Burst are orthogonal: you can use jobs without Burst, and you can Burst-compile functions that aren't jobs. In Unity 6.6 Burst moves from a package into the engine as built-in modules^[24].

13How Unreal does it

Unreal has two layered task systems, the old one and the new one, and learning Unreal multithreading in 2026 mostly means understanding which one to reach for.

TaskGraph (the legacy system)

The original Unreal task system, FTaskGraphInterface, is a job graph where each task has prerequisites and runs on either a specific named thread or "any thread." The named threads are GameThread, ActualRenderingThread, RHIThread, AudioThread, and a few others^[25]. The reason named threads exist is that many of Unreal's subsystems (UObjects, the RHI, the audio engine) are not thread-safe, so work that touches them has to be funneled onto a specific thread.

This works, but it's rigid. Once several non-thread-safe systems each need exclusive access, you either add more named threads or queue everything onto one thread and bottleneck on it. The newer API offers a third option.

UE::Tasks (the new system)

Introduced in UE 5.0 and matured through 5.3+, UE::Tasks lives in Tasks/Task.h. The model is closer to what we built in §10: launch a task, attach prerequisites, the scheduler handles the rest. Its distinctive primitive is the Pipe^[9]:

using namespace UE::Tasks;

// Independent task, no prereqs.
FTask Physics = Launch(UE_SOURCE_LOCATION, [] { DoPhysics(); });

// Dependent task: waits for Physics, then runs.
FTask Culling = Launch(UE_SOURCE_LOCATION, [] { DoCulling(); }, Physics);

// Multiple prereqs.
FTask DrawLists = Launch(UE_SOURCE_LOCATION, [] { BuildDrawLists(); },
                         Prerequisites(Physics, Culling));

// Pipe: tasks launched through the same pipe never run concurrently.
static FPipe WorldPipe{ UE_SOURCE_LOCATION };
WorldPipe.Launch(UE_SOURCE_LOCATION, [Actor1] { TickActor(Actor1); });
WorldPipe.Launch(UE_SOURCE_LOCATION, [Actor2] { TickActor(Actor2); });
// Both run on workers, but only one at a time.

A Pipe is an alternative to named-thread affinity. Instead of saying "this work has to run on the game thread because UWorld isn't thread-safe," you say "these tasks share the UWorld pipe, so never run two at once." Epic's docs note that execution order is usually predictable but launch order is not guaranteed^[9]. The scheduler can put successive pipe tasks on different worker threads as long as they don't overlap in time, which spreads load better than nailing everything to one thread.

Other Unreal pieces worth knowing

• FRunnable / FRunnableThread: a single long-lived dedicated thread. Use for streaming workers, network threads, or anything that wants its own execution forever.
• ParallelFor(N, lambda): parallel loop helper built on the task graph. Docs note it uses TaskGraph for "unbalanced tasks and offers better work distribution among threads at the cost of a little bit more synchronization"^[26].
• TPromise<T> / TFuture<T>: standard producer/consumer future-promise pair. The producer eventually calls SetValue; the consumer waits on the future.
• Render thread / RHI thread pipelining: the game thread simulates frame N+1 while the render thread builds frame N's commands, and the RHI thread translates those commands into graphics-API calls, trailing the render thread by up to a frame^[27].

14The 2026 state of the art

Three developments are worth following.

C++26 senders and receivers

In June 2024 at the WG21 St. Louis plenary, the C++ standard committee adopted std::execution (paper P2300) into the C++26 working draft^[10], and a year later added a shared parallel scheduler (P2079)^[44]. Together they give the standard library a composable model for asynchronous work and the execution resources it runs on. Briefly:

• A sender is a lazy description of an async operation. Think "a function object for sync code, but for async."
• A receiver is a bundle of callbacks: set_value, set_error, set_stopped.
• A scheduler is a factory for senders that complete on a particular execution context (CPU thread pool, GPU, custom).
• Composition is via algorithms like then, let_value, when_all and bulk; std::this_thread::sync_wait runs a sender and blocks for its result. (start_detached and ensure_started were removed before adoption in favor of async scopes.)

namespace ex = std::execution;

// C++26's shared thread pool (P2079). With stdexec today, use
// exec::static_thread_pool and its get_scheduler() instead.
auto scheduler = ex::get_parallel_scheduler();

auto physics   = ex::schedule(scheduler) | ex::then([] { return runPhysics(); });
auto animation = ex::schedule(scheduler) | ex::then([] { return runAnimation(); });
auto render    = ex::when_all(std::move(physics), std::move(animation))
               | ex::then([](auto&& physicsResult, auto&& animationResult) {
                   buildDrawLists(physicsResult, animationResult);
                 });

std::this_thread::sync_wait(std::move(render));   // start the graph, block until done

NVIDIA's stdexec is the reference implementation and you can use it today^[29]. The CUDA scheduler in the same repo shows the design's intended payoff: the same sender pipeline can target a CPU thread pool or a GPU by swapping the scheduler. Whether engines adopt it is a separate question, but the vocabulary is now standard, so library authors can write portable async code without shipping their own runtime.

Structured concurrency

Nathaniel Smith's 2018 essay "Notes on structured concurrency"^[30] argued that unconstrained spawn (or go, or async) primitives are the concurrency analog of goto: they leak control flow out of lexical scope, making cancellation, error propagation, and resource cleanup intractable. The alternative, first built in Smith's own Trio library for Python, is a "nursery": a scope that owns a set of child tasks and cannot exit until all of them complete. Kotlin coroutines and Swift concurrency adopted the same model, and C++'s senders/receivers design is built around it. For job systems, the practical impact is: an exception thrown by a leaf job propagates cleanly back to its parent, and cancellation of the parent cancels every child. Both are surprisingly hard to get right with raw thread pools.

GPU work graphs

The same idea is now appearing on the GPU. D3D12 work graphs, shown at GDC 2024^[31], let a shader enqueue more shader work directly, as a graph of nodes, without a round trip to the CPU; the GPU schedules the nodes itself.

15Pitfalls and how to spot them

Failure modes that turn up in real job systems, what they look like, and how to fix them.

The ABA problem

A thread reads value A from a CAS slot, gets preempted, returns to find the slot still says A, and CASes successfully. But while it was away, the value went from A to B and back to A; the slot is no longer the same object, even though the CAS thinks it is^[32]. The classic fix is a tag or stamp packed next to the pointer (spare high bits, or a double-width CAS), so two A's a million operations apart are distinguishable. The tag stops the false match but not the read of a freed node's next pointer beforehand, so production stacks pair it with a reclamation scheme such as hazard pointers, RCU, or epoch-based reclamation, or with a node pool that never returns memory to the OS. The Lock-free Queues tutorial walks through the reclamation side.

Spin-loop pitfalls

Don't busy-spin on an atomic without telling the CPU. A tight while (!flag) burns power, starves the SMT sibling, and on Intel cores the exit from the loop triggers a memory-order pipeline flush. Use _mm_pause() on x86 (or __builtin_ia32_pause(), YieldProcessor()) which emits the PAUSE instruction^[33]. On ARM use __yield(). If you spin for more than a few microseconds, fall back to sleeping on a futex or event-count primitive.

// Pattern: spin briefly with PAUSE, then fall back to sleeping.
// Spinning pays off when the flag usually flips within a few
// microseconds; past that, the spinning core is wasted.
auto startTime = std::chrono::steady_clock::now();
while (!readyFlag.load(std::memory_order_acquire)) {
  // PAUSE marks this as a spin loop: the CPU hands execution resources to
  // the SMT sibling and avoids a pipeline flush when the wait ends. Its
  // latency varies widely across microarchitectures, so bound the spin by time.
  for (int spins = 0; spins < 64; spins++)
    _mm_pause();

  // Spun too long: give up the core. Park the current fiber on the flag
  // (in a fiber-aware scheduler) or sleep on a futex/event-count primitive.
  auto elapsedMicros = std::chrono::duration_cast<std::chrono::microseconds>(
      std::chrono::steady_clock::now() - startTime).count();
  if (elapsedMicros > 10) {
    parkFiberOrSleepUntilSet(readyFlag);   // returns once readyFlag is set
    return;
  }
}

Priority inversion

A high-priority task is blocked by a resource held by a low-priority task, while a medium-priority task preempts the low one, indefinitely delaying the high one^[34]. The Mars Pathfinder mission hit this in 1997. The fix is priority inheritance (boost the holder's priority while the high-priority task waits) or avoiding long lock-holds. In a job system the same shape appears without any mutex: a high-priority job waits on a counter that low-priority jobs must decrement, while a stream of normal-priority jobs keeps every worker busy. Common fixes are to raise the priority of the jobs a waiter depends on, or to have workers pull from lower-priority queues now and then so nothing starves.

Memory ordering bugs

The worst kind: code that looks right on x86 because x86 is total-store-order and forgives most ordering mistakes, but fails on ARM once you ship to a Switch or a phone. Russ Cox's "Hardware Memory Models" essay^[35] is a clear walkthrough of why x86 forgives and ARM doesn't. Test on weak hardware, and run TSan, which catches data races, including the ones a missing acquire/release causes on ordinary data. When in doubt, use seq_cst and measure; you can relax later if the measurement says it matters.

Hyperthreading surprise

Two SMT siblings share one core's L1 cache, execution units and TLB, and split its store buffer. Two threads that each saturate the same resources get far less than twice one thread's throughput from sharing a core, and in bad cases (cache thrashing) less than one thread alone^[36]. If your engine has eight worker threads and the box has eight physical / sixteen logical cores, prefer to pin to physical cores when possible. Treat the SMT siblings as a bonus lane for asymmetric work (audio next to render is usually fine; two render workers on the same core is usually not).

16Where to go from here

You now have a code-level picture of what a job system is and why most modern engines have one. The next step is reading other people's code: shipped schedulers make different trade-offs, and reading a few builds the instincts.

Read these libraries

• EnkiTS: Doug Binks's zlib-licensed task scheduler in plain C++^[37]. Compact, with no fibers; a readable small example of a production scheduler.
• Marl: Google's hybrid thread + fiber scheduler^[22]. Hand-written fiber switches for eight CPU architectures, plus work stealing.
• FiberTaskingLib: an explicit reimplementation of the Naughty Dog design^[38]. Reading this is the easiest way to understand the Gyrling talk.
• Intel GTS: Intel's Games Task Scheduler^[39]. Optimized for game workloads, with detailed documentation of design choices.
• NVIDIA stdexec: the reference C++26 senders/receivers implementation^[29].

Read these papers

• Blumofe and Leiserson, Scheduling Multithreaded Computations by Work Stealing^[20]. The mathematical foundation.
• Chase and Lev, Dynamic Circular Work-Stealing Deque^[6]. The data structure.
• Lê, Pop, Cohen, Zappa Nardelli, Correct and Efficient Work-Stealing for Weak Memory Models^[18]. The version you'd actually ship.
• Frigo, Leiserson, Randall, The Implementation of the Cilk-5 Multithreaded Language^[19]. The work-first principle.

Talks

• Gyrling, Parallelizing the Naughty Dog Engine Using Fibers, GDC 2015^[2]. The canonical AAA reference.
• Tatarchuk, Destiny's Multithreaded Rendering Architecture, GDC 2015^[3]. The companion case study.
• Parent, Better Code: Concurrency, code::dive 2016^[40]. The C++ futures-and-channels mindset.
• Stevens, How to Benefit from Multithreading in Your Unreal Engine Projects, Unreal Fest Gold Coast 2024^[28]. The recent Epic perspective.

The final exam

Five questions covering the whole tutorial. If you can answer all five without scrolling back, you've got the fundamentals.

17Sources & further reading

Numbered citations refer to the superscripts above. Most entries are freely available on the open web; the rest are on the GDC Vault or the ACM Digital Library.

1. Albrecht, T. (2009). Pitfalls of Object-Oriented Programming. Game Connect: Asia Pacific. PDF. The canonical primary source for data-oriented design.
2. Gyrling, C. (2015). Parallelizing the Naughty Dog Engine Using Fibers. GDC. GDC Vault, slides PDF. The defining fiber-based job-system talk.
3. Tatarchuk, N. (2015). Destiny's Multithreaded Rendering Architecture. GDC. GDC Vault (abstract: "to optimally take advantage of all available resources, a game engine must be designed from the ground up for job-based multithreading"), slides with notes (Halo: Reach's thread-per-system design and its load-balancing problems).
4. Genova, B. (2015). Multithreading the Entire Destiny Engine. GDC. GDC Vault. The Bungie engine-side companion talk.
5. Blumofe, R. D., Joerg, C. F., Kuszmaul, B. C., Leiserson, C. E., Randall, K. H., & Zhou, Y. (1995). Cilk: An Efficient Multithreaded Runtime System. PPoPP. ACM DL. An early efficient work-stealing runtime with a provable performance model.
6. Chase, D., & Lev, Y. (2005). Dynamic Circular Work-Stealing Deque. SPAA. doi.org; PDF (archived). The lock-free growable work-stealing deque behind Java's ForkJoinPool and crossbeam-deque.
7. Reinalter, S. (2015–2016). Job System 2.0: Lock-Free Work Stealing. Molecular Musings blog. Part 1, Part 2, Part 3, Part 4, Part 5. A complete worked C++ implementation.
8. Unity Technologies. Job System Overview / Unity Manual. Unity 6.3. docs.unity3d.com. Also: IJobParallelFor (batch sizes), AtomicSafetyHandle (the ENABLE_UNITY_COLLECTIONS_CHECKS safety checks), Entities job scheduling.
9. Epic Games. Tasks System in Unreal Engine. UE 5.7. dev.epicgames.com. Plus the Launch API.
10. Dominiak, M., Baker, L., Howes, L., Shoop, K., Garland, M., Niebler, E., & Adelstein Lelbach, B. (2024). P2300R10 std::execution. WG21 paper, adopted into C++26 at the St. Louis plenary, 29 June 2024. wg21.link.
11. Andersson, J. (2010). Parallel Futures of a Game Engine (v2.0). Stockholm Game Developer Forum. SlideShare. DICE's Frostbite engine job-graph design.
12. Lemire, D. (2023). Measuring the size of the cache line empirically. lemire.me. 64 B on x86-64, 128 B on Apple M-series.
13. Wikipedia. False sharing. en.wikipedia.org. "If any data in a cache line is modified, the entire cache line must be synchronized."
14. alic.dev (2023). The False Sharing Penalty. alic.dev/blog/false-sharing. Packed versus padded per-producer indices in an MPSC queue on Apple M1 Pro, Intel i5-9600K, AMD EPYC and Intel Cascade Lake; the packed layout loses on every platform.
15. Lemire, D. (2020). Cost of a thread in C++ under Linux. lemire.me. Creating and joining a thread: about 9 µs on a Skylake server, 20 µs on AMD Rome, 200 µs on an Ampere ARM server.
16. Vyukov, D. Bounded MPMC queue. 1024cores. 1024cores (sites.google.com). The reference MPMC design: one CAS per operation, and "not lockfree in the official meaning."
17. Preshing, J. (2012). Acquire and Release Semantics. preshing.com. The canonical practitioner explanation of memory ordering.
18. Lê, N. M., Pop, A., Cohen, A., & Zappa Nardelli, F. (2013). Correct and Efficient Work-Stealing for Weak Memory Models. PPoPP. PDF. The version of Chase-Lev that's correct on ARM and POWER.
19. Frigo, M., Leiserson, C. E., & Randall, K. H. (1998). The Implementation of the Cilk-5 Multithreaded Language. PLDI. PDF. The work-first principle.
20. Blumofe, R. D., & Leiserson, C. E. (1999). Scheduling Multithreaded Computations by Work Stealing. J. ACM. PDF. Proves randomized work stealing runs fully strict computations in expected time T₁/P + O(T∞), within a constant factor of optimal.
21. Microsoft. Fibers (Win32). Microsoft Learn. learn.microsoft.com.
22. Google. Marl: a hybrid thread / fiber task scheduler written in C++ 11. GitHub: github.com/google/marl. Cross-platform fiber implementation.
23. Stackless vs. stackful coroutines. Primary references: cppreference (C++20 coroutines); the Boost.Fiber overview at boost.org ("less than a hundred cycles" per fiber switch).
24. Unity Technologies. Burst User Manual. Package 1.8. docs.unity3d.com. Also: "The future of Burst in Unity 6.6" (Unity, March 2026): Burst becomes a set of built-in modules.
25. Epic Games. FTaskGraphInterface API. dev.epicgames.com.
26. Epic Games. ParallelFor API. dev.epicgames.com.
27. Epic Games. Parallel Rendering Overview. UE 5.7. Game, render and RHI thread pipelining. dev.epicgames.com.
28. Stevens, A. (2024). How to Benefit from Multithreading in Your Unreal Engine Projects. Unreal Fest Gold Coast. Talk page; companion repo.
29. NVIDIA. stdexec: reference implementation of P2300. GitHub: github.com/NVIDIA/stdexec.
30. Smith, N. J. (2018). Notes on structured concurrency, or: Go statement considered harmful. vorpus.org. Plus Roman Elizarov's independent Kotlin treatment.
31. Chajdas, M. (2024). Work graphs and draw calls: a match made in heaven! GDC 2024 Advanced Graphics Summit (AMD). gpuopen.com. D3D12 work graphs: GPU-side scheduling of shader work.
32. Wikipedia. ABA problem. en.wikipedia.org.
33. Intel. PAUSE: Spin Loop Hint. felixcloutier.com.
34. Wikipedia. Priority inversion. en.wikipedia.org. The Mars Pathfinder incident is the classic.
35. Cox, R. (2021). Hardware Memory Models (Memory Models, Part 1). research.swtch.com.
36. Wikipedia. Simultaneous multithreading. en.wikipedia.org.
37. Binks, D. enkiTS: a permissively-licensed, lightweight, embeddable, task scheduler. GitHub: github.com/dougbinks/enkiTS.
38. RichieSams. FiberTaskingLib. GitHub: github.com/RichieSams/FiberTaskingLib. A reimplementation of the Naughty Dog architecture.
39. Intel. GTS: Games Task Scheduler. GitHub: github.com/GameTechDev/GTS-GamesTaskScheduler.
40. Parent, S. (2016). Better Code: Concurrency. code::dive. YouTube. "No raw synchronization primitives."
41. Frykholm, N. (2010). Task Management: A Practical Example. Bitsquid blog. bitsquid.blogspot.com. The single-global-queue counterpoint to work stealing: fine at their granularity until ">32 cores."
42. Desrochers, C. (2014). moodycamel::ConcurrentQueue. GitHub: github.com/cameron314/concurrentqueue; design write-up at moodycamel.com.
43. Unity Technologies. Awaitable completion and continuation. Unity 6 Manual. docs.unity3d.com. "To get the most of multi-core CPUs and parallelize your algorithms, use the job system instead."
44. Teodorescu, L. R., Arutyunyan, R., Howes, L., & Voss, M. (2025). P2079R10 Parallel scheduler. WG21 paper, adopted into C++26 at the Sofia meeting, June 2025. wg21.link. std::execution::get_parallel_scheduler().
45. Cambridge Computer Lab. C/C++11 mappings to processors. cl.cam.ac.uk. How each memory order compiles on x86, ARM and POWER.
46. GCC. Warning Options: -Winterference-size. gcc.gnu.org. Why GCC warns about hardware_destructive_interference_size in ABI-relevant code.