From 340 Lines of Python to Everyone Else’s Build Pipeline

In 2016 Brandon Cowen wrote 340 lines of Python over a single Saturday because a build he did not own took forty minutes, and a recognisable third of those lines still run today inside tooling used by people who have never heard of him. The project is called plait. Given a pile of tasks and the dependencies declared between them, it decides what runs in what order and what may run at the same time. That is the entire scope: no website beyond a repository, no logo, nothing being sold.

What follows is a walk through the trick at the centre of it. The short version: Brandon Cowen did not write a faster graph algorithm. He wrote an ordinary one and deleted most of the graph before running it, and the deletion mattered about ten times as much as the algorithm.

The dependencies were not real

The build belonged to a project he had been sending patches to. Six hundred and twelve tasks: compile steps, codegen, schema checks, a documentation pass, four flavours of test. It ran in a conservative sequential order and took thirty-eight minutes, every time, on a machine with eight mostly idle cores. Nobody called this a bug. It was how long the build took.

Cowen spent the first part of that Saturday reading the dependency file rather than the scheduler, which is the decision the story hangs on. The graph the build tool was so carefully obeying turned out to be fiction.

“Nobody adds a dependency because they measured one. They add it because something broke once at four in the afternoon and adding an edge made it stop breaking. Then they leave the project and the edge stays forever. A build file is sediment. You are not reading a graph, you are reading a record of other people’s bad afternoons.”

Brandon Cowen, by email

That is the whole insight, and it is not an algorithmic one. Every build tool of the era trusted the declared graph, because the declared graph is the only thing you can read without running anything. Trusting it is safe: you will never produce a wrong result. It is also how a decade of defensive edges nobody dared delete serialises a build with no real ordering constraints.

What Brandon Cowen tried first

The first ninety minutes went the way they always go. The file that survives in the repository history opens with a textbook topological sort — the correct thing to write first and the wrong thing to keep.

# schedule.py — Saturday morning, before the coffee ran out
from collections import deque

def serial_order(tasks, declared):
    """Kahn. Correct. One task at a time, all the way down."""
    blocked_by = {t: len(declared.get(t, ())) for t in tasks}
    ready = deque(t for t in tasks if blocked_by[t] == 0)

    out = []
    while ready:
        t = ready.popleft()
        out.append(t)
        for other, needs in declared.items():
            if t in needs:
                blocked_by[other] -= 1
                if blocked_by[other] == 0:
                    ready.append(other)
    return out

# 612 tasks -> 612 steps -> 38 min 40 s of wall clock
# the longest chain that actually matters is nine

This is correct, and useless. A topological sort returns a line: six hundred and twelve tasks come out as six hundred and twelve steps, and eight cores stay idle. The obvious fix is to emit levels instead — everything with no outstanding blockers goes in wave one, everything unblocked by wave one in wave two. Cowen wrote that version before lunch. It gave him forty-seven waves with a median width of three tasks, and took the build from thirty-eight minutes to thirty-four.

Forty-seven, because the declared graph really was forty-seven deep. The scheduler was not the bottleneck. It was faithfully executing a lie.

The prune: 96% of declared edges, gone before scheduling

Here is the part that turned a weekend script into something other people vendor. Before scheduling anything, ask of every declared edge whether it could possibly matter, and discard the ones that provably cannot.

# prune.py — the thirty lines that turned a script into infrastructure
UNDECLARED = object()

def real_edges(tasks, declared):
    """Keep a -> b only if b could ever read something a writes."""
    writes = {t.name: frozenset(t.outputs) for t in tasks if t.outputs}
    reads  = {t.name: frozenset(t.inputs)  for t in tasks if t.inputs}

    keep = set()
    for b in sorted(declared):
        for a in sorted(declared[b]):
            produced = writes.get(a, UNDECLARED)
            consumed = reads.get(b, UNDECLARED)
            if produced is UNDECLARED or consumed is UNDECLARED:
                keep.add((a, b))     # nobody said. assume the worst
            elif produced & consumed:
                keep.add((a, b))     # a genuinely feeds b
            elif impure(a) or impure(b):
                keep.add((a, b))     # order matters for other reasons
    return keep

Three branches, in order of paranoia. If either task failed to declare what it reads or writes, keep the edge: ignorance is not evidence. If the outputs of a intersect the inputs of b, keep it, because that is a real dependency. If either task is impure — touches the network, mutates shared state — keep it on principle. Everything else goes. On the 612-task fixture, 4,118 declared edges come out as 171: 4.2 percent retained, at a cost of one set intersection per edge.

This is not an approximation. The prune does not discard edges that look unimportant, or edges below some threshold; it discards edges where no observable behaviour can depend on the ordering. If a writes nothing b reads and neither reaches outside the declared world, running them in either order produces the same bytes. The result is the same schedule with the ceremony removed.

Determinism was a design decision, not a performance one

The next choice is the one I would not have made, and the one that separates a working engineer from a clever one. There is no randomness anywhere in the 2016 script. No work stealing, no dynamic rebalancing, no search that stops wherever the wall clock happens to land. Every collection is walked in sorted() order, every tie is broken by task name, and the same inputs produce a byte-identical plan on any machine.

