Scheduling a Parallel Build from a Dependency Graph

Topological order gets a build finished. It does not get it finished quickly, and the difference between a build that finishes on time and one that does not is almost never the compiler’s speed. A build graph is a directed acyclic graph whose nodes are commands and whose edges are file dependencies: an edge from A to B means B reads a file that A writes. Running the graph correctly is a topological sort. Running it fast is a scheduling problem, and the scheduling problem is harder than it looks because the costs are not known in advance, the graph is not known in advance either, and the machine’s parallelism is not uniform.

The naive scheduler is a ready queue. Nodes with no unfinished prerequisites are runnable; the scheduler pops as many as the job limit allows, starts them, and on each completion adds any node whose prerequisites are now satisfied. That is correct, and it is what most build tools implement. Everything interesting lies in what the naive scheduler does badly. The correctness of the queue rests entirely on the edges being right, and the edges come from header dependency discovery plus whatever the build declares by hand.

Critical path versus ready-queue order

With unlimited parallelism the makespan is the longest path in the graph weighted by node cost. With a finite number of workers, the makespan is at least that and at least the total work divided by the worker count. A scheduler that always picks the next node in the ready queue by arrival order can leave the critical path idle while it works on nodes with slack.

The standard improvement is to prioritise by the length of the longest path from the node to the end of the graph, computed once by a reverse traversal that knows the node costs. Nodes on the critical path run first; nodes with large slack fill in later. When costs are known, this is close to optimal for the common case of a graph with one dominant chain and much parallel work hanging off it.

Costs are rarely known. A build system can record how long each command took on the previous run and use that as the estimate, which is a reasonable predictor because compilation time for a given file is stable across runs unless the file changes. The estimate is wrong exactly when it matters: a file that has just been edited heavily may take much longer than its history suggests. Weighting by history still beats unweighted arrival order, and the recording is cheap.

A second refinement is to start long jobs early even when they are not on the critical path, because a long job occupies a worker for a long time and starting it late extends the tail of the schedule. The heuristic is the same as longest-processing-time-first list scheduling, whose makespan is at most $4/3 - 1/(3m)$ times the optimum on $m$ workers.

The graph is discovered while it is being executed

The harder problem is that the edges are not all known before execution starts. Header dependencies are the canonical case: the compiler can only report which headers a translation unit opened after preprocessing it, so the edge from a header to an object file is discovered during the compilation of that object file. The dependency is also discovered too late to prevent the wrong order: if the header changes after the object was compiled, the object is stale, and the build must notice.

Two strategies exist. The first is to preprocess everything first, in a separate pass, collecting all dependencies before compiling anything. That doubles the front-end work and serialises two phases, but it produces a complete graph and therefore a correct schedule. The second is to compile optimistically and detect staleness afterwards, which is what a build system does when it re-reads the dependency files generated by the previous build and compares timestamps or content hashes. Optimistic builds are faster when few headers changed and produce a wasted recompile when one did.

The correctness requirement in either case is that no output be considered up to date unless every input that went into it is older, or content-identical, to what it was when the output was produced. Timestamps are a weak proxy for this: a file restored from a backup, or checked out by a version control system that preserves modification times, can appear older than an output that is in fact stale. Content hashing removes the ambiguity at the cost of reading every input on every build.

Why make’s recursive model has a cost

Traditional make evaluates rules recursively: to build a target it walks its prerequisites, and each prerequisite may itself be a target with its own rules. The search is repeated for each target because the tool has no global view of the graph, and it re-stats files as it goes.

The visible consequence is a per-target search cost that grows with the number of files. Every target is reached by walking prerequisites that were already walked for another target, so the work is repeated once per dependent rather than once per file, and the effect worsens with deep prerequisite chains because each level re-evaluates. Build tools designed for large trees instead load a precomputed description of the graph once and traverse it in memory, which removes the repeated search and makes the scheduling decisions cheap enough to be made well.

The other cost of the recursive model is that it cannot see the whole graph, so it cannot prioritise by critical path. It starts what it can start and lets the job server throttle it. That is fine for a graph whose nodes are roughly uniform and wrong for one with a few long nodes.

Job servers, load, and the limits of a fixed job count

A job limit of N means at most N commands run at once. Choosing N is a guess. Too low wastes cores; too high oversubscribes memory and the memory bandwidth that compilation consumes. Compilers are memory-hungry relative to most command-line tools, so the optimal N for a tree of large C++ translation units is often below the core count, and the optimal N for a tree of small C files is above it.

Distributed builds add a second dimension. Work can be sent to remote machines, and the scheduler’s decisions now involve network latency, the cost of shipping inputs, and the risk that a remote worker fails. Shipping a compilation requires the full input set, which is exactly the dependency closure the graph already knows, so a distributed build must be able to materialise that closure. Content addressing is what makes that transfer bearable: an input the remote side already holds, identified by its hash, need not be sent again, so a build that changes few files transfers little.

import heapq

def schedule(graph, workers):
    """graph: node -> {'needs': [...], 'estimate': seconds}
    Ready nodes are keyed on estimated cost. Keying on the longest remaining
    path instead gives critical-path order, which needs a reverse traversal.
    """
    remaining = {n: len(node['needs']) for n, node in graph.items()}
    dependents = {n: [] for n in graph}
    for n, node in graph.items():
        for p in node['needs']:
            dependents[p].append(n)
    ready = [(-graph[n]['estimate'], n) for n in graph if not remaining[n]]
    heapq.heapify(ready)
    running, done = [], set()
    while ready or running:
        while ready and len(running) < workers:
            running.append(heapq.heappop(ready)[1])
        finished = running.pop(0)          # stands in for a completion event
        done.add(finished)
        for n in dependents[finished]:     # each node is queued exactly once
            remaining[n] -= 1
            if remaining[n] == 0:
                heapq.heappush(ready, (-graph[n]['estimate'], n))

The loop above is schematic in ways that matter: it assumes an acyclic graph and so never detects a cycle, it has no notion of failure, it assumes at least one worker, and it keys on total estimated cost, the weakest of the orderings described above. It shows the shape, though: a priority queue keyed on estimated cost, a per-node count of unfinished prerequisites that reaches zero exactly once, and a bounded set of running jobs. Real implementations add cycle detection, error propagation that cancels dependents, and a rule that a failed job does not stop independent work already in flight.

Failure behaviour and the tail

A parallel build’s failure mode is not the same as a serial one’s. In a serial build, the first failure stops everything and the output is a clean prefix. In a parallel build, jobs already running complete, jobs that were about to start may be cancelled or may run, and the set of files on disk after a failure is arbitrary. Builds that assume a failed run leaves a consistent partial state are wrong.

The tail is the other practical concern. Near the end of a build the graph narrows to a few final links, and those links are serial by nature: one executable per target. A build with a thousand compilations and one link spends its last stretch with N-1 workers idle. Some build systems overlap link steps across independent targets, which helps only when there are many executables. Others interleave the final links with the last compilations by scheduling links as soon as their own inputs are ready, which is what critical-path prioritisation already does if the link’s estimated cost is large enough to be chosen early.

The interaction with caching is worth stating: a scheduler that knows which nodes will hit a cache does not need to run them at all, and the graph shrinks before scheduling begins. That makes the cache key the real determinant of schedule length, and the correctness of the key the determinant of whether the schedule is valid at all. Content-Addressed Build Cache Keys covers what has to be inside such a key.