Row- and column-major order
In row-major order, consecutive elements of the rows of the array are contiguous in memory; in column-major order, consecutive elements of the columns are contiguous.
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
There are two aspects: row/column, and major/minor.
In matrix notation, the first/left index indicates the row, and the second/right index indicates the column, e.g., a1,2 is in the first row and in the second column. Even though the row is indicated by the first index and the column by the second index, no grouping order between dimensions is implied yet. This convention is carried over to two-dimensional arrays in computer languages, although often with indexes starting at 0 instead of 1.
An obvious way to order objects with more than one attribute is to first group and order them by one attribute, and then, within each such group, group and order them by another attribute, etc. (not all attributes have to participate in ordering). If more than one attribute participate in ordering, the first would be called major and the last minor. If two attributes participate in ordering, it is sufficient to name only the major attribute.
Applied to two-dimensional arrays, e.g., for row-major order, all elements of the first row come before all elements of the second row, etc., and, within each row, elements are ordered by column. As one steps though consecutive memory locations, the index associated with the major order varies slowest, and the index associated with the minor order varies fastest (unless there is only one index value in that dimension).
would be stored as follows in the two orders:
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.
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.
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. The programmer must then decide whether or not to rearrange the elements in memory, based on the actual usage (including the number of times that the array is reused in a computation).
Address calculation in general
The concept generalizes to arrays with more than two dimensions.
For a d-dimensional array with dimensions Nk (k=1...d), a given element of this array is specified by a tuple of d (zero-based) indices .
In row-major order, the last dimension is contiguous, so that the memory-offset of this element is given by:
In column-major order, the first dimension is contiguous, so that the memory-offset of this element is given by:
For a given order, the stride in dimension k is given by the multiplication value in parentheses before index nk 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.
- Matrix representation
- Vectorization (mathematics), the equivalent of turning a matrix into the corresponding column-major vector
- "Arrays and Formatted I/O". FORTRAN Tutorial. Retrieved 19 November 2016.
- MATLAB documentation, MATLAB Data Storage (retrieved from Mathworks.co.uk, January 2014).
- Spiegelhalter et al. (2003, p. 17): Spiegelhalter, David; Thomas, Andrew; Best, Nicky; Lunn, Dave (January 2003), "Formatting of data: S-Plus format", WinBUGS User Manual (Version 1.4 ed.), Robinson Way, Cambridge CB2 2SR, UK: MRC Biostatistics Unit, Institute of Public Health, PDF document
- An Introduction to R, Section 5.1: Arrays (retrieved March 2010).
- "Multi-dimensional Arrays". Julia. Retrieved 6 February 2016.
- "Java Language Specification". Oracle. Retrieved 13 February 2016.
- "object Array". Scala Standard Library. Retrieved 1 May 2016.
- "The N-dimensional array (ndarray)". SciPy.org. Retrieved 3 April 2016.
- "11.2 – Matrices and Multi-Dimensional Arrays". Retrieved 6 February 2016.
- "Tensor". Retrieved 6 February 2016.
- "Tensor". Torch Package Reference Manual. Retrieved 8 May 2016.
- "BLAS (Basic Linear Algebra Subprograms)". Retrieved 2015-05-16.
- Donald E. Knuth, The Art of Computer Programming Volume 1: Fundamental Algorithms, third edition, section 2.2.6 (Addison-Wesley: New York, 1997).