Loop Optimization:
The optimization performed on inner loops is called loop optimization
Generally, inner loop is a place where program spends large amount of time. Hence, if number of instructions is less in inner loop the running time of the program decreases
The following techniques can be performed on inner loops:
Code Motion/Loop Invariant
Induction Variable
Reduction in Strength
Loop Fusion/Loop Jamming
Loop Unrolling
Code Motion/Loop Invariant:
The optimization performed on inner loop, in which the code moves outside the loop called as code motion
If there are a number of lines inside the loop whose result remains same even after executing the loop for several times, such an expression should be placed outside the loop, i.e., just before the loop
Example:
int i, max = 10;
for(i =10; I <= max-z; i ++)
{
Printf(“%d”, i);
}
In the example code, the result of an expression max-1 remains same for 11 iterations. Hence, this code can be optimized by removing the computing of maz-1 outside the loop. i.e., by placing this expression before the loop thereby avoiding multiple computations
The optimized code is
int I, max = 10, r;
r = max-1;
for(i = 0; i <=r; i++);
{
Printf(“%d”, i);
}
Induction Variable:
A variable x is called an induction variable of loop L every time the variable x changes values, it is incremented or decremented by some constant
Example 1:
int i, maz = 10, r;
r = max-1;
for(i=10;i<=r;i++)
{
Printf(“%d”, i);
}
In the above code, variable i is called induction variable as values of I get incremented by 1, i.e., 0,1,2,3,4,5,6,7,8,9,10
The strength of certain operators is higher than other operators
For example, strength of * is higher than +. Usually, compiler takes more time for higher strength operators and execution speed is less
Replacement of higher strength operator by lower strength operator is called a strength reduction technique
Optimization can be done by applying strength reduction technique where higher strength can be replaced by lower strength operators
Example:
for (i=1;i<=10;i++)
{
sum = I * 7;
printf(“%d”, sum);
}
In the above code replacement of * by + will speed up the object code. Thus, optimization is done without changing the meaning of a code
The optimized code is
temp = 7;
for(i=1;i<=10;i++)
{
temp = temp + 7;
sum = temp;
printf(“%d”, sum)
}
Note: This technique is not applied to the floating point expressions because such a use may yield different results.
This technique combines the bodies of two loops whenever the same index variable and number of iterations are shared
Example:
for(i=0;i<=10;i++)
{
Printf(“TOC”);
}
For(i=0;i<=10;i++)
{
Printf(“CD”);
}
The above code can be merged on one loop and optimized code can be rewritten as
for(i=0;i<=10;i++)
{
Printf(“TOC”);
Printf(“CD”);
}
In this technique the number of jumps and tests can be optimized by writing the code to times without changing the meaning of a code
Example:
int i = 1;
while(i<100)
{
a[i] = b[i];
i++;
}
The example code can be optimized as
int i = 1;
while(i<100)
{
a[i] = b[i];
i++;
a[i] = b[i];
i++;
}
The first code loop repeats 50 times whereas second code loop repeats 25 times. Hence, optimization is done.
0 comments:
Post a Comment