Sixteen Threads, Six Cache Lines
A profiling team is tuning a telemetry aggregator written in C++17 on a 2-socket server with 16 cores per socket, 64-byte cache lines and 96 GB of RAM. Each worker thread owns one slot of a global array: struct Slot { uint64_t events; uint64_t bytes; uint32_t errors; }; Slot slots[16]; and each of 16 threads runs a tight loop incrementing slots[tid].events 200 million times. Single-threaded that loop takes 0.9 s. With 16 threads pinned to 16 distinct cores on one socket, wall time is 14.1 s - barely faster than serial - and CPU utilisation is only 12%. Deleting the increments drops the runtime to 0.2 s, so the loop itself is the cost. A developer then marks the counter volatile, and it gets slower still. The manager asks whether the machine is faulty and whether a CPU with twice the clock speed will fix it.
1. Explain the 14.1 s. Include the struct layout, how many threads share a cache line, and why the increment is so expensive.
Read the worked answer
Layout first. sizeof(Slot) is 8 + 8 + 4 = 20 bytes, padded to 24 for alignment. The array is 16 x 24 = 384 bytes, which is exactly 6 cache lines of 64 bytes. Slot 0 occupies bytes 0-23 and slot 1 bytes 24-47, both inside line 0; slot 2 starts at 48 and straddles into line 1. So each cache line holds parts of two or three slots, meaning roughly three threads are hammering the same 64-byte line - the classic false-sharing shape.
Why that is catastrophic. A store must own the line exclusively. When thread 0 increments slots[0].events it issues a read-for-ownership and takes the line in Modified state; every other core holding that line must invalidate its copy. Thread 1's next increment then misses and pulls the line away from thread 0, and so on. The line ping-pongs between cores for the entire loop, and on a 2-socket machine any cross-socket transfer costs on the order of 100+ ns instead of a 4-cycle L1 hit.
The arithmetic confirms it. Serial cost is 200 million increments in 0.9 s, about 4.5 ns per increment. If the code scaled, 16 threads would finish in about 0.9 s; instead each thread takes 14.1 s, about 70 ns per increment. The per-operation cost rose by a factor of ~15 because the cores are not computing, they are queuing for ownership of six contended lines. The 12% CPU utilisation is the tell: the cores are stalled, not busy.
2. Give the fix, state the expected result, and explain why marking the field volatile made it worse.
Read the worked answer
Fix the layout so each thread's hot data lives alone on a line:
struct alignas(64) Slot { uint64_t events; uint64_t bytes; uint32_t errors; char pad[64 - 20]; };
This makes each slot 64 bytes and forces the array to 16 lines, one per thread, so no two cores ever write the same line. Expect the 16-thread runtime to drop to roughly the single-thread time, about 0.9-1.0 s, and CPU utilisation to approach 100%.
An even cheaper variant that avoids padding entirely: accumulate into a local uint64_t inside the loop and store once into slots[tid] at the end. One write per thread means one line transfer instead of 200 million. Do this when the loop body does not need the shared array.
Caveats worth stating:
- alignas(64) is not enough if the array itself is not 64-byte aligned; the alignas on the struct type does give the array the right alignment, but verify with sizeof(Slot) and a pointer-modulo-64 check.
- 128-byte padding is needed on some Intel parts, which fetch lines in adjacent pairs - if 64-byte padding does not fully fix it, try 128.
Why volatile backfired: volatile in C++ means the compiler must emit every read and write and may not keep the value in a register or merge the increments. That forces 200 million explicit load-modify-store pairs instead of a register increment, so the number of coherence transactions goes up rather than down. volatile also does not provide atomicity or ordering across threads, so it is the wrong tool twice over - it neither fixes false sharing nor makes the counter safe. The real fix is separation of the data, and if cross-thread visibility is genuinely needed, use std::atomic with a relaxed memory order on separate cache lines.
3. How would you answer the manager's two questions, and what measurements would you present?
Read the worked answer
Answer to 'is the machine faulty': no. The evidence is that the same loop is fine single-threaded and the runtime collapses when the increments are removed. Hardware that fails like that is not hardware - it is a data-placement problem, and the identical code would misbehave on any multi-core machine with the same struct layout.
Answer to 'will a 2x faster CPU fix it': no. The cost is not instruction throughput, it is inter-core line transfer latency. Doubling clock speed might shave the compute portion but the transfer latency is dominated by coherence and interconnect, which improves far less than 2x, and doubling the number of cores would make the contention worse, not better.
Measurements to present:
- A scaling curve: runtime at 1, 2, 4, 8, 16 threads before and after padding. Flat or rising time with more threads is the signature, and near-linear scaling after the fix is the proof.
- Hardware counters: HITM (hit-modified) events per core, or perf c2c on Linux, which reports cache-line contention by address. Show the six offending lines by address before the fix and zero after.
- CPU utilisation and instructions per cycle: 12% utilisation with a 0.2 s floor is the quantitative gap.
- Memory bandwidth and NUMA placement: if any thread sits on the far socket, pin threads and check the remote-access counters.
Frame the conclusion as a one-line change with a measurable 15x improvement, and note that Amdahl still applies - if the 0.2 s of surrounding work is serial, the ceiling is around 0.2 s plus thread start-up, not zero.