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, just one hop. Here we want the opposite thing, a shape — rows and columns, like a spreadsheet, a chessboard, or the pixels of a photo. But here is 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 is genuinely all there is. So a matrix is a quiet trick that folds a two-dimensional idea flat onto one-dimensional memory. The one question worth chasing is this: where, in that single line, does cell (i, j) actually live? Answer that and the rest falls out. By the end you will compute any cell's address in your head, feel why summing a grid row-by-row beats column-by-column on identical work, and know exactly when a real contiguous block crushes 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, because its memory is exactly what Volume 1 gave us. It is a single sequence of addressed slots, box 0, box 1, box 2, marching off in one direction only, with no "up," no "down," and no second axis anywhere. So to store a grid at all, the machine has to flatten it, unrolling the rectangle into one long strip.

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

Make the fold concrete before the formula arrives. Take that 3×4 grid and label its cells a through l, reading left to right, top to bottom: [a,b,c,d] on top, [e,f,g,h] in the middle, [i,j,k,l] at the bottom. Row-major writes them into memory in exactly that reading order, twelve slots with no gaps: a b c d e f g h i j k l. Cell b and cell c were side by side in the grid, and they stay side by side in the line. But a and e sat one directly above the other, and now four slots separate them. That single gap is the whole story of this chapter. Going sideways is cheap. Going down costs a full row.

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 out. To reach the start of row i, you must 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. The cell's position in the flat line is its linear index, and it works out to:

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

Here base is the RAM address of cell (0,0), and itemsize is the bytes per slot (8 for a 64-bit number). That is one multiply, one add, a fixed amount of arithmetic no matter how vast the grid. This is 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. That is exactly what array indexing did back when we built the array, now with the 2D→1D twist baked 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.

Feel why that rectangle is non-negotiable. Suppose row 0 held 4 cells but row 1 held only 2. The formula still wants to compute i × ncols to skip past whole rows, but which ncols? There is no single width to multiply by, so the jump lands somewhere meaningless. A grid earns its O(1) indexing precisely because every row is the same width. The moment the widths differ, the machine must store where each row begins and look it up, so the free arithmetic is gone and you are back to a jagged pile of separate lists.

Let's plug real numbers in and watch it fire. Stay with the 3×4 grid, so ncols is 4, and ask for cell (1,2): row 1, column 2, which is the value g from a moment ago. First step past the rows behind it. There is one full row above, so that is 1 × 4 = 4 slots. Then walk 2 more slots into row 1. You land at slot 4 + 2 = 6. Count it off on the strip a b c d e f g, and g really is the seventh box, index 6. No scanning, no searching. One multiply, one add, and you are standing on the cell.

Now stretch it so the formula has to work a little harder. Picture a 5×8 grid, five rows by eight columns, and reach for cell (3,6). Step past the three full rows behind it, which is 3 × 8 = 24 slots. Then walk 6 more into row 3, landing at 24 + 6 = 30. If each cell is an 8-byte number, that is a byte offset of 30 × 8 = 240 from base. One multiply, one add, one shift, and the grid could be a million rows deep without changing that count.

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 single 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), the machine's own words for the same fact. Stepping one column over moves 4 bytes, one slot to the neighbour. Stepping one row down moves 20 bytes, a whole 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, and it is 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 does not 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 will 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 sit ncols slots apart.

Put a number on that 64-byte line, because the next paragraph leans on it. Our cells are 64-bit integers, so each one weighs 8 bytes, and 64 ÷ 8 = 8. Every trip to RAM therefore drags back eight numbers at once, whether you asked for eight or just one. Read them in the order they arrived and all eight get used before the next trip. Read one, jump far away, read one again, and you paid for eight but kept one. Seven of every eight numbers hauled in and thrown straight back out. That ratio, not the operation count, is what the timings below are really measuring.

So walk it row by row, with the inner loop running 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, with the inner loop running down i, and every single step jumps a full ncols × itemsize stride to a different cache line. That means a fresh miss per element, seven-eighths of every fetched line thrown away, and the prefetcher left blind. Same n² reads. Wildly different metal.

We measured both. In pure Python, a nested loop over a 2000×2000 list-of-lists does four million additions either way. Row-major ran ≈354 ms and column-major ≈480 ms, about 1.36× slower. Timings are hardware-dependent, and 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.

Put it in nanoseconds to feel the height difference. That 4096×4096 block holds 4096² = 16,777,216 cells, about 16.8 million. Reading it in memory order in ≈41 ms works out to roughly 2.4 ns per cell. Reading it strided in ≈250 ms is about 14.9 ns per cell — the very same cell, visited the same number of times, costing six times as long. The curve keeps its shape, but column-major draws it far taller.

Sit with what those two numbers mean, because it dents a comfortable belief. Big-O said both walks are O(n²), and that is true: the exponent, how the cost grows as the grid gets bigger, is identical. But Big-O deliberately hides the constant factor sitting out front. Here that hidden constant reached a full 6× once the interpreter was out of the way. Both loops touch every cell the same number of times and grow at the same rate. One simply spends several times longer per cell, because it keeps throwing fetched cache lines away. Same shape of curve, very different height. That gap is exactly where careful data-structure work earns its keep.

