Loop Optimization in C: Unrolling and Fusion

In C programming, performance is a frequently discussed topic. One effective method to improve the execution speed of code is to optimize loops. This article will introduce two common loop optimization techniques: Loop Unrolling and Loop Fusion. These techniques can reduce the runtime of programs and enhance code efficiency.

Loop Unrolling

Concept

Loop unrolling is a method that reduces the total number of loop iterations by increasing the workload in each iteration. During unrolling, we attempt to lower the overhead caused by control structures by executing several operations within the loop multiple times.

Example

Here is a simple example demonstrating how to unroll a loop performing addition:

Original Code

#include <stdio.h>
void add_arrays(int *a, int *b, int *result, int size) {    for (int i = 0; i < size; i++) {        result[i] = a[i] + b[i];    }}

Unrolled Code

We can repeat the operations in the <span>for</span> loop twice to reduce control structure overhead and increase pipeline efficiency:

#include <stdio.h>
void add_arrays_unrolled(int *a, int *b, int *result, int size) {    int i;
    // Handle elements not divisible by 4    for (i = 0; i <= size - 4; i += 4) {        result[i]     = a[i]     + b[i];        result[i + 1] = a[i + 1] + b[i + 1];        result[i + 2] = a[i + 2] + b[i + 2];        result[i + 3] = a[i + 3] + b[i + 3];    }
    // Process remaining elements less than four    for (; i < size; ++i) {        result[i] = a[i] + b[i];    }}

Advantages and Disadvantages

• Advantages:

• Reduces the number of bypass instructions, making the program more efficient.
• Improves data locality, which helps with cache friendliness.

• Disadvantages:

• Increases the size of the code within a single function, which may lead to less friendly instruction caching.
• The effectiveness varies across different hardware, and the increased overhead may impact performance.

Loop Fusion

Concept

Loop fusion is a method that combines multiple independent but related loops into one, reducing unnecessary data reads/writes and conflicts from similar types of instructions. It is particularly suitable for multiple small independent computation blocks that share calculations or similar functions.

Example

Consider the case where summation and squaring of two arrays are performed separately:

Original Code

#include <stdio.h>
void process_arrays(int *a, int *b, int *sum_result, int* square_result,int size) {    for (int i = 0; i < size; ++i) {        sum_result[i]      = a[i]+b [i];       }
      for (int j=0;j<size;++j){          square_result[j]=a[j]*a[j];         }  }

Combined Code

We can place both operations into the same <span>for</span> loop to improve efficiency:

#include <stdio.h> 
void process_arrays_combined(int* a,int* b,int* sum_result,int* square_result,int size){      for(int k=0;k<size;++k){          sum_result[k]=a[k]+b[k];            square_result[k]=a[k]*a[k];         }  }

Advantages and Disadvantages

• Advantages:

• Reduces the time required to access arrays, as the same data is read only once during processing.
• Simplifies logic in many cases, making it easier for the compiler to optimize overall performance.

• Disadvantages:

• When too many combinations or complex tasks are involved, it can make a single function appear bloated and harder to manage and debug.
• If there are conditional statements or early exits, this method may introduce unnecessary complexity beyond manageable limits.

Conclusion

In C, by mastering protocols and utilizing various best practices such as unrolling and fusion, we can continuously enhance application performance. However, it is essential to balance maintainability with performance. Making choices in different contexts, especially concerning hardware architecture and high-level application scenarios, remains crucial. I hope this article helps beginners understand and apply these techniques.