Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
If we consider computing b=A*x with x column vector, for row-major A we may use inner-products of vectors, A(i,:)^T x to get b(i); for column-major we may only need scalar multiplying vectors, sum_i A(:,i) x(i). It seems to me column major is much better! What do you think? – Hui Zhang Dec 2 '12 at 7:54
    
Train yourself to like column-major. It's easy when you visualize vectors as columns, or their transposition as rows. It makes visualization of matrix multiplication very simple, and makes it easy to follow lots of published math. – Mike Dunlavey Dec 3 '12 at 20:12

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.

share|improve this answer

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.

share|improve this answer
1  
I think these are poor arguments. The fact that the last index in '''double a[3][2]''' varies fastest is not a coincidence -- it was a concious design decision in just the same way as it was a conscious design decision in Fortran to do it the other way around when you have a '''real(3,2)''' array. – Wolfgang Bangerth Dec 2 '12 at 5:20
    
Furthermore, it's not true any more that pretty much all highly efficient numerical linear algebra is column major. This may still be true for BLAS and LAPACK, but it's not true at all for every major linear algebra library that has appeared in the past 15 years: for example, both PETSc and Trilinos use row major sparse matrix storage formats. – Wolfgang Bangerth Dec 2 '12 at 5:22
    
I'm aware that the C convention was a conscious decision, probably based off of natural reading order. I meant that it probably wasn't designed with numerical linear algebra in mind, making it a coincidence that it's row major. Second, I didn't intend the argument to hold for sparse matrices, only dense. For sparse, it's a bit of a mixed back out there, with both compressed row and column formats. – Victor Liu Dec 2 '12 at 10:58
4  
Not to belabor the point, but C was originally a systems language, based off earlier languages B and BCPL, running on systems like the PDP-11 which did not originally have floating point numbers. To say that they designed it with numerics in mind is quite a stretch. – Victor Liu Dec 2 '12 at 20:19
6  
Been there, etc. The reason matrices in C move the last index fastest is because C does not have matrices. It has vectors of vectors, that can be transparently implemented as solid blocks of memory, or as arrays of pointers to arrays. Making index-order compatible with Fortran was (I'm guessing) not even on Dennis Ritchie's radar. – Mike Dunlavey Dec 3 '12 at 20:06

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:

  • element $m_{i,j}$ will be stored at index $i \times m + j$ if row-major order is used
  • element $m_{i,j}$ will be stored at index $j \times n + i$ if column-major order is used

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:

  1. 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.

  2. rule of thumb: the quickly-varying index should be mapped to successive locations in memory.

  3. 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...)

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.