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

Issue

In the C and C++ programming languages, arrays are stored in a row-major layout; thus, column-major accesses are not 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 arrays 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 C and C++ code should access multi-dimensional arrays using a row-major order.

Actions

Change the code to access the multi-dimensional array in a row-major order.

Code example

In the following code, an outer loop iterates over the columns of a bidimensional array and then an inner loop iterates over the rows for each one of those columns.

#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;
    }
  }
}

This way of iterating and accessing the elements of the array doesn’t match its layout in memory. The optimal way is to iterate over the rows sequentially, then do the same for each column within the row:

#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

TAGS: