How does a job system with dependency counters spread a game's per-frame work across all cores instead of keeping one core busy?
answer
- one thread does everything
- small units, a worker per core
- count of unfinished prerequisites
- batches for a parallel-for
basics
~20 sA job system breaks each frame into many small jobs run by about one worker thread per core. Each job counts its unfinished prerequisites; when that count reaches zero the job becomes ready, so every core pulls work as dependencies resolve.
solid answer
~50 sA single game thread uses one core however many the machine has, and a dedicated thread per subsystem only reaches as many cores as there are subsystems, with the slowest one setting the pace. A **job system** runs a pool of about one worker thread per core and feeds it small **jobs**, each a function plus its data. The frame becomes a **graph**: each job holds a **dependency counter** of unfinished prerequisites, the worker that finishes a job decrements its dependents' counters, and any dependent that reaches zero is pushed onto the ready queue. Big loops become a **parallel-for**: 20,480 objects in batches of 256 is 80 jobs, so idle workers always find work. The main thread runs jobs instead of waiting idle. What it cannot remove is the serial part: the longest dependency chain still runs one job after another.
code
pseudocode · 23 linesstruct Job:
run // function to call
data // what it works on
pending // count of unfinished prerequisites
dependents // jobs that wait for this one
// the whole graph is built before the frame starts; only roots are pushed
function start_frame(graph):
remaining = graph.job_count
// collect roots before pushing any: a running root may already bring a
// dependent to zero and push it, so it must not be pushed a second time
roots = [job for each job in graph.jobs if job.pending == 0]
for each job in roots:
ready_queue.push(job)
function worker_loop():
loop:
job = ready_queue.pop_or_wait()
job.run(job.data)
for each d in job.dependents:
if atomic_decrement(d.pending) == 0: // returns the new value
ready_queue.push(d)
atomic_decrement(remaining)go deeper
Recall what a job is, a function plus its data, and that a pool of about one worker per core runs jobs instead of one thread per subsystem.
Walk through the dependency counter: who decrements it, who pushes the job when it reaches zero, and how a parallel-for turns one loop into many batch jobs.
Discuss batch sizing, ordering conflicting writes through graph edges, letting the main thread run jobs while it waits, and why the critical path still bounds the frame.
Judge where a job system pays off for a codebase: how much of the frame can be made wide, and what discipline, such as no hidden shared writes, the team must keep.
## Why one core stays busy A classic engine runs the frame on one thread: input, gameplay, physics, culling and draw preparation, one after another. On an eight-core machine, seven cores idle. The first fix teams reach for is a **thread per subsystem** (a physics thread, an AI thread), and it stalls quickly: - it reaches only as many cores as there are subsystems, so a 16-core machine gets no more from it than an 8-core one; - subsystems differ in cost, so the slowest sets the frame time while the others finish early and wait; - every pair of subsystems that share data invents its own hand-off and locking. ## What a job is A **job** is a small unit of work: a function plus a pointer to the data it works on, short enough to run to completion in somewhere between microseconds and a few milliseconds. A **job system** keeps a pool of **worker threads**, usually about one per hardware core (often one fewer, because the main thread joins in), and a queue of ready jobs. Workers loop: take a ready job, run it, report that it finished. How ready jobs are spread over workers, through one shared queue or per-worker queues with stealing, is general scheduler design; the engine's part is what goes into the jobs and how they depend on each other. ## Dependency counters and the per-frame graph A frame is not a bag of independent jobs: culling needs final transforms, and draw preparation needs culling's results. The engine expresses this as a **per-frame job graph**: 1. Build the graph: each job records its **dependents** and a **counter** of unfinished prerequisites. 2. Push every job whose counter is already zero (the roots) onto the ready queue. 3. When a worker finishes a job, it atomically decrements the counter of each dependent. 4. The worker whose decrement takes a counter to zero pushes that dependent onto the ready queue. 5. The frame's work is done when a frame-wide counter of remaining jobs reaches zero. No thread polls and no central scheduler picks an order: readiness propagates through the counters. A common variant attaches one counter to a whole **batch** of jobs, and code that needs their results waits until that counter reaches zero. The graph is also how the engine stops parallel jobs from writing the same data. Two jobs that write the same data, or where one writes what the other reads, are ordered by an edge; jobs that only read can run side by side. An entity-component system can derive those edges from the components each system declares it reads and writes. ## Parallel-for: one loop, many jobs A loop over thousands of objects becomes a **parallel-for**: the range is cut into batches and each batch is a job. In an illustrative frame, 20,480 objects in batches of 256 give 20,480 / 256 = 80 jobs for eight workers, ten each on average, so a worker that finishes early takes another batch and the tail of the loop stays short. | Batch size | Effect | |---|---| | Too small (a handful of objects) | Scheduling overhead per job rivals the work itself | | Balanced (several batches per worker) | Workers stay busy and finish close together | | Too large (one batch per worker) | One slow batch leaves the other workers idle at the end | ## What a job system does not fix The **serial fraction** stays serial. If a frame does 20 ms of work on one thread and 16 ms of it can be split, eight workers give at best 4 + 16 / 8 = 6 ms, about 3.3 times faster rather than eight. The same holds inside the graph: the longest chain of dependent jobs, the **critical path**, runs one job after another however many cores there are. A job system pays off when that chain is short and the rest of the frame is wide.
- How do you pick a batch size for a parallel-for over game objects?Aim for several batches per worker so early finishers can take more, but keep each batch large enough that scheduling overhead is small next to its work. Then measure: if workers finish at very different times, batches are too large; if the timeline is dominated by tiny jobs and queue traffic, they are too small.
- What should the main thread do while it waits for the frame's jobs?Run jobs itself. A main thread that blocks idle wastes a core; one that takes jobs from the same queue until the counter it is waiting on reaches zero turns its wait into useful work.
- How does the job graph stop two jobs from writing the same data at once?Any two jobs that write the same data, or where one writes what the other reads, get a dependency edge, so they never overlap. Jobs that only read shared data run in parallel freely. Some engines derive these edges from declared read and write sets instead of hand-written dependencies.
- A job system means one thread per subsystem, such as a physics thread and an AI thread.
- More worker threads than cores always gives more throughput.
- Every job should be as small as possible to balance the load perfectly.
- On eight cores, a job system makes every frame eight times faster.
- Workers should keep polling every job's prerequisites to find runnable work.