The question this answers
I doubled the workers and got 1.4x. Which of the five things that eat speedup is eating mine?
A batch job that scores ten million records, run with 1, 2, 4, 8 and 16 workers on one machine, timed end to end each time.
A read-only model shared by all workers, a per-worker output buffer, one shared progress counter, and — invisibly — the memory bus, the last-level cache and the run queue, which are shared whether or not your program mentions them.
Every record is scored exactly once and the set of output rows is identical at every worker count. Speedup may vary; the result may not.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The curve, and what the gap under the ideal line is made of
Plot speedup against workers and you get a curve that starts near the diagonal, bends away from it, and eventually flattens or turns down. Nobody is surprised by this in the abstract and almost everybody is surprised by the specific numbers — 8 workers giving 4.5x means each worker is running at 56% efficiency, and half your machine is producing nothing.
The single most useful reframing is to stop asking "why is it not 8x" and start asking "which of these five is my gap": the serial fraction, synchronization, memory bandwidth, cache-coherence traffic, and scheduling overhead. They are additive, they have different signatures, and the fix for each is different. Guessing wrong is expensive — most teams reach for locks when their problem is bandwidth, or buy cores when their problem is a serial prologue.
The curve also tells you where to stop. Between 8 and 16 workers this job gains 0.4x for double the resources, which is a 6% efficiency point. If those are cloud cores you are paying twice for a rounding error; if the curve turns *down*, as it does past 16 here, you are paying twice to be slower (More Threads Is Not More Speed).
- Efficiency = speedup / workers. Track it, not speedup — it makes the loss visible instead of the gain.
- A curve that bends early points at a serial fraction; one that bends suddenly at a particular width points at a saturated shared resource.
- A curve that turns down means the marginal worker costs more than it produces. That point is a capacity decision, not a mystery.
Five causes, five different tells
The serial fraction is Amdahl's (Amdahl's Law): whatever must run once — reading the config, loading the model, sorting the final output — sets a hard ceiling of 1/s regardless of hardware. With a 10% serial fraction the ceiling is 10x, so 4.5x at eight workers is not even the binding constraint yet. Its tell is that the *absolute* serial time is constant across worker counts, which you can see directly by timing the phases.
Synchronization is time workers spend waiting for each other: locks, barriers, joins, a shared queue head. Its tell is that CPU utilization does not reach 100% as you add workers, and lock-wait time grows superlinearly (What Contention Actually Costs). Memory bandwidth is the opposite tell — utilization looks fine, instructions retired per cycle falls, and per-worker throughput drops in exact proportion to the worker count (Memory Bandwidth: More Cores, Same Bus).
Coherence traffic shows up when workers write to memory that is close together: False Sharing: Different Variables, Same Cache Line on adjacent counters, or genuine sharing of a hot object. Its tell is dramatic and specific — a tiny padding change fixes it completely. And scheduling overhead is the tell of oversubscription: far more runnable threads than cores, involuntary context switches climbing, and time going to migration and cache refill rather than work (Oversubscription, The Cost of a Context Switch).
| Cause | Signature in the numbers | What to measure | Fix | Cost of the fix |
|---|---|---|---|---|
| Serial fraction | Curve bends immediately; ceiling is 1/s | Absolute time of each phase at each width | Parallelize or remove the serial phase; overlap it with setup | Often a redesign; sometimes impossible |
| Synchronization | CPU never reaches 100%; lock wait grows superlinearly | Lock wait time, blocked-thread count, queue head contention | Shrink the critical section; shard the lock; use per-worker state | More state to combine; more code |
| Memory bandwidth | CPU looks busy; IPC falls; per-worker throughput drops ~1/N | Instructions per cycle, bytes moved per second | Improve locality; compress; do more arithmetic per byte | Algorithmic work, sometimes a data layout change |
| Coherence traffic | Sudden collapse at a specific width; padding fixes it | Cache-line contention events; which lines are shared | Pad to line boundaries; per-worker accumulators | Memory footprint; a subtle, easily-reverted change |
| Scheduling / oversubscription | Curve turns down past core count; involuntary switches climb | Runnable threads vs cores; context switch rate | Size the pool to the machine; stop nesting parallelism | Requires knowing the real core budget, including siblings |
Watching the eight lanes
The timeline is the same run drawn as lanes, and it shows why an aggregate speedup number hides so much. There is a serial prologue where seven workers do not exist yet, a parallel region where they mostly run, a barrier where the fast workers wait for the slow one, and a serial epilogue where one worker merges. The wall clock is the sum of all four, and only the second one benefits from more cores.
The load skew at the barrier is worth naming separately because it is so common and so easy to fix. If chunks have uneven cost, seven workers finish early and idle while the eighth grinds — the barrier waits for the maximum, not the average. Smaller chunks with dynamic assignment, or Work Stealing, converts that idle time back into work, and it is frequently the cheapest speedup available in an existing parallel job.
Finally: measure the whole thing, not the parallel region. It is completely normal for a parallel region to show 7.6x while the job shows 4.5x, and to spend a week optimizing the region for no end-to-end gain at all. That mistake has a name in Performance — Microbenchmark or End-to-End: Why p99 Did Not Move — and parallel work is where it happens most.
Key points
- Speedup is sublinear because five distinct costs eat into it, each with a different signature and a different fix.
- Track efficiency (speedup / workers), not speedup: 8 workers at 4.5x is 56% efficiency, which is the number that prompts action.
- A curve that bends immediately means a serial fraction; a curve that bends sharply at a particular width means a shared resource just saturated.
- A curve that turns down means the marginal worker costs more than it produces — usually oversubscription or contention.
- Measure end-to-end, not the parallel region: a 7.6x region inside a 4.5x job means the serial parts are where the remaining work is.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Split the job into a serial prologue, a parallel region and a serial epilogue; the first and last do not shrink with worker count.
- • Inside the parallel region, each worker's effective rate is reduced by time waiting on locks, time waiting at the barrier, and time stalled on memory.
- • Shared resources saturate at some width — memory bus first for streaming work, last-level cache for working sets that stop fitting, coherence for shared lines.
- • Beyond the core count, additional workers do not add throughput; they add context switches, cache pollution and run-queue pressure, so the curve turns down.
- • The observed speedup is the composition of all of these, which is why a single-cause explanation is nearly always wrong.
- • The benign one: eight workers process disjoint chunks and never observe each other. Correct under every schedule; the only cost is on shared hardware, which no schedule reveals.
- • The one that costs 3% here: W1 reads progress (14,220); W3 reads progress (14,220); W1 writes 14,221; W3 writes 14,221 — one increment lost. The count is wrong and every worker also serialized on that cache line to get it wrong.
- • The barrier schedule: W0..W6 arrive and block; W7 arrives 18 units later; all eight resume. Seven workers were correct, idle, and irrelevant for 18% of the run.
- • The oversubscription schedule: 24 runnable workers on 8 cores means the scheduler rotates them; each worker's cache working set is evicted by the two that ran in between, so every quantum starts with a cold cache (Parallelism Can Destroy Locality).
- • The nested-parallelism schedule: the parallel region calls a library that itself parallelizes, producing 64 runnable threads on 8 cores, and the curve turns down without anything in your code changing.
- • Parallelizing guarantees the same results at every worker count *only* for order-independent computations. Floating-point reductions are not order-independent — see Reduction Ordering: The Sum Changed When the Worker Count Did.
- • Disjoint chunk assignment guarantees no write-write conflicts on the output, with no synchronization.
- • A barrier guarantees every worker reached it and that prior writes are visible afterwards — and guarantees nothing about how long the slowest worker took to get there.
- • Nothing guarantees a speedup at all. Adding workers can and does make jobs slower, and no runtime warns you.
- • Nothing guarantees the curve is stable across machines: core count, cache sizes, memory channels and co-tenants all move it.
- • Lock and barrier waiting is the visible contention, and it is measurable directly as blocked time per worker.
- • The memory bus and the last-level cache are contended by every worker whether or not your program has a single lock; this contention is invisible in thread dumps.
- • The run queue is contended when runnable threads exceed cores, adding migrations and involuntary switches that cost cache warmth rather than CPU time.
- • One shared counter updated per item is enough to serialize eight workers on a single cache line — the cheapest-looking line of code in the loop, and often the most expensive.
- • Negative scaling: more workers, longer wall clock, with no error and no obvious culprit.
- • Load skew leaving most workers idle at a barrier while one grinds — the aggregate looks like "insufficient parallelism", the fix is chunking.
- • Optimizing the wrong cause: adding lock-free structures to a bandwidth-bound job, or buying cores for an Amdahl-bound one.
- • Benchmarking only the parallel region and shipping a change that moves nothing end to end.
- • Nested parallelism producing an oversubscription cliff that appears only under production load, when both levels are active at once.
- • Measuring on an idle developer machine and deploying to a container with a fraction of the cores and a noisy neighbour.
- • Running the scaling study at all: 1, 2, 4, 8, 16 workers, same input, same machine, times recorded. It is a couple of hours and it decides where the next month goes.
- • Whenever a capacity decision is on the table: the curve tells you what the next core is worth, in the only units that matter.
- • As a regression guard — a scaling curve that got worse between releases is a specific, actionable signal that an aggregate throughput number would hide.
- • When the measurement is done badly: a warm-cache second run, an idle machine, or a benchmark input that fits in cache when production data does not — all produce optimistic curves that will not survive.
- • When the curve becomes the goal. Efficiency at 16 workers is irrelevant if you only ever run 4.
- • When it is used to justify parallelizing at all: a job that runs for 200ms does not need a scaling study, it needs to be left alone (Parallel Overhead).
- • Wall clock at 1, 2, 4, 8, 16 workers on the same input and machine — the study itself, and the thing most teams have never actually run.
- • Per-phase absolute time at each width; the phases that stay constant are your serial fraction, measured rather than estimated.
- • CPU utilization plus instructions-per-cycle together: busy-with-low-IPC is memory, not-busy is synchronization. This pair distinguishes the two most-confused causes.
- • Blocked time and lock wait per worker, and time spent at barriers, so waiting is attributed rather than lumped into "overhead".
- • Involuntary context switches and thread migrations per second, to detect oversubscription before it shows up as a downward curve.
- • A scaling study needs a repeatable environment — pinned inputs, a quiet machine, cold-start control — which is real infrastructure work, and without it the numbers mislead.
- • Attributing the gap requires several tools at once (a profiler, hardware counters, lock instrumentation), and interpreting them together is a skill the team has to build.
- • Fixes are structural: removing a serial phase, resharding a lock, changing a data layout. None are local edits, and each carries its own correctness risk.
- • The curve must be re-measured after every fix, because fixing the binding constraint promotes the next one and the diagnosis changes.
- • Make the single-threaded version faster first. A 3x algorithmic win applies at every worker count and adds no coordination risk.
- • Run more independent copies of the whole job (process-level parallelism over separate inputs) instead of parallelizing inside one — no shared state, near-linear scaling, and much simpler.
- • Accept the sublinear curve and buy the cores anyway, when they are cheap relative to engineering time and the curve is still rising.
- • Move the work off the critical path entirely, when the deadline rather than the throughput is the real requirement.
Why is 8 cores only 4.5×?
| workers | ideal | Amdahl only | realistic | limited by |
|---|---|---|---|---|
| 1 | 1.0× | 1.00× | 1.00× | none |
| 2 | 2.0× | 1.90× | 1.85× | serial |
| 4 | 4.0× | 3.48× | 3.19× | serial |
| 6 | 6.0× | 4.80× | 4.17× | serial |
| 8 | 8.0× | 5.93× | 4.17× | bandwidth |
| 10 | 10.0× | 6.90× | 4.17× | bandwidth |
| 12 | 12.0× | 7.74× | 4.17× | bandwidth |
| 14 | 14.0× | 8.48× | 4.17× | bandwidth |
| 16 | 16.0× | 9.14× | 4.17× | bandwidth |
Amdahl's law: the serial ceiling
s = 0.10 n = 32
Amdahl S(n) = 1 / (s + (1 − s)/n) = 7.805× ← fixed problem, more machine
S(1 000 000) = 10.000× ← a million cores, and still under 10×
Gustafson S(n) = s + n(1 − s) = 28.900× ← fixed time, bigger problemEight threads, one lock
More workers than cores
What people believe, and what is true
Sublinear scaling means we did not parallelize enough of the code.
Usually it means a shared resource saturated, or the serial fraction is binding. More parallel code does not help either of those, and can make both worse.
The parallel region scales at 7.6x, so the job scales well.
The job scales at whatever the whole wall clock does. Serial prologue plus epilogue plus barrier idle is routinely 20-40% of a run.
If CPU utilization is high, we are using the cores well.
A core stalled waiting for memory is counted as busy. High utilization with falling instructions-per-cycle is the bandwidth signature, not a healthy one.
More workers can only help or do nothing.
Past the core count the curve turns down. Context switching, cache pollution and contention are real costs that grow with worker count.