Row-major order

From Wikipedia, the free encyclopedia
  (Redirected from Column-major order)
Jump to: navigation, search

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 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.[1] In some media such as tape or NAND flash memory, accessing sequentially is orders of magnitude faster than nonsequential access.

Explanation and example[edit]

Following conventional matrix notation, rows are numbered by the first index of a two-dimensional array and columns by the second index, i.e., a1,2 is the second element of the first row, counting downwards and rightwards. (Note this is the opposite of Cartesian conventions.)

The difference between row-major and column-major order is simply that the order of the dimensions is reversed. Equivalently, in row-major order the rightmost indices vary faster as one steps through consecutive memory locations, while in column-major order the leftmost indices vary faster.

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:

Programming languages and libraries[edit]

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, Python[citation needed], Speakeasy, SAS, and C#/CLI/.Net.

Column-major order is used in Fortran, OpenGL and OpenGL ES, MATLAB,[2] GNU Octave, S-Plus,[3] R,[4] Julia,[5] Rasdaman[citation needed], Scilab.

Iliffe vectors are implicitly used as the underlying implementation in Java/Scala.[6]

Multi-dimensional arrays are not supported by, or programmers typically use Iliffe vectors explicitly in, Lua[7] and Swift.

Multi-dimensional arrays may also be supported in external libraries.

Column-major order is the default in Torch[8] (for Lua).

Transposition[edit]

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.[9]

Address calculation in general[edit]

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 Nk (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

See also[edit]

References[edit]

  1. ^ "Intel® Developer Zone". Retrieved 2015-05-16. 
  2. ^ MATLAB documentation, MATLAB Data Storage (retrieved from Mathworks.co.uk, January 2014).
  3. ^ 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 
  4. ^ An Introduction to R, Section 5.1: Arrays (retrieved March 2010).
  5. ^ "Multi-dimensional Arrays". Julia. Retrieved 6 February 2016. 
  6. ^ "Java Language Specification". Oracle. Retrieved 13 February 2016. 
  7. ^ "11.2 – Matrices and Multi-Dimensional Arrays". Retrieved 6 February 2016. 
  8. ^ "Tensor". Retrieved 6 February 2016. 
  9. ^ "BLAS (Basic Linear Algebra Subprograms)". Retrieved 2015-05-16. 

Sources[edit]