Scheduling a Job Graph Around Its Critical Path

Adding runners to a pipeline that already has spare capacity does not make it finish sooner. The wall-clock time of a job graph is bounded below by its critical path, the longest chain of dependent jobs, and no amount of parallelism changes that number. What parallelism changes is how far above the bound the actual finish time sits, and the useful question for a pipeline is always the same: how much of the gap between the critical path and the observed duration is scheduling, and how much is work that no schedule can overlap.

Two lower bounds, and which one is binding

The first bound is the critical path. Sum the durations along every path from the start to the end, take the maximum. No schedule can be shorter, because the jobs on that path must run in order.

The second bound is total work divided by capacity: the sum of all job durations divided by the number of parallel slots. No schedule can be shorter than that either, for the obvious reason that every job consumes a slot for its duration.

The binding bound is the larger of the two. A graph with a long serial chain has a large critical path and a small total work, so adding machines does nothing. A graph with a wide fan-out and short chains has a small critical path and a large total work, so adding machines helps until capacity catches up with width. Measuring both before optimizing tells you which lever exists; measuring neither leads to adding hardware and wondering why the number did not move.

The total-work bound is why caching is usually a better lever than scheduling. A cache hit removes work from the numerator entirely, whereas parallelism only divides it by a constant that hardware limits. The two compose, and the order matters: removing work first changes which bound is binding, sometimes making further parallel capacity pointless. The mechanisms for removing work are in What a Build Cache Key Must Cover.

The greedy schedule and its known worst case

The scheduling problem for a job graph with durations known in advance is list scheduling: whenever a slot is free, start the ready job with the longest remaining downstream path. This is the standard heuristic for a reason, and its worst-case behaviour is characterized.

Greedy list scheduling on a graph with unit-length jobs and m machines produces a makespan at most (2 - 1/m) times the optimum. The bound is tight, meaning there are graphs where greedy really is that bad, and it is also pessimistic for real pipelines, whose durations vary and whose graphs are shallow. The practical value of the bound is that it says the worst case is a constant factor, so a schedule that is dramatically worse than optimal is not a scheduling failure in the algorithmic sense. It is usually an artifact of unknown durations.

Unknown durations are the common case. A pipeline does not know how long a test job will take, so it either guesses from history or does not guess at all. Guessing from recent history is much better than guessing nothing, because the longest-first ordering depends on the comparison being roughly right, and a duration estimate that is wrong by a small factor reorders little.

The real complication is that durations change in response to the schedule. Ten test jobs running concurrently on one machine contend for memory bandwidth and disk, and each runs slower than it would alone. The pipeline’s estimate comes from previous runs, which ran with a different degree of concurrency. This is why doubling the workers sometimes produces less than half the time, and why the observation is not evidence that the scheduler is broken.

Fan-out is only worth it above a threshold

A job that splits into N shards pays a fixed cost per shard: process start, checkout or artifact download, toolchain setup, result upload. If the shard’s work is not much larger than that fixed cost, the fan-out increases total work rather than reducing wall-clock time.

The arithmetic is simple enough to do before implementing. If a single test job takes T and the fixed overhead per shard is O, running N shards takes roughly T/N + O in the best case, ignoring contention. The fan-out helps while T/N > O, and stops helping at N ≈ T/O. Continuing past that point adds cost with no benefit, and contention makes the real turning point earlier than the arithmetic suggests.

This threshold is the practical argument for the conventional pattern in which a small number of large jobs does most of the work and fan-out is reserved for the stages that are both slow and partitionable. Test execution is partitionable because tests are independent. A compile step is partitionable only at the granularity the build graph already provides, which is why the compile phase of a large project is usually parallelized by the build system rather than by the pipeline.

import hashlib

def shard_for(test_id: str, shards: int) -> int:
    # Stable across machines and across runs: the same test always lands in
    # the same shard, so a shard's failure is reproducible from the id alone.
    d = hashlib.sha256(test_id.encode('utf-8')).digest()
    return int.from_bytes(d[:8], 'big') % shards

Hashing rather than slicing an ordered list is the choice that matters here. Slicing is balanced only if the test list is stable and the durations are uniform; adding one test shifts every later test into a different shard, which changes which failures appear in which shard and makes historical comparison useless. Hashing keeps a test’s shard fixed, so a shard’s duration drifts slowly and a new test lands somewhere that can be predicted.

Hashing does not balance durations. It balances counts, and test durations are heavy-tailed: a small number of tests account for a large share of the time, so count-balanced shards can differ in duration by a large factor. The remedy is to hash with a weight, assigning tests to shards by a greedy pass over historical durations within the hash-derived order. That requires duration history, which requires the pipeline to store per-test timings, which is a small amount of state with a large payoff.

Resource classes and the queueing that hides them

Treating all slots as interchangeable is the second scheduling mistake. Test jobs are usually CPU-bound and memory-heavy, packaging jobs are I/O-bound, deployment jobs hold a lock on an environment and must not run concurrently at all. A scheduler that models one pool forces these into contention.

Modeling them is a small extension: each job declares a resource class, each pool has a size, and a job is ready only when its class has a free slot and its predecessors are complete. The interesting case is the job that holds an exclusive resource, such as a shared test database or a staging environment. Its critical path contribution includes the queueing time behind other holders, which is not a property of the job at all and cannot be reduced by making the job faster.

Locks of this kind are where pipelines most often diverge from their models. A stage that takes two minutes of work but waits ten minutes for a lock has a twelve-minute critical path contribution, and optimizing the work is beside the point. Serializing the lock holders, or provisioning a second environment, reduces the wall clock by the queueing term rather than by the work term.

Failure, retry, and the economics of re-running

A retry re-executes a job and everything downstream of it. If the downstream jobs are on the critical path, the cost of a flaky job is its duration plus the duration of the chain it invalidates, which can be far larger than the job itself.

This changes the priority order for reliability work. A flaky two-minute test in the middle of a ten-minute chain costs twelve minutes when it fails; a flaky thirty-second test at the end costs thirty seconds. Both are equally annoying to read in a log, and they are not equally expensive.

Partial re-run, where a failed job is restarted and completed jobs are reused, requires that job results be cached across runs in a way that respects the same correctness conditions as the build cache. A job whose result is reused must have had all of its inputs as its key, including the ones that came from other jobs. Getting that wrong reintroduces the failure mode of a cache hit for a job that never ran, and the failure is silent because the pipeline reports success for a job whose result came from a different revision.

Ending the analysis at the right place

The critical path is a diagnostic, not a target. Pipelines that are already within a small factor of their critical path bound have no scheduling problem left, and the remaining time is the path itself. That path is shortened by removing stages, by merging stages whose handoff costs more than their separation saves, or by making the longest stage faster.

The handoff cost deserves attention at this point, because it is the term that fan-out architectures systematically underestimate. Every edge in the graph that crosses a machine boundary carries an artifact transfer and a verification step, and those are on the critical path. The mechanisms and their failure modes are the subject of Passing Build State Between Jobs Without a Shared Workspace, and a pipeline that widens its graph without accounting for them can end up with a longer critical path than it started with.