Interview Prep Zoneby CuriouserLabs

Question 2 of 5 · staff level

How do CPU caches actually work — lines, sets, associativity, eviction and write policies?

🎤 Say this first

Caches move fixed 64-byte lines, never single bytes — touching one field drags in its 63 neighbors (spatial locality is a hardware bet). An address splits into tag | set index | offset: the line can live only in one set, in any of that set's N ways (N-way set associative — a compromise between direct-mapped conflicts and fully-associative search cost). Eviction within a set is pseudo-LRU. Writes: modern caches are write-back (dirty lines flushed on eviction) with write-allocate — RAM lags the truth, and coherence (next question) papers over it.

The full picture

  • The 64-byte line is the practical unit of memory cost: array-of-structs vs struct-of-arrays, field ordering to pack hot fields into one line, and Java's Valhalla value-object motivation are all 'what shares my cache line' questions.
  • Conflict misses are real and weird: iterating a matrix by a power-of-two stride can hammer one set (all addresses share the set index) — the notorious '2048×2048 matrix is slower than 2047×2047' effect. Padding to break power-of-two strides is a legitimate fix.
  • Miss taxonomy (the 3 Cs) — compulsory (first touch; prefetching fights it), capacity (working set > cache; blocking/tiling fights it), conflict (associativity limits; padding fights it). Diagnosing which C is the actual work of cache tuning.
  • Prefetchers reward predictability: sequential and constant-stride patterns get recognized and fetched ahead — a further reason arrays beat pointer-chasing beyond the line effect: the prefetcher can't guess where a linked list goes next.
  • Instruction cache is a silent player: megamorphic call sites and bloated inlining hurt i-cache — one of the JIT's quiet balancing acts (inline for speed vs code-size blowup).

🔄 Likely follow-up questions

  • What's the difference between write-back and write-through, and where is each used?
  • Explain cache blocking/tiling with matrix multiply as the example.
  • How would you detect that conflict misses (not capacity) are your problem?