Row-major layout in Python

Why this matters

A program keeps its data in memory. Memory is a long line of numbered slots, and each slot holds one byte. When your program needs a value, the processor does not fetch only that value. It fetches a block of neighbouring bytes and keeps the block in a small, fast store called the cache. If the next value you need is already in that block, the read is almost free. If it is somewhere else, the processor has to wait for a new block.

So the order in which a loop reads a grid can change how often the processor waits. This lesson shows how a grid is laid out in memory, why the layout is called row-major, and why reading row by row is usually faster than reading column by column. It also shows that in Python the speed difference is smaller than in lower-level languages, because the interpreter does much more work for each step.

The idea of references comes from the lessons before this one. The cache in general is covered in the cache locality lesson later in this module. Here you only need one rule: memory next to the value you just read is cheap to read.

A grid is a line of cells with a formula

Start with a small grid. It has 3 rows and 4 columns. A row is one horizontal line of cells. A column is one vertical line of cells.

Memory has no rows and no columns. It only has one line of slots. To store a grid there, you put all the cells in one line. The usual choice, used by C, C++ and NumPy, is row-major order. Write the whole first row, then the whole second row, then the whole third row.

In a grid with cols columns, the cell at row r and column c goes to this position in the line:

r * cols + c

The position is called an index. An index counts from 0, so the first cell has index 0. Every index in this lesson starts at 0.

Here is a program that stores a 3 by 4 grid in one flat list. A flat list is a list with one dimension. The values are chosen so you can read the row and column from each number: the value 23 is in row 2, column 3.

Type nothing into the Input box for this program.

[0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23]
index 0 is row 0, col 0
index 1 is row 0, col 1
index 2 is row 0, col 2
index 3 is row 0, col 3
index 4 is row 1, col 0
index 5 is row 1, col 1
index 6 is row 1, col 2
index 7 is row 1, col 3
index 8 is row 2, col 0
index 9 is row 2, col 1
index 10 is row 2, col 2
index 11 is row 2, col 3

The first line shows the whole list. The values 0 to 3 are the first row, 10 to 13 the second row, and 20 to 23 the third row. The loop at the bottom goes the other way. It starts from an index and works out the row and column.

The two arithmetic operators in that loop are worth knowing. The // operator is floor division, which throws away the fraction. So 9 // 4 is 2. The % operator gives the remainder, so 9 % 4 is 1. This is how a flat index turns back into a row and a column. The row is index // cols and the column is index % cols.

Here are a few cells worked out by hand:

The index for row 1, column 0 is 4, because the first row used up the indices 0 to 3. Each row takes cols slots, so the start of row r is at r * cols. That is the whole idea of row-major order.

Lists of lists

Python does not have a built-in two-dimensional array. The usual way to write a grid is a list of rows, where each row is a list. Writing grid[r][c] looks up the row first, and then the cell in that row.

Use a comprehension to make the rows. The form [[0] * 4] * 3 would put the same row in all three slots, which is the trap from lesson 1. The comprehension makes a new row on each pass.

Type nothing into the Input box for this program.

len(grid) = 3
len(grid[0]) = 4
grid[1] = [10, 11, 12, 13]
jagged lengths: 3 and 5

The outer list has 3 slots, one for each row. Each slot holds a reference to another list with 4 slots. len(grid) is the number of rows. len(grid[0]) is the number of columns in row 0.

The last part of the program shows something a flat list cannot do. The rows of jagged have different lengths, 3 and 5. This works because each row is its own list. A flat list has one length, so every row in it would have the same length.

Python does not say where the row lists sit in memory. Inside one row, the references are in order in one block, so a loop that walks one row reads neighbouring slots in order. Each slot points at an integer object, though, and those objects can be anywhere in memory. This is the main difference from a flat array of numbers, and it is why the next example uses the array module.

Which loop order is faster

The speed question comes down to the cache. When the processor reads one value, it loads a block of memory into the cache. A block is commonly 64 bytes on current computers.

Consider a loop that reads row by row. It reads the references of one row in order, and the values that those references point at are visited in the same order. Each step is close to the one before it.

