re_vision: Storage orders

There are two different storage orders for matrices and two-dimensional arrays: column-major and row-major. This page explains these storage orders and how to specify which one should be used.

Table of contents

Column-major and row-major storage

The entries of a matrix form a two-dimensional grid. However, when the matrix is stored in memory, the entries have to somehow be laid out linearly. There are two main ways to do this, by row and by column.

We say that a matrix is stored in row-major order if it is stored row by row. The entire first row is stored first, followed by the entire second row, and so on. Consider for example the matrix

$A = \begin{bmatrix} 8 & 2 & 2 & 9 \\ 9 & 1 & 4 & 4 \\ 3 & 5 & 4 & 5 \end{bmatrix}.$

If this matrix is stored in row-major order, then the entries are laid out in memory as follows:

 8 2 2 9 9 1 4 4 3 5 4 5

On the other hand, a matrix is stored in column-major order if it is stored column by column, starting with the entire first column, followed by the entire second column, and so on. If the above matrix is stored in column-major order, it is laid out as follows:

 8 9 3 2 1 5 2 4 4 9 4 5

This example is illustrated by the following Eigen code. It uses the PlainObjectBase::data() function, which returns a pointer to the memory location of the first entry of the matrix.

Example	Output
Matrix<int, 3, 4, ColMajor> Acolmajor; Acolmajor << 8, 2, 2, 9, 9, 1, 4, 4, 3, 5, 4, 5; cout << "The matrix A:" << endl; cout << Acolmajor << endl << endl; cout << "In memory (column-major):" << endl; for (int i = 0; i < Acolmajor.size(); i++) cout << (Acolmajor.data() + i) << " "; cout << endl << endl; Matrix<int, 3, 4, RowMajor> Arowmajor = Acolmajor; cout << "In memory (row-major):" << endl; for (int i = 0; i < Arowmajor.size(); i++) cout << (Arowmajor.data() + i) << " "; cout << endl;

Example

Output

Matrix<int, 3, 4, ColMajor> Acolmajor;
Acolmajor << 8, 2, 2, 9,
             9, 1, 4, 4,
             3, 5, 4, 5;
cout << "The matrix A:" << endl;
cout << Acolmajor << endl << endl; 

cout << "In memory (column-major):" << endl;
for (int i = 0; i < Acolmajor.size(); i++)
  cout << *(Acolmajor.data() + i) << "  ";
cout << endl << endl;

Matrix<int, 3, 4, RowMajor> Arowmajor = Acolmajor;
cout << "In memory (row-major):" << endl;
for (int i = 0; i < Arowmajor.size(); i++)
  cout << *(Arowmajor.data() + i) << "  ";
cout << endl;

Storage orders in Eigen

The storage order of a matrix or a two-dimensional array can be set by specifying the Options template parameter for Matrix or Array. As Tutorial page 1 - The Matrix class explains, the Matrix class template has six template parameters, of which three are compulsory (Scalar, RowsAtCompileTime and ColsAtCompileTime) and three are optional (Options, MaxRowsAtCompileTime and MaxColsAtCompileTime). If the Options parameter is set to RowMajor, then the matrix or array is stored in row-major order; if it is set to ColMajor, then it is stored in column-major order. This mechanism is used in the above Eigen program to specify the storage order.

If the storage order is not specified, then Eigen normally defaults to storing the entry in column-major order. This is also the case if one of the convenience typedefs (Matrix3f, ArrayXXd, etc.) is used. However, it is possible to change the default to row-major order by defining the EIGEN_DEFAULT_TO_ROW_MAJOR preprocessor directive.

Matrices and arrays using one storage order can be assigned to matrices and arrays using the other storage order, as happens in the above program when Arowmajor is initialized using Acolmajor. Eigen will reorder the entries automatically. More generally, row-major and column-major matrices can be mixed in an expression as we want.

Which storage order to choose?

So, which storage order should you use in your program? There is no simple answer to this question; it depends on your application. Here are some points to keep in mind:

Your users may expect you to use a specific storage order. Alternatively, you may use other libraries than Eigen, and these other libraries may expect a certain storage order. In these cases it may be easiest and fastest to use this storage order in your whole program.
Algorithms that traverse a matrix row by row will go faster when the matrix is stored in row-major order because of better data locality. Similarly, column-by-column traversal is faster for column-major matrices. It may be worthwhile to experiment a bit to find out what is faster for your particular application.
The default in Eigen is column-major. Naturally, most of the development and testing of the Eigen library is thus done with column-major matrices. This means that, even though we aim to support column-major and row-major storage orders transparently, the Eigen library may well work best with column-major matrices.