The question this answers
The work is spread across eight threads and the speedup is 1.05 — where did the parallelism go?
A document indexer: eight worker threads parse documents independently, then insert their terms into one shared inverted index guarded by a single global mutex.
One inverted index and one mutex over it. The parsing — which is 90% of the CPU work — shares nothing at all, which makes the failure especially frustrating: the parallelisable part really is parallelisable, and it never gets to run in parallel.
Every term in every parsed document appears in the index exactly once per occurrence. That is preserved perfectly by the global lock. The property that fails is not correctness but the *reason for the threads to exist*: total throughput should grow with worker count, and here it does not grow at all.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The flat curve
The clearest way to see false parallelism is to plot throughput against worker count and look at the shape. Real parallel speedup rises, bends, and plateaus. False parallelism does not have a bend — it is essentially flat from one worker onward, and after a point it goes *down*, because the extra workers add contention and context switches without adding throughput.
The number to hold on to is effective parallelism: total throughput divided by single-worker throughput. If eight workers deliver 1.05× the work of one, your effective parallelism is 1.05, and you are running a serial program with eight threads' worth of overhead. The curve below is that measurement.
The cause is arithmetic and unavoidable. If each document takes 900 µs of parsing and 100 µs inside the lock, the lock can serve at most 10 000 documents per second, and no worker count exceeds that. This is Amdahl's law with a serial fraction of 10% — see Amdahl's Law — and the maximum speedup at that fraction is 10×, reached only at infinite workers. Push the locked portion to 50% and the ceiling is 2×; push it to 90% and it is 1.1×, which is what the curve shows.
Eight threads taking turns
The trace makes the mechanism concrete. Each worker parses independently — genuinely in parallel, genuinely using its own core — and then queues at the same door. Because the lock section is long relative to the parsing, the queue never empties, and each worker's parse of the next document does not start until it has been let through.
Follow the parallel workers state value. It reaches 8 briefly at the very start, when all workers are parsing their first document, and then collapses to 1 for the rest of the run. That collapse is the whole phenomenon: the parallel phase exists, and it is over within one document because the workers immediately fall into a queue and stay there, arriving one at a time forever after.
This is also where the difference between concurrency and parallelism becomes practical rather than definitional. The program is *concurrent* — eight independent tasks overlapping in time. It is not *parallel* in any useful sense — one core's worth of work is being produced. See Which One Does This Workload Need?; the distinction is not pedantry, it is the difference between a program that scales and one that does not.
| # | Worker 1 | Worker 2 | Workers 3–8 | State |
|---|---|---|---|---|
| 1 | · | · | all 8 workers parse their first document (900 µs each) | t=0 µs parallel workers=8 docs indexed=0 |
| 2 | lock(index) — acquired; inserts terms (100 µs) | · | · | t=900 µs parallel workers=1 docs indexed=0 queue=7 |
| 3 | · | lock(index) — blocks | · | t=901 µs parallel workers=1 queue=7 |
| 4 | · | · | workers 3–8 all block on the same lock | t=902 µs parallel workers=1 queue=7 cores idle=7 ✕ Scaling: seven cores are idle while seven threads wait on one mutex. From here the system produces one core's worth of output regardless of how many workers exist. |
| 5 | releases at t=1000 µs; resumes parsing document 2 | · | · | t=1000 µs docs indexed=1 queue=6 |
| 6 | · | acquires; inserts (100 µs) | · | t=1000 µs parallel workers=1 docs indexed=1 |
| 7 | · | · | ... the queue is served one at a time, 100 µs each | t=1700 µs docs indexed=8 queue=0 |
| 8 | finishes parsing doc 2 at t=1900 µs and rejoins the queue | · | · | t=1900 µs queue=1 steady rate=10 000 docs/s |
Fixing it: give each worker its own state
The fix for false parallelism is almost never a better lock. It is to notice that the workers do not actually need a shared index *while they are working* — they need one at the end. Build eight local indexes, one per worker, and merge them once. The lock disappears; the merge is a single pass over eight structures and takes a fraction of the time the contention was costing.
This is the general shape and it is worth naming: accumulate privately, combine once. It is the same move as a parallel reduction (Parallel Reduce), the same move as per-thread metric counters, and the same move as map/reduce (The Map/Reduce Pattern). What makes it applicable is that the operation is associative — merging two partial indexes gives the same result as inserting into one — which is a property to check, not to assume.
When the shared structure genuinely must be live throughout — a cache other requests are reading — the fallback is sharding, which converts one 100% contended lock into sixteen locks each contended a sixteenth as often. Both moves attack the same term: the fraction of time a worker spends in a region that only one worker can occupy. That fraction *is* your parallelism ceiling, and everything else is detail.
1const index = new InvertedIndex()2const indexLock = new Mutex()3 4async function worker(docs: AsyncIterable<Doc>) {5 for await (const doc of docs) {6 const terms = parse(doc) // 900 us, fully parallel7 await indexLock.acquire() // ... and then everyone queues here8 try { for (const t of terms) index.add(t, doc.id) } // 100 us serial9 finally { indexLock.release() }10 }11}12// effective parallelism at 8 workers: ~1.051async function worker(docs: AsyncIterable<Doc>): Promise<InvertedIndex> {2 const local = new InvertedIndex() // owned by this worker alone3 for await (const doc of docs) {4 const terms = parse(doc) // 900 us, parallel5 for (const t of terms) local.add(t, doc.id) // 100 us, ALSO parallel6 }7 return local // no shared state was touched8}9 10const partials = await Promise.all(shards.map(worker))11const index = partials.reduce(merge, new InvertedIndex()) // once, at the end12// effective parallelism at 8 workers: ~6.4 (bounded now by memory13// bandwidth and uneven document sizes, not by a lock)The shared index was never required during the run — only at the end. Removing it makes the 100 µs insert parallel as well, so the serial fraction drops from 90% to the cost of one merge. The requirements are that merge is associative and that per-worker memory is affordable; if the index must be queryable during the run, shard it instead and accept 16 smaller serial regions rather than one large one.
Key points
- False parallelism is a program that is concurrent in structure and serial in execution — parallel threads that all queue at the same lock.
- Measure effective parallelism: throughput at N workers divided by throughput at one. If it is near 1.0, the threads are decoration.
- The ceiling is set by the fraction of time spent in the exclusive region, exactly as Amdahl describes; core count does not enter into it.
- The fix is usually to give each worker private state and merge once, not to make the shared lock faster.
- Past the ceiling, adding workers makes throughput fall, because overhead grows while the ceiling does not.
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.
- • Each worker performs independent work that genuinely uses its own core.
- • Each worker then enters a region that only one worker may occupy at a time.
- • Because the exclusive region is a significant fraction of the per-item cost, workers arrive faster than the region can serve them and a permanent queue forms.
- • Steady-state throughput becomes 1 / (exclusive-region time), independent of worker count, while the parallel portion sits idle waiting.
- • Additional workers add memory, scheduling and wakeup overhead on top of an unchanged ceiling, so measured speedup declines.
- • One worker: parse 900 µs, insert 100 µs, repeat. 1 000 docs/s per worker with no contention.
- • Eight workers, first round: all parse in parallel; the first to finish takes the lock and the other seven queue. Parallelism 8 for 900 µs, then 1 forever.
- • Eight workers, steady state: the lock is busy 100% of the time and serves one insert per 100 µs — 10 000 docs/s total, the same figure eight independent single-threaded processes would beat.
- • Sixteen workers: identical ceiling, plus 16 threads' context switches and wakeups, so measured throughput falls below the eight-worker figure.
- • Private accumulation: no worker ever waits; all eight parse and insert simultaneously; the only serial step is one merge at the end whose cost is amortised over the whole run.
- • A global lock guarantees the index is never corrupted and never observed mid-update. It guarantees nothing about throughput, and it caps it silently.
- • Running N threads guarantees N *tasks* can be in flight. It does not guarantee N-way parallel execution — that depends entirely on whether they are ever runnable at the same time. See Async Is Not Parallelism for the async version of the same confusion.
- • Private accumulation guarantees the same final index only if the merge is associative and the per-item operation commutes; for counters and postings lists it does, for order-sensitive structures it may not. See Reduction Ordering: The Sum Changed When the Worker Count Did.
- • Sharding guarantees per-shard exclusivity and gives up a globally consistent instantaneous view.
- • A speedup measured on an idle laptop guarantees nothing about a loaded server, where the memory bandwidth and cache the parallel portion depends on are shared with everything else.
- • Contention here is total: the exclusive region is busy 100% of the time in steady state, so every arriving worker waits by definition.
- • The wait per worker is (N−1) × region time, which grows linearly with worker count while throughput stays flat — this is why latency degrades even as throughput does not improve.
- • Beyond the ceiling, each additional worker contributes a wakeup, a context switch and cache pressure per item without contributing output.
- • The parallel portion still competes for memory bandwidth and cache, so the "free" part of the work is not free either — see Memory Bandwidth: More Cores, Same Bus.
- • Flat or declining scaling curve — the primary signature, and it requires actually running the experiment at several worker counts.
- • Latency growth with no throughput growth, which capacity planning based on throughput alone will miss entirely.
- • The scaling illusion in reverse: horizontal scaling appears to work (each instance has its own lock) while vertical scaling does nothing, leading to a much more expensive deployment than necessary.
- • Convoy formation on the global lock once any holder stalls. See Lock Convoys.
- • Effort misdirected into optimising the parallel portion, which is not the bottleneck and whose improvement changes nothing.
- • A global lock is the right starting point: it is simple, obviously correct, and often uncontended. False parallelism is a problem of scale, not a design error at small scale.
- • It genuinely helps when the exclusive region is a tiny fraction of per-item work — a 1% serial fraction gives a ceiling of ~100×, which no realistic machine will reach anyway.
- • It helps when the threads exist for latency rather than throughput: overlapping I/O waits benefits from concurrency even when the CPU portion is serialised. See Classifying the Work: Computing or Waiting?.
- • Whenever the exclusive region is a double-digit percentage of per-item cost — then the ceiling is low enough to be the dominant fact about the system.
- • When the shared structure is only needed at the end, which makes the entire cost avoidable.
- • When it drives a scaling decision: a team that never measured effective parallelism buys larger machines that cannot help, or more instances that could have been fewer.
- • Run at 1, 2, 4, 8 and 16 workers on the same input and plot throughput. The shape answers the question; a single-point measurement cannot.
- • Effective parallelism = throughput(N) / throughput(1). Report this number rather than "we parallelised it"; it is the only honest summary.
- • Lock held-percentage on the suspected global lock. If it is near 100%, the ceiling is 1/hold-time and nothing else matters until that changes.
- • A wall-clock profile or off-CPU analysis, since a CPU profile of a lock-bound program shows the parsing code and hides the waiting entirely. See
flame-graphs. - • Compare against N independent single-threaded processes on the same box. If they beat the threaded version, the shared state is the entire problem.
- • Private accumulation costs memory proportional to worker count and requires a merge step whose cost must be checked against the contention it removes.
- • The merge introduces an ordering question for anything not perfectly associative — floating-point sums are the classic case. See Reduction Ordering: The Sum Changed When the Worker Count Did and Determinism: Same Input, Same Output?.
- • Sharding adds a shard count, a hash, and cross-shard operations that need their own ordering discipline.
- • Measuring effective parallelism requires a repeatable benchmark harness, which is real work most teams have not done — and without it, every claim in this area is folklore.
- • Independent processes with no shared structure, merged at the end by a file or a database write — often simpler than threads and immune to this failure.
- • A concurrent data structure with internal striping or lock-free insertion, which turns one serial region into many. See Lock-Free Is a Progress Guarantee and its honest caveats.
- • Batching: accumulate 1 000 terms locally and take the lock once, which reduces the serial fraction by the batch factor without changing the design.
- • Accept the ceiling and scale horizontally, when the exclusive region is genuinely irreducible — but do so knowing the number, not by accident.
What people believe, and what is true
We used eight threads, so the work is eight-way parallel.
Thread count is what you requested; effective parallelism is what you got. Measure throughput(8)/throughput(1) — if it is 1.05, the eight threads are executing serially with extra overhead.
The lock is fine because the critical section is short.
Short relative to what? A 100 µs section against 900 µs of parallel work is a 10% serial fraction and a hard ceiling of 10×. "Short" only means anything as a ratio.
The fix is a faster or fairer lock.
A faster lock raises the ceiling proportionally to how much faster it is, which is usually a few percent. Removing the shared structure removes the ceiling. Attack the sharing, not the primitive.
Go deeper
Overview
Eight threads all queue at one lock, so eight cores produce one core's worth of work. The program looks parallel and executes serially.
Practical
Measure throughput at 1, 2, 4 and 8 workers. If the curve is flat, find the lock that is held ~100% of the time and ask whether the state it protects is needed during the run or only at the end. Usually it is only needed at the end.
Advanced
Effective parallelism is the honest unit of account for any parallel change, and it is bounded above by 1/(serial fraction). Knowing that fraction before writing the code tells you whether the work is worth doing — a 20% serial fraction caps you at 5× regardless of hardware, and no engineering effort on the parallel portion changes that number.
Internals
Amdahl and Gustafson answer different questions and both apply. Amdahl fixes the problem size and asks how much faster it can go: the answer is 1/s, and it is brutal. Gustafson fixes the *time* and asks how much bigger a problem you can solve: the answer is much more encouraging, and it is the reason large-scale parallelism is worth building at all. See Gustafson's Law and Work and Span.