Cache-Friendly Data Structures

TL;DR: Layout beats algorithm at this scale. A cache line is 64 bytes on current parts and it moves between cores as one unit, which produces two effects that show up constantly in infrastructure code. First, a data structure that stores pointers to elements makes every lookup two dependent memory accesses, and the second cannot begin until the first returns, so the stalls serialize; storing elements inline makes it one. Second, two threads updating variables that happen to share a line contend as if they shared data, which is false sharing and it is fixed by padding each independently-updated field onto its own line. The costs are concrete: an uncontended access to a line already owned is a couple of nanoseconds and a contended transfer is tens to over a hundred, and a DRAM miss is around 80 nanoseconds against a one-nanosecond comparison.

The line is the unit

A core does not read a byte; it reads a 64-byte line into its cache, and it owns that line exclusively while writing to it. Everything below follows from those two facts.

the numbers to carry
  cache line                      64 bytes on current x86 and Arm server parts
  L1 hit                          a few cycles
  DRAM access                     roughly 80 ns
  a comparison or add             roughly 1 ns
  an uncontended atomic increment on a line you own      a few ns
  the same increment when the line must be transferred   tens to over 100 ns

what that ratio means
  80 ns of memory against 1 ns of arithmetic is 80 to 1, so a structure that causes one extra
  miss per operation is 80 times more expensive than one that causes an extra compare
sanity: this is why layout decisions dominate algorithmic ones at these sizes, and why a
        theoretically worse algorithm with better locality frequently wins

Pointer chasing, and why a node-based map is slow

A hash map that stores each element in its own heap node has a lookup that goes: hash the key, read the bucket array, dereference the pointer, compare. Steps two and three are both potential misses, and step three cannot start until step two returns, so the hardware cannot overlap them.

a lookup on a map too large for cache
  node-based:  hash (~1 ns) + bucket miss (~80 ns) + dependent node miss (~80 ns) + compare
               ≈ 162 ns, and the two misses serialize
  flat, open-addressed: hash (~1 ns) + one slot miss (~80 ns) + compare
               ≈ 81 ns, and a linear probe usually stays in the same line

  ratio ≈ 2x, which is the ceiling on what the layout change can buy
sanity: this predicts the measured range for real implementations, which is why the
        node-based structure's cost is a property of the layout rather than of the code
        quality

The reason standard node-based maps exist is a guarantee rather than an oversight: keeping references to elements valid across a rehash forces each element into its own allocation, because a reallocated array would move them. Flat maps trade that guarantee away, which is exactly the property to check before substituting one.

False sharing, the same mechanism on unrelated data

Two counters in one structure occupy one line. Two threads incrementing them independently force that line to move between cores on every write, so unrelated variables contend exactly as if they were shared.

three counters in a struct, no padding
  8 + 8 + 8 = 24 bytes, all inside one 64-byte line
  thread A increments the first, thread B the second: the line ping-pongs

padded
  each counter aligned to its own line: 3 x 64 = 192 bytes
  the memory cost is 168 extra bytes; the throughput gain at high thread counts is large

when to pay it
  hot counters updated by different threads: always
  an array of millions of small structs: never, since the memory cost dominates
sanity: C++17 exposes hardware_destructive_interference_size rather than hardcoding 64,
        because the value is a property of the target and not a constant of the universe

The thread-local version is worth naming as the better answer where it applies: a counter each thread owns privately costs one instruction, no coherence traffic and no atomics, and the totals are summed at report time. Concurrency in Python, Go and C++ covers the threading models these choices sit inside.

Where this shows up in infrastructure code

• Metrics and telemetry, where per-thread counters are incremented millions of times a second and a shared atomic becomes a top profile entry.
• Schedulers and queues, where a per-worker structure touched by other workers during stealing needs its shared and private parts on different lines.
• Index structures over job records, trace lines or interval sets, where the flat-against-node choice is the difference between one miss and two per lookup.
• Log and trace parsing, where an array of structs against a struct of arrays decides whether a scan reads only the fields it needs.

What interviewers are listening for

The mechanism, named. Saying a structure is slow is folklore; saying the lookup is two dependent misses because the elements live in separate allocations is understanding, and it generalizes to structures the interviewer has not asked about. For the threading half, the signal is knowing false sharing exists at all, since it is invisible in the code, and knowing that padding costs memory so it belongs on hot counters rather than everywhere.

Key takeaways

• A 64-byte cache line is the unit of transfer and of coherence, and roughly 80 ns of DRAM against 1 ns of arithmetic is why layout dominates.
• Node-based lookups pay two dependent misses, about 162 ns, against roughly 81 for a flat structure, capping the gain near 2x.
• Node-based maps exist to keep references valid across a rehash, so check whether code relies on that before switching.
• False sharing is unrelated variables contending for one line; pad independently-updated hot counters onto their own line at 64 bytes each.
• A thread-local non-atomic counter beats every shared design where a global total is only needed at report time.