
This recommendation is part of the open catalog of best practice rules for performance that is automatically detected and reported by Codee.
Issue
Indirect array access may impact performance.
Actions
Consider using techniques like loop fusion, loop interchange, loop tiling or changing the data layout to avoid non-consecutive accesses in hot loops.
Relevance
Accessing an array indirectly (e.g. through another array containing the positions to be accessed) is generally less efficient than accessing consecutive positions because the latter improves locality of reference.
Code examples
Consider the example code below to illustrate the presence of indirect access patterns. The elements of array a
are accessed in an indirect manner through the array b. Thus, the code exhibits random accesses that cannot be predicted before the actual execution of the code.
void example(float *a, unsigned *b, unsigned size) {
for (unsigned i = 0; i < size; ++i) {
a[b[i]] = 0.f;
}
}
Next, consider another example code where memory access patterns are optimized in order to improve locality of reference. More specifically, 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]];
}
}
The alternative implementation shown below takes advantage of loop interchange to improve locality of reference. Now, 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]];
}
}
Related resources
References
- Memory access pattern (indirect array access)
- Locality of reference
- Loop interchange
- Loop tiling

Building performance into the code from day one with Codee