Loop fission

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

Loop fission is a program optimization technique that works by splitting a originally unvectorizable loop into two or more loops. The goal of the fission is to isolate the statements preventing the vectorization into a dedicated loop. By doing this, we enable vectorization in the rest of the loop, which can lead to speed improvements.

To illustrate loop fission, consider the following example:

for (int i = 0; i < n; i++) {
    a[index[i]] = expensive_computation();
}

Assuming that the code in expensive_computation is vectorizable, the whole loop is unvectorizable because of the indirect memory access to array a. This type of memory access renders compiler autovectorization inefficient, and the compiler will omit it.

A solution is to perform the loop fission: split the loop into two and isolate the vectorization-preventing statements into a separate loop. After fission, our example looks like this:

double* tmp = malloc(n * sizeof(double));

for (int i = 0; i < n; i++) {
    tmp[i] = expensive_computation();
}
for (int i = 0; i < n; i++) {
    a[index[i]] = tmp[i];
}

free(tmp);

For more information about statements that prevent automatic compiler vectorization, see vectorization.