Loop Optimization Techniques
- Code Motion
- Induction Variable Elimination
- Strength Reduction
- Loop Fusion
- Loop Unrolling
We will discuss these techniques one by one.
Code Motion
Also known as Frequency Reduction or Loop Invariant, this technique reduces the number of lines of code in a loop by moving some statements outside the loop.
Only those statements or expressions that do not affect a program's semantics and give the same result even after not shifting the statements can be placed just before the loop.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int a = 50;
int x, y = 10, z = 10;
while(a>0) {
x = y + z;
if(a%x==0)
printf("%d",a);
a--;
}
}
You can also try this code with Online C Compiler
Run Code
In the above code, a variable a is initialized to 50. Then a loop is there, running till a > 0 means 50 times in which a variable x is assigned to y + z and a condition checking if a divided by x leaves remainder 0 then prints the value of a.
In the loop, the only variable whose value is getting updated is a. The value of x, y, and z is not getting changed. So, we can optimize this code by placing the statement x = y + z outside the loop.
Hence, the optimized code will be-
#include <stdio.h>
void main() {
int a = 50;
int x, y = 10, z = 10;
x = y + z;
while(a>0) {
if(a%x==0)
printf("%d",a);
a--;
}
}
You can also try this code with Online C Compiler
Run Code
Induction Variable Elimination
In the induction variable elimination technique, there is an induction variable. A variable x is called an induction variable in a loop L; if in every round of the loop, the value of x changes, it either gets incremented or decremented.
The aim of the induction variable elimination method is to replace the induction variable from the loop. This technique improves the execution time of a program.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int a[20], b[20];
int i, j, k;
for (i = 0, j = 0, k = 0; i < 20; i++)
a[j++] = b[k++];
}
You can also try this code with Online C Compiler
Run Code
In the above code, there are three induction variables i, j, and k. The variable i is a counter variable that is running a loop to copy the values from array b to array a while the variables j and k are just pointing to the current indices of the two arrays. Thus, we can eliminate the induction variables j and k to optimize our code.
Hence, the optimized code will be-
#include <stdio.h>
void main() {
int a[20], b[20];
int i;
for (i = 0; i < 20; i++)
a[i] = b[i];
}
You can also try this code with Online C Compiler
Run Code
Strength Reduction
Strength reduction or reduction in strength is a technique in which we replace expensive operations with cheaper operations. For example, the strength of the * operator is higher than the + operator. So, the compiler takes more time to execute the multiplication operation than the addition operation. To optimize the code, we will simply try to replace the *, i.e., high strength or expensive operator, with the +, i.e., low strength or cheap operator.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int a = 1, b;
while (a<10) {
b = a * 2;
a++;
}
}
You can also try this code with Online C Compiler
Run Code
In the above code, there are 2 variables a and b. Variable a is a loop variable. Inside the loop, a multiplication operation is being performed in which variable a and the digit 2 are multiplied, and the result is stored in variable b. Since * is a high-strength operator, we will replace it with the + operator.
Hence, the optimized code will be-
#include <stdio.h>
void main() {
int a = 1, b;
while (a<10) {
b = a + a;
a++;
}
}
You can also try this code with Online C Compiler
Run Code
Loop Fusion
Also known as Loop Jamming, this technique combines two or more loops which have the same index variable and number of iterations.
This technique reduces the time taken in compiling all the loops.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int a[10], b[10], i;
for(i = 0; i < 10; i++)
a[i] = 1;
for(i = 0; i < 10; i++)
b[i] = 2;
}
You can also try this code with Online C Compiler
Run Code
In the above code, there are two loops. The first loop running ten times assigns the value 1 at each index of the array a while the second loop also runs ten times, assigning the value 2 at each index of the array b. We can observe that the work of both these loops is almost the same. Both are running ten times and assigning a value to an array. Thus, we can combine both these loops to optimize our code.
Hence, the optimized code will be-
#include <stdio.h>
void main() {
int a[10], b[10], i;
for(i = 0; i < 10; i++) {
a[i] = 1;
b[i] = 2;
}
}
You can also try this code with Online C Compiler
Run Code
Loop Unrolling
The loop unrolling technique transforms the loop. In this technique, the number of jumps and tests can be optimized by writing the code to times without changing the meaning of the code. It reduces the number of iterations and increases the program’s speed by eliminating the loop control instructions and loop test instructions.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int i = 1;
int a[100], b[100];
while(i<100) {
a[i] = b[i];
i++;
}
}
You can also try this code with Online C Compiler
Run Code
In the above code, a loop is running 100 times. We can optimize this code by repeating the statements so that the loop runs only 50 times.
Hence, the optimized code will be-
#include <stdio.h>
void main() {
int i = 1;
int a[100], b[100];
while(i<100) {
a[i] = b[i];
i++;
a[i] = b[i];
i++;
}
}
You can also try this code with Online C Compiler
Run Code
Frequently Asked Questions
Is loop jamming a loop optimization techniques?
Yes. Loop jamming is a loop optimization technique. It is a combination of two or more loops in a single loop. It is important because it is used to reduce the time taken to combine a large number of for loops.
How to optimize for loop in C?
To optimize for loops in C, consider techniques such as loop unrolling, reducing iterations, reusing values, loop invariant code motion, using cache-friendly data structures, and parallelization. Balance these optimizations with code readability and maintainability, and measure performance to ensure improvement.
Define loop optimization.
Loop optimization is a machine-independent optimization technique that increases a program's execution speed by decreasing the overhead of loops. Since the most time of a compiler is spent executing the loops, reducing the number of instructions in a loop will improve the program's running time and help execute the code faster.
What are the loop optimization techniques?
Loop optimization can be performed by using the following techniques-
- Code Motion
- Induction Variable Elimination
- Strength Reduction
- Loop Fusion
- Loop Unrolling
Conclusion
In this article, we have studied Loop Optimization. We went through the concept thoroughly, discussing various loop optimization techniques, including code motion, induction variable elimination, strength reduction, loop fusion, and loop unrolling, along with an example of each.
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy Learning!