Loop Unrolling

Loop Unrolling

Topic : Loop Unrolling
source of the topic : Code Complete2

Loop Unrolling, is a technique for optimizing parts of computer programs. The goal of loop unrolling is to reduce the amount of loop housekeeping.
Note: Loop unrolling undesirable if you are concerned about readability of the code.

// Example of normal loop i=0 while ( i < count ) { a[ i ] = i; i++; }

Use this technique only when you desire for code optimization. It will severely hurts program readability

// Loop unrolled once i = 0; while ( i < count -1 ) { a[ i ] = i; a[ i + 1 ] = i + 1; // Unrolling once i = i + 2; } if ( i == count) { // These lines pick up the case a[ i - 1 ] = i - 1;// that might fall through the } // cracks if the loop went by // twos instead of by ones

The technique replaced the original a[ i ] = i line with two lines, and i is incremented by 2 rather than by 1. The extra code after the while loop is needed when count is odd and the loop has one iteration left after the loop terminates.
We can see a gain of 43% in performance with loop unrolling once.

// Loop unrolled twice i = 0; while ( i < count - 2 ) { a[ i ] = i; a[ i + 1 ] = i+1; a[ i + 2 ] = i+2; i = i + 3; } if ( i <= count - 1 ) { a[ count - 1 ] = count - 1; } if ( i == count - 2 ) { a[ count -2 ] = count - 2; }

We can see a gain of 43% in performance with loop unrolling once.
The results indicate that further loop unrolling can result in further time savings, but not necessarily so, as the Java measurement shows.

Divide and Conquer algorithms, trick

Possible mistake in implementing Divide and Conquer algorithms is, In many cases you may need to divide the input range.

Take Binary search as an example:
in each step we need to calculate "mid".

//Common practice of doing this:
// Broke - if (start + end) > Integer.MAX_VALUE
// Mid value will be assigned with -ve value.
mid = (start + end) / 2;                                                      

// Better way to avoid the problem
mid = start + (end - start)/2 ;