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

This recommendation is part of the open catalog of best practice rules for performance that is automatically detected and reported by Codee.

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.

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.

Actions

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

Code example

In the following code, the matrix A is accessed in a column-wise manner: every time the increment variable i of the innermost loop is increased, the code is accessing a new row.

#define ROWS 100
#define COLS 100

void foo() {
  int A[ROWS][COLS];

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

Because the matrix is stored row-major, this code is not accessing neighboring memory locations. Instead, it is accessing memory non-sequentially. The optimal way is to iterate over the memory sequentially, then do the same for each column within the row. To do this, we  interchange loops over i and j, loop over j becoming the inner loop and loop over i becoming the outer loop:

#define ROWS 100
#define COLS 100

void foo() {
  int A[ROWS][COLS];

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

Related resources

• PWR010 examples at GitHub
• Row-Major and Column-Major Array Layouts – MATLAB & Simulink
• Memory layout of multi-dimensional arrays
• Row- and column-major order
• Loop interchange