# plan.py — same inputs, same plan, on any machine, in any year
def waves(tasks, declared, graph, history):
    edges   = real_edges(tasks, declared)
    blocked = {t.name: set() for t in tasks}
    for a, b in edges:
        blocked[b].add(a)

    done, plan = set(), []
    pending = sorted(t.name for t in tasks)
    while pending:
        ready = [n for n in pending if blocked[n] <= done]
        if not ready:
            raise Cycle(pending[:8])   # the whole run stops right here
        ready.sort(key=lambda n: (-round(priority(n, graph, history), 6), n))
        plan.append(tuple(ready))
        done.update(ready)
        pending = [n for n in pending if n not in done]
    return plan

In 2016 that meant explicitly sorting things later CPython versions would have happened to iterate in a stable order anyway. Cowen sorted them regardless, which reads as superstition until you remember what a build is for. The plan is part of the artifact: a scheduler that reorders itself between runs makes the artifact impossible to reproduce and the regression impossible to bisect. The other reason is smaller and more important.

“The first question anybody asks a scheduler is never ‘is this optimal.’ It is ‘why did it do that today and not yesterday.’ If you cannot answer that in one sentence, you have not shipped a build tool. You have shipped a slot machine that occasionally emits binaries.”

Sunil Okpara-Vance, maintainer of Latchwork, which vendors plait

Engineers build a mental model of a build the way they build one of a colleague. Watch the same plan four mornings running and you know where to look when the fifth is slow. A scheduler faster on average but different every time destroys that model, which is worth more than the average.

Explainable and slightly slower beat optimal and opaque

Within a wave, something still has to decide what starts first when there are more ready tasks than cores. One function, three constants.

# weights.py — what runs first, and why
CRITICAL_PATH = 1000.0   # length of the longest chain still behind this task
FANOUT        =   10.0   # tasks unblocked the moment this one lands
DURATION      =    0.1   # median seconds across the last twenty runs

def priority(name, graph, history):
    depth  = graph.longest_chain_behind(name)
    unlock = len(graph.dependents[name])
    secs   = history.median_seconds(name, default=1.0)
    return CRITICAL_PATH * depth + FANOUT * unlock + DURATION * secs

I re-ran the 612-task fixture against the level-batched declared graph and against the tagged plait release, on eight cores, cold cache.

Two of those rows are losses and both are real. Planning costs seventeen times what it did, which nobody notices, and peak memory goes up almost fivefold, which anyone with a laptop and a browser open notices at once. Forty-one compilers running is a different machine from three. The documented answer is a concurrency cap, the first thing every downstream project sets.

A third cost never shows up in a table. I wrote a work-stealing variant of the same scheduler — tasks pulled by whichever worker frees up first, no fixed plan — and it finished the fixture in 5 m 48 s, seven percent faster, with a different execution order every run. That seven percent is what determinism costs. Cowen made the trade in 2016 and has twice declined to revisit it in the issue tracker.

What the code gets wrong

I have been generous so far, so here is the part where I am not. The constants in weights.py are a genuinely bad idea, and they still carry the values Brandon Cowen typed on a Saturday in 2016.

Look at the magnitudes: 1000, 10, 0.1. Those are not weights. They are decimal tiers, and what the function computes is a lexicographic sort — critical path, then fanout, then duration — wearing a weighted sum as a disguise. If that is the intent, say so and return a tuple; a tuple sorts correctly forever and needs no defending. As written, the tiers hold only while the inputs stay small. A hundred dependents contribute as much fanout score as a whole unit of critical-path depth; a hundred-second task outweighs ten dependents. Both exist in any large repository. Past those thresholds the ordering silently stops being the one the author described, and no test will catch it, because none could without writing down the intent the constants exist to avoid.

Three smaller ones, in descending order of how much they bother me:

• real_edges reads every task’s declared inputs and outputs once, at startup, and caches the result for the whole run. Any build whose codegen emits new task definitions violates that assumption, and the failure mode is not an error — it is a stale prune that schedules a consumer before its producer. The documented workaround is two invocations. There should be a check.
• raise Cycle(pending[:8]) aborts the run and reports the first eight remaining task names alphabetically, which is very unlikely to be the cycle. Finding the strongly connected component is a dozen lines and turns a twenty-minute debugging session into a ten-second one.
• round(priority(...), 6) is load-bearing: it stops float comparison from making tie-breaks platform-dependent, and as far as I can find nothing asserts it. Delete the round and the suite stays green, right up until two machines disagree about a build.

Reading Brandon Cowen’s function in 2023

He released it publicly in 2017 and it spread the way boring things spread: one file, no third-party dependencies, small enough to read in an afternoon and therefore to vendor without asking anyone. It arrived inside build tooling rather than being adopted as build tooling, which is why most people who depend on it daily could not name it. Ines Vaszary contributed the wave batching in 2019 and remains the only other person with more than four merged patches. Cowen reviews the rest alone.

The descendant of real_edges in the current tree is about 210 lines: type annotations, dataclasses instead of loose tuples, a real exception path, tests. The shape is untouched. Assume the declared graph is wrong, discard every edge whose ordering cannot be observed, batch what is left, break every tie with something a person can say out loud. Seven years on, the load-bearing idea is still that most of the constraints you inherit are not constraints.

In September 2022 a company that sells continuous-integration infrastructure offered to buy plait and take it closed-source. He said no. When I asked, he answered in two sentences and came across as less principled than puzzled, genuinely unable to work out what the buyer imagined they would be holding.

“It was 340 lines because I had one Saturday. Most of the good decisions in it were decisions not to do something.”

Brandon Cowen

Benchmarks were run on the tagged release against a synthetic 612-task fixture; the fixture and run script are linked from the discussion thread. Cowen reviewed the code excerpts for accuracy and declined to comment on the numbers.