Lecture
In computing, row-major order and column-major order are methods for storing multidimensional arrays in linear memory, 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, 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.
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 non-sequential 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, which operate on vectors of data. In some media, such as magnetic-tape data storage , sequential access is orders of magnitude faster than non-sequential access.
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, and so on. If more than one attribute participates in the ordering, the first is called major and the last minor . If two attributes participate in the 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 ; for example, given a matrix A , the entry a1,2 is in its first row and second column. This convention carries over to the syntax of programming languages , although often with indices starting from 0 instead of 1.
Even though the row is denoted by the first index and the column by the second index , this does not imply any grouping order between the dimensions. Thus, the choice of how to group and order the indices, either by row or by column, is a matter of convention. The same terminology can be applied to arrays of even higher dimensions. Grouping by row starts from the leftmost index, and grouping by column starts from the rightmost index, resulting in lexicographic and colexicographic (or colex) order respectively.
For example, the array
can be stored in two ways:
| Address | Row-major order | Column-major order |
|---|---|---|
| 0 | a11 | a11 |
| 1 | a12 | a21 |
| 2 | a13 | a12 |
| 3 | a21 | a22 |
| 4 | a22 | a13 |
| 5 | a23 | a23 |
Programming languages handle this differently. In C, multidimensional arrays are stored in row-major order, and array indices are written row-first (lexicographic access order):
| Address | Access | Value |
|---|---|---|
| 0 | A |
a11 |
| 1 | A |
a12 |
| 2 | A |
a13 |
| 3 | A |
a21 |
| 4 | A |
a22 |
| 5 | A |
a23 |
In Fortran, on the other hand, arrays are stored in column-major order, while array indices are still written row-first (colexicographic access order):
| Address | Access | Value |
|---|---|---|
| 1 | A(1,1) |
a11 |
| 2 | A(2,1) |
a21 |
| 3 | A(1,2) |
a12 |
| 4 | A(2,2) |
a22 |
| 5 | A(1,3) |
a13 |
| 6 | A(2,3) |
a23 |
Note that the use of A[i][j]with multi-step indexing as in C, as opposed to a neutral notation like A(i,j)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 row A[i]part can even be assigned to an intermediate variable that is then indexed in a separate expression. (No other implications should be assumed; for example, Fortran is not column-major merely because of its notation, and even the aforementioned implication can be deliberately circumvented in a new language.)
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 indices (using the first index for the column and the second index for the row), and another is to bypass the language syntax by explicitly computing positions in a one-dimensional array. Of course, deviating from the convention likely entails costs that grow with the degree of required interaction with conventional language features and other code, not only in the form of increased vulnerability to errors (forgetting to also invert the order of matrix multiplication, reverting to the convention while writing code, maintenance, etc.), but also in the form of the need to actively permute elements, all of which must be justified by some ultimate goal, such as improved performance.
Programming languages or their standard libraries that support multidimensional arrays typically have a native storage order for these arrays, either row-major or column-major.
Row-major order is used in C / C++ / Objective-C (for C-style arrays), PL/I , Pascal , Speakeasy and SAS .
Column-major order is used in Fortran , MATLAB , GNU Octave , Julia , S , S-PLUS , R , Scilab , Yorick and Rasdaman
A typical alternative for storing dense arrays is to use Iliffe vectors , which usually store pointers to the elements of the same row contiguously (e.g. in row-major order), but not the rows themselves. They are used in (in order of age): Java , C# / CLI / .Net , Scala , and Swift .
Even less dense is the use of lists of lists, for example in Python , and in the Wolfram Language of Wolfram Mathematica .
An alternative approach uses tables of tables, for example in Lua .
Support for multidimensional arrays can 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).
Column-major order is the default in Eigen and Armadillo (both for C++).
A special case is OpenGL (and OpenGL ES ) for graphics processing. Since "recent mathematical treatments of linear algebra and related fields invariably treat vectors as columns", designer Mark Segal decided to change this convention from the one in the predecessor IRIS GL , which wrote 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 a trick to "[just] say that matrices in OpenGL are stored in column-major order". This really only mattered for the presentation, because matrix multiplication was stack-based and could still be interpreted as post-multiplication, but, even worse, reality leaked through the C-based API, because access to individual elements would be as M[vector][coordinate]or, effectively, M[column][row], which unfortunately confused the convention the designer sought to adopt, and this was even retained in the OpenGL Shading Language , which was added later (although it also allows accessing coordinates by name instead, such as M[vector].y). As a result, many developers now simply state that having the column as the first index is the definition of column-major, although this is clearly not the case with a true column-major language such as Fortran.
Torch (for Lua) changed its default from column-major order to row-major order.
Since swapping the array indices is the essence of transposing an array , an array stored as row-major but read as column-major (or vice versa) will appear transposed (as long as the matrix is square). Since actually performing this permutation in memory is usually an expensive operation, some systems provide options to designate individual matrices as stored transposed. The programmer must then decide whether to reorder the elements in memory, based on actual usage (including the number of times the array is reused in a computation).
For example, Basic Linear Algebra Subprograms functions are passed flags indicating which arrays are transposed.
The concept generalizes to arrays with more than two dimensions.
For a d -dimensional 
array with dimensions N k ( 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:
where the empty product is the multiplicative identity element , i.e. 
.
For a given order, the stride in dimension k is given by the multiplication value in parentheses before the index n k in the summation on the right-hand side above.
In general, there are d! possible orders for a given array, one for each permutation of the dimensions (with row-major and column-major order being just 2 special cases), although the lists of stride values are not necessarily permutations of each other; for example, in the 2-by-3 example above, the strides are (3,1) for row-major and (1,2) for column-major.
Comments