The Memory Hierarchy: Why Arrays Are Fast

The last lesson ended with a confession. The RAM model, the cost model underneath every big-O statement in this course, assumes that any single operation costs the same constant amount, including touching any location in memory. That assumption is false on real hardware, and not slightly false. This lesson is about exactly how false, why hardware works that way, and what it means for the data structures you choose.

Let's start by catching the model in the lie.

Take a square grid of numbers: 4,096 rows by 4,096 columns, about 17 million 32-bit integers, 64MB of data. Two functions sum every cell:

function sum_row_major(grid):        function sum_col_major(grid):
    total = 0                            total = 0
    for i from 0 to n-1:                 for j from 0 to n-1:
        for j from 0 to n-1:                 for i from 0 to n-1:
            total += grid[i][j]                  total += grid[i][j]
    return total                         return total

The left version walks the grid row by row: finish a row, move down. The right version walks it column by column: finish a column, move right. Both visit every cell exactly once. Both perform the same 17 million loads and 17 million additions. In the RAM model they have identical cost, the same O(n²) over a grid of side n, the same count to the last step.

Race them and the row version finishes in a few milliseconds. The column version takes roughly ten times longer. On the machine this course is produced on the gap is about 10x; on yours the exact ratio will differ, but it will not be 1x. Same big-O, same instruction count, an order of magnitude apart. Nothing in lesson 1 can explain that, and the explanation is the single most important fact about real-world performance that big-O doesn't capture.

Narrowing the suspect

Each loop iteration does two things: it loads one integer from memory, and it adds that integer to a running total. The additions are identical in both versions, same operation, same count, so the additions are innocent. All that's left is the load.

