Symptom
The profile was unambiguous: 94% of wall-clock time in one loop, and the loop’s iterations are independent. You parallelise it across sixteen cores, the flame graph flattens exactly as predicted, and the end-to-end time goes from 40 seconds to 17.
Not 2.5 seconds. Seventeen. And the machine with 64 cores gives you 14.
Nobody made a mistake. The 6% you did not touch is now the entire story, and it will stay the entire story no matter what hardware you buy. The arithmetic that says so is one line long, and running it before the sprint rather than after is most of what this post is for.
Statement
Let $p$ be the fraction of the work that can be parallelised, so $1-p$ is the serial fraction — the part that must happen in order, on one worker, no matter how many are available. With $N$ workers:
The second equation is the one with teeth. The speedup ceiling depends only on the serial fraction, and $N$ has disappeared from it entirely. Five percent serial caps you at 20×. One percent caps you at 100×. There is no quantity of hardware that moves either number.
Argument
There is no proof technique here to admire; it is division, and that is exactly why the law is trustworthy. It follows from the definition of “serial” and nothing else — no assumptions about the hardware, the scheduler, the memory system, or the workload.
Total time on one worker is the serial part plus the parallel part:
$$T(1) = T_s + T_p$$Give the parallel part $N$ workers and it takes $T_p/N$; the serial part is unchanged, because that is what serial means:
$$T(N) = T_s + \frac{T_p}{N}$$Normalise $T(1) = 1$, so $T_s = 1-p$ and $T_p = p$. Speedup is the ratio:
$$S(N) = \frac{T(1)}{T(N)} = \frac{1}{(1-p) + p/N}$$Let $N \to \infty$ and the second term vanishes, leaving $1/(1-p)$.
The corollary worth memorising. Ask when you reach half of the theoretical ceiling. Set $S(N) = S(\infty)/2$:
$$(1-p) + \frac{p}{N} = 2(1-p) \quad\Longrightarrow\quad \frac{p}{N} = 1-p \quad\Longrightarrow\quad N = \frac{p}{1-p}$$At $p = 0.95$ that is $N = 19$. Nineteen cores gets you halfway to the 20× limit — to 10×. Getting from 10× to 15× costs another 38 cores. Getting to 19× is several hundred. The ceiling is not approached; it is asymptoted at, expensively.
Measuring $p$ instead of guessing it. The law is only useful if you know the serial fraction, and the profiler’s answer is not it. Rearranging $S(N)$ for the serial fraction gives the Karp–Flatt metric: from a single measured speedup $S$ on $N$ workers,
$$e = \frac{1/S - 1/N}{1 - 1/N}$$where $e$ is the experimentally determined serial fraction — everything that failed to parallelise, including the coordination costs the profiler never attributed to your loop.
Run the opening example through it. The profiler said 6% serial, which predicts $S(16) = 1/(0.06 + 0.94/16) = 8.4$ and a 4.8-second run. The measurement was 40 → 17, so $S = 2.35$, and
$$e = \frac{1/2.35 - 1/16}{1 - 1/16} = \frac{0.4255 - 0.0625}{0.9375} = 0.39$$The effective serial fraction is 39%, not 6%. The gap between those two numbers is the finding: thirty-three points of the workload are being spent on something that is not the loop and is not in the flame graph — false sharing, allocator contention, a mutex around a shared accumulator, thread startup. The ceiling is not 16×; it is 2.6×, and the 64-core machine’s 16 seconds was a fair approximation of it. Karp–Flatt run at two different $N$ values is more informative still: if $e$ stays flat as $N$ grows, the serial part is genuinely serial; if $e$ climbs, you are paying coordination overhead that will get worse.
Efficiency makes it starker. At $p = 0.95$ and $N = 64$, $S = 15.4$, so each core delivers 24% of a core. Three quarters of a machine you are paying for, idle by arithmetic.
| $p$ | ceiling $S(\infty)$ | $N$ for half the ceiling |
|---|---|---|
| 0.50 | 2× | 1 |
| 0.90 | 10× | 9 |
| 0.95 | 20× | 19 |
| 0.99 | 100× | 99 |
| 0.999 | 1000× | 999 |
Forbids
Linear scaling of a fixed workload. Any nonzero serial fraction bounds speedup by a constant. This kills “we will scale it later by adding cores” as a plan, unless someone has measured $p$.
Buying your way out of a serial section. If a request holds a global lock for 2 ms, no amount of parallelism below that lock reduces the 2 ms, and the p99 will not move. The only available action is removing the lock.
Order-of-magnitude wins from small $p$. To get 100× from parallelism, at least 99% of the work must parallelise. Most code that has never been measured is nowhere near that, and the measurement usually takes an afternoon.
Interpreting a scaling test as a scaling projection. Two data points cannot distinguish $p = 0.95$ from $p = 0.99$, and those differ by 5× at the ceiling.
Does not forbid
It does not say parallelism is not worth it. “Amdahl proves there is no point past eight cores” is a real thing people say, and it is not a statement about anything. The ceiling is $1/(1-p)$, and $p$ is a property of your program that you can go and measure this afternoon. For $p = 0.99$ the law permits 100×. It forbids nothing until you know the number.
It does not apply when the problem grows. This is the largest misreading and it has its own post: Amdahl assumes the workload is fixed. Rendering farms, model training, and nightly ETL do not have a fixed workload — given a bigger machine, they run a bigger problem in the same time, and the serial fraction of that scaled workload is smaller. Gustafson’s law (T082) is the same algebra asked the other way round, and it gives a speedup linear in $N$. Which law applies is decided by one question: is the problem size pinned?
It does not govern throughput scaling of independent work. A stateless HTTP service behind a load balancer is not one job being split; it is many jobs being run. Doubling the replicas doubles the throughput, and Amdahl has nothing to say until a shared resource — the database, a cache, a coordination service — becomes the serial part. Applying the law to horizontal scaling of independent requests confuses a latency bound with a throughput one.
It does not say $p$ is fixed. The most consequential misreading, because it
turns a diagnosis into a fatalism. The serial fraction is a property of the
implementation, not of the problem. Per-CPU counters in the Linux kernel, RCU
replacing reader-writer locks, lock striping in ConcurrentHashMap, and sharded
counters in every high-write database are all the same engineering move: someone
looked at the serial part and discovered most of it was not essential. Amdahl
tells you what $p$ costs you. It says nothing about how small $p$ can be made.
Superlinear speedup is not a refutation. Measured speedups above $N$ are real and are usually cache: a working set that does not fit in one core’s L2 fits in the aggregate L2 of eight. The law models time, not memory hierarchy, so this is outside its scope rather than against it.
Boundary
- Scale the problem instead of the machine. Gustafson (T082), and the HPC distinction between strong scaling (fixed problem, Amdahl) and weak scaling (problem grows with $N$, Gustafson).
- Amdahl is the optimistic bound. It has no term for coordination, so it can only ever be too generous. The Universal Scalability Law adds a negative term and predicts that past some $N$ the throughput falls — also T082, and the more useful curve for a distributed system.
- Attack $p$, not $N$. Almost always the higher-return work, and the law is what tells you how much a given reduction is worth before you attempt it.
- Latency versus throughput. Amdahl is a statement about one job’s elapsed time. For a system serving many jobs, Little’s law (T083) and the utilisation curve (T084) are the relevant results, and they will bite long before the parallel ceiling does.
- Amortise the serial part. If the serial section is a fixed setup cost, its fraction shrinks as the parallel work grows — which is, in one sentence, the entire content of the next post.