Table of contents:
Issue
Avoid column-major array accesses in the C and C++ programming languages.
Definition
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;
}
}
}