55The matrix — a grid in a straight line of memory

In Chapter 54 the hash map handed us a value straight from its key — no order, no geometry, one hop. Here we want the opposite: a shape. Rows and columns, like a spreadsheet, a chessboard, or the pixels of a photo. But here's the catch the whole chapter turns on: the machine underneath has no grid. Volume 1 drew RAM as a single line of numbered boxes, one address after the next, and that really is all there is. So a matrix is a quiet trick — a two-dimensional idea folded flat onto one-dimensional memory. The one question worth chasing is where, in that single line, does cell (i, j) actually live? Answer that and the rest falls out. By the end you'll work out any cell's address in your head, see why summing a grid row-by-row beats column-by-column on identical work, and know exactly when a real contiguous block beats Python's list-of-lists.

01A grid is a story we tell; memory is a line

Let's start by drawing a 3×4 matrix. Your eye sees a rectangle — three rows stacked, four columns side by side. The CPU sees no such thing. Its memory is exactly what Volume 1 gave us: a single sequence of addressed slots — box 0, box 1, box 2 — running off in one direction only. There is no "up," no "down," no second axis anywhere. So to store a grid at all, the machine has to flatten it — unroll the rectangle into one long strip.

There are two honest ways to unroll it. The near-universal choice is row-major order: lay down all of row 0 end to end, then all of row 1 right after it, then row 2 — the rows concatenated into one contiguous run. (The other way, column-major, lays down whole columns first; Fortran, MATLAB, and Julia use it, and it will matter later.) Row-major is how C arranges a grid, and therefore how NumPy does, and therefore almost every image and tensor you touch. The rectangle in your head is a line in RAM.

If the whole grid is one flat line, then cell (i, j) lands at some exact position in it. Which one? There's a single formula — and it's the reason indexing a matrix is instant →

02The one formula: base + (i·ncols + j)·slot

Look at the strip again and reason it through. To reach the start of row i, you have to step past every row before it. Each of those rows is exactly ncols slots wide, and there are i of them — so i × ncols slots lie behind you. Now walk j slots into row i to reach the column you want. So the cell's position in the flat line — its linear index — is:

index = i × ncols + j  →  address = base + (i × ncols + j) × itemsize

where base is the RAM address of cell (0,0) and itemsize is the bytes per slot (8 for a 64-bit number). That's one multiply, one add — a fixed amount of arithmetic, no matter how vast the grid. That's why reading matrix[i][j] is O(1): the machine never searches for a cell. It computes where the cell must be and fetches it directly, just as array indexing did when we first built the array — now with the 2D→1D twist folded into the offset. And notice what does the work: ncols, the width. The formula only holds because every row is the same width, so the grid is rectangular. Store a jagged grid and the trick collapses.

We didn't take this on faith. NumPy lays a matrix out as exactly this flat block, so we can ask the machine for each cell's real address and check it against the formula:

import numpy as np
M = np.arange(20).reshape(4, 5)      # a 4×5 grid, so ncols = 5
base = M.ctypes.data                 # RAM address of cell (0,0)

for (i, j) in [(0,0), (0,3), (1,0), (2,4), (3,4)]:
    offset = (M[i, j:j+1].ctypes.data - base) // M.itemsize
    print((i, j), "formula i*ncols+j =", i*5 + j, " measured offset =", offset)

print("strides (bytes):", M.strides)      # (20, 4)  ·  one row = 5×4 bytes
print("C_CONTIGUOUS:", M.flags['C_CONTIGUOUS'])   # True

Line 2 builds the grid and reshapes it row-major. Line 3 grabs the base address. The loop asks NumPy for the true byte address of each cell, subtracts base, and divides by the slot size to get the offset in elements. Every one matched the formula exactly: (0,0)→0, (0,3)→3, (1,0)→5, (2,4)→14, (3,4)→19. The last line prints the strides — (20, 4) — which is the machine's own way of saying the same thing. Stepping one column over moves 4 bytes (one slot, the neighbour); stepping one row down moves 20 bytes (a full ncols × itemsize leap). Hold onto that asymmetry — the next section is entirely about it.

One multiply, one add, and you're at any cell. So why can two loops that touch every cell — same count, same Big-O — finish many times apart? Because of which direction you walk the line →

03Row by row is a sprint; column by column is a stumble

Here is the payoff — the whole Big-O lesson from Volume 3 made physical. Summing an n×n grid touches n² cells no matter which way you loop, so the operation count, the Big-O, is identical. But the machine doesn't charge by the operation. It charges by the cache line. Recall the metal: every miss to RAM hauls in a whole 64-byte line, betting you'll want the neighbours next, and a prefetcher races ahead when it spots a straight march. A matrix is laid out so that row neighbours are memory neighbours — while column neighbours are ncols slots apart.

So walk it row by row (the inner loop runs along j) and you stream straight down the contiguous strip. One miss pulls in eight useful numbers, and the prefetcher sees your line and readies the next. Walk it column by column (the inner loop runs down i) and every step jumps a full ncols × itemsize stride to a different cache line. That's a fresh miss per element, seven-eighths of every fetched line thrown away, the prefetcher blind. Same n² reads. Wildly different metal.

