In computing, row-major order and column-major order are methods for storing multidimensional arrays in linear storage such as random access memory. The difference between the orders lies in which elements of an array are contiguous in memory. In row-major order, the consecutive elements of a row reside next to each other, whereas the same holds true for consecutive elements of a column in column-major order. While the terms allude to the rows and columns of a two-dimensional array, i.e. a matrix, the orders can be generalized to arrays of any dimension by noting that the terms row-major and column-major are equivalent to lexicographic and colexicographic orders, respectively. Matrices, being commonly represented as collections of row or column vectors, using this approach are effectively stored as consecutive vectors or consecutive vector components. Such ways of storing data are referred to as AoS and SoA respectively. Data layout is critical for correctly passing arrays between programs written in different programming languages. It is also important for performance when traversing an array because modern CPUs process sequential data more efficiently than nonsequential data. This is primarily due to CPU caching which exploits spatial locality of reference. In addition, contiguous access makes it possible to use SIMD instructions that operate on vectors of data. In some media such as magnetic-tape data storage, accessing sequentially is orders of magnitude faster than nonsequential access.
Explanation and example The terms row-major and column-major stem from the terminology related to ordering objects. A general way to order objects with many attributes is to first group and order them by one attribute, and then, within each such group, group and order them by another attribute, etc. If more than one attribute participates 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. In the case of arrays, the attributes are the indices along each dimension. For matrices in mathematical notation, the first index indicates the row, and the second indicates the column, e.g., given a matrix A {\displaystyle A} , the entry a 1 , 2 {\displaystyle a_{1,2}} is in its first row and second column. This convention is carried over to the syntax in programming languages, although often with indexes starting at 0 instead of 1. Even though the row is indicated by the first index and the column by the second index, no grouping order between the dimensions is implied by this. The choice of how to group and order the indices, either by row-major or column-major methods, is thus a matter of convention. The same terminology can be applied to even higher dimensional arrays. Row-major grouping starts from the leftmost index and column-major from the rightmost index, leading to lexicographic and colexicographic (or colex) orders, respectively. For example, the array
A = a y , x = [ a 11 a 12 a 13 a 21 a 22 a 23 ] {\displaystyle A=a_{y,x}={\begin{bmatrix}\color {Blue}a_{11}&\color {Blue}a_{12}&\color {Blue}a_{13}\\\color {Orange}a_{21}&\color {Orange}a_{22}&\color {Orange}a_{23}\end{bmatrix}}}
could be stored in two possible ways:
Programming languages handle this in different ways. In C, multidimensional arrays are stored in row-major order, and the array indexes are written row-first (lexicographical access order):
On the other hand, in Fortran, arrays are stored in column-major order, while the array indexes are still written row-first (colexicographical access order):
… excerpt ends here. Continue reading the full article.
