PWR036: Avoid indirect array access to improve performance

Issue

Indirect array access may impact performance.

Relevance

Accessing an array indirectly (eg. through another array containing the positions to be accessed) is generally less efficient than accessing consecutive positions because the latter improves locality of reference.

Actions

Consider using techniques like loop fusion, loop interchange, loop tiling or changing the data layout to avoid non-sequential access in hot loops.

Code example

In this example, the elements of array a are accessed indirectly, through array index. What this means is that the program is accessing random elements of the array a, which leads to a low performance because of the poor usage of the memory subsystem.

for (int i = 0; i < LEN_1D; ++i) {
    for (int j = 1; j < LEN_1D; j++) {
        c[i] += a[index[j]];
    }
}

To fix it, we perform loop interchange. The loop over j becomes the outer loop, and the loop over i becomes the inner loop. By doing this, the access to a[index[j]] is an access to a constant memory location, since the value of j doesn’t change inside the loop. This leads to performance improvement.

for (int j = 1; j < LEN_1D; j++) { 
    for (int i = 0; i < LEN_1D; ++i) {
        c[i] += a[index[j]];
    }
}