We measured both. In pure Python — a nested loop over a 2000×2000 list-of-lists, four million additions either way — row-major ran ≈354 ms and column-major ≈480 ms, about 1.36× slower. (Timings depend on the hardware; here the interpreter's own overhead swamps most of the cache cost.) To see the effect undiluted, strip the interpreter away and move the same bytes through NumPy's C loop. Reading a 4096×4096 block in memory order took ≈41 ms; reading it strided down the columns took ≈250 ms — about 6× for the identical data. Same work. The only thing that changed was the direction of the walk.

M = [[1]*2000 for _ in range(2000)]      # a 2000×2000 nested list

def row_major():                          # inner loop runs ALONG a row
    t = 0
    for i in range(2000):
        row = M[i]                        # one row object, then stream it
        for j in range(2000):
            t += row[j]                   # memory neighbours — cache-friendly
    return t

def col_major():                          # inner loop runs DOWN a column
    t = 0
    for j in range(2000):
        for i in range(2000):
            t += M[i][j]                  # jumps between scattered rows — hostile
    return t
# measured best-of-5: row_major ≈ 354 ms · col_major ≈ 480 ms  (≈1.36×)

The two functions compute the identical sum. The only difference is the loop nesting. In row_major the inner loop fixes i and sweeps j, so line 9 marches along one contiguous row after hoisting it into row. In col_major the inner loop fixes j and sweeps i, so line 16 re-indexes a different row object on every step, chasing pointers all over the heap. Swapping two for lines is the whole change — and it's free speed.

The pure-Python numbers were oddly muted — only 1.36×. That's a clue: a Python "matrix" isn't really a contiguous block at all. Which raises the real question — where does a list-of-lists live in memory? →

04Python's grid isn't a grid: list-of-lists vs one true block

When you write [[0]*cols for _ in range(rows)], you do not get one flat block. You get what Volume 1 would predict: an outer list holding rows eight-byte references, each one pointing off to a separate row-list object allocated somewhere else on the heap. Each of those row-lists is itself a contiguous run of references, pointing to separate integer objects, scattered again. That's three levels of indirection, and the rows can sit anywhere — so "moving to the next row" means a pointer-chase to an unrelated address. That's exactly why our column-major stumble was only 1.36×: the layout is already so scattered that walking it "the right way" barely helps.

NumPy does the opposite. An np.zeros((1000,1000)) is one contiguous block of raw values — no per-cell object, no per-row indirection — with a tiny header describing the shape and strides. Let's weigh the two:

import sys, numpy as np
r = c = 1000

nested = [[0]*c for _ in range(r)]                 # list of 1000 row-lists
struct = sys.getsizeof(nested) + sum(sys.getsizeof(row) for row in nested)
print("nested list, structure only:", struct, "B")   # 8,064,856 B ≈ 8.06 MB

block = np.zeros((r, c), dtype=np.int64)           # one contiguous block
print("numpy block:", block.nbytes, "B")              # 8,000,000 B  (+128 B header)

# the catch: those shared 0s are ONE cached int. Give each cell a real value:
big = [[i*c + j for j in range(c)] for i in range(r)]  # 1,000,000 distinct ints
print("with distinct values: ~", (struct + r*c*28)//10**6, "MB vs numpy 8 MB")

Line 4 sums the outer list's header plus all 1000 row-lists: 8,064,856 bytes, about 8.06 MB — and that's only the structure, because every cell is the integer 0, which Python caches as a single shared object (Vol 1). The NumPy block on line 7 is 8,000,000 bytes of raw int64 plus a 128-byte header — much the same here, since an 8-byte reference and an 8-byte integer weigh the same. The trap springs on line 12: the moment the cells hold distinct values, each becomes a real ~28-byte integer object on the heap. Now the nested version balloons to ~36 MB while NumPy stays flat at 8 MB — about 4.5× heavier, and every one of those objects is a separate cache-missing pointer-chase. NumPy stores numbers; a list-of-lists stores directions to numbers.

So the matrix is a deal: one rigid contiguous block, unbeatable when you touch cells by (i,j) and walk them in storage order. The last move is knowing when that deal is the right one to strike →

05The 1% move: pick the layout that matches your walk

Here's the human insight worth stealing. Someone had to notice that a two-dimensional grid doesn't need two dimensions — flatten it once, agree on row-major, and a single multiply-add reaches any cell forever. That's the whole invention: trade the intuitive rectangle for a formula, and indexing becomes free. The row-major-versus-column-major choice wasn't obvious either. It's a genuine historical fork: C chose row-major, Fortran chose column-major, and MATLAB and Julia inherited Fortran's. Neither is "right." What's wrong is code that fights its own storage order — a column-sweeping loop over a row-major block, or the reverse, quietly paying the cache tax on every step.

So here's the transferable move, the thing that is being good at data structures: know your access pattern before you pick your layout. Ask what you'll do most. Will you index arbitrary cells by (i, j) and sweep in a predictable direction? Then a matrix is the answer — dense, contiguous, O(1) access, and near-free to stream if your loop nesting agrees with the storage order. Will you mostly walk columns? Then store column-major, or transpose once up front and walk rows. The matrix isn't fast in the abstract. It's fast when your walk and its fold point the same way.

Everything so far — the array, the linked list, the stack, the queue, and now the matrix — has lived on a line, whether contiguous or chained. The matrix was the boldest bet on the line: cram a whole second dimension into it, and pay with rigid, dense storage. The next family gives that up entirely. It scatters its data across the heap as nodes joined by pointers, and in exchange for giving up the contiguous block it buys something the line never could: the power to halve the search space at every single step.

The next chapter opens the hierarchy family with the binary tree — a structure with no straight line at all, where each node points to two children, and that simple branching is the seed of logarithmic search. →