The question this answers
Why is my parallel version slower than the sequential one, on the same machine, with more cores working?
Applying x * 1.05 to each element of an array, decomposed into one task per element — 50 million tasks, each performing one multiply.
Nothing in the computation itself; each element is independent. The shared state is entirely in the *machinery*: the task queues, the scheduler's counters, the join's completion count, and the cache lines those live on.
The parallel version must produce the same result as the sequential one AND finish sooner. The first half is usually verified; the second half is assumed, and it is the half that fails.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The four costs the sequential version never pays
Parallelising adds four categories of work. Split: partitioning the input, allocating task objects, capturing arguments. Schedule: pushing to a queue, a worker taking it, possibly a steal, and the cache misses when a task lands on a core that has never seen its data. Synchronize: joins, barriers, atomic completion counters, and any locking inside the tasks. Combine: folding partial results, plus the memory traffic to gather them.
None of these scale down with task size. A task object costs roughly the same to allocate whether its body does one multiply or ten million, so the *ratio* of overhead to work is entirely determined by granularity. This is the whole mechanism behind "parallelising tiny work is slower", and it is worth stating as a ratio rather than a threshold, because the absolute numbers move with hardware, runtime and allocator while the ratio argument does not.
The matrix below is the diagnostic version: which cost dominates tells you what to change. A tiny-task program is dominated by split and schedule and needs a coarser cutoff. A program with a hot lock inside the tasks is dominated by synchronization and needs a smaller critical section, not bigger tasks. A program whose combine is expensive needs fewer chunks. These are different fixes and applying the wrong one is the usual outcome of "it did not get faster, add more workers".
| Cost | What it is | Dominates when | Signal | Fix |
|---|---|---|---|---|
| Split | Partitioning, task allocation, argument capture | Tasks are tiny and numerous | Allocation rate and GC pressure track task count, not data size | Raise the sequential cutoff; chunk instead of per-element tasks |
| Schedule | Queue push/pop, steals, worker wakeups, cold caches on arrival | Task duration is near the scheduling cost | Steal attempts per completed task is high; profile shows runtime internals | Coarser tasks; fewer, larger chunks |
| Synchronize | Joins, barriers, atomic counters, locks inside tasks | Tasks share anything mutable, or the phase has many barriers | Lock wait time or atomic contention visible in the profile | Shrink critical sections, use private accumulators, remove barriers |
| Combine | Folding partials, gathering results, extra memory passes | Chunk count is high or the combine is expensive per chunk | Combine phase is a visible fraction of wall time | Fewer chunks; tree-combine instead of a linear fold |
| Memory traffic | Extra passes and lost locality from migration | Per-element work is trivial and the data is large | Achieved bandwidth near machine peak with cores idle | Not a decomposition problem — reduce passes or vectorise instead |
The anatomy of one task that should not have existed
The timeline traces a single one-multiply task through the machinery. The multiply is one lane segment; everything around it is the tax. Reading it, the conclusion is not "scheduling is slow" — a task hand-off is genuinely cheap in absolute terms — but that "cheap" is relative to what the task does, and one multiply is cheaper than anything.
The comparison lane shows the same 50 million multiplies as 8 chunked tasks. The identical overhead is paid 8 times instead of 50 million times, and it disappears into the noise. Nothing about the algorithm changed; only the granularity did. This is why the practical form of a parallel loop is always "parallel over chunks, sequential within a chunk", and why library parallel-for implementations chunk automatically rather than trusting the caller.
The rule to internalise is a ratio, not a number: a task must do enough work to make its own scheduling cost irrelevant. Whether that means a few microseconds or a few hundred depends on the runtime, the allocator, whether the task was stolen and how cold its data was on arrival — which is exactly why this lesson refuses to name a universal threshold and tells you to sweep the cutoff instead.
The crossover, and why it is a shape rather than a number
Plot speedup against workers for a fixed decomposition and you get a curve with three regions. Below the crossover the parallel version is *slower than sequential* — speedup under 1.0 — because overhead exceeds the work, and adding workers makes it worse by adding steals and contention. Around the crossover the curve climbs but stays well under ideal. Well above it, the curve approaches ideal until some other ceiling (span, bandwidth, a serial fraction) takes over, which is Amdahl's Law territory.
The curve below is a fine-grained decomposition, and the important feature is that it starts and stays below 1.0 and *declines* as workers are added. That decline is the signature to recognise: a program that gets slower with more workers while the CPU graph rises is doing more coordination, not more work. Contrast More Threads Is Not More Speed, which is the same shape arriving from oversubscription rather than granularity.
Getting the crossover for your case is a sweep, not a lookup. Fix the workload, vary the chunk size (or cutoff constant) across a doubling ladder, and record wall time — the curve is flat-and-good over a broad middle and bad at both ends, so you are looking for the middle rather than an optimum. It moves with the machine, the runtime version, and whether the data is in cache, so pin it as a configurable constant with a comment rather than a magic number, and re-measure when any of those change.
- Speedup below 1.0 means the parallel version is a pessimisation; more workers make it worse, not better.
- Sweep the chunk size or cutoff on a doubling ladder — you are looking for the broad flat middle, not a precise optimum.
- The crossover moves with hardware, runtime version and cache residency; treat it as configuration, not a constant of nature.
- Always keep the sequential implementation: below the cutoff it *is* the implementation, not a fallback.
Key points
- Split, schedule, synchronize and combine are work the sequential version never does, and none of them shrink with task size.
- What matters is the ratio of overhead to useful work per task, which is why granularity — not core count — decides whether parallelism pays.
- A speedup below 1.0 that declines with more workers is the signature of too-fine granularity.
- The fix for tiny tasks is chunking: parallel over chunks, sequential within a chunk. Library parallel-for does this for you.
- Which of the four costs dominates determines the fix; adding workers is not one of them.
- The crossover is a shape you measure by sweeping the cutoff, not a threshold anyone can give you.
- Below the cutoff, the sequential version is the correct implementation — keep it and call it.
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.
- • A parallel decomposition allocates a task per piece, pushes it to a scheduler, and pays a hand-off and possibly a steal before the body runs.
- • The task body runs on a worker whose caches may know nothing about its data, adding cold misses proportional to the working set.
- • Completion is recorded through a shared counter or a join, which is an atomic operation on a contended cache line.
- • Partial results are combined, adding memory traffic and, for many chunks, a visible combine phase.
- • Total parallel time ≈ (work ÷ effective workers) + overhead × task count + combine — so shrinking tasks raises the middle term while lowering the first.
- • A sequential cutoff caps task count by stopping decomposition below a size, which is the only lever that reduces the middle term directly.
- • One-multiply task: allocate, push, wake a worker, steal, cold miss, multiply once, increment the completion counter. The useful step is one of seven.
- • Fifty million such tasks: workers spend most of their time in queue operations and steals, and the profile is dominated by runtime internals rather than user code.
- • Chunked into eight tasks: the same seven-step machinery runs eight times and vanishes into the noise, while each body streams through six million elements with the prefetcher working.
- • Contention feedback loop: as tasks shrink, deques empty faster, steal attempts rise, the contended index gets hotter, and each steal costs more — so the overhead per task grows as granularity falls rather than staying constant.
- • A barrier per element instead of per chunk: every worker waits for the slowest at every step, so the phase costs (elements × slowest-worker time) instead of (elements ÷ workers) (Barriers).
- • Guaranteed: the parallel version computes the same result, if the decomposition is correct. Overhead is a performance property, not a correctness one.
- • NOT guaranteed: that parallel is faster. At fine granularity it is reliably slower, on every machine, at every core count.
- • NOT guaranteed: that adding workers helps. Below the crossover it hurts, monotonically.
- • NOT guaranteed: that a cutoff tuned on one machine holds on another — it depends on cache sizes, allocator behaviour and runtime version.
- • NOT guaranteed: that a library parallel algorithm chunks well for your element cost. Most chunk by count, not by estimated work.
- • NOT guaranteed: that overhead is constant per task. It rises as tasks shrink, because steal rates and contention rise with task count.
- • Task queues and completion counters are the contended objects, and their contention grows as tasks get smaller — the opposite of what you want.
- • Steal attempts rise sharply when deques drain quickly, so fine granularity converts a lock-free fast path into a contended slow path.
- • Barriers at fine granularity make every worker wait on the slowest at every step, converting imbalance into a multiplier.
- • Cold-cache arrival is contention for memory bandwidth rather than for a lock, and it is invisible in lock-wait metrics.
- • Pessimisation: a correct parallel version that is measurably slower than sequential and consumes many times the CPU.
- • Negative scaling: throughput declining as workers are added, misdiagnosed as a machine or runtime problem.
- • Allocation pressure and GC churn driven by task-object count rather than data size.
- • Scheduler thrash: workers spending the majority of their time hunting for work (Work Stealing).
- • Cache-locality collapse from tasks migrating between cores, so the same computation issues far more memory traffic than the sequential version.
- • A cutoff tuned once, then silently wrong after a machine class change or a runtime upgrade.
- • It never helps — this lesson describes a cost. What helps is *knowing* it exists, which converts "parallelism did not work here" into "the granularity was wrong".
- • The overhead is worth paying when per-task work is large relative to it, which is the ordinary case for chunked decompositions.
- • Accepting slightly more overhead is correct when it buys load balance: over-decomposing to 4× the worker count trades a little overhead for a lot of imbalance tolerance (Fork/Join).
- • Per-element tasks over cheap operations — the archetype, and reliably slower than a plain loop.
- • Deep recursive decomposition with no sequential cutoff, where the leaves are single elements.
- • Barriers or synchronization inside the inner loop rather than at phase boundaries.
- • Parallelising an operation already limited by memory bandwidth, where the extra passes make it worse and no core count helps.
- • Parallelising a fast operation on a small input to "future-proof" it — the overhead is paid every run, and the future input size may never arrive.
- • Parallel wall time against sequential wall time on the same input. If this comparison is not run, nothing else matters — and it is skipped constantly.
- • Speedup versus workers: values below 1.0, or a declining curve, identify granularity as the problem immediately.
- • Task count and mean task duration. Microsecond means with millions of tasks is a diagnosis on its own.
- • Fraction of profile time in runtime internals (queue operations, steal loops, allocation) versus user code.
- • Steal attempts per completed task, which rises sharply as granularity falls.
- • Allocation rate correlated with task count rather than input size.
- • A cutoff sweep on a doubling ladder, reporting wall time — the flat middle is the answer.
- • A cutoff constant enters the code, needs a rationale, and needs re-measurement when hardware or runtime changes.
- • Two code paths — chunked-parallel and sequential — must both be tested, and the boundary between them is a real edge case.
- • Performance now depends on a decomposition parameter, so a performance regression can come from a data-shape change with no code change at all.
- • Reasoning about performance requires distinguishing four overhead categories that all present as "it is slow".
- • The sequential version. Below the crossover it is faster, simpler and already correct — this is the alternative, and it wins more often than parallel advocacy suggests.
- • Chunking with a library parallel-for that sizes chunks itself, which removes the most common way to get this wrong.
- • SIMD within one thread: for trivial per-element operations it delivers real speedup with zero scheduling cost (SIMD: One Instruction, Many Elements).
- • Reducing passes over memory instead of parallelising them, when the operation is bandwidth-bound — fusing two loops beats parallelising either.
- • Parallelising at a coarser level entirely: one task per file, per request or per document rather than per element, which usually makes the ratio problem disappear.
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 |
CPU parallelism simulator
Amdahl’s term, a synchronisation term, an oversubscription term and a bandwidth ceiling, each one a knob you can switch off. Real curves have more causes than four and are rarely this smooth. There is no ideal core count to read off this chart.
Work stealing between deques
Own work → popped from the HEAD of my deque (LIFO: hottest in cache)
Stolen → taken from the TAIL of a victim's deque (oldest, biggest sub-task)
Two ends → the owner and the thief rarely touch the same slot, so the
common case is uncontended and needs no lock at all.What people believe, and what is true
Parallel code might not be faster, but it will not be slower.
At fine granularity it is reliably slower — often by more than 2× — while using every core. The overhead is real work the sequential version never does.
More, smaller tasks give the scheduler more to work with.
Past the crossover they give it more to *do*. Overhead per task is fixed and steal rates rise, so the coordination grows faster than the parallelism.
There is a standard minimum task size to aim for.
The ratio matters, not the absolute size, and the ratio depends on runtime, allocator, cache state and whether the task was stolen. Sweep it.
It was slower, so the machine or the library must be at fault.
Check task count and mean task duration first. Millions of microsecond tasks is a granularity finding, not a platform bug.
Go deeper
Overview
Splitting work up costs something. If each piece is tiny, you spend more on the splitting than on the work.
Practical
Chunk instead of per-element tasks, keep a sequential cutoff, and always compare against the plain loop before believing a parallel version.
Advanced
Diagnose which of split, schedule, synchronize or combine dominates — they have different fixes. Overhead per task rises as tasks shrink, so the problem compounds.
Internals
The dominant hidden cost at fine granularity is usually not queue operations but cold-cache arrival: a stolen task pulls its working set across the interconnect, which no lock-wait metric reports.