Why does traversing a 64-byte cache-line-aligned array outperform a pointer-chasing linked list by 10x–20x even when both are O(n)?

A strong answer

When answering Why does traversing a 64-byte cache-line-aligned array outperform a pointer-chasing linked list by 10x–20x even when both are O(n)?, start from the hardware and runtime invariants taught in Cache lines and prefetching. Explain 64-byte CPU cache lines, hardware spatial prefetching, L1/L2/L3 vs DRAM latency, and pointer-chase memory stalls.

First, walk the interviewer through the concrete physical mechanism: on modern multi-core CPUs, memory is transferred in 64-byte cache lines governed by the MESI cache-coherency protocol, where an L1 cache hit costs roughly ~1 ns (4 cycles), an L2 hit costs ~4 ns, an L3 hit costs ~12 ns, and a main-memory DRAM fetch or cross-socket cache-line invalidation costs ~65–100 ns (over 200 cycles). Whenever an algorithm chases scattered pointers, triggers branch mispredictions (~15–20 cycle pipeline flush), or contends on a shared cache line via atomic Read-Modify-Write operations, the CPU's out-of-order execution engine stalls waiting on memory subsystems rather than arithmetic ALUs.

Second, state the exact correctness and progress guarantees: distinguish clearly between blocking synchronization (where a preempted lock holder stalls all waiters) and non-blocking / lock-free synchronization (where at least one thread makes system-wide progress in a finite number of steps via atomic Compare-And-Swap loops, paired with explicit memory ordering and safe reclamation). Always quantify both the asymptotic bound and the cache-line / memory-bandwidth constant factor.

What the interviewer is listening for

• Hardware-grounded mechanics: Citing concrete 64-byte cache line behavior, MESI invalidation traffic, branch predictor pipelines, or atomic memory ordering (acquire/release vs seq_cst) rather than hand-waving "it's faster".
• Exact correctness invariant: Explaining the exact race window (such as ABA recycling or use-after-free during concurrent readers) and how the mechanism closes it.
• Production trade-offs: Knowing when a simpler contiguous array, sharded lock, or Epoch-Based Reclamation beats a complex lock-free pointer structure.

Common mistakes

• Confusing asymptotic Big-O step counts with actual hardware execution time when pointer-chasing causes an L3/DRAM cache miss on every step.
• Using memory_order_relaxed when publishing shared pointers or forgetting that unlinking a node in a lock-free structure does not make it safe to free() while concurrent readers are mid-traversal.
• Benchmarking without preventing compiler dead-code elimination or without inspecting hardware performance counters (perf stat).