PWR035: avoid non-consecutive array access to improve performance

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

Issue

Non-consecutive array access may impact performance.

Relevance

Accessing an array in a non-consecutive order is less efficient than accessing consecutive positions because the latter maximises locality of reference. 

Actions

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

Code example

A binary tree is stored in an array. The top of the tree is in the array at position 0. If the node is at position X, then its children are in position 2 *X + 1 and 2 * X + 2. Here is the code that recursively calculates the sum of all nodes in the tree.

double calculate_sum(double* tree, int n) {
    return calculate_sum_internal(tree, 0, n);
}
     
double calculate_sum_internal(double* tree, int i, int n) {
    If (i < n) {
        return tree[i] + calculate_sum_internal(tree, 2 * i + 1, n) + calculate_sum_internal(tree, 2*i + 2, n); 
    } else {
        return 0.0;
    }
}

But since we know that the array is full and the addition is associative, we can calculate the sum using a simple for loop that iterates through all of the array.

double calculate_sum(double* tree, int i, int n) {
    double sum = 0.0;
    for (int i = 0; i < n; i++) {
        sum += tree[i];
    }
    return sum;
}