Summing a sequence in parallel is the first thing anyone writes with threads, and it is still the best small example of how a correct program can be slower on eight cores than on one. The pattern below is the same in every variant: split the index range across threads, let each thread accumulate, combine at the end. The variants differ only in where the accumulator lives, and that single choice moves the throughput by a factor of almost three hundred on an Apple-silicon laptop (Apple M1, 8 cores).

The experiment

To keep memory bandwidth out of the picture the "data" is computed rather than loaded: element i is a cheap integer hash of i. Each thread then handles a contiguous range of indices.

static inline uint64_t f(uint64_t i) {              /* a few integer ops per element */
    uint64_t x = i * 0x9E3779B97F4A7C15ull;
    x ^= x >> 31;
    return x & 0xFF;
}

static _Atomic uint64_t total;                      /* the one shared result */
static _Atomic uint64_t packed[64];                 /* 8-byte slots, 16 per 128-byte line */
struct padded { _Atomic uint64_t v; char pad[120]; } __attribute__((aligned(128)));
static struct padded padded_acc[64];
static _Atomic uint64_t next_chunk;                 /* for dynamic scheduling */

static void *worker(void *p) {
    struct arg *a = p;
    uint64_t lo = N / a->nthreads * a->tid, hi = (a->tid == a->nthreads - 1) ? N : lo + N / a->nthreads;
    uint64_t local = 0;
    switch (a->mode) {
    case SHARED_ATOMIC:
        for (uint64_t i = lo; i < hi; i++) atomic_fetch_add_explicit(&total, f(i), memory_order_relaxed);
        break;
    case PACKED:
        for (uint64_t i = lo; i < hi; i++) atomic_fetch_add_explicit(&packed[a->tid], f(i), memory_order_relaxed);
        break;
    case PADDED:
        for (uint64_t i = lo; i < hi; i++) atomic_fetch_add_explicit(&padded_acc[a->tid].v, f(i), memory_order_relaxed);
        break;
    case LOCAL:
        for (uint64_t i = lo; i < hi; i++) local += f(i);
        atomic_fetch_add_explicit(&total, local, memory_order_relaxed);
        break;
    case LOCAL_DYNAMIC:
        for (;;) {
            uint64_t c = atomic_fetch_add_explicit(&next_chunk, CHUNK, memory_order_relaxed);
            if (c >= N) break;
            uint64_t end = c + CHUNK < N ? c + CHUNK : N;
            for (uint64_t i = c; i < end; i++) local += f(i);
        }
        atomic_fetch_add_explicit(&total, local, memory_order_relaxed);
        break;
    }
    return NULL;
}

The three per-element variants use a relaxed atomic add on purpose. A plain acc[tid] += f(i) on a slot that no other thread touches is not a data race, but the compiler would then be entitled to keep acc[tid] in a register for the whole loop and store it once at the end, which quietly turns the experiment into the LOCAL variant. The atomic forces one read-modify-write of memory per element, which is the behaviour I want to measure.

Threads are created with pthread_create, joined with pthread_join, and given the QOS_CLASS_USER_INTERACTIVE quality-of-service class so that the scheduler prefers the four performance cores while they are available. The per-element variants process 228 elements and the two register variants 231, so that every run lasts between a tenth of a second and a few seconds; the results are reported as throughput, which makes the two sizes comparable. Each cell is the median of nine runs, built with clang -O3 (Apple clang 17.0.0).

Results

elements / s (×10⁹) 1 thread 2 3 4 5 6 7 8
one shared atomic counter 0.431 0.202 0.142 0.112 0.078 0.050 0.055 0.059
per-thread atomics, packed 0.406 0.133 0.110 0.089 0.068 0.080 0.092 0.113
per-thread atomics, padded to 128 bytes 0.414 0.781 1.122 1.351 1.722 1.852 1.913 2.055
register accumulator, one atomic at end 3.519 6.754 9.427 11.889 12.107 12.830 13.538 13.966
register accumulator, dynamic chunks 2.481 4.654 6.556 8.485 9.235 10.377 10.673 10.192
Left: throughput in billions of elements per second versus thread count for the five variants on a log scale; the shared and packed variants fall as threads are added, the padded and register variants rise. Right: speed-up relative to one thread, with an ideal line and a shaded region for threads five to eight.
Throughput and speed-up of the five reductions, 1 to 8 threads, median of nine runs (bars: interquartile range). The two variants that touch a shared cache line on every element get slower as threads are added.

Reading the chart

The shared counter gets slower with every thread. 0.43 billion elements per second on one thread, 0.06 on eight. Every atomic_fetch_add needs the cache line in the exclusive state in the issuing core's cache, so with eight threads the line migrates between cores on nearly every increment, and the atomics serialise on it. This is the textbook contended-atomic result. Even on one thread, with no contention at all, the shared-counter loop runs 8.2 times slower than the register version (0.43 against 3.5). That ratio is not the price of one atomic against one add: with the sum in a register clang is free to vectorise the whole loop, and it does, while the atomic loop performs one ldadd per element. It is the price of a memory read-modify-write in the hot loop, which is the comparison that matters here.

Packed per-thread counters are just as bad, and that is the surprise. No thread ever reads another thread's slot; logically there is no sharing. But packed[0] through packed[7] occupy 64 bytes of one 128-byte cache line (sysctl hw.cachelinesize reports 128 on this machine), and the coherence protocol tracks lines, not variables. Two threads writing to neighbouring slots invalidate each other's copy of the line exactly as if they were writing the same counter. With two threads the throughput is 3.1 times lower than with one. This is false sharing.