You might expect exactly 8× then, since we keep one number in every eight. Real hardware never quite hits that ceiling. The prefetcher still salvages a little even on the strided walk, some of the data already sits in a larger outer cache, and the row-major run itself is not perfectly free. So the clean 8:1 ratio erodes to the ≈6× we actually measured. The lesson survives untouched: most of every fetched line is hauled in and wasted, and you pay for it in real wall-clock time.

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 holds rows eight-byte references, each 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 is three levels of indirection, and the rows can sit anywhere. So "moving to the next row" is a pointer-chase to an unrelated address. That is precisely why our column-major stumble was only 1.36×. The layout is already so scattered that walking it "the right way" barely helps.

Walk that chain once by hand to feel the cost. To read cell grid[7][3], the machine first reads slot 7 of the outer list, which is not a number but an address, so it goes there. That lands on row 7's own list, where it reads slot 3, again an address, so it goes there too. Only now, at a third and unrelated spot in memory, does it finally find the actual integer. Three hops for one value, and the second and third can be anywhere the allocator happened to have room. The prefetcher, which only rewards a straight march through memory, has nothing to lock onto. Every cell is a small treasure hunt.

Tally what that chain costs against a real block. Reading one cell of the list-of-lists can trigger three separate cache misses (the outer slot, the row-list, then the integer), each potentially a fresh 64-byte line dragged in for a single 8-byte value. A contiguous NumPy row pays one miss and then rides that line for the next eight cells for free. Same logical grid, same (i, j) lookups, but one layout asks the memory system for several times the work. The structure you never see is the one quietly setting the bill.

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

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 is 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. That is essentially 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. 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.

INPUTW, H = 4, 3                                  # 4 columns wide, 3 rows tall

# A. the nested grid - build it with a COMPREHENSION, never with *
grid = [[0] * W for _ in range(H)]           # H independent row-lists
grid[1][2] = 7
print("grid       :", grid)
print("grid[1][2] :", grid[1][2])

# B. the flat grid - one list, and the formula from section 02
flat = [0] * (W * H)
flat[1 * W + 2] = 7                          # r*W + c
print("flat       :", flat)
print("flat[1*W+2]:", flat[1 * W + 2])
print("same cell? ", grid[1][2] == flat[1 * W + 2])

# the formula, and its inverse
r, c = divmod(6, W)                          # slot 6 -> which (row, col)?
print("divmod(6, W) ->", (r, c), "and back:", r * W + c)

# rows and columns out of the flat list
print("row 1      :", flat[1 * W:(1 + 1) * W])
print("column 2   :", flat[2::W])

# transpose without touching a cell twice
print("zip rows   :", list(zip(*grid)))

OUTPUTgrid       : [[0, 0, 0, 0], [0, 0, 7, 0], [0, 0, 0, 0]]
grid[1][2] : 7
flat       : [0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0]
flat[1*W+2]: 7
same cell?  True
divmod(6, W) -> (1, 2) and back: 6
row 1      : [0, 0, 7, 0]
column 2   : [0, 7, 0]
zip rows   : [(0, 0, 0), (0, 0, 0), (0, 7, 0), (0, 0, 0)]

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 is the whole invention. Trade the intuitive rectangle for a formula, and indexing becomes free. The row-major-versus-column-major choice was not obvious either — it is a genuine historical fork. C chose row-major, Fortran chose column-major, and MATLAB and Julia inherited Fortran's, so neither is "right." What is wrong is code that fights its own storage order, a column-sweeping loop over a row-major block, or vice versa, quietly paying the cache tax on every step.

This fork is not a museum piece; it bites in real code. Load an image with a C-based library and you get a row-major block. Hand those same bytes to a Fortran-descended routine that assumes column-major, and unless someone converts, it reads your rows as columns and quietly returns a transposed, wrong answer. Nothing crashes. NumPy even lets you ask for either layout explicitly, with order='C' or order='F'. The bytes can look identical on disk. The agreement about how to fold them back into a grid is the thing you have to get right, and getting it wrong fails silently.

You do not have to guess which fold you are holding. Ask the array: A.flags['C_CONTIGUOUS'] is True for a row-major block and A.flags['F_CONTIGUOUS'] is True for a column-major one. A fresh transpose flips which flag is set without moving a byte, which is the strides trick showing through. When a routine hands back a transposed, wrong answer, this one-line check is usually how you catch it before the bytes ever mislead you.

So 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. Do you index arbitrary cells by (i, j) and sweep in a predictable direction? 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? 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.

# Build cells as runtime-made objects so identity is meaningful
# (small ints are cached by CPython, which would fake the result).
W = H = 3
m = [[f"r{i}c{j}" + "" for j in range(W)] for i in range(H)]
for row in m:
    print(row)

def rotate90(m):
    """Clockwise. Reverse the ROWS, then transpose - that is all."""
    return [list(t) for t in zip(*m[::-1])]

