PWR039: Consider loop interchange to improve the locality of reference and enable vectorization

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

Issue

Inefficient matrix access pattern detected that can be improved through loop interchange.

Relevance

Inefficient memory access pattern and low locality of reference are among the main reasons for low performance on modern computer systems. Matrices are stored in a row-major order in C and column-major order in Fortran. Iterating over them column-wise (in C) and row-wise (in Fortran) is inefficient, because it uses the memory subsystem suboptimally.

Nested loops that iterate over matrices inefficiently can be optimized by applying loop interchange. Using loop interchange, the inefficient matrix access pattern is replaced with a more efficient one. Often, loop interchange enables vectorization of the innermost loop which additionally improves performance.

Actions

Interchange inner and outer loops in the loop nest.

Note

Loop interchange can be performed only on perfectly nested loops, i.e. on loops where all the statements are in the body of the innermost loop. If the loops are not perfectly nested, it is often possible to make them perfectly nested through refactoring.

Code example

The following code shows two nested loops:

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

The matrix A is accessed column-wise, which is inefficient. To fix it, we perform the loop interchange of loops over i and j. After the interchange, the loop over j becomes the outer loop and loop over i becomes the inner loop.

After this modification, the access to matrix A is no longer column-wise, but row-wise, which is much faster and more efficient. Additionally, the compiler can vectorize the inner loop.  

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

Related resources

• PWR040: Consider loop tiling to improve the locality of reference
• PWR010: Avoid column-major array access in C/C++