Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
In programming dense matrix computations, is there any reason to choose a row-major layout of the over the column-major layout?
I know that depending on the layout of the matrix chosen, we need to write the appropriate code to use the cache memories effectively for speed purposes.
The row-major layout seems more natural and simpler (at least to me). But major libraries like LAPACK which are written in Fortran use the column major layout, so there must be some reason for having made this choice.
The column major layout is the scheme used by Fortran and that's why it's used in LAPACK and other libraries.
In general it is much more efficient in terms of memory bandwidth usage and cache performance to access the elements of an array in the order in which they're laid out in memory. Depending on how your matrices are stored, you'll want to pick algorithms that take advantage of this.
Internal storage of column major format
In vacuum without considering any existing software, there's no reason to prefer column major over row major from the code point of view. However, most mathematical literature is written in a way that groups vectors into a matrix by storing them as columns instead of rows. For example when you write the full eigenvalue equation $AX=X\Lambda$, the $X$ matrix contains all the eigenvectors written out in columns. You never really see it written the other way (though I hear that statistics folks like row vectors). Therefore, it was natural that the earliest software assumed column major format so that if you have a matrix which is a set of vectors, the storage of any single vector is contiguous. Thus, I imagine that tradition has just been carried forward to the present day, and if you want to interact with the ye olde Fortran, you want to use column major. So pretty much all highly efficient numerical linear algebra is done in column major.
The reason C is row major is somewhat of a consequence of its array syntax; you declare a 3 row by 2 column array as double a[3][2], and later indices vary faster than earlier indices, which for 2D arrays makes it row major. Combine this with the natural Western reading order from left to right, it makes row major seem more natural.
The choice of row-major / column-major indexing can have a significant impact on performances because of the way memory and cache works, and the way multiple indices are converted into a linear index. Internally, memory is a single 1-dimensional array, and the elements of a $m\times n$ matrix will be arranged linearly:
Now imagine the following algorithm:
for i from 1 to m
for j from 1 to n
do something with m(i,j)
If row-major order is used, then this will traverse all the linear indices $i \times m + j$ sequentially, resulting in good memory locality, whereas if column-major order is used, then successive memory accesses will be scattered in memory. Consequences can be dramatic especially when virtual memory / swapping enters the scene.
Conclusions:
yes, it has an importance, but the choice depends on the way data is accesed. For the previous example, if column-order is used, what you can do is simply swapping the two loops.
rule of thumb: the quickly-varying index should be mapped to successive locations in memory.
more importantly, measuring / benchmarking the impact of the choice is fundamental, since it depends on many parameters (the size of the data, the size of the cache, the way the used language maps multiple indices to a linear index, the way the operating system manages virtual memory, the way loops are nested in the linear algebra library that you use...)
Column-major order seems to be more natural. For example suppose if you want to save movie to file picture by picture then you are using column order, and that is very intuitive and nobody would save it in row-major order.
If you are programmer in C/C++ you should use some higher level libraries for matrices (Eigen, Armadillo,...) with default column-major order. Only maniac would use raw C pointers with row-major order, although C/C++ offers something that reminds matrix indexing.
For simplicity everything with row-major order should be considered as at least strange formed. Slice by slice is simply natural order and it means column-major order (like Fortran). Our fathers/mothers had a very good reasons why they chose it.
Unfortunately before it became clear several interesting libraries were created in row-major order, probably due to lack of experience.
To clarify recall the definition of row-major order where right index vary faster in one step through memory eg A(x,y,z) it is z-index, it means that in memory pixels from different slices are adjacent, what we wouldn't want. For movie A(x,y,t) the last index is time t. It is not hard to imagine that it is simply impossible to save movie in row-major mode.
