The question this answers
What does concurrency cost, and how do I decide whether this workload can afford it?
A nightly reconciliation job over 40 000 orders. It runs in 11 minutes sequentially. A four-way parallel version runs in 3.5 minutes and took two weeks to make correct.
In the sequential version: nothing. In the parallel version: a shared "already reconciled" set, a shared error accumulator, a database connection pool, and a progress counter — four pieces of state that did not exist before and each of which needs an invariant.
Every order is reconciled exactly once and appears in exactly one of the success or failure lists — the same guarantee the sequential loop provided for free and the parallel version must now be argued for.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The invoice, itemised
Concurrency is usually presented as a performance technique with a caveat attached. It is more honestly a trade: you sell determinism, debuggability and simplicity, and you buy latency or throughput. That is often a good trade. It is never a free one, and teams that treat the price as a footnote pay it in incidents instead of in design time.
Four of the five costs below are measurable and boring: cycles, cache, memory, switches. The fifth is the one that actually hurts. When a system is sequential, a passing test is meaningful evidence: the code took one path and that path worked. When it is concurrent, a passing test tells you that one of an enormous number of legal schedules worked, and the schedule you did not run is the one production will find at 4 a.m. under load you have never generated.
That is a change in the *epistemics* of your test suite, not a change in its coverage percentage, and no amount of additional tests fixes it. [[heisenbugs]] and [[stress-testing-concurrency]] are the honest responses; "we have 90% coverage" is not one.
| Cost | What it actually is | Where it shows up | Rough scale | Mitigation |
|---|---|---|---|---|
| Coordination | Atomic operations, lock acquire/release, queue push/pop, cache-line transfers between cores | CPU time that does no work; contended locks turn into wait time | Tens of nanoseconds uncontended; microseconds to milliseconds contended | Shrink the critical section; shard the state; avoid sharing at all |
| Context switching | Saving and restoring registers, plus the cache and TLB the incoming task now has to refill | CPU rises while throughput falls — the signature of oversubscription | A few microseconds direct; the cache refill often costs far more | Fewer runnable threads than cores plus a small margin; batch work per switch |
| Memory | A stack per thread, a task frame per coroutine, plus per-worker buffers and queue entries | RSS grows with concurrency; the OOM kill arrives long before CPU saturates | Megabytes per OS thread; hundreds of bytes to kilobytes per task | Prefer tasks to threads at high counts; bound the number in flight |
| Debugging difficulty | The failure depends on a schedule you cannot reproduce, and observation changes the schedule | A bug that vanishes under a debugger, under a log line, on a quiet machine | Days to weeks per bug; unbounded when it cannot be reproduced | Race detectors, deterministic replay, stress tests, and designing to eliminate sharing |
| Nondeterminism | The same input can legally produce different orderings, different float sums, different error attributions | Flaky tests, unreproducible support tickets, reconciliation mismatches | Permanent — it is a property of the model, not a defect | Restore order explicitly at joins; make operations commutative; accept and document it |
The bug the sequential version could not have had
The parallel reconciliation job keeps a set of order ids already handled, so a retry does not double-post a ledger entry. Check the set, and if absent, reconcile and add. In the sequential version this is correct by construction — there is one actor, so between the check and the add nothing can happen.
In the parallel version, the gap between the check and the add is a window, and two workers can both be inside it. The schedule below double-posts a ledger entry for order 8812. It requires the two workers to be within roughly a microsecond of each other on the same order, which happens when a batch is retried and two workers pick up overlapping ranges — a condition that occurs perhaps once per several thousand runs, which is to say once a month at nightly cadence, which is to say four months after the code shipped and passed review.
This is check-then-act, the most common shape of race condition there is, and the mitigation is not "add a lock around the set" — a concurrent set is already thread-safe and it does not help, because the invariant spans two operations rather than one. The critical section is the check *and* the act together, or the operation must be a single atomic test-and-insert. [[finding-the-critical-section]] is the lesson; [[atomicity-illusion]] is why the thread-safe set felt like enough.
| # | Worker 1 | Worker 2 | State |
|---|---|---|---|
| 1 | pick order 8812 from batch A | · | done.has(8812)=false ledgerEntries=0 |
| 2 | if (done.has(8812)) → false | · | done.has(8812)=false ledgerEntries=0 |
| 3 | · | pick order 8812 from retried batch A | done.has(8812)=false ledgerEntries=0 |
| 4 | · | if (done.has(8812)) → false | done.has(8812)=false ledgerEntries=0 |
| 5 | POST ledger entry for 8812 | · | done.has(8812)=false ledgerEntries=1 |
| 6 | done.add(8812) | · | done.has(8812)=true ledgerEntries=1 |
| 7 | · | POST ledger entry for 8812 | done.has(8812)=true ledgerEntries=2 ✕ Order 8812 now has two ledger entries. W2 acted on a check it performed before W1's write, and every individual operation involved was atomic and thread-safe. |
| 8 | · | done.add(8812) — no-op, already present | done.has(8812)=true ledgerEntries=2 |
Where the speedup stops paying for the complexity
The reconciliation job went from 11 minutes to 3.5 — a 3.1× win that took two engineer-weeks, introduced four pieces of shared state, and shipped one duplicate-posting bug that took three days to find. Whether that was worth it depends entirely on a question nobody asked at the time: what does 11 minutes cost?
If the job runs at 02:00 and must finish before 06:00, 11 minutes and 3.5 minutes are the same number and the correct amount of concurrency was zero. If it runs on the critical path of a month-end close where finance is waiting, the trade looks very different. The engineering decision is not "is 3× nice" — it is "is 7.5 minutes worth two weeks, four new invariants and a permanent increase in the cost of every future change to this job".
The curve makes the shape of the trade visible: speedup saturates while complexity keeps climbing, so the ratio has a maximum and it is usually at a small worker count. Two workers here delivered 1.9× for one obvious change; going from four to sixteen delivered nothing and added the pool, the queue, the sharded state and the backpressure. When the curve flattens, every further increment is pure cost. See [[parallel-scaling-is-not-linear]] and [[amdahls-law]].
Key points
- Concurrency is a trade: you sell determinism, debuggability and simplicity to buy latency or throughput.
- The four measurable costs are coordination cycles, context switches, memory per unit of concurrency, and cache disruption.
- The fifth cost is the expensive one: a passing test stops being evidence that the code is correct.
- Shared state is created by the coordination, not by the work. Four new invariants appeared in a job whose sequential version had none.
- Check-then-act is the most common race shape, and thread-safe individual operations do not prevent it — atomicity must cover the pair.
- Speedup saturates; complexity does not. The best value is usually at a small worker count, well before the flat part of the curve.
- The real question is never "is 3× nice" but "is the saved time worth the two weeks, the new invariants, and every future change being harder".
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.
- • Concurrency introduces coordination: at minimum a completion signal, usually shared state, often a lock or an atomic.
- • Each coordination point costs cycles even uncontended, and costs wait time when contended — a cost that grows superlinearly with worker count.
- • Each unit of concurrency costs memory: a stack for a thread, a frame for a task, plus buffers and queue entries.
- • Each switch between units costs registers plus the cache and TLB that the incoming unit must refill, which is usually the larger half.
- • Each interleaving point multiplies the number of legal executions, so the space your tests sample from grows combinatorially while your test count does not.
- • Each of those consequences persists for the lifetime of the code, and is paid again by everyone who modifies it.
- • W1 checks, W1 adds, W2 checks, W2 skips — the schedule that runs in every test and every code review.
- • W1 checks, W2 checks, W1 acts, W2 acts — the duplicate ledger entry, roughly a microsecond wide, found four months later.
- • W1 acts and crashes before adding to the set; a retry sees the order as not done and posts a second entry — the same invariant broken by a different schedule, and a lock does not prevent this one at all.
- • Sixteen workers all hit the connection pool: fourteen block, throughput falls below the four-worker case, and CPU rises because the box is switching rather than working.
- • Sequential: one worker, one order at a time, no window, no shared set — the invariant holds by construction and needs no argument.
- • Concurrency guarantees you will spend time on coordination that the sequential version spent on work. Whether the trade is positive is an empirical question, not a design one.
- • It guarantees that the number of legal executions grows and that your tests sample a shrinking fraction of them.
- • It does not guarantee a speedup: below the point where the work amortises the coordination, the concurrent version is slower.
- • Thread-safe data structures guarantee each operation is atomic. They guarantee nothing about a sequence of operations, which is where invariants actually live.
- • No amount of testing guarantees the absence of an interleaving bug. Race detectors and deterministic replay raise your odds; they do not close the gap. See
[[race-detectors]].
- • The "already done" set is contended by every worker on every order — the highest-frequency shared access in the job.
- • The connection pool is contended above four workers and is the actual ceiling; every worker above that number waits rather than works.
- • The error accumulator is contended only on failure, which means it is untested under contention until the day there are many failures.
- • The progress counter is contended constantly and buys nothing but a log line — the classic case of coordination added for observability that costs more than it reports.
- • Check-then-act race producing duplicate side effects — the schedule above, and the most common concurrency bug in business logic.
- • Heisenbug: adding a log line to investigate changes the timing and the bug stops reproducing. See
[[heisenbugs]]. - • Flaky test: a test that fails one run in 400, gets marked as flaky, gets retried in CI, and is a real bug the whole time.
- • Oversubscription: throughput falls as workers rise, and CPU rises at the same time, so the graphs argue for a bigger machine.
- • Memory exhaustion: unbounded in-flight units, OOM-killed at 03:40 with every latency graph looking healthy right up to the kill.
- • Nondeterministic totals: a parallel float reduction that reconciles to a different cent than the sequential one it replaced.
- • When the saved wall clock has a genuine consumer: a user waiting, a deadline, a queue that would otherwise back up.
- • When the workload is embarrassingly parallel and shares nothing, so the complexity cost is close to its minimum.
- • When the ceiling is high enough that a small worker count captures most of the win, keeping you on the steep part of the curve.
- • When the alternative is a bigger machine that costs more per month than the engineering time costs once.
- • When nobody is waiting for the result. An 11-minute nightly job with a four-hour window has no latency problem to solve.
- • When the work is small: coordination overhead exceeds the work, and the concurrent version is both slower and harder.
- • When the team is small or the code is rarely touched, because the complexity is paid by whoever next opens the file with no context.
- • When the real ceiling is elsewhere. Parallelising in front of a saturated database converts one queue into two.
- • When correctness is high-stakes and the invariant is subtle: money, inventory and permissions are where a one-microsecond window becomes a legal problem.
- • Wall clock before and after, against engineer-time spent — the only ratio that answers whether the trade was good.
- • Count of shared mutable variables introduced. It is a crude proxy for future bug count and it is remarkably predictive.
- • CPU time total, not just wall clock: a concurrent version that halves wall clock while doubling CPU has bought latency with money.
- • Speedup per additional worker. When the increment drops below roughly 0.2, further workers are pure complexity.
- • Flaky-test rate and mean time to diagnose concurrency incidents before and after — the debugging cost made visible.
- • Peak RSS against worker count, which is what determines whether the OOM kill arrives before the throughput ceiling does.
- • Every shared variable needs a documented invariant and a documented protection, and both need to survive the next refactor.
- • The code becomes non-local: correctness now depends on what other workers may do between any two of your statements.
- • The test suite needs a second category — stress and randomised-schedule tests — that is slower, flakier and harder to interpret than the first.
- • Operations gains a new class of incident, and diagnosing it needs tools (thread dumps, lock metrics, race detectors) the team may not have.
- • Onboarding cost rises permanently: the next engineer must understand the concurrency model before making any change to this file.
- • Do nothing. If the deadline is met, 11 minutes is not a problem, and zero is the correct amount of concurrency.
- • Optimise sequentially first. A missing index or a removed N+1 frequently beats a 3× parallel win and adds no invariants. See
[[bottleneck-migration]]. - • Partition at the process or machine level: four processes each handling a disjoint shard of order ids share nothing, need no locks, and get the same speedup with none of the shared-state cost.
- • Make the operation idempotent instead of exclusive. If posting a ledger entry twice is harmless because the entry is keyed by order id, the entire race stops mattering. See
[[idempotency]]— designing the race away beats synchronising it. - • Buy a bigger machine. Genuinely: two engineer-weeks costs more than a year of a larger instance in most organisations.
More workers than cores
Eight threads, one lock
if (balance >= 100) withdraw(100) — drive it until it overdraws
balance = 100
withdraw(amount): # both tasks run this concurrently
b = read(balance) # 1
if b >= amount: # 2 <- decided on a value that may already be stale
debit(amount) # 3| # | Withdrawal A (100) | Withdrawal B (100) | State |
|---|---|---|---|
| 1 | rA ← read balance | · | balance=100 paidOut=0 |
| 2 | if rA >= 100 | · | balance=100 paidOut=0 |
| 3 | debit 100 | · | balance=0 paidOut=100 |
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 |
What people believe, and what is true
We use thread-safe collections, so we are safe.
Thread-safe means each operation is atomic. Invariants almost always span several operations, and the schedule above breaks one using nothing but atomic operations.
The tests pass, so the concurrency is correct.
The tests exercised some legal schedules. The number of legal schedules is combinatorial in the number of interleaving points, and the failing one is selected by production load, not by CI.
More workers, more speed.
Speedup saturates at the first genuine bottleneck and then declines from switching and contention. Complexity rises monotonically the whole way.
This test is flaky.
A test that fails one run in 400 in a concurrent code path is usually reporting a real race at its real frequency. Retrying it in CI is deleting the only evidence you have.
Go deeper
Overview
Concurrency buys speed with complexity. Coordination costs cycles, tasks cost memory, switches cost cache, and bugs cost you the meaning of a passing test.
Practical
Before adding concurrency, write down what the current latency actually costs. If nobody is waiting, the answer is zero workers. If someone is, take the small worker count on the steep part of the curve and stop there.
Advanced
The costs are asymmetric in time. Cycles, memory and switches are paid at runtime and are measurable. Debugging difficulty and nondeterminism are paid by every future change to the code, are not measurable, and do not appear in the benchmark that justified the change.