The CPU Cache Hierarchy

Fetching a value from main memory (RAM) takes a CPU roughly 100-300 clock cycles. Fetching a value already sitting in the CPU's fastest on-chip storage takes about 4 cycles. That's a 25-75x gap for doing nothing but reading a number — before any arithmetic even happens. Two pieces of code can perform the exact same additions in the exact same order and differ in wall-clock speed by an order of magnitude purely because of where in memory they happened to look, and in what order. That gap is the cache hierarchy, and it is one of the most consistently underestimated forces in performance-sensitive code.

The idea: a warehouse with shelves at different distances

Picture a CPU as a worker at a desk who needs parts to assemble something. Walking to the main warehouse (RAM) for every single part is slow — it's far away. So there's a small drawer right at the desk (L1 cache, typically 32-64 KB, about 4 cycles away), a bigger cabinet a few steps away (L2 cache, a few hundred KB to a few MB, about 12 cycles), and a shared storage room down the hall (L3 cache, several MB, shared across cores, about 40 cycles) before you're all the way back at the warehouse (RAM, 100-300+ cycles). Each level is bigger but farther and slower than the one before it.

The trick that makes this work is that when the worker walks to fetch one part, they don't grab just that part — they grab the whole nearby shelf section (a cache line, typically 64 bytes on modern x86 CPUs) and bring it back to the drawer, betting that the next part needed will be physically near the one just fetched. This bet pays off constantly in real programs because of two patterns: temporal locality (if you used a value recently, you'll likely use it again soon — keep it nearby) and spatial locality (if you used an address, you'll likely use a nearby address next — an array, not scattered objects). Code that respects these patterns gets fed from the fast drawer almost every time (a cache hit); code that jumps around unpredictably keeps forcing a trip to the slow warehouse (a cache miss).

Worked example: row-major traversal versus column-major traversal

A 2D array in most languages (including NumPy, by default) is stored row-major: row 0's elements are contiguous in memory, then row 1's elements immediately after, and so on. Summing a 1000×1000 matrix by iterating rows-then-columns walks memory in exactly the order it's laid out — each 64-byte cache line fetched holds 8 consecutive float64 elements you're about to use anyway (for float64, 8 bytes each, $64 / 8 = 8$ elements per line), so the CPU almost never waits on RAM.

import numpy as np, time

A = np.random.rand(4000, 4000)

t0 = time.perf_counter()
total = 0.0
for i in range(A.shape[0]):        # row-major: matches memory layout
    for j in range(A.shape[1]):
        total += A[i, j]
print("row-major:", time.perf_counter() - t0)      # baseline

t0 = time.perf_counter()
total = 0.0
for j in range(A.shape[1]):        # column-major: fights memory layout
    for i in range(A.shape[0]):
        total += A[i, j]
print("column-major:", time.perf_counter() - t0)    # noticeably slower

Trace the column-major version: each step to A[i+1, j] jumps 4000 elements ahead in memory (one full row's width), not 1. That's 4000 × 8 bytes = 32,000 bytes away — far outside any 64-byte cache line just fetched. Every single access is effectively a fresh trip to a farther cache level or RAM. Even though both versions do the exact same number of additions in the exact same total set of memory locations, the row-major version can run several times faster purely from access order — with pure Python loops (as above) both are slow overall, but the relative gap between the two orderings is the same mechanism that, in optimized C++ code operating close to cache speed, routinely shows up as a 5-10x difference.

column-major traversal jumps a full row's width each step -- fights memory order

Where this shows up

In a quant-dev interview, this is the mechanism behind "why is my C++ code slower than expected even though the algorithm is optimal" — expected answers involve cache-line size, access patterns, and struct layout (packing frequently-accessed fields together, called "hot/cold splitting"). In production, it directly informs data structure choice on the hot path of a matching engine or market-data handler: an order book is commonly implemented as a flat array indexed by price level rather than a tree of pointer-linked nodes, specifically because sequential array access is cache-friendly while chasing pointers through a tree (Order Book Data Structure) is not, even though the tree might look cleaner in an algorithms textbook and have the same asymptotic complexity.