Exercises — False sharing problem

Compute the line index of each — that is the only test that matters. $\lfloor \frac{4096}{64}\rfloor =\lfloor 64\rfloor =64,\lfloor \frac{4100}{64}\rfloor =\lfloor 64.06\rfloor =64.$ Same line index $\Rightarrow$ yes, they false-share. The bytes differ, but the unit of transfer (the whole line 64) is identical, so each write kicks the line out of the other core's cache.

$\lfloor \frac{4096}{64}\rfloor =64,\lfloor \frac{4160}{64}\rfloor =\lfloor 65\rfloor =65.$ Different line indices ($64\ne 65$) $\Rightarrow$ no false sharing. Note $4160-4096=64=L$, so the second variable starts exactly one line later — the smallest gap that fully separates them.

The first line spans addresses $4096$ to $4096+63=4159$ (that's the 64 bytes with line index 64). Each int occupies 4 bytes, so how many fit? $64/4=16$ ints fit in a line, but we only have 8, so all 8 counter[0..7] share the same cache line. If 8 different cores each hammer their own counter, all 8 collide on one line — the worst case.

int = 4 bytes, so element $k$ sits at $8192+4k$. Line index of element $k$: $\lfloor \frac{8192+4k}{64}\rfloor =128+\lfloor \frac{4k}{64}\rfloor =128+\lfloor \frac{k}{16}\rfloor .$ For $k=0$: $128+0=128$. For $k=15$: $128+\lfloor 15/16\rfloor =128+0=128$. Same line — they false-share. In fact all indices $\mathrm{0..15}$ give line 128, so every element of this 16-int (64-byte) array lives in one line. No pair is ever separated — this array is one big collision zone.

Slowdown factor: $\frac{T_{\text{false}}}{T_{\text{local}}}=\frac{150}{2}=75\times .$ For $N=10^7$ increments: $\text{local: }2\times 10^7=2\times 10^7\text{ cycles},\text{false: }150\times 10^7=1.5\times 10^9\text{ cycles}.$ The false-sharing version does 75 times more work for the identical program output.

Because the struct is only 13 bytes (padded to 16) and starts at a line boundary, every field has line index equal to the struct's base line index. counter (offset 4), checksum (offset 8), done (offset 12) all fall inside the same 64-byte line. All three cores false-share on one line — a three-way ping-pong, even nastier than two-way because each write invalidates two remote copies.

To force each element into its own line, the stride between consecutive elements must be $\ge L=64$. So the padded struct size must be a multiple of 64: $\text{padded\_size}=\lceil \frac{\text{sizeof(value)}}{L}\rceil \times L=\lceil \frac{4}{64}\rceil \times 64=1\times 64=64\text{ bytes}.$ Padding bytes needed: $64-4=60$. Memory actually used is 4 bytes out of 64, so the useful fraction is $4/64=6.25\%$; the waste ratio is $60/64=93.75\%$. See Memory allocators for how allocators can hand back cache-aligned blocks.

Element $i$'s value lives at $B+64i$. Its line index is $\lfloor \frac{B+64i}{64}\rfloor =\frac{B}{64}+i$ (the division is exact because $B$ is a multiple of 64, and $64i/64=i$). So the line index of element $i$ is $\frac{B}{64}+i$. For $i\ne j$: $\frac{B}{64}+i\ne \frac{B}{64}+j,$ so the line indices differ — no shared line, no false sharing. The padding turned "same line" into "line index increases by exactly 1 per element."

sizeof(Bad) = 32 + 4 = 36 bytes (assume no extra alignment padding). Element $i$ begins at $B+36i$; its value is at $B+36i+32$.

• Element 0 value: offset $32$, line index $\lfloor 32/64\rfloor =0$ (relative to base line).
• Element 1 value: offset $36+32=68$, line index $\lfloor 68/64\rfloor =1$.

Here elements 0 and 1 happen to land in different lines (0 vs 1) — but this is luck of the offsets, not a guarantee. Element 1 value (offset 68) and element 2 value (offset $72+32=104$, line $\lfloor 104/64\rfloor =1$) both give line index 1 → they collide! Half-padding is fragile: the correct fix is a full-line stride of 64, as in L3.2.

Use std::hardware_destructive_interference_size (the standard's name for "$L$ that separates hot data") together with alignas:

#include <new>
struct alignas(std::hardware_destructive_interference_size) Cell {
    double value;
};
Cell arr[4];   // each Cell begins on its own line

Mechanism: alignas(k) forces each Cell to start at an address that is a multiple of $k$, and sizeof(Cell) is rounded up to a multiple of $k$ too — so the stride becomes $k$. Picking $k=L$ guarantees distinct line indices (the L3.2 proof). Why it adapts: the constant is provided by the compiler for the target architecture, so on a CPU with 128-byte lines it becomes 128 automatically — no hard-coded 64 to break.

Atomics from Atomic operations guarantee each increment is indivisible (no torn read/write), but an atomic RMW still needs the line in Modified state, so it still triggers coherence invalidations. With all 8 bins in one line, every core's atomic increment bounces the line — the ping-pong of the parent note, unchanged. Two-part fix:

1. Keep std::atomic<long> for correctness (safe concurrent updates).
2. Add padding/alignment so each bin gets its own line:

struct alignas(64) Bin { std::atomic<long> v; };
Bin bin[8];

Now correctness and performance are both handled. See Lock-free data structures for structures that assume this padding as a default.

Padded cost: $64\text{ cores}\times 64\text{ bytes}=4096$ bytes = 4 KiB, versus $64\times 4=256$ bytes unpadded — a $16\times$ blow-up, but tiny in absolute terms. When not to pad: False sharing only bites on writes that need exclusive ownership. If the counters are almost always read (Shared state can be held in many caches simultaneously — reads don't invalidate), the coherence traffic is negligible and padding just wastes space and cache capacity. NUMA connection: on a NUMA machine, an even bigger cost is placing a core's counter in remote memory. Padding to a line boundary is necessary but not sufficient — you also want each core's line allocated in its local NUMA node so reads/writes stay on-socket. See NUMA architectures and Multicore scaling.

Total increments across all cores: $N\times I=8\times 5\times 10^6=4\times 10^7$. Cores run in parallel, so wall-clock time is set by per-core work (each core does $I$ increments) — but under full false sharing the ping-pong serializes writes, so we count the aggregate cycles as the bottleneck resource.

(b) Unpadded (serialized ping-pong): total cycles = $N\cdot I\cdot t_{\text{far}}=4\times 10^7\times 160=6.4\times 10^9$ cycles. $T_{\text{unpad}}=\frac{6.4\times 10^9}{3.2\times 10^9}=2.0\text{ seconds}.$

(a) Padded (fully parallel, each core local): each core independently does $I\cdot t_{\text{loc}}=5\times 10^6\times 2=1\times 10^7$ cycles, and all 8 run at once, so wall-clock cycles = $1\times 10^7$. $T_{\text{pad}}=\frac{1\times 10^7}{3.2\times 10^9}=3.125\times 10^{-3}\text{ s}=3.125\text{ ms}.$

Speed-up: $\frac{T_{\text{unpad}}}{T_{\text{pad}}}=\frac{2.0}{3.125\times 10^{-3}}=640\times .$ Padding turned a 2-second job into 3 milliseconds.

With $I=5\times 10^6$, $t_{\text{far}}=160$, $f=3.2\times 10^9$: $T(N)=N\cdot 5\times 10^6\cdot 160/3.2\times 10^9=N\times 0.25$ s.

• $N=1$: $0.25$ s
• $N=2$: $0.50$ s
• $N=4$: $1.00$ s
• $N=8$: $2.00$ s

Time grows linearly with core count — negative scaling. Ideal parallel time is flat at $T_{\text{ideal}}=5\times 10^6\cdot 2/3.2\times 10^9=3.125\times 10^{-3}$ s regardless of $N$. This is the sharpest illustration of the Multicore scaling failure: false sharing converts extra cores from a benefit into a coherence-traffic tax. The fix (padding) restores the flat ideal curve.

Unpadded: $M/s=2048/4=512$ counters fit. Padded to full line: $M/L=2048/64=32$ counters fit. For 8 cores you need 8 padded counters = $8\times 64=512$ bytes $\le 2048$ — yes, padding fits comfortably (uses one quarter of the budget). The apparent $16\times$ waste per element is irrelevant here because 8 is far below the 32-counter ceiling.

The line index test for two addresses is ::: $\lfloor A/L\rfloor$ equal $\Rightarrow$ they false-share. Minimum stride to isolate elements is ::: exactly $L$ (64 bytes), a full line. Atomics fix ::: correctness (races), not false-sharing performance. Padding an int to a line wastes ::: $60/64=93.75\%$ of that block. False sharing makes scaling ::: negative — time grows with core count.