A load asks memory for a few bytes at a specific address, so look at the addresses each version generates. The grid lives in memory as one long block, row after row (this is called row-major layout, and it's how C, Go, NumPy by default, and essentially every flat array works). So the row-major loop asks for address 0, then 4, then 8: immediate neighbors, marching left to right through memory. The column-major loop asks for address 0, then 16,384, then 32,768, because stepping down one row means stepping over 4,096 integers of 4 bytes each, a 16KB jump per access.

Same number of loads, completely different address patterns, and the pattern is the only variable left. The conclusion forces itself on us: the cost of a memory access depends on where you're reaching and on what you touched just before. One step is not one step.

The gap

How much can a single load cost? A modern core runs at several billion cycles per second, and an integer addition takes about one cycle, a fraction of a nanosecond. A trip to main memory, the actual DRAM, takes on the order of 100 nanoseconds. Do the division: in the time one value crawls back from RAM, the core could have executed a few hundred additions.

This gap is not an accident of one chip, and it grew. From the 1980s onward, processor speed improved at a sprint while DRAM latency improved at a stroll, and the difference compounded year over year until architects gave it a name: the memory wall. The blunt consequence: on modern hardware, arithmetic is nearly free, and the real cost of a program is moving data to the core. A processor that went to RAM for every value would spend over 99% of its cycles stalled, waiting.

The hierarchy

Hardware's answer to the wall is to cheat with copies. Between the core and main memory sit layers of progressively smaller, progressively faster storage called caches:

Every load checks L1 first. If the value is there, that's a hit: pay about a nanosecond and keep moving. If not, a miss: the request falls to L2, then L3, then RAM, paying more at every floor until something answers, and the value is copied into the upper levels on its way back so the next access is cheap.

The last column is the one to internalize. Scaled to human time, an L1 hit is grabbing a pen off your desk and a RAM access is walking down the hall. A program whose every load misses to RAM is an office worker who commutes down the hallway for every word they read. The arithmetic we counted so carefully in lesson 1 is the one second at the desk.

The whole tower is a bet, the same bet at every level: whatever you touched recently, you are about to touch again. Modern performance rests almost entirely on that bet coming true. The rest of this lesson is about what makes it come true.

Cache lines: memory moves in blocks

One mechanism explains almost everything else. When a load misses and data comes up from memory, the hardware does not transfer the 4 bytes you asked for. It transfers a fixed-size block called a cache line: 64 bytes on most machines (128 on Apple Silicon). Ask for one 32-bit integer and you receive sixteen, your integer plus its fifteen nearest neighbors, parked in L1.

Why ship blocks? Because the expensive part of the trip is the trip itself, not the cargo. Once you have paid ~100ns of latency to reach DRAM, transferring 64 bytes costs barely more than transferring 4, so the machine hauls the whole neighborhood. Notice the assumption silently built into that decision: if you wanted this byte, you will probably want the ones next to it.

Locality

The bet has a name, two names actually, and they are the two most useful words in performance work:

• Temporal locality: what you touched recently, you will touch again soon. This is why caches keep your recent values. Loop counters, accumulators, and hot variables live in L1 and cost effectively nothing.
• Spatial locality: near what you touched is what you will touch next. This is why a miss hauls in the full 64-byte line, neighbors included.

Most real programs honor both bets most of the time, not because programmers are careful but because code is loops and data is sequences. Data structures are fast when they keep these two promises and slow when they break them, which is finally enough machinery to solve the opening mystery.

The mystery, solved

Replay the row-major loop, watching cache lines instead of cells. The loop asks for cell 0: miss, a ~100ns trip hauls back the line, sixteen integers. Cells 1 through 15: already present, fifteen hits at ~1ns each. Cell 16 misses and hauls the next line, then fifteen more hits. One slow trip buys sixteen cells, so the average cost per element is about (100 + 15) / 16 ≈ 7ns, and the prefetcher (next section) drives it lower still.

Now the column-major loop. Cell (0,0): miss. Step down one row, 16KB away: a different line, miss again. Every single access in the column traversal lands on a fresh cache line, so nearly every access pays the full trip. Worse, each miss hauled up sixteen integers and the loop used one. The other fifteen would be useful when the traversal wraps around to the next column, but by then 4,096 other lines have shoved through the cache and this one is long gone, evicted. The column version pays the trip almost every time and throws away about 94% of everything it hauls.

Same 17 million loads. Row-major pays one miss per sixteen accesses; column-major pays one miss per access. That is the 10x, and notice what produced it: not the algorithm, not the instruction count, only the order of access.

The prefetcher

Sequential access has one more gift waiting. The CPU watches the stream of addresses you load, and when it detects a pattern (this line, the next line, the next), it stops waiting for you and starts fetching lines you have not asked for yet, ahead of the loop. This is the hardware prefetcher. On a steady forward march through memory it hides the trip latency almost entirely: by the time the loop arrives, the data is already in cache, and the array stops being read line by line and starts streaming, limited only by raw memory bandwidth, tens of gigabytes per second on a laptop.

That is the full answer to this lesson's title. Arrays are fast because they are contiguous, one solid block of memory, which makes a scan sequential, which means every cache line hauled is fully used and the prefetcher can see the future. The array is not lucky. It is, by construction, the exact access pattern the machine was built to reward.

Pointer chasing: the anti-array

Now meet the opposite. A linked list stores each element in its own separately allocated node, and each node holds a pointer, the address of the next node. The nodes can live anywhere in the heap, and in a long-running program, they do.

Sum a linked list of the same 17 million integers. Load the first node: miss, ~100ns. Where is the next node? Unknown, until that load completes, because the address of step two is data sitting at the end of step one. The CPU cannot start the next fetch early, and the prefetcher sees no pattern because there is none. Each line hauled up carries 64 bytes of which the node uses a fraction; the neighbors belong to unrelated objects. Traversal degenerates into a chain of dependent misses: 100ns × 17 million ≈ 1.7 seconds, where the array took milliseconds.

Both are O(n). Both "visit each element once." One streams, one commutes. This is the canonical example of two same-big-O algorithms separated by an order of magnitude or more purely by memory behavior.

Linked lists do have real wins (cheap insertion in the middle, no resize spikes, stable element addresses), and lesson 5 is precisely about when those wins are worth the toll. The point here is only that the toll exists and that it is large.

The race, in real code

The videos stay in pseudocode; here is the opening demo in the three languages this course carries, so you can reproduce the race yourself.

The TypeScript version uses a flat Int32Array, indexed as i * n + j, which makes the memory layout explicit; a JS array-of-arrays would add a pointer chase per row, which is its own small lesson.

const n = 4096
const grid = new Int32Array(n * n)
 
function sumRowMajor(): number {
  let total = 0
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) total += grid[i * n + j]
  return total
}
 
