Two threads each increment their own private counter, but the two counters are adjacent fields of the same object. Measured throughput is worse than one thread doing both increments, and it gets worse as you add cores. Explain what the hardware is doing and how you would confirm and fix it.
answer
- Private variables, same line → false sharing
- Write needs exclusive ownership → invalidate
- Line ping-pongs; negative scaling with cores
- Confirm: coherence-miss counters or separate-and-measure
- Fix: pad/align, or accumulate per thread and merge
basics
~20 sFalse sharing. Coherence tracks whole cache lines, so both counters live in one line; each write must take exclusive ownership and invalidates the other core's copy, so the line ping-pongs between caches. Confirm with coherence-miss counters or by separating the fields; fix by padding or aligning them onto different lines, or by accumulating per thread.
solid answer
~50 sThe counters are logically private but physically share one cache line, and coherence works at line granularity. To write, a core must hold the line in an exclusive/modified state, so every increment invalidates the other core's copy and pulls the line across the interconnect. The line ping-pongs, each increment costs a coherence miss instead of an L1 hit, and adding cores makes it worse — negative scaling on data that is not actually shared. To confirm rather than guess: look at hardware counters for coherence misses on modified lines, or run the controlled experiment — move one counter to a separate allocation, or pad the struct to a line boundary, and re-measure. Fixes, in order of preference: give each thread its own line-aligned slot (padding/alignment), or better, accumulate in a thread-local variable and merge on read so the shared line is touched rarely. Padding costs memory and cache footprint, so apply it only to measured hot spots.
code
text · 11 lines// contended: two counters in one line
struct Stats { long a; long b; } // offsets 0 and 8 -> same 64B line
// padded: one counter per line
struct PaddedCounter { long value; byte pad[56]; } // 64 bytes total
PaddedCounter counters[NUM_THREADS]; // thread i touches counters[i] only
// usually better: no shared line on the hot path
local = 0
loop { local += 1 } // register / thread-local
atomic_add(shared_total, local) // once per batchgo deeper
Recognise the phrase false sharing and say that coherence works on whole lines, so unrelated adjacent variables collide; know that padding separates them.
Explain the ownership mechanism and the ping-pong, describe the negative-scaling signature, and name both fixes: padding and thread-local accumulation.
Lead with diagnosis — counters or the separate-and-measure experiment — then apply the narrowest fix and discuss padding's memory cost and fragility under a relocating runtime.
Treat it as a layout-and-ownership design question: which state is per-core by construction, what write rate the design implies, and when to redesign for private accumulation instead of patching layout.
## The mechanism Caches track memory in aligned blocks (cache lines, typically 64 bytes) and coherence hardware maintains, per line, an invariant close to *single writer or multiple readers*. A core that wants to write must obtain the line in an exclusive state, which requires invalidating every other core's copy. Reads can be replicated freely; writes cannot. The hardware knows nothing about variables. Two counters at, say, offsets 16 and 20 of one object are one line as far as coherence is concerned. So thread A's increment of counter A invalidates thread B's cached copy of the line that holds counter B, and vice versa. Every increment becomes a request across the interconnect and a wait for the line to arrive, instead of a load-add-store hitting L1. ``` core A: write cA -> invalidate line in core B, take ownership core B: write cB -> invalidate line in core A, take ownership core A: write cA -> invalidate again ... ``` This is **false sharing**: no logical sharing, full hardware contention. Its signature is distinctive — a workload with zero synchronisation and no shared state that gets *slower* as threads are added, with the slowdown proportional to write rate. ## True sharing vs. false sharing If the two threads were incrementing the *same* counter, the same line traffic would appear — that is **true sharing**, and the fix is algorithmic (shard the counter, batch updates). False sharing is the nastier case because the source code offers no clue: the fields are private, the fix is about physical layout. Both show up identically in profiles, so diagnosis must distinguish them by asking whether the *addresses* collide, not whether the *variables* do. ## Confirming it 1. **Hardware counters.** Most CPUs expose events for cache misses served from another core's modified line. A hot line under such an event, attributed to a store instruction in the loop, is close to proof. 2. **The separation experiment.** Move one counter into its own allocation, or insert padding so the two are more than a line apart, and re-measure. If throughput jumps and scaling turns positive, it was false sharing. This works everywhere and needs no special tooling. 3. **Scaling curve.** Plot throughput against thread count. False sharing typically flattens or inverts the curve early; a genuine bandwidth or algorithmic limit flattens more gradually. Do not diagnose it by reading code alone — layout depends on the allocator and the runtime, and the guess is often wrong in both directions. ## Fixes - **Padding / alignment.** Give the hot mutable field its own line: align the containing structure to the line size and pad it to a full line, or place each thread's slot at a line-sized stride in an array. Some hardware prefetches lines in pairs, so a stride of two lines is occasionally needed. - **Per-thread accumulation.** Better than padding when possible: each thread accumulates in a register or thread-local variable and flushes into shared state rarely (on a timer, on batch boundaries, or at the end). This removes almost all the traffic instead of merely spreading it out, and it costs no per-object memory. - **Separate hot from cold.** Keep frequently written fields away from fields other threads read constantly. A read-mostly field sitting next to a write-hot one turns cheap replicated reads into invalidations. - **Reduce the write rate.** Sampling, approximate counters, or per-shard counters summed on read are often acceptable and beat any layout trick. ## Costs and cautions Padding is not free: a padded counter can grow from 8 bytes to 64 or 128, which matters if you have millions of them — you trade coherence traffic for capacity misses and memory. Padding also assumes a line size you have hard-coded, and language runtimes may reorder fields or relocate objects, so a padding scheme can be silently undone by a compiler, allocator, or moving collector. That is why the credible answer is always *measure, apply narrowly to the hot structure, and re-measure*, and why the structural fix (do not share the line at all, accumulate privately) is preferred where the design allows it.
- How would you prove it is false sharing rather than true sharing or a plain memory-bandwidth limit?Ask whether the addresses collide or the data does. If the threads write distinct variables and separating those variables onto different lines restores scaling, it was false sharing. If they write the same variable, no layout change helps and the fix must be algorithmic. A bandwidth limit shows up as a ceiling that does not move when you change layout, and as high traffic to DRAM rather than core-to-core transfers.
- When is padding the wrong fix?When the padded objects are numerous, because inflating each instance to a full line multiplies memory and evicts other useful data; when the fields are actually read together, since spreading them costs extra misses on the read path; and when the runtime may rearrange or relocate the layout, so the padding is not guaranteed to survive. In those cases prefer reducing the write rate: thread-local accumulation, sharded counters merged on read, or sampling.
Two colleagues keep their notebooks in one shared drawer that only one person may hold at a time. Neither reads the other's notebook, yet every jotting requires taking the drawer back — the collision is over the container, not the contents.
saying these in an interview costs you the question
- Saying the counters need a lock or an atomic operation — there is no correctness problem, only a performance one
- Believing false sharing is a correctness bug that can produce wrong values
- Padding everything by default rather than the measured hot structure
- Assuming reads cause the same contention as writes
- Diagnosing from source code alone without checking actual layout or counters