Why the Busiest Stage Is Not Always the Critical Path

A function that consumes thirty percent of total CPU time looks like the obvious target. Suppose it is one of twelve stages in a fan-out: the request handler computes credentials, fetches user records, fetches preferences, and evaluates permissions concurrently, then waits for all of them. Shaving thirty percent off the credential stage changes elapsed time only if credentials complete last. If preferences take longer, the saving is absorbed entirely by the earlier idle window, and the measured total is unchanged.

This gap between where time is spent and where time is added to the total is the most common way a well-measured profile produces a useless optimization plan. The profile attributes cost to work; the request’s duration is set by the shape of the dependencies among that work.

Cost accounting versus duration accounting

A sampling profiler produces a per-function breakdown of CPU time. That breakdown is a partition of effort, and it sums to the total consumption because every cycle is charged somewhere. Duration is not a partition in the same sense. In a single-threaded sequential program the two coincide: the elapsed time equals the sum of the durations of the executed segments, so a thirty percent share of functions is a thirty percent share of duration, and the hottest function is also the largest contributor to latency.

The coincidence fails under any of three conditions, and all three are ordinary.

The first is concurrency. When a thread blocks on I/O, the CPU time during that block is charged to nothing, though the elapsed time grows. A function that spins for a fixed duration while waiting is charged to the code that spins; a function that blocks efficiently is charged to nothing at all. Either way, the profile’s partition of CPU time does not extend to a partition of wall time.

The second is fan-out with joins. Work executed in parallel branches contributes to elapsed time only through the slowest branch. All the other branches’ cost is real, consumes resources, and is invisible in the duration, because it fits inside slack.

The third is the presence of a critical path that is not the busy one. A pipeline whose stages have very different service times — the classic unbalanced assembly line — has a total duration that is the sum of all stages on one request, but a throughput set by the slowest stage and queueing behaviour set by the backlog in front of it. Reducing a fast stage improves neither.

Slack, and what it absorbs

Slack is the amount by which a branch’s duration can grow before it delays the join. It is computed by propagating deadlines backwards from the end of the request: the join at time $J$ gives every branch that must complete before it a completion deadline of $J$, and each branch has slack equal to its deadline minus its actual completion time.

def critical_path(tasks, deps):
    """tasks: {name: (start_hint, duration)}. deps: {name: [predecessors]}.
    Returns per-task (earliest_finish, slack) for the whole DAG."""
    finish = {}
    for name in topological_order(tasks, deps):      # avoids recursion depth issues
        begin = max((finish[p] for p in deps[name]), default=0.0)
        finish[name] = begin + tasks[name][1]
    # Slack: how far a task could be delayed before it moves the end of the graph.
    horizon = max(finish.values())
    arrive = {}
    for name in reversed(topological_order(tasks, deps)):
        succ = [t for t, ps in deps.items() if name in ps]
        deadline = min((arrive[s] for s in succ), default=horizon)
        arrive[name] = deadline - tasks[name][1]
    return {n: (finish[n], arrive[n] - finish[n] + tasks[n][1]) for n in tasks}

The formula is the standard forward-backward pass of deterministic scheduling. Tasks with zero slack lie on at least one critical path; tasks with positive slack have room. A task with a tenth of a second of slack cannot contribute to the reduction of a request that finishes in half a second by saving a twentieth of a second per task: the first tenth of a second saved is consumed by the slack and produces no change in the total at all.

This produces the apparently paradoxical result that a very expensive operation can be entirely off the critical path. A twelve-hundred-millisecond analytics computation launched asynchronously with results collected at the end of the request, where the request’s critical path is four hundred milliseconds, contributes nothing to latency until it grows past that four hundred. Halving it, or eliminating it, does nothing measurable; eliminating it saves CPU, memory, and queue pressure, which matter for capacity but not for the response time measured at the edge. The distinction is exactly a question of which objective the work is charged against, as the workload-mix objective discussion sets out: the same component is expensive under one metric and free under another, and neither statement is a property of the component alone.

The three axes a stage can improve

For any stage one can ask which of three totals it affects: elapsed time of one request (latency), requests processed per unit time (throughput), or the cost of the resources it consumes (CPU-seconds, bytes, memory). These are not equivalent, and a stage’s position in the dependency graph determines which it can move.

A stage with zero slack sits on the critical path and affects latency one-for-one up to the point where slack in the remaining structure reappears. Reducing it also raises throughput if it is the throughput limiter, which it need not be: throughput is set by the busiest resource under the offered load, and a latency-critical path may contain no resource that is near saturation.

A stage with positive slack affects neither latency nor throughput, but it affects capacity: its CPU-seconds are a real share of the machine. On a system sized by CPU, removing slack work allows more concurrent requests on the same hardware, which raises the sustainable throughput even though it does not reduce any single request’s duration. That is a genuine and sometimes large win, and it is a different win from the one the profile’s percentage suggests.

A stage that is the busiest resource affects throughput and, through queueing, latency as well. Where a queue forms, latency grows faster than an equal absolute reduction would suggest: near saturation, the queue length is approximately $\rho/(1-\rho)$ for utilization $\rho$, so reducing service time from a utilization of 0.9 to 0.8 reduces mean queue length from nine to four. Waiting time is where the leverage is.

Reading a profile for the path, not the partition

The practical procedure is to obtain a concurrency-aware trace rather than a CPU-sampled profile, because only a trace carries the timestamps from which the forward-backward pass can be computed. Trace spans that carry start and end times per operation permit both the critical path and the slack for each span; the critical path is then the chain with zero slack, and it can differ from the chain with the largest total duration if the graph has alternative routes.

When no trace is available, three cheaper approximations are useful.

Take a differential measurement. Disable or stub one stage and observe the change in end-to-end latency. Stages whose removal does not move the median are off the critical path, regardless of their cost. This is the ablation approach described in measuring component cost by ablation, applied to the latency metric.

Look for join points and their completion distribution. A join where the final arrival is nearly always from the same branch puts that branch on the critical path for nearly all requests; a join whose last arrival varies is balanced, and reducing any single branch yields a fraction of the benefit, weighted by the frequency with which it is last. Recording which branch arrived last requires one comparison per request and answers the question precisely.

Check the queue. A stage that is not on the critical path can still be the one that makes the system slow through saturation, because the critical path of a queued request includes waiting. In the latency metric the queueing delay is on the critical path by definition; the capacity view of the same system asks the different question of what load the system can absorb.

Why this changes the order of work

The consequence for planning is a constraint on candidate selection that precedes any payoff arithmetic. A candidate whose effect is absorbed by slack has zero effect on latency and should be scored as a capacity candidate instead, against CPU-seconds saved rather than milliseconds removed. Scoring it against milliseconds inflates its apparent value and displaces work that would actually shorten requests.

The inverse error is also common: a change that reduces CPU-seconds in a slack branch is scored as though it were a latency win, is judged against a latency target, and is rejected as insufficient — when it was addressing the correct objective and the objective was mis-specified. Getting the axis right, before computing any fraction, is what makes the expected-payoff numbers mean something.