Scheduling Actions Across a Dependency Graph

A build graph defines a partial order, and any linearisation consistent with it is a correct execution order. Within that freedom the executor decides what runs when, and the decision determines wall-clock time. The interesting cases are all about the boundary between the two: what the order must preserve, and how much freedom is actually worth exploiting.

The ready set

At any instant the executor holds a set of actions whose dependencies have all completed. An action leaves that set and starts when a worker is free; on completion its successors may become ready, and their in-degree counters decrement. The bookkeeping is a small amount of state per action and one decrement per satisfied dependency, so for a graph with tens of thousands of actions the scheduling overhead is negligible next to the cost of spawning the processes.

Two constraints restrict the choice from the ready set. The first is the topology itself, which is the only constraint that exists for the local case: an action whose prerequisites have not finished cannot start, and no amount of parallelism changes that. The second is a set of resources whose capacity is smaller than the number of workers. Ninja expresses the second as named pools with a depth, so that a set of actions known to saturate memory or some shared facility can be limited independently of the overall job count. GNU Make expresses it less directly, and a build with recursive invocations coordinates its total concurrency through a jobserver so that sub-makes do not each start a full complement of jobs.

The tension between the two constraints appears when a limited resource is also on the critical path. Throttling the resource protects the machine, but if the throttled actions form a chain, the whole build inherits their serialisation. Choosing the pool depth becomes a measurement about the machine rather than about the graph.

The longest path is the floor

For a single worker, the schedule is a linear extension and the makespan is the sum of all action durations, regardless of order. With unlimited workers it is the length of the longest path through the graph, weighted by action duration, which is the critical path. Real executions lie between those extremes, at best reaching the critical path bound and at worst doing no better than serial.

Greedy list scheduling, which is what nearly every executor does, picks a ready action according to a priority and starts it as soon as a worker is available. Its worst-case ratio to the optimal makespan is well studied: with a longest-remaining-path priority it is within a small constant factor of optimal for any number of workers, and that factor tends toward one as the number of workers grows. The result is a bound, not a prediction; its practical meaning is that priority inversion matters most on machines with few cores, and the achievable improvement from better priorities shrinks as workers are added.

def longest_remaining(graph, duration, order):
    # order lists every action after its prerequisites; path[n] is the
    # duration of the longest chain from n to a sink, used as the priority.
    path = {}
    for n in reversed(order):
        path[n] = duration[n] + max((path[m] for m in graph[n]), default=0)
    return path

def next_action(ready, path):
    # Among actions whose dependencies are satisfied, prefer the one that
    # unblocks the longest remaining chain.
    return min(ready, key=lambda n: -path[n])

The practical implication for build-file authors is that the shape of the graph dominates. A graph consisting of a broad set of independent compilations converging on a single link has a critical path close to one compilation plus the link, so it scales well until the link becomes the entirety of the schedule. A graph that is largely a chain of generation steps scales not at all.

Local execution: what the workers actually cost

On a single machine the parallelism ceiling is set by overlap, not by core count alone. Compiler invocations spend a large fraction of their time in the filesystem: reading headers, opening the source, writing the object. For a tree whose working set exceeds the page cache, the workers contend for the same storage device, and adding workers past the device’s capability lengthens the schedule because the actions interfere. The observable symptom is that the build stops getting faster somewhere below the core count, and the explanation is queueing rather than scheduling.

Process creation is a per-action fixed cost, on the order of a millisecond on contemporary Unix systems, which matters for actions whose actual work is comparable to it. A build with a hundred thousand tiny actions spends a noticeable fraction of its time in fork and exec alone. Amortising it requires coarser actions or a long-lived server process that performs work on request, which trades the fixed cost for the complexity of a stateful worker.

Memory is the resource that most often binds first. Each compiler process may hold hundreds of megabytes of working state at peak, so a machine with many cores and modest RAM cannot run one action per core without swapping. The correct concurrency limit is therefore derived from the memory profile of the heaviest actions, not from the core count, and expressing that limit as a pool is more accurate than reducing the global job count, which also throttles cheap actions that could have run in parallel.

When the workers are elsewhere

Distributing actions to other machines removes the local resource constraints but introduces new ones. The schedule is now a flow problem: each action needs its input tree transferred to a worker, its output tree transferred back, and its execution status tracked across a network that can fail independently of the build. The action representation that makes this tractable is a content-addressed one: an action identified by its key, and a worker that demonstrates possession of the required input digests before being asked to run it. That mechanism is described in Remote Execution and Content-Addressed Input Trees.

Two properties of the distributed case change the scheduling problem qualitatively. Transfer cost is not uniform: an action whose inputs are already on a worker, because another action with a shared input prefix ran there, is cheaper than one whose inputs must be shipped. Schedulers therefore prefer workers near the data, in the same sense that a storage system prefers the replica that is geographically close. And the variance of action duration across a fleet is larger than on one machine, because workers differ in hardware, in contention, and in how loaded they already are.

That variance produces stragglers: a small number of actions finishing far later than the rest, holding up their successors while the fleet sits idle. The standard remedies are to over-subscribe workers relative to the number of actions, accepting some contention in exchange for less idling, and, where actions are known to be deterministic, to launch a duplicate on another worker and take whichever finishes first. Speculative duplication wastes work, so it is applied to the tail of the longest remaining paths rather than uniformly.

Priorities that survive a fleet

Longest-remaining-path priority is computed from the graph and from duration estimates. Locally, the estimates only need to be roughly ordered to be useful. Across a fleet they also affect fairness: a machine running many builds will interleave them, and a scheduler that ignores the cost of an action’s successors can fill the fleet with work that unblocks nothing.

A second consideration is the interaction between priority and caching. Actions on the critical path that are cheap to run but expensive to get wrong deserve to run early, and actions whose results are already in the cache should be resolved before any execution order is computed, since a hit removes the node from the schedule entirely. Ordering the graph, resolving what can be resolved from the cache, and only then scheduling the remainder is one reason a single-graph model is easier to reason about than a pipeline of separate tools.

The failure modes are concentrated at the boundaries. If a worker dies between completing an action and reporting it, the action must be retried or its output lost, and the retry must not deadlock successors that are waiting on the report rather than on the work. If a scheduler over-commits a worker, the memory pool it did not model becomes the limit and the machine swaps. And if the graph is wrong in that an edge is missing, the scheduler is free to run two actions in either order, so a scheduling change is often what converts a latent graph defect into an observed failure. The property that makes such defects detectable rather than merely intermittent is hermeticity, and its enforcement is described in Hermetic Actions and Undeclared Inputs.