Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Loop Optimization?
3.
Loop Optimization Techniques
3.1.
Code Motion
3.1.1.
Example:
3.2.
Induction Variable Elimination
3.2.1.
Example: Consider the following piece of code.
3.3.
Strength Reduction
3.4.
Loop Fusion
3.5.
Loop Unrolling
4.
Frequently Asked Questions
4.1.
Is loop jamming a loop optimization techniques?
4.2.
How to optimize for loop in C?
4.3.
Define loop optimization.
4.4.
What are the loop optimization techniques?
5.
Conclusion
Last Updated: May 23, 2024
Easy

Loop Optimization

Author Pakhi Garg
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Loop Optimization

Introduction

Loop optimization is a code optimization technique that focuses on improving the performance of loops in computer programs. It aims to reduce the number of operations or iterations required to complete a loop. Techniques include loop unrolling, unswitching, invariant code motion, and software pipelining.

In compiler design, code optimization is a program transformation technique that improves the intermediate code to consume fewer resources such as CPU, memory, etc., resulting in faster machine code.

The optimization process can be broadly divided into two types.

  1. Machine Independent Optimization- This code optimization process optimizes the intermediate code to produce a better target code.
  2. Machine Dependent Optimization- This optimization is performed after the target code has been created and converted according to the target machine architecture.

This article will learn about loop optimization, a machine-independent optimization technique.

What is 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.

Loop optimization can be performed by using the following techniques-

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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--;
    }
}

In the above code, a variable is initialized to 50. Then a loop is there, running till a > 0 means 50 times in which a variable 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--;
    }
}

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++];
}

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];
}

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++;
    }
}

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++;
    }
}

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;
}

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;
    }
}

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++;
    }
}

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++;
    }
}

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!

Previous article
Machine Independent Optimization
Next article
DAG Representation in Compiler Design
Live masterclass