The question this answers
Why did splitting this loop across eight workers move more memory and run slower than the single-threaded version?
A pass over a 500 MB array of records, computing a score per record and writing it into an output array — first single-threaded, then partitioned across eight workers.
Logically nothing: disjoint input slices, disjoint output slices, no locks. Physically a great deal — the shared last-level cache, the cache lines at chunk boundaries, and the per-core caches that a migrated task leaves behind.
Every record is scored exactly once and written to its own output index, at every worker count and under every scheduling decision. Locality changes the cost; it never changes the answer.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The warm cache a migrating task leaves behind
A thread running on one core accumulates state in that core's private caches: the data it just touched, the instructions it is executing, the address translations it needs. That accumulated state is worth a lot — an access that hits it is roughly two orders of magnitude cheaper than one that goes to DRAM — and it is completely invisible in your program.
When the scheduler moves the thread to another core, none of it moves. The thread arrives on a cold core and re-populates everything from scratch, at full miss cost, while the state it built on the old core is evicted by whatever runs there next. The thread is running the entire time; nothing blocks, nothing is contended, and no metric in your application notices. It is simply slower for a while.
This is why the naive intuition "eight workers means eight times the cache" is backwards for many workloads. Eight workers on eight cores each get a private cache, yes — but they share the last-level cache, so each one's effective share of it *shrinks*, and each migration throws away work that was already paid for. Oversubscription makes it dramatically worse: with 24 runnable workers on 8 cores, every worker's private cache is refilled by the two others that ran in between it and its last quantum (Oversubscription, The Cost of a Context Switch).
The partitioning decision is a locality decision
How you split the array decides how much of this you suffer, and the two obvious splits behave completely differently. Blocked: worker k gets the contiguous range [k*n/W, (k+1)*n/W). Each worker walks its own region sequentially, the hardware prefetcher recognizes the stride immediately, and the regions do not overlap in cache except at the boundaries. Interleaved: worker k takes every W-th element. Each worker's accesses are strided by W elements, every cache line is touched by every worker, and you pay the full line fetch for one useful element in each.
Interleaved partitioning looks appealing because it balances load perfectly when per-element cost varies. It is usually the wrong default anyway, because the locality penalty is large and constant while the load-balance benefit only matters if the cost actually varies. When it does vary, the right answer is blocked chunks that are *smaller than the whole slice* and assigned dynamically — many chunks, each contiguous, handed out as workers finish — which keeps the prefetcher happy and rebalances at the same time. That is what a work-stealing scheduler does (Work Stealing), and it is why the chunk-size parameter in every parallel-for API exists.
Chunk size is then a genuine trade-off with locality on one side and balance on the other: chunks too large and one straggler holds the barrier; chunks too small and you pay dispatch overhead per chunk plus a cold cache at each chunk boundary. There is no universal number — it depends on the per-element cost, the variance, and the working-set size relative to the private cache — which is a theme this domain keeps returning to.
- Give each worker a contiguous region, then make the regions smaller if you need balance — do not interleave.
- Chunk boundaries are where lines are shared; align chunk starts to cache-line boundaries and the sharing disappears.
- A per-element cost that varies by 10x makes balance dominate; one that is uniform makes locality dominate. Know which you have.
| Partitioning | Prefetcher | Line sharing | Load balance | Verdict |
|---|---|---|---|---|
| Blocked: contiguous slice per worker | Recognizes the stride immediately | Only at chunk boundaries | Poor if per-element cost varies | Best default for uniform work |
| Interleaved: every W-th element | Strided; much weaker | Every line touched by every worker | Perfect by construction | Usually a net loss; the locality cost is constant |
| Many small blocked chunks, dynamic | Good within each chunk | Only at chunk boundaries | Good — rebalances as workers finish | Best when per-element cost varies |
| Work-stealing deques | Good; stolen chunks are contiguous | Boundaries only, plus steal traffic | Very good, self-tuning | Best general answer; more machinery |
The accumulator that is not shared but behaves like it is
The other half of this lesson is what workers *write*. A results array indexed by worker id — counts[workerId] += 1 — is the most natural thing to write and one of the most expensive. Eight 8-byte counters occupy a single cache line, so eight cores writing "their own" counter are in fact fighting over one line, which bounces between their private caches on every increment. There is no lock, no atomic, no shared variable in the source, and throughput can drop by an order of magnitude. That is False Sharing: Different Variables, Same Cache Line, and it is the sharpest, most reproducible version of the locality problem.
The fix is to give each worker a private accumulator in its own stack frame and combine once at the end. This is better than padding — which also works — because it eliminates the traffic entirely rather than spreading it out, and because it composes: a worker-local accumulator has good locality *and* no coherence traffic *and* no dependence on a padding constant that a struct layout change might silently break.
The general principle underneath both halves of this lesson: give each worker its own contiguous region to read and its own private variable to write, and combine at the end. That single rule prevents false sharing, keeps the prefetcher effective, avoids coherence traffic, and removes the need for synchronization in the hot loop. Almost everything else in parallel performance tuning is a variation on it.
1std::vector<double> partial(W, 0.0); // 8 doubles = one cache line2 3parallel_for(0, W, [&](int w) {4 for (size_t i = start(w); i < end(w); ++i)5 partial[w] += score(rec[i]); // every += bounces the line6});7 8double total = 0;9for (double p : partial) total += p;1std::vector<double> partial(W, 0.0);2 3parallel_for(0, W, [&](int w) {4 double local = 0.0; // lives in a register / this core's stack5 for (size_t i = start(w); i < end(w); ++i)6 local += score(rec[i]); // zero coherence traffic in the hot loop7 partial[w] = local; // one write per worker, total8});9 10double total = 0;11for (double p : partial) total += p;Both versions are correct — no data race, no lock needed, identical results. The first writes to a shared cache line once per record and the line ping-pongs between eight cores; the second writes to it once per worker. Same algorithm, same synchronization (none), and a difference that can exceed 10x on a tight loop. Note that the combine step still adds the partials in worker order, so the floating-point total depends on W — see Reduction Ordering: The Sum Changed When the Worker Count Did.
Key points
- A thread's warm cache is real, unowned state that does not follow it when the scheduler moves it to another core.
- Parallelism shrinks each worker's share of the shared last-level cache while adding migrations and preemptions that discard warm state.
- Blocked (contiguous) partitioning preserves locality; interleaved partitioning destroys it in exchange for a load balance you usually do not need.
- When per-element cost varies, use many small contiguous chunks assigned dynamically rather than interleaving.
- Give each worker a contiguous region to read and a private variable to write, then combine once — that one rule prevents most of the problems in this lesson.
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 core keeps private caches and address-translation state populated by whatever ran on it most recently.
- • A migration or a preemption leaves that state behind; the thread resumes on a cold core and refills at miss cost while still counting as "running".
- • Workers sharing the last-level cache evict each other's lines, so the effective cache per worker falls as worker count rises.
- • Interleaved index assignment makes every cache line useful to only one worker per fetch, multiplying bytes moved per useful element.
- • Writes by different workers to the same cache line force the line to move between cores on every write, whether or not the bytes overlap.
- • The correctness-neutral one: any interleaving of eight workers over disjoint slices produces the same output. Nothing in the schedule can break the invariant — the schedule only changes the cost.
- • The expensive one: W0 writes partial[0]; W1 writes partial[1]; W0 writes partial[0] again — same 64-byte line, so it is invalidated on W1's core and fetched back for W0, repeatedly, at every increment.
- • The migration one: W3 runs on core 5 for 4ms building a warm working set; the scheduler moves it to core 1; it runs the same code 3x slower for the next millisecond while nothing is blocked and utilization stays at 100%.
- • The oversubscription one: 24 workers on 8 cores; each worker's footprint is evicted by the two workers that ran between its quanta, so no worker ever reaches its warm steady state.
- • The boundary one: W0's slice ends mid-line and W1's begins in the same line; the two workers share that one line for the whole run, which is harmless at one boundary and significant if you chunked into thousands of tiny pieces.
- • Cache coherence guarantees that a load returns the most recently written value, regardless of which core wrote it — correctness is never the issue here.
- • Disjoint slices guarantee no data race and no need for synchronization, at any worker count.
- • Nothing guarantees a thread stays on a core, that its cache survives a quantum, or that a parallel version moves fewer bytes than the sequential one.
- • Nothing guarantees that "no shared variables" means "no shared cache lines" — false sharing is invisible at the language level, and no compiler or type system flags it.
- • A parallel-for API guarantees the iterations run; it makes no promise at all about the locality of the assignment it chooses.
- • Cache-line contention from adjacent per-worker writes: no lock, no blocking, and a serialization enforced by the coherence protocol.
- • Last-level cache capacity contention: workers evict each other, so per-worker miss rates rise as parallelism rises.
- • Run-queue contention when runnable workers exceed cores, producing the migrations and preemptions that discard warm state.
- • Prefetcher contention: several workers streaming different regions can exceed the number of streams the hardware tracks, and prefetching quietly stops helping any of them.
- • False sharing on a per-worker counter array: an order-of-magnitude throughput loss with no lock and no shared variable in the source.
- • Parallel version slower than sequential because interleaved partitioning multiplied the bytes moved.
- • Throughput that degrades as the machine gets busier, because migrations increase — reproducible only under load.
- • Chunk size tuned on a machine with a large private cache and shipped to one with a small one, where the working set no longer fits.
- • Oversubscription from nested parallel libraries: no single component is wrong, and every worker runs cold.
- • A benchmark whose input fits entirely in cache, showing scaling that production never reproduces.
- • Any parallel loop over a large array: choosing contiguous chunks over interleaved indices is free at authoring time and frequently worth several times the throughput.
- • Hot accumulation loops, where switching a shared-array slot to a local variable is a two-line change with a large, reliable effect.
- • Sizing pools to the real core budget instead of a larger number, which removes migrations you were paying for and getting nothing from.
- • When it becomes premature: for a loop that runs once over a small array, none of this is measurable and the tuning is noise.
- • When padding is applied everywhere defensively, inflating memory footprint and *causing* cache pressure to avoid a problem that was not there.
- • When chunk size is tuned to one machine and hard-coded, so it is wrong on every other machine and silently so.
- • When locality reasoning is used to justify pinning threads without measuring — see Thread Affinity: Pinning, and What It Costs You for what that costs.
- • Bytes moved from DRAM for the parallel version against the sequential one. Same work, more bytes, means the partitioning is the problem.
- • Cache miss rate per worker at increasing worker counts; a rise means workers are evicting each other rather than helping each other.
- • Involuntary context switches and thread migrations per second — the direct measure of how much warm state is being discarded.
- • The false-sharing check: pad the per-worker slots to a full cache line and re-run. A large change is a diagnosis, and it costs ten minutes.
- • The chunk-size sweep: run the same job at several chunk sizes. The curve is usually flat in the middle with sharp edges, and that middle is where to live.
- • Locality-aware partitioning adds a chunking parameter that must be chosen, documented and re-checked on new hardware.
- • Padding for false sharing bakes a cache-line constant into your data structures, which is machine-dependent and easily lost in a refactor.
- • Worker-local accumulation adds a combine step, which for floating-point results introduces a dependence of the answer on the worker count.
- • Reasoning about any of this requires hardware counters or careful A/B experiments; it is not visible in ordinary application profiling.
- • Fewer workers. A four-worker run with warm caches routinely beats a sixteen-worker run with cold ones, and it is a one-line change.
- • Fuse the passes so the data is touched once while it is resident, rather than optimizing where several passes run — the Memory Bandwidth: More Cores, Same Bus fix, which also fixes this one.
- • Reduce the working set: a smaller record, a narrower projection or a compressed representation may make the whole thing fit and remove the question.
- • Use a work-stealing runtime and stop hand-partitioning, accepting its chunking heuristics in exchange for not owning the parameter.
Two counters, no lock, one cache line
struct Counters {
long a; // byte 0..7
long b; // byte 8..15 <- same 64-byte line as a
}; // sizeof == 16Work 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.More workers than cores
What people believe, and what is true
Eight workers means eight times the cache.
Eight private caches, yes — but a shared last-level cache split eight ways, plus migrations that discard warm state. Effective cache per worker usually falls.
No shared variables means no sharing.
Sharing is per cache line, not per variable. Eight adjacent per-worker counters are one line and are contended by the hardware without any lock in sight.
Interleaving indices is the fair way to split a loop.
It is the fair way and usually the slow way: every cache line is fetched by every worker for one useful element. Use small contiguous chunks instead.
The parallel version cannot be slower — it is the same work.
It is the same computation and can move several times the memory. Bytes moved, not operations performed, is what a memory-bound loop is billed for.