function sumColMajor(): number {
  let total = 0
  for (let j = 0; j < n; j++)
    for (let i = 0; i < n; i++) total += grid[i * n + j]
  return total
}

const n = 4096
 
var grid = make([]int32, n*n)
 
func sumRowMajor() int64 {
	var total int64
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			total += int64(grid[i*n+j])
		}
	}
	return total
}
 
func sumColMajor() int64 {
	var total int64
	for j := 0; j < n; j++ {
		for i := 0; i < n; i++ {
			total += int64(grid[i*n+j])
		}
	}
	return total
}

constexpr int n = 4096;
std::vector<int32_t> grid(n * n);
 
int64_t sum_row_major() {
    int64_t total = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) total += grid[i * n + j];
    return total;
}
 
int64_t sum_col_major() {
    int64_t total = 0;
    for (int j = 0; j < n; ++j)
        for (int i = 0; i < n; ++i) total += grid[i * n + j];
    return total;
}

All three index the same flat block two ways. The inner expression is identical; only the loop order differs, which means only the address pattern differs. Time them (wrap in console.time, testing.B, or std::chrono) and you will see the gap on your own machine. If you want to go one level deeper, run the C++ or Go version under a profiler that reports cache misses (perf stat -e cache-misses on Linux, Instruments on macOS) and watch the miss counter, not the time, tell the whole story.

Where this shows up in production

Once you see access patterns, you see them everywhere:

• Columnar databases. Analytics engines like ClickHouse store tables by column rather than by row, precisely so that a query scanning one field becomes one giant sequential read. That is the row race won on purpose, and it is how a single machine scans billions of values per second.
• Game engines. The industry moved from objects scattered across the heap toward tightly packed arrays of components (entity component systems), because simulating ten thousand entities per frame is a loop, and loops love contiguous data.
• Your standard library. The default sequence type in every mainstream language (C++ vector, Go slice, JS array, Python list, Rust Vec) is a contiguous block, not linked nodes. The defaults encode this lesson.
• The insertion sort oddity from lesson 1. Real sorting libraries switch to insertion sort, a quadratic algorithm, below a few dozen elements. Now you can name the reason: at that size the whole array is two or three cache lines, insertion sort just slides neighbors around inside L1, and its steps are so physically cheap that the asymptotically better algorithm cannot pay off its overhead before the work is done.

Big-O first, then the machine

Does any of this dethrone big-O? No, and it is worth being precise about why. The memory hierarchy changes the price of a step, by a factor of 10, sometimes 100. It does not change how the number of steps grows. A quadratic algorithm with perfect locality still loses to a linear one at some n, always: a 100x constant factor is still a constant, and the gap between n and n² is not. The growth ladder from lesson 1 is undefeated.

What the hierarchy explains is everything big-O leaves blank: why two O(n) functions differ by 10x, why "fewer, friendlier steps" beats "fewer steps" at real-world sizes, why the structures that run production are arrays under the hood far more often than the textbooks suggest.

So the discipline of this course, from here on, prices everything twice. First the shape: how does cost grow with n. Then the layout: is each step a desk reach or a hallway commute. Get the shape wrong and no layout saves you. Get the layout wrong and you leave a factor of ten on the table.

Next lesson we take the hardware's favorite shape, the contiguous block, and build the thing you actually use every day on top of it: the dynamic array. Allocation, growth, the doubling trick from lesson 1's amortized math, and the exact moment an innocent-looking append quietly costs O(n).