Now consider a loop that reads column by column. It reads grid[0][0], then grid[1][0], then grid[2][0]. Each of those is in a different row list. For a grid 2048 values wide, each step lands in a different block of memory. The processor has to fetch a new block almost every time.

To keep the layout exact, the next program stores the flat version in an array from the standard library. An array holds plain 4-byte integers in one block, the same as a Java int[]. A list of Python integers holds references instead, so the flat version here uses the array module.

The program builds a 2048 by 2048 grid, which holds about 4 million values, and sums it three ways: row by row in the list of lists, column by column in the list of lists, and row by row in the flat array.

import array
import statistics
import time
 
n = 2048
grid = [[(r + c) % 7 for c in range(n)] for r in range(n)]
flat = array.array("i", [(r + c) % 7 for r in range(n) for c in range(n)])
 
def sum_rows(m):
    s = 0
    for row in m:
        for v in row:
            s += v
    return s
 
def sum_cols(m):
    s = 0
    for c in range(len(m[0])):
        for r in range(len(m)):
            s += m[r][c]
    return s
 
def sum_flat(f):
    s = 0
    for v in f:
        s += v
    return s
 
# Warm-up runs, so the first timed run is not slower because of setup.
for f, arg in [(sum_rows, grid), (sum_cols, grid), (sum_flat, flat)]:
    f(arg)
 
rows_times = []
cols_times = []
flat_times = []
total = 0
for t in range(5):
    start = time.perf_counter()
    total += sum_rows(grid)
    rows_times.append(time.perf_counter() - start)
 
    start = time.perf_counter()
    total += sum_cols(grid)
    cols_times.append(time.perf_counter() - start)
 
    start = time.perf_counter()
    total += sum_flat(flat)
    flat_times.append(time.perf_counter() - start)
 
print("total (checksum) =", total)
print("median ms, rows:   ", round(statistics.median(rows_times) * 1000, 1))
print("median ms, columns:", round(statistics.median(cols_times) * 1000, 1))
print("median ms, flat:   ", round(statistics.median(flat_times) * 1000, 1))

Two parts of this program matter for a fair test.

The warm-up runs each function once before any timing starts. The first run of a function can be slower, because of memory set-up that happens once. Timing only after the warm-up measures the normal cost.

The program takes 5 timings for each function and prints the median, which is the middle value after sorting. One slow run, caused by the operating system or by the garbage collector, does not change the median much. The total is printed too, so the summing work is not thrown away.

On the machine used to write this lesson, a WSL2 Linux system with Python 3.14.4, one run printed these lines:

total (checksum) = 188743680
median ms, rows:    49.8
median ms, columns: 105.1
median ms, flat:    54.0

The column loop was about twice as slow as the row loop in this run. That is a smaller gap than in lower-level languages, because each step in Python does more work, and that work hides part of the cost of the cache misses. The exact numbers depend on your processor, its cache sizes and what else the computer is doing. Run the program on your own machine and compare the three numbers with each other, not with the numbers above.

The flat array was about as fast as the row loop over the list of lists. Both read memory in order. The flat version has one loop instead of two, and here that saving was small.

The checksum is the same in every run, because every function adds the same values in a different order. The total does not depend on the order. Only the speed does.

NumPy and the same layout

The third-party package NumPy stores an array in one block, in row-major order by default. Its reshape method uses the same formula. The next block needs NumPy installed, so it is not in a run block. It prints 11 twice, and True for the contiguity check, which means the values are in one block.

import numpy as np
 
a = np.arange(12).reshape(3, 4)
print(a[2, 3])
print(a.ravel()[2 * 4 + 3])
print(a.flags.c_contiguous)

The output is:

11
11
True

The first two lines show that row 2, column 3 is at index 11 in the flat order. The third line shows that the array is one contiguous block. NumPy is the usual choice for numeric grids in Python, because its loops run in compiled code, not in the interpreter.

Common mistakes

The mistakes below are the ones this lesson's program makes on purpose. Each one raises an error that you can read.

Swapping the two parts of the formula

The correct formula is r * cols + c. Writing c * cols + r gives a different number. For row 2, column 3, the correct index is 11, but the wrong formula gives 14. A flat list with 12 items has no index 14, so Python raises an IndexError:

Type nothing into the Input box for this program.

23
IndexError: list index out of range

