OPEN CATALOG

Best practices for performance

PWR010: Avoid column-major array access in C/C++

Issue #

In the  C and C++ programming languages, matrices are stored in a row-major layout; thus, iterating the matrix column-wise is non-optimal and should be avoided if possible.

Actions #

Change the code to access the multi-dimensional array in a row-wise manner.

Relevance #

The most efficient way to process arrays is to iterate over its elements in the same order in which they are laid out in memory, so that the program performs a sequential access to consecutive data in memory. The C and C++ language specifications state that matrices are laid out in memory in a row-major order: the elements of the first row are laid out consecutively in memory, followed by the elements of the second row, and so on. As a result, in order to maximize performance, the C and C++ code should access multi-dimensional arrays in a row-wise manner.

Code examples #

In the following code, the matrix A is accessed in a column-wise manner. Given a value of the loop iterator variable j, the j-th column of A is accessed by increasing the loop iterator variable i of the innermost loop. As the matrix A is stored according to a row-major layout in C/C++, this code is accessing non-consecutive memory locations.

 for (int j = 0; j < n; ++j) {
    for (int i = 0; i < n; ++i) {
      A[i][j] = 0;
    }
  }

The optimal way is to iterate over the memory sequentially. The code below performs the same computations, the difference being that matrix A is accessed in row-major order matching the row-major layout of C/C++. Thus, given a value i, the i-th row of A is accessed by increasing the loop iterator variable j of the innermost loop. Note that in the example above the loop nest order is ji while now it is ij.

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      A[i][j] = 0;
    }
  }

Related resources #

References #