Performance
Cache vs big-O: multiple-choice review
Crux Multiple-choice synthesis across the cache-vs-big-O unit — memory hierarchy, cache lines, false sharing, branch prediction, data layout, and reading a perf profile.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at senior altitude — in orbitSix questions that cut across the whole unit. None is a definition to recite — each is the judgement call you make when a “fast” algorithm loses to a “slow” one and big-O has nothing to say about it.
Goal
Confirm you can connect the memory hierarchy, cache-line behaviour, false sharing, branch prediction, and data layout into one diagnostic instinct: read the profile, name the constant-factor cause, pick the matching fix.
Quiz
Completed
A linked list of 1M nodes iterates ~17x slower than an array of 1M ints, though both are O(N). Which statement best explains the gap?
Heads-up Big-O is asymptotic and correct — both are O(N). What it omits is the per-operation constant, which the memory hierarchy sets: ~1 ns for a cache hit vs ~100 ns for a RAM miss.
Heads-up Instruction count per node is comparable; the CPU stalls waiting on memory, not on extra arithmetic. The cost is miss latency, not op count.
Heads-up Even when both working sets exceed cache, the array still wins: sequential access is prefetched while pointer-chasing is data-dependent and unpredictable. It is access pattern, not just capacity.
Quiz
Completed
A team flips a matrix-multiply inner loop from row-major to column-major order on a 10 000×10 000 double matrix and sees a ~9x slowdown. The arithmetic is identical. Root cause?
Heads-up Both loop orders are O(N²) with identical operation counts. The regression lives entirely in the constant factor — cache-miss rate — not the asymptotic class.
Heads-up No flag fixes an 80 000-byte stride. The access pattern itself defeats the prefetcher and SIMD; the fix is loop reordering or cache-oblivious tiling, not a flag.
Heads-up It is a square 10k×10k matrix — rows and columns are equal length. Memory layout (row-major storage), not dimension, drives the gap.
Quiz
Completed
A counter array is made lock-free with atomics and gets slower than the locked version as threads scale. perf shows IPC 0.4 and a 72% cache-miss rate. Diagnosis?
Heads-up Atomics are not locks. Lock contention shows as off-CPU wait time; this signature — high CPU, IPC collapse, high cache-miss rate — is memory-bound coherency traffic, i.e. false sharing.
Heads-up A handful of uint64 counters is ~128 bytes — trivially L1-resident. The defect is multiple cores writing the same 64-byte line, not capacity.
Heads-up An atomic add has no data-dependent branch. Branch misses raise the branch-miss counter, not the cache-miss counter; the 72% figure points squarely at memory.
Quiz
Completed
Sorting an array before summing the elements above a threshold yields a 2–3x speedup, despite the extra O(N log N) sort. Why does it pay back?
Heads-up Every element is still compared to the threshold after sorting — the comparison count is unchanged. The win is branch predictability, not fewer comparisons.
Heads-up A linear scan of an array is already cache-friendly whether sorted or not. The dominant effect here is branch prediction, not memory locality.
Heads-up Auto-vectorisation does not depend on sort order. The documented, architecture-independent speedup comes from turning an unpredictable branch into a predictable one.
Quiz
Completed
A hot ML loop runs 5x slower than a reference C++ port; perf shows IPC 0.8 and 25% L3 miss rate. Someone proposes adding SIMD intrinsics. What is the correct first move?
Heads-up SIMD on AoS data forces gather/scatter (~10x a contiguous load) and does nothing for a memory-bound loop. IPC 0.8 + 25% L3 miss is a layout problem; SIMD on bad layout buys nothing.
Heads-up Flags are worth checking, but they cannot turn an interleaved AoS layout into contiguous SIMD-friendly data. The signature is memory-bound, not under-optimised compute.
Heads-up Both versions run the same algorithm; a 5x gap with high L3 miss rate is a constant-factor layout cost, not an asymptotic difference.
Quiz
Completed
perf stat on a hot loop reports IPC 0.40, branch-miss 25%, and LLC-miss 47%. You can fix one thing first. Which, and why?
Heads-up A 10–30 cycle flush is real, but a RAM miss is ~300 cycles and 47% of L3 lookups miss. The memory stall is the larger lever here; fix layout first, then branches.
Heads-up IPC is not a knob — it is the result of stalls. It is 0.40 because the CPU waits on memory and mispredicted branches. Remove those causes and IPC rises on its own.
Heads-up Nothing in the profile points to the asymptotic class; it points to constant factors — layout and branch behaviour. A 'better' big-O with worse locality could easily be slower.
Recap
The unit’s through-line is one decision tree: big-O sizes how cost grows with N, but the memory hierarchy sets the constant — and that constant swings ~100x with layout. Contiguous beats pointer-chasing; loop order must match storage order; per-thread writes need their own cache line; unpredictable branches want sorting or branchless code; one-field-at-a-time work wants SoA. When a profile is in front of you, read miss rates and IPC first, name the constant-factor cause, and apply the matching fix — measure, never guess.