A wrong formula does not always go out of range. For row 0, column 1, the wrong formula gives 1 * 4 + 0, which is index 4. That is row 1, column 0, a real cell. The program runs with no error and reads the wrong value. This is the hardest kind of bug to find, because nothing crashes. Keep the formula in one function, and test it on a few cells you can count by hand.

Forgetting to create a row

[None] * 3 makes 3 row slots, but none of the rows exists yet. Each slot holds None, which means "no object here". Writing to grid[0][0] tries to put an item into None. The error is a TypeError:

Type nothing into the Input box for this program.

TypeError: 'NoneType' object does not support item assignment

The fix is to create each row before writing into it:

grid = [None] * 3
grid[0] = [0] * 4
grid[0][0] = 1

Or use [[0] * 4 for _ in range(3)], which creates the rows for you.

Going one past the last column

A row with 4 columns has indices 0, 1, 2 and 3. Index 4 is one past the end. Writing to it raises an IndexError. This is an off-by-one error. It is common when a loop uses <= where it should use <.

Type nothing into the Input box for this program.

IndexError: list assignment index out of range

The message says assignment, because the failing line stores a value. A read of the same index gives list index out of range.

Using the first row's length for every row

A loop that uses len(grid[0]) works for a normal grid, where every row has the same length. In a jagged grid, a shorter row causes an error. Here row 1 has 2 cells, and the loop goes up to the length of row 0, which is 3. The loop reads jag[1][2], and that index does not exist:

Type nothing into the Input box for this program.

1 2 3 4 5 
IndexError: list index out of range

Inside a row loop, use len(jag[r]), which is the length of the row you are on.

Practice

Exercise 1. In a grid with 3 rows and 4 columns stored in row-major order, what is the index of the cell in row 2, column 3?

Show the answer

The index is 2 * 4 + 3, which is 11. The last cell of the last row is always the last index, which is rows * cols - 1, so 11 is correct for a 12-cell grid.

Exercise 2. The index is 9 in the same 3 by 4 grid. Which row and column is it in?

Show the answer

Row 9 // 4, which is 2, and column 9 % 4, which is 1. So it is row 2, column 1.

Exercise 3. Write a function count_zero_rows that takes a list of lists and returns how many rows contain only zeros. Use the row-by-row order. For this grid, the answer should be 2:

m = [[0, 0, 0], [0, 1, 0], [0, 0, 0], [2, 0, 0]]

Show the answer

def count_zero_rows(m):
    count = 0
    for row in m:
        if all(v == 0 for v in row):
            count += 1
    return count

The function returns 2 for that grid. Rows 0 and 2 contain only zeros. Row 1 has a 1 and row 3 has a 2. The loop reads each row in order, so it is also the cache-friendly order.

Exercise 4. What does this code print, and why?

g = [None] * 2
g[1][0] = 5

Show the answer

It raises TypeError: 'NoneType' object does not support item assignment. Row 1 was never created, so g[1] holds None. Create it with g[1] = [0] * 3 before writing g[1][0].

Exercise 5. Write a function column_totals that takes a list of lists and returns a list with the sum of each column. Read the grid row by row, not column by column. For [[1, 2, 3], [4, 5, 6]], the answer is [5, 7, 9].

Show the answer

def column_totals(m):
    totals = [0] * len(m[0])
    for r in range(len(m)):
        for c in range(len(m[r])):
            totals[c] += m[r][c]
    return totals

The outer loop goes over rows, so each row is read in order. The inner loop adds each value to the total of its column. The result is [5, 7, 9], which is 1 + 4, 2 + 5 and 3 + 6.

Summary

• A grid can be stored in one flat sequence in row-major order, with the cell at row r and column c at index r * cols + c.
• Going back from an index, the row is index // cols and the column is index % cols.
• A Python grid is usually a list of row lists. Rows can have different lengths, and Python does not promise where the rows sit in memory.
• Loops that read a row in order use the cache well. Loops that jump from row to row are slower on large grids, but the gap is smaller in Python than in lower-level languages.
• Measure speed with a warm-up, several runs and the median, and compare the results on your own machine.
• The usual grid bugs are a swapped formula, a row that was never created, and an off-by-one column index.