Row-Major Array Addressing
A processor sees no rows and no columns — only a flat, one-dimensional expanse of numbered bytes. Yet
programmers happily write grid[i][j] and tensor[i][j][k] as if the machine kept
their data in a tidy rectangle. Somewhere in the compiler, that comfortable fiction must be turned back
into a single number: the byte address of exactly one element. The rule that does the turning is the
addressing polynomial, and choosing how to flatten a multi-dimensional array into one
line of memory is the difference between row-major and column-major
layout.
This is not a footnote. It is where the elegance of
expression translation
meets the hard geometry of memory. Every a[i][j] in the source becomes a little burst of
multiplications and additions in the
intermediate code —
and getting that arithmetic exactly right, once, in the code generator, is what lets a loop over a matrix
run at the speed of light instead of reading garbage.
One dimension is just base plus scaled index
Start where expression
translation left off. A one-dimensional array a of elements that
are each w bytes wide stores a[i] at
\textit{addr}(a[i]) \;=\; \textit{base}(a) \;+\; i \times w.
The width w is type-driven — 4 for a 32-bit
int, 8 for a double — and comes from the symbol
table. Nothing here is surprising; the interesting part is what happens when we nest.
Row-major: last index varies fastest
Picture a 3 \times 4 matrix. Row-major order (used by C, C++,
Python/NumPy by default, Pascal, Rust) lays the whole first row down first, then the whole second row,
then the third — so as you step through memory the rightmost index changes fastest. Element
a[i][j] of an array declared with n_2 columns sits
at linear element-offset i \times n_2 + j: skip i
whole rows of n_2 elements, then step j across the
row you land in. The figure shows the flattening for a[1][2].
Multiply that element-offset by the byte width and add the base, and you have the full two-dimensional
addressing formula:
\textit{addr}(a[i][j]) \;=\; \textit{base}(a) \;+\; (\,i \times n_2 + j\,)\times w.
Notice that the number of rows n_1 never appears — only the number of
columns n_2 matters, because it is the length of one row, the stride
between successive values of i. That asymmetry is the whole personality of
row-major order.
The addressing polynomial, in general
For k dimensions the pattern nests, and it nests as a
Horner polynomial. An array declared with bounds
[n_1][n_2]\cdots[n_k] stores element
a[i_1][i_2]\cdots[i_k] at element-offset
i_1 n_2 n_3\cdots n_k \;+\; i_2 n_3\cdots n_k \;+\; \cdots \;+\; i_{k-1}n_k \;+\; i_k,
which is far nastier written flat than it is written the way a compiler actually emits it — by
Horner's method, folding the indices in from the left, one multiply-and-add per
dimension:
\textit{offset} \;=\; \big(\cdots((i_1)\,n_2 + i_2)\,n_3 + i_3)\cdots\big)\,n_k + i_k,\qquad
\textit{addr} = \textit{base} + \textit{offset}\times w.
For three dimensions this is the tidy
\textit{base} + ((i\,n_2 + j)\,n_3 + k)\times w — an accumulator
that starts at the first index and, for each further dimension, multiplies by that dimension's size and
adds the next index. It is exactly the loop you would write to evaluate any polynomial efficiently, and
it costs only k-1 multiplications and k-1 additions
for a k-dimensional access.
- An array with declared dimension sizes n_1,\dots,n_k stores its elements
with the last index varying fastest (rows contiguous).
- The element-offset of a[i_1]\cdots[i_k] is the Horner form
((\cdots(i_1 n_2 + i_2)n_3 + i_3)\cdots)n_k + i_k; the byte address is
\textit{base} + \textit{offset}\times w.
- The strides are the running products of trailing sizes: dimension
d has stride w\prod_{m>d} n_m. The very first
(row) stride is the largest; the last is just w.
Row-major vs column-major
Column-major order (Fortran, MATLAB, R, Julia, and the BLAS/LAPACK numeric world) makes
the first index vary fastest: it stores whole columns contiguously. Same elements, mirror-image
polynomial —
\textit{addr}_{\text{col}}(a[i][j]) \;=\; \textit{base}(a) \;+\; (\,j \times n_1 + i\,)\times w.
The choice is pure convention, but it has teeth. The elements you touch consecutively in the fast layout
are adjacent in memory, so they share cache lines; touch them in the wrong order and every
access is a cache miss. That is why a matrix loop written for i { for j { a[i][j] } } flies
in C (row-major, inner index j strides by one) but crawls if you transpose the loops — and
why the identical nesting is exactly backwards in Fortran.
| Layout | Contiguous unit | Fastest-varying index | Address of a[i][j] | Languages |
|---|
| Row-major | a row | last (j) | (i\,n_2 + j)\,w | C, C++, Rust, NumPy, Pascal |
| Column-major | a column | first (i) | (j\,n_1 + i)\,w | Fortran, MATLAB, Julia, R |
How the IR lowers a[i][j]
In three-address code the access is not a primitive — it is the Horner polynomial spelled out as a chain
of tiny instructions, ending in an indexed load or store. For an int matrix with
n_2 = 4 columns, x = a[i][j] lowers to:
t1 = i * 4 // i * n2 (n2 = number of columns)
t2 = t1 + j // (i*n2 + j) — the element index
t3 = t2 * 4 // scale by element width w = 4 bytes
t4 = a[t3] // indexed read at the computed byte offset
x = t4
Every dimension after the first adds one multiply-by-size and one add-the-next-index —
the accumulator of Horner's method, made of primitive TAC operators. The final scale-by-w
converts the element index into a byte offset for the indexed access. The code generator below builds this
for an array of any rank.
The addressing polynomial, in code
Here is Horner's method as a compiler would apply it: fold the indices against the dimension sizes to get
an element-offset, then scale by the width and add the base. We compute a couple of addresses in a
3 \times 4 matrix of 4-byte ints and one in a
2 \times 3 \times 4 tensor of 8-byte doubles.
// Row-major linear address of a[i1][i2]...[ik].
// dims = declared sizes [n1, n2, ..., nk]
// idx = the indices [i1, i2, ..., ik]
// base = base byte address of the array
// width = element size in bytes
function rowMajorAddr(dims: number[], idx: number[], base: number, width: number): number {
// Horner fold: offset accumulates one (× size, + index) per dimension.
let offset = 0;
for (let d = 0; d < idx.length; d++) {
offset = offset * dims[d] + idx[d]; // × this dimension's size, + this index
}
return base + offset * width; // scale element-offset to bytes, add base
}
// 3 x 4 int matrix, base 1000, width 4.
const dims2 = [3, 4];
for (const [i, j] of [[0, 0], [1, 2], [2, 3]]) {
const a = rowMajorAddr(dims2, [i, j], 1000, 4);
console.log(`int a[${i}][${j}] offset = ${(a - 1000) / 4} addr = ${a}`);
}
console.log("---");
// 2 x 3 x 4 double tensor, base 5000, width 8.
const dims3 = [2, 3, 4];
for (const [i, j, k] of [[0, 0, 0], [1, 2, 3], [0, 1, 2]]) {
const a = rowMajorAddr(dims3, [i, j, k], 5000, 8);
console.log(`double t[${i}][${j}][${k}] offset = ${(a - 5000) / 8} addr = ${a}`);
}
The matrix's a[1][2] lands at element-offset 1\times 4 + 2 = 6,
byte address 1000 + 24 = 1024 — exactly what the figure highlighted. The
tensor's t[1][2][3] folds to ((1\cdot 3 + 2)\cdot 4 + 3) = 23, the
very last element, at byte 5000 + 184. One loop, any rank.
Then the compiler plays a lovely trick. If indices run from \textit{low} rather
than 0, the naive address is \textit{base} + (i - \textit{low})\times w. But
(i-\textit{low})\times w = i\times w - \textit{low}\times w, and that second
term is a constant the compiler knows at compile time. So it precomputes a virtual
base \textit{base} - \textit{low}\times w — an address that may point
before the array actually starts — and then addresses every element with the plain
i\times w formula. The offset for the lower bound is paid once, folded into a
fictitious base, and the hot inner loop stays as cheap as if the array were zero-based. It generalises
cleanly to every dimension of a multi-dimensional array.
The single most common blunder is to reach for the wrong dimension size. In row-major
a[i][j], the stride between successive rows is the number of
columns n_2, not the number of rows. Students constantly write
i\times n_1 + j using the row count — which computes a plausible-looking but
completely wrong address, and worse, one that only sometimes reads out of bounds, so the bug
hides until n_1 \ne n_2. The rule to burn in: in row-major you multiply an
index by the product of all the dimension sizes to its right. For a plain 2-D array that product
is just n_2. And the mirror trap: use the row-major polynomial on a
column-major array (or vice versa) and you will transpose your entire matrix silently. Match the
polynomial to the language's layout.