rot = rotate90(m)
print("rotated 90 clockwise:")
for row in rot:
    print(" ", row)

# WHAT zip(*m) ACTUALLY BUILT - proved with id()
print()
print("zip(*m) type of a row:", type(list(zip(*m))[0]).__name__)
print("m[2][0] is rot[0][0]:", m[2][0] is rot[0][0])       # SAME cell object
print("m[2] is rot[0]      :", m[2] is rot[0])             # NEW row container
print("distinct row objects:", len({id(r) for r in rot}) == H)
print("cells re-referenced, not copied:",
      all(rot[i][j] is m[H - 1 - j][i] for i in range(H) for j in range(W)))
print()
print("four turns returns the original values:",
      rotate90(rotate90(rotate90(rotate90(m)))) == m)

# ['r0c0', 'r0c1', 'r0c2']
# ['r1c0', 'r1c1', 'r1c2']
# ['r2c0', 'r2c1', 'r2c2']
# rotated 90 clockwise:
#   ['r2c0', 'r1c0', 'r0c0']
#   ['r2c1', 'r1c1', 'r0c1']
#   ['r2c2', 'r1c2', 'r0c2']
#
# zip(*m) type of a row: tuple
# m[2][0] is rot[0][0]: True
# m[2] is rot[0]      : False
# distinct row objects: True
# cells re-referenced, not copied: True
#
# four turns returns the original values: True

# THE IN-PLACE TRANSPOSE, for a SQUARE grid - no new objects at all.
sq = [[f"{i}{j}" + "" for j in range(3)] for i in range(3)]
before = (id(sq), [id(r) for r in sq])
for i in range(3):
    for j in range(i + 1, 3):                # upper triangle ONLY
        sq[i][j], sq[j][i] = sq[j][i], sq[i][j]
after = (id(sq), [id(r) for r in sq])
for row in sq:
    print(" ", row)
print("same outer list:", before[0] == after[0], "| same row objects:", before[1] == after[1])

#   ['00', '10', '20']
#   ['01', '11', '21']
#   ['02', '12', '22']
# same outer list: True | same row objects: True

# WHY REVERSE-THEN-TRANSPOSE IS A CLOCKWISE TURN. Follow the top-left cell,
# r0c0. A clockwise quarter-turn must carry it to the top-RIGHT. m[::-1]
# flips the rows top-to-bottom, so r0c0 drops to the bottom-left. Transpose
# then reflects across the main diagonal, and the bottom-left corner lands
# on the top-right. Two reflections make a rotation - which is also why
# reversing the COLUMNS instead (zip(*m) then reverse each row) turns it
# anticlockwise. One reflection is a mirror; two are a turn.
#
# WHAT zip GAVE BACK, EXACTLY. Each row of zip(*m) is a TUPLE, not a list,
# which is why the comprehension wraps it - drop the list() and you get a
# grid you cannot assign into. And the cells were never copied: m[2][0] is
# rot[0][0] came back True, and the all() check confirmed it for every one
# of the nine. So the rotation wrote 9 references and 3 new row containers.
# It did NOT touch the strings themselves. On a million-cell grid that is a
# million pointer writes and zero cell copies - which is exactly why NumPy
# can go one better and rotate by rewriting two stride numbers, moving
# nothing at all (the deeper cut in section 04).
#
# THE CATCH THAT FOLLOWS FROM IT. Because the cells are shared, a rotation
# of a grid of MUTABLE cells gives you two grids pointing at one set of
# objects - mutate a cell through one and the other sees it. Fine for
# strings and numbers, which cannot change. A real trap for a board of
# lists or dataclasses, and the fix is the same as always: copy the cells
# yourself if you meant a copy.
#
# AND THE BOUNDS ON THE IN-PLACE VERSION. The inner loop starts at i + 1,
# so it visits each unordered pair once. Start it at 0 and you swap every
# pair twice, which returns the grid unchanged - a bug that looks like
# "the transpose did nothing" rather than like an error. Note also that
# this only works on a SQUARE grid: a 3x5 transpose is 5x3, a different
# shape, so there is no in-place version to write.

One case the closing figure hints at deserves a sentence of its own: what if the grid is mostly empty? Picture a 100,000 × 100,000 matrix of web links, where almost every cell is 0 and only a handful per row are ever set. A dense block would demand ten billion slots, nearly all of them storing nothing. Here the honest layout is a sparse matrix: keep only the non-zero cells, each tagged with its own (i, j), and let every absent cell mean zero by default. You give up the free O(1) address arithmetic in exchange for a lookup, but you store thousands of numbers instead of billions. Same rule as ever. The access pattern, and now the fill, decides the layout.

Everything so far has lived on a line, whether contiguous or chained: the array, the linked list, the stack, the queue, and now the matrix. The matrix was the boldest bet on the line. It crams a whole second dimension into it and pays with rigid, dense storage. The next family gives that up entirely. It scatters its data across the heap as nodes joined by pointers. In exchange for abandoning 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. →