Memory is one long line of bytes, so where does a grid go? Row after row. Watch twelve writes land in the grid and in the line at once.
Laying a grid out in a line
A 3 × 4 grid and the memory that holds it
int main(void){ int m[ROWS][COLS]; for (int r = 0; r < ROWS; r++) for (int c = 0; c < COLS; c++) m[r][c] = 10 * r + c; printf("m[2][1] = %d\n", m[2][1]); printf("sizeof m = %zu, sizeof m[0] = %zu\n", sizeof m, sizeof m[0]); return 0;}main has started. m is 3 rows of 4 int cells: 48 bytes in one line from 0x7fc0, nothing written yet.
Output
Describe this picture
A grid of 3 rows and 4 columns, its row and column numbers at the edges and each row faintly tinted, above a strip of 12 int cells with their addresses, from 0x7fc0. The code pane shows grid.c from main on, with the line about to run marked. The clip takes about 18 seconds. The loops write 10 · r + c into each cell, row by row; at each write the cell lights in the grid and its value drops into the strip, and a formula under the grid gives the cell’s place in the line, such as “m[1][2] is cell 1 × 4 + 2 = 6”. In row-major order the strip fills from left to right, four cells per row: 0 1 2 3, 10 11 12 13, 20 21 22 23, its tints in blocks of four. Then the program reads m[2][1], cell 9, and prints m[2][1] = 21 and sizeof m = 48, sizeof m[0] = 16. After the clip, the control “Storage order” switches to Column-major: the code becomes grid-column-major.c, the strip is int cells[12], and the same walk replays with each write jumping three cells along the strip and wrapping, landing at 0, 3, 6, 9, then 1, 4, 7, 10, then 2, 5, 8, 11. The tints interleave, and the program prints cell (2, 1) = 21, from index 5. Under the pictures are the program’s output and one sentence on the current step. The transport plays and pauses, steps one line back or forward, and scrubs; the order and a paused step are kept in the page address as grid.order and grid.step.
One line of cells
Memory has addresses one after another; it has no rows and columns. A grid has to be laid out along that line, and there are two natural ways: row-major, row 0 first, then row 1, then row 2, or column-major, column 0 first, then column 1, and so on. C uses row-major. Some numerical languages and libraries use column-major, so the same grid can lie in two orders.
Whatever the order, the cell (r, c) of the grid is one cell of the line, and a formula says which. The grid in the picture is the idea the program has in mind; the strip is what the memory holds.
The code and its cost
Row-major: m[r][c]
#include <stdio.h>
#define ROWS 3
#define COLS 4
int main(void)
{
int m[ROWS][COLS];
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++)
m[r][c] = 10 * r + c;
printf("m[2][1] = %d\n", m[2][1]);
printf("sizeof m = %zu, sizeof m[0] = %zu\n", sizeof m, sizeof m[0]);
return 0;
}int m[3][4] is 3 rows, each an array of 4 ints, stored one row after another: 12 cells, 48 bytes. m[r] is row r, itself an array of 4 cells, so sizeof m[0] is 16. To reach m[r][c], step over r whole rows of 4 cells, then c cells more:
m[2][1] is cell 2 × 4 + 1 = 9, at 0x7fc0 + 9 × 4 = 0x7fe4. It holds 21. Swapping the indices does not reach the same cell: m[1][2] is cell 6, holding 12.
Column-major, done by hand
C has no column-major arrays, so the variant stores the grid in a plain line of 12 and does the arithmetic itself:
int cells[ROWS * COLS];
...
cells[c * ROWS + r] = 10 * r + c;
printf("cell (2, 1) = %d\n", cells[1 * ROWS + 2]);Now the cell (r, c) is at c · rows + r: step over c whole columns of 3 cells, then r more. The line reads 0 10 20 1 11 21 2 12 22 3 13 23, and (2, 1) is at index 1 × 3 + 2 = 5, address 0x7fd4. The program prints cell (2, 1) = 21 and sizeof cells = 48: the same 48 bytes, in another order.
Three ways to build a grid
- A fixed array,
int m[ROWS][COLS]: its size is known when the program is compiled, and it lives in the function’s frame. - One heap block, indexed by hand:
int *g = malloc(ROWS * COLS * sizeof *g);, theng[r * COLS + c]. Its size can be chosen while the program runs, and onefree(g)gives it back. - An array of row pointers,
int *rows[ROWS], each pointing to its own block.rows[r][c]reads row r’s address first, then the cell. The rows may have different lengths, and each needs its ownfree.
More dimensions: strides
A block of any number of dimensions is still one line. The stride of an index is the number of cells inside one step of it. For int b[2][3][4] the strides are 12, 4 and 1 cells: one step of the first index skips a whole 3 × 4 layer, one step of the second skips a row of 4, one step of the last moves one cell. Each index times its stride, added up, is the offset.
Walking order
The loops above run c fastest, along the row, so they touch the line in order, one cell after the next. Swap the two loops and each step jumps a whole row ahead. In row-major storage, the inner loop should run over the last index.
Worked example
A block of three dimensions. In int b[2][3][4], b[1][2][3] is cell 1 × 12 + 2 × 4 + 3 = 23, the last of the 24, and 23 × 4 = 92 bytes from the start. The traced program block3d.c fills b with 0 to 23 in loop order and prints b[1][2][3] = 23, 92 bytes in, sizeof b = 96, and strides: 12 4 1 cells, worked out from sizeof b[0], sizeof b[0][0] and sizeof b[0][0][0].
One heap block.
int *g = malloc(ROWS * COLS * sizeof *g);
if (g == NULL)
return 1;
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++)
g[r * COLS + c] = 10 * r + c;
printf("g[2 * COLS + 1] = %d\n", g[2 * COLS + 1]);
free(g);One block of 48 bytes on the heap, the same row-major line the fixed array has, and one free. It prints g[2 * COLS + 1] = 21.
Row pointers, and a triangle.
int *rows[ROWS];
for (int r = 0; r < ROWS; r++) {
rows[r] = malloc(COLS * sizeof *rows[r]);
if (rows[r] == NULL)
return 1;
for (int c = 0; c < COLS; c++)
rows[r][c] = 10 * r + c;
}Three blocks of 16 bytes, which in the trace sit 32 bytes apart: 0x1000, 0x1020 and 0x1040 in the course’s short addresses. The rows are not one line any more, and freeing them takes three calls to free. What the row pointers buy is rows of different lengths: a triangle whose row r has r + 1 cells needs 1 + 2 + 3 = 6 cells instead of 12. row-pointers.c builds both, printing rows[2][1] = 21, then triangle: 6 cells, tri[2][2] = 22.
Walking a large grid. Summing a 1000 × 1000 grid of int row by row steps 4 bytes at a time. Column by column, each step jumps a whole row, 1000 × 4 = 4,000 bytes. Once the grid is larger than the cache, the small fast memory that holds the bytes near those just read, the second order is markedly slower on most machines, because almost every read misses the cache.
Two checks. In a 3 × 4 grid, what is the offset in cells of (1, 3) in row-major order? (1 × 4 + 3 = 7.) In column-major? (3 × 3 + 1 = 10.) What are the strides of double d[5][6][7] in bytes? (6 × 7 × 8 = 336, 7 × 8 = 56, and 8.)
Where it’s used
Images. A picture is a grid of pixels stored row by row, one line after another (Images as signals). Filters that run along a row read memory in order.
Matrices in numerical code. The storage order decides which loop order is fast (Matrix multiplication); libraries document whether they expect row-major or column-major input.
Boards and tables. Spreadsheets, game boards and seat maps are grids indexed by row and column.
Reference card
| Code or idea | Meaning |
|---|---|
int m[R][C] | R rows of C cells, row after row |
| row-major (r, c) | base + (r · C + c) · size |
| column-major (r, c) | base + (c · R + r) · size |
m[r] | row r, an array of C cells |
| one heap block | malloc(R * C * sizeof *g), g[r * C + c], one free |
| row pointers | int *rows[R], a block per row, a free per row |
| stride | cells inside one step of an index |
| fast loop order | inner loop over the last index (row-major) |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.