Row- and column-major order
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.
Such ways of storing data are referred to as AoS and SoA respectively.
This is primarily due to CPU caching which exploits spatial locality of reference.
[1] In addition, contiguous access makes it possible to use SIMD instructions that operate on vectors of data.
[citation needed] The terms row-major and column-major stem from the terminology related to ordering objects.
If more than one attribute participates in ordering, the first would be called major and the last minor.
This convention is carried over to the syntax in programming languages,[2] although often with indexes starting at 0 instead of 1.
The choice of how to group and order the indices, either by row-major or column-major methods, is thus a matter of convention.
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): Note how the use of A[i][j] with multi-step indexing as in C, as opposed to a neutral notation like A(i,j) as in Fortran, almost inevitably implies row-major order for syntactic reasons, so to speak, because it can be rewritten as (A[i])[j], and the A[i] row part can even be assigned to an intermediate variable that is then indexed in a separate expression.
To use column-major order in a row-major environment, or vice versa, for whatever reason, one workaround is to assign non-conventional roles to the indexes (using the first index for the column and the second index for the row), and another is to bypass language syntax by explicitly computing positions in a one-dimensional array.
Of course, deviating from convention probably incurs a cost that increases with the degree of necessary interaction with conventional language features and other code, not only in the form of increased vulnerability to mistakes (forgetting to also invert matrix multiplication order, reverting to convention during code maintenance, etc.
), but also in the form of having to actively rearrange elements, all of which have to be weighed against any original purpose such as increasing performance.
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), PL/I,[4] Pascal,[5] Speakeasy,[citation needed] and SAS.
[6] Column-major order is used in Fortran,[7][8] IDL,[7] MATLAB,[8] GNU Octave, Julia,[9] S, S-PLUS,[10] R,[11] Scilab,[12] Yorick, and Rasdaman.
[13] A typical alternative for dense array storage is to use Iliffe vectors, which typically store pointers to elements in the same row contiguously (like row-major order), but not the rows themselves.
[18] 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.
Since "recent mathematical treatments of linear algebra and related fields invariably treat vectors as columns," designer Mark Segal decided to substitute this for the convention in predecessor IRIS GL, which was to write vectors as rows; for compatibility, transformation matrices would still be stored in vector-major (=row-major) rather than coordinate-major (=column-major) order, and he then used the trick "[to] say that matrices in OpenGL are stored in column-major order".
[21] This was really only relevant for presentation, because matrix multiplication was stack-based and could still be interpreted as post-multiplication, but, worse, reality leaked through the C-based API because individual elements would be accessed as M[vector][coordinate] or, effectively, M[column][row], which unfortunately muddled the convention that the designer sought to adopt, and this was even preserved in the OpenGL Shading Language that was later added (although this also makes it possible to access coordinates by name instead, e.g., M[vector].y).
Torch (for Lua) changed from column-major[22] to row-major[23] default order.
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).
For example, the Basic Linear Algebra Subprograms functions are passed flags indicating which arrays are transposed.
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.
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.