False sharing: private counters, shared cache line packed: _Atomic uint64_t acc[8] 8 × 8 bytes = 64 bytes, all inside one 128-byte line core 0 acc[0] += d[i] core 1 acc[1] += d[j] L1d of core 0 copy of the same line L1d of core 1 copy of the same line every write by one core invalidates the other core's copy; the line migrates on each increment one 128-byte cache line (hw.cachelinesize = 128) 0 1 2 3 4 5 6 7 acc[0] … acc[7]: 64 bytes unused: 64 bytes No thread ever reads another's counter. The coherence protocol does not know that; it tracks lines, not variables. padded: struct { _Atomic uint64_t v; char pad[120]; } each counter starts a new 128-byte line (alignas / aligned(128)) core 0 acc[0].v += d[i] core 1 acc[1].v += d[j] L1d of core 0 line 0, exclusive L1d of core 1 line 1, exclusive no coherence traffic in the loop: each line stays in the modified state in its owner's cache 0120 bytes of padding 1120 bytes of padding 2… Costs 1 KiB for 8 counters. Cheaper still: keep the partial sum in a register and publish it once at the end.
False sharing. Private variables, shared line: the protocol does not know that the two cores never read each other's counter.

Padding fixes the sharing but not the atomic. With each counter on its own line, throughput rises with threads to 2.1 billion elements per second on eight, a speed-up of 5.0. But every element still pays for an atomic read-modify-write, so the one-thread baseline is the same 0.4 as before, 8.5 times below the register variant.

Keep the sum in a register, publish once. The LOCAL variant follows the pattern behind every parallel reduction: accumulate privately, then combine the partial results once. Here the private accumulator stays in a register for the whole loop and the combining step is a single atomic add per thread. An OpenMP reduction clause gives each thread its private copy and leaves the combining to the implementation; MPI's Allreduce applies the same idea across processes, combining one buffer from each. 3.5 billion elements per second on one thread, 11.9 on four, 14.0 on eight.

Eight cores are not eight equal cores. The register variant speeds up 3.4 times on four threads but only 3.97 times on eight. This laptop has four performance cores and four efficiency cores, and the static partition hands an efficiency core exactly as many elements as a performance core. The slowest thread decides the finishing time, so threads five to eight add only 17 %. Handing out the work in chunks from a shared atomic counter (LOCAL_DYNAMIC, 2048 chunks of 220 elements) lets fast cores take more chunks: the speed-up on eight threads becomes 4.1. In this implementation the dynamic loop also runs about 30 % slower on a single thread, which I have not chased down (the compiled inner loop differs from the static one), so the absolute throughput on eight threads ends up lower, 10.2 against 14.0. On a machine with uniform cores the dynamic version would have no advantage at all; on this one the lesson is that the partitioning strategy matters as much as the accumulator.

WARNING

The scheduler, not the program, decides which thread runs on which core, and macOS exposes no CPU affinity API. In a first sweep made while the laptop was heavily loaded, single-thread runs came out up to 2.3 times slower than their median; in the nine-run sweep above they stayed within 5 % of it. That is why the harness requests the interactive QoS class and reports the median of nine runs. If your scaling curve has a knee at half the core count on a laptop, check whether half the cores are a different kind before blaming the code.

The memory-ordering primer

The fast variant is correct only because of two rules of the C11 memory model, and both are worth stating precisely because the same rules decide whether lock-free code is correct.

A data race is undefined behaviour. Two threads accessing the same non-atomic object, at least one of them writing, without a happens-before relation between the accesses, is a data race, and the standard makes no promise about the program at all. Not "the value may be stale", no promise. Atomics exist to make concurrent access defined, and volatile does not help: it constrains the compiler's reordering of that object but says nothing about other cores.

Happens-before is built from synchronisation. Within one thread, program order is sequenced-before. Across threads, the edges come from synchronisation operations: a release store that is read by an acquire load, a mutex unlock followed by a lock, thread creation before the thread's first statement, and a thread's last statement before the matching pthread_join returns. Everything the worker wrote is visible to the main thread after join because of that last rule, which is why the final atomic_load(&total) can be relaxed too.

The orders used in this post, and what the compiler turned them into on this machine:

C11 order Where used AArch64 instruction emitted
memory_order_relaxed fetch-add every accumulator update ldadd
memory_order_seq_cst store (atomic_store) resetting counters before a run stlr
memory_order_seq_cst load (atomic_load) reading the result after pthread_join ldar

Relaxed is enough for a counter whose value is only consumed after a join: the atomicity guarantees the increments are not lost, and the join guarantees visibility. Relaxed is not enough to publish a result through a flag (done = 1; ... if (done) use(result)), because nothing then orders the write of result before the write of done; that needs a release store on done and an acquire load of it. A lock-free queue is built on exactly that pair; a later post works through one.

Why the chunked loop uses a relaxed fetch-add too

next_chunk is a work-distribution counter. Each atomic_fetch_add_explicit(&next_chunk, CHUNK, memory_order_relaxed) returns a unique starting index because the read-modify-write is atomic, and no thread reads data written by another thread as a consequence of which chunk it received. The only cross-thread data flow is the final total, which is again covered by the join. If instead the chunks pointed into a buffer that another thread had filled, the fetch-add would have to be an acquire and the filling thread's completion a release.

Further reading