Row- and column-major order

In computing, row-major order and column-major order describe methods for arranging multidimensional arrays in linear storage such as memory.

In row-major order, consecutive elements of the rows of the array are contiguously stored in memory; in column-major order, consecutive elements of the columns of the array are contiguously stored.

Array layout is critical for correctly passing arrays between programs written in different languages. It is also important for performance when traversing an array because accessing array elements that are contiguous in memory is usually faster than accessing elements which are not, due to caching. In some media such as tape or NAND flash memory, accessing sequentially is orders of magnitude faster than nonsequential access.

Explanation and example

This array

$A={\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{bmatrix}}$

would be stored as follows in the two orders:

Column-major order
e.g., Fortran

Address	Value
0	$a_{11}$
1	$a_{21}$
2	$a_{12}$
3	$a_{22}$
4	$a_{13}$
5	$a_{23}$

Row-major order
e.g., C

Address	Value
0	$a_{11}$
1	$a_{12}$
2	$a_{13}$
3	$a_{21}$
4	$a_{22}$
5	$a_{23}$

To select correct element one must know whether A[a][b] notation in a particular language is treated in a row-major or in a column-major mode, eg. in C foo[0][1] would result in $a_{12}$, while in Fortran it would result in $a_{21}$.

Programming languages and libraries

Programming languages or their standard libraries that support multi-dimensional arrays typically have a native row-major or column-major storage order for these arrays.

Row-major order is used in C/C++/Objective-C (for C-style arrays), Mathematica, PL/I, Pascal, Speakeasy, SAS, and C#/CLI/.Net.

Column-major order is used in Fortran, OpenGL and OpenGL ES, MATLAB, GNU Octave, S-Plus, R, Julia, Rasdaman, Scilab.

A typical alternative is to use Iliffe vectors, which store elements in the same row contiguously (like row-major order), but not the rows themselves. They are used in Java, Scala, and Swift.

Support for multi-dimensional arrays may also be provided by external libraries, which may even support arbitrary orderings, where each dimension has a stride value, and row-major or column-major are just two possible resulting interpretations.

Row-major order is the default in NumPy (for Python).

Torch (for Lua, which has no built-in support) changed from column-major to row-major default order.

Transposition

As exchanging the indices of an array is the essence of array transposition, an array stored as row-major but read as column-major (or vice versa) will appear transposed. As actually performing this rearrangement in memory is typically an expensive operation, some systems provide options to specify individual matrices as being stored transposed.

For example, the Basic Linear Algebra Subprograms functions are passed flags indicating which arrays are transposed.

Address calculation in general

The concept generalizes to arrays with more than two dimensions.

For a d-dimensional $N_{1}\times N_{2}\times \cdots \times N_{d}$ array with dimensions N_k (k=1...d), a given element of this array is specified by a tuple $(n_{1},n_{2},\ldots ,n_{d})$ of d (zero-based) indices $n_{k}\in [0,N_{k}-1]$.

In row-major order, the last dimension is contiguous, so that the memory-offset of this element is given by:

$n_{d}+N_{d}\cdot (n_{d-1}+N_{d-1}\cdot (n_{d-2}+N_{d-2}\cdot (\cdots +N_{2}n_{1})\cdots )))=\sum _{k=1}^{d}\left(\prod _{\ell =k+1}^{d}N_{\ell }\right)n_{k}$

In column-major order, the first dimension is contiguous, so that the memory-offset of this element is given by:

$n_{1}+N_{1}\cdot (n_{2}+N_{2}\cdot (n_{3}+N_{3}\cdot (\cdots +N_{d-1}n_{d})\cdots )))=\sum _{k=1}^{d}\left(\prod _{\ell =1}^{k-1}N_{\ell }\right)n_{k}$

For a given order, the stride in dimension k is given by the multiplication value in parentheses before index n_k in the right hand-side summations above.

More generally, there are d! possible orders for a given array, one for each permutation of dimensions (with row-major and column-order just 2 special cases), although the lists of stride values are not necessarily permutations of each other, e.g., in the 2-by-3 example above, the strides are (3,1) for row-major and (1,2) for column-major.

See also

• Matrix representation
• Vectorization (mathematics), the equivalent of turning a matrix into the corresponding column-major vector

Sources

• Donald E. Knuth, The Art of Computer Programming Volume 1: Fundamental Algorithms, third edition, section 2.2.6 (Addison-Wesley: New York, 1997).