Tuesday, July 17, 2007

Code Optimization Techniques

“Premature optimization is root of all evils.” - Donald Knuth.

Thus one should first find out if she really wants to optimize her code, and usually there are more reasons to decide not to optimize the code.
The common reasons why one should not optimize are below

  • Optimization can introduce more bugs.
  • Optimization will surely reduce understandability and readability of code.
  • Optimization will make it difficult to maintain and extend the code.
  • Time spent in optimization may not be that much effective in overall performance of the application.
  • At last optimizing code may minimize portability of code.

But if optimization is evil why we need it?
Most of the time code consumes lot of resources such as memory, CPU cycles, bandwidth etc, thus minimizing overall performance.
We have following options to achieve this target

  1. Using more efficient algorithm.
  2. Using Manual optimization.
  3. Using optimizing compilers.
  4. Using JIT or adaptive compilers.

Using More Efficient Algorithm:
The most common example would be "sum of n natural numbers"
Instead of using
for (int i=0; i<n; i++){
sum += i;
}
We can use
sum = n*(n+1)/2;
But usually we would be using the best algorithm available or might be this is too late to change the algorithm.
Point to remember: It’s better to calculate performance of any algorithm at initial stage of any implementation.


Using Manual Optimization:
As its clear from the name, optimizations are done manually and needs a lot of man power, thus the best way to plan and carry out optimization is to include optimization early in product development and using these while coding, instead of altering completed code/modules.

1. General Optimization Techniques
These techniques are general and language independent, these are simple techniques witch is useful in achieving optimization by just simple restructuring or modification in the code.


Strength Reduction: It’s a method of replacing an operation with an equivalent but more efficient operation. For example – using shift operation instead of multiplication and division, that is using x>>1 instead of x/2 and x<<1.
Common Sub-Expression Removal: Removing redundant calculations.
For example
float surfaceArea=6*lengt*width;
float volume=length*width*height;
Can be changed in
float area=length*width;
float surfaceArea=6*area;
float volume=area*height;



Code Motion: Moving the code, witch yields a constant output, out of loop/block where the calculation is done, so that it is calculated only once.
For Example
for (int r=1;r<10;r++){
totalarea=(22/7)*r*r;
}
Can be changed in
double pi=22/7;
for (int r=1;r<10;r++){
totalarea=pi*r*r;
}

Unrolling Loops: Doing more calculations in single iteration and reducing the number of iterations required. Good amount of optimization can be achieved through loop unrolling.
For example - if we know that length of the array is always multiple of 5 than
for (int i=1;i<10;i++){
someArray[i]=i;
}
Can be changed in
for (int i=1;i<10;i+=5){
someArray[i]=i;
someArray[i+1]=i+1;
someArray[i+2]=i+2;
someArray[i+3]=i+3;
someArray[i+4]=i+4;
}


2. Advanced Optimization Techniques (Java)
Please See: Optimizing Java Code

3. Using optimizing compilers
There are many commercial optimizing compilers to help, but one should first understand full working of optimizing compiler, and then what else that particular compiler offers and what are the risks involve in using that compiler.
Remember its not a good idea to use optimizing compiler just at the time of delivery, it would be better to use it from the beginning so that you will be able to know issues and limitations of the compiler.
Please See: Default Optimization by Javac Compiler.

4. Using JIT or adaptive compilers
Javac compiles the code in the byte code to enable compile once run anywhere feature, but JVM looses good amount of time because of overheads involved in providing these feature at runtime. JVM has to interpret byte code and convert it to machine command to give us portability, sometimes the thing witch we didn’t wanted at all, suppose the server is going to be only on given platform say Linux.

JIT compilers comes to help us in these situations, these compilers compiles the Java code into machine dependent instruction code thus giving high efficiency.

Adaptive Compiler are yet another breed of compiles based on Java HotSpot technology with concentrate on 80-20 rule and try to find and optimize the 20 percent of code witch is high resource consuming and referenced repetitively, these compilers use transformations to optimize code, they learn from given samples and adapt themselves to produce results for given environmental conditions.

No comments: