Amdahl's Law as a Ceiling on Optimization Returns

A routine that occupies forty percent of a program’s elapsed time cannot be optimized into a fivefold overall improvement, no matter how clever the rewrite. Make that routine instantaneous and the remaining sixty percent still dominates: the best possible result is a factor of about 1.67. The arithmetic behind that statement is trivial, and it is the single most useful filter available before any optimization work begins, because it converts an open-ended question (“how fast can this get?”) into a bounded one (“what is the ceiling for this candidate?”).

The arithmetic of a fraction

Let $f$ be the fraction of elapsed time spent in the code a change targets, and $s$ the factor by which that code becomes faster. The new elapsed time is the untouched remainder plus the reduced target:

$$T’ = T(1-f) + \frac{Tf}{s}$$

Dividing the original time by the new time gives the overall speedup:

$$S = \frac{1}{(1-f) + f/s}$$

Two limits follow directly. As $s$ grows without bound, the second term vanishes and $S$ approaches $1/(1-f)$. That asymptote depends only on $f$, never on the quality of the optimization. With $f = 0.9$ the ceiling is 10x; with $f = 0.5$ it is 2x; with $f = 0.1$ it is about 1.11x. The other limit is at $s = 1$, where $S = 1$ by construction.

def speedup(fraction: float, factor: float) -> float:
    """Overall speedup when `fraction` of the time is cut by `factor`."""
    return 1.0 / ((1.0 - fraction) + fraction / factor)

for f in (0.1, 0.5, 0.9):
    row = [f"{speedup(f, s):.2f}" for s in (2, 4, 10, 100)]
    print(f"f={f:.1f}  s=2,4,10,100 -> {row}  ceiling={1/(1-f):.2f}")

The printed table makes the shape visible. At $f = 0.5$, doubling the speed of the target yields 1.33x overall; quadrupling yields 1.60x; a tenfold improvement yields 1.82x. Each additional factor of two in the local speedup buys progressively less, because the untouched half of the program sets the floor. At $f = 0.9$, the same local improvements pay much better, and the ceiling is far away.

The practical consequence is that the ceiling should be computed before the effort is estimated. A candidate whose ceiling is 1.05x is not worth a week of work if measurement noise on the relevant workload is five percent, while a candidate whose ceiling is 1.6x may justify substantial restructuring. This is the first filter in expected-payoff ranking, where the ceiling is combined with an estimate of the achievable factor to produce a single comparable number per candidate.

Marginal return and the last doubling

The derivative of the speedup curve matters more than the curve itself. Going from $s = 1$ to $s = 2$ on a fraction $f$ captures a large share of the total available gain; going from $s = 10$ to $s = 20$ captures very little. For $f = 0.5$:

local factor $s$	overall $S$	share of the 2x ceiling reached
2	1.33	33%
4	1.60	60%
10	1.82	82%
100	1.98	98%

Half of the achievable improvement arrives with the first doubling. The rest costs increasingly specific machinery: special-cased fast paths, hand-written kernels, data layout changes that ripple through the codebase. That is why the last doubling of a hot routine is usually a poor trade, and why the arithmetic should be run at the point where a candidate is proposed rather than after it has been half-implemented.

There is a second, subtler form of diminishing return. The measured fraction $f$ is not a constant of the program; it is a property of the program and its input mix. After a change lands, the profile renormalizes. The optimized fraction shrinks, every other fraction grows, and the next candidate’s ceiling is lower than the same candidate’s ceiling computed on the original profile. Optimizations interact through the denominator, not through the numerator, so gains from disjoint candidates add in the denominator of $S$ rather than multiplying cleanly.

Combining candidates without double counting

Two changes that each yield 1.2x do not generally produce 1.44x. If both target the same fraction of time, they act on the same denominator term, and the combined local factor is the product only if the second change survives the first (a faster algorithm may make a micro-optimization inside it irrelevant). If they target disjoint fractions $f_1$ and $f_2$ with local factors $s_1$ and $s_2$, the combined speedup is

$$S = \frac{1}{(1 - f_1 - f_2) + f_1/s_1 + f_2/s_2}$$

which is additive in saved time, not multiplicative in speedup. Summing per-candidate percentages from a profile and treating the total as a predicted speedup is the most common arithmetic error in optimization planning. Saved time adds; speedup ratios do not.

The same arithmetic explains why a set of small wins can still be worth doing when they land on different parts of the time budget, and why a set of large-looking wins on the same hot loop collapses into one. It also gives a defensible order of work: apply the change with the largest saved time first, re-measure, then recompute the remaining candidates against the new profile. The critical path article covers the case where the time being saved is not elapsed time at all but one stage of a pipeline whose other stages do not shrink.

Where the fixed-work assumption breaks

Amdahl’s formulation holds the amount of work constant and asks how much faster a fixed job completes. That is the right question for a batch job with a deadline. It is the wrong question for a server whose demand expands to fill available capacity, and the difference is not cosmetic.

Gustafson’s scaled formulation makes the alternative explicit: if the problem size grows with the available parallelism, the serial fraction’s weight in the total work shrinks, and the achievable speedup grows roughly linearly rather than approaching a constant. Applied to a throughput system, the analogous statement is that reducing time in a stage raises capacity in proportion to that stage’s share, until some other stage becomes the limiter. The ceiling then belongs to the next bottleneck, not to the fraction just optimized.

This is why a change that yields 1.15x on a single request can still be valuable: if the optimized stage was the throughput limiter and demand is elastic, the capacity gain is what matters, and the per-request ratio understates it. Conversely, a change that yields 1.5x on a request whose stage was never the limiter may free capacity that nothing can use. The objective has to be stated before the arithmetic is applied; choosing an objective for a workload mix treats that choice as a design decision rather than a given.

What the law does not bound

Three costs sit outside the formula and are routinely omitted from the decision.

The first is the cost the optimization itself adds to the unoptimized path. A memoization layer charges a lookup on every call, including the misses; a specialized fast path charges a branch and a duplicated code path that must be maintained and tested. If the added cost applies to the fraction $(1-f)$, the denominator grows and the real speedup is smaller than the model predicts. Cache hit-rate break-even derives the threshold at which that added cost is repaid.

The second is memory and complexity. Amdahl’s law bounds time only. A change that halves the time of a stage by tripling its working set may lose overall once the memory system is under pressure, and a change that duplicates logic to gain a constant factor has a maintenance cost that compounds for the life of the code.

The third is measurement error. A ceiling of 1.08x on a workload whose run-to-run variation is several percent cannot be distinguished from no change at all. The law is most honest when used as a rejection filter: it reliably eliminates candidates whose ceiling is too small to matter, and it only weakly predicts the payoff of the candidates that survive. The decision to stop pursuing a line of work entirely, once the remaining fractions are small, is the subject of recognizing the optimization plateau.