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.

Tips on Using loop statement in Java

Topic: Tips on using the loops statements
Source of Topic: Effective Java, Programming Language Guide, by Joshua Bloch.

"The most powerful technique for minimizing the scope of a local variable is to declare it
where it is first used."

Prefer for loop over to while loop.
Reason: for loop has a chance of initializing the loop variables, limiting the scope to exact region where they're needed.

For example, here is the preferred way of iterating over a collection:

for ( Iterator i = c.iterator(); i.hasNext(); i++ ) { doSomething ( i.next() ) ; }

To see why this for loop is preferable to the more obvious while loop, consider the following
code fragment

Iterator i = c.iterator(); while (i.hasNext()) { doSomething(i.next()); } ... Iterator i2 = c2.iterator(); while (i.hasNext()) { // BUG! doSomethingElse(i2.next()); }

Above error is resulted with the habit of cut-and-paste the code: It initializes a new loop variable, i2, but uses the old one,
i, which unfortunately is still in scope. Above code doesn't give any compile error or doesn't throw any exception. Runs silently.
Instead of iterating over c2, the second loop terminates immediately, giving the false impression that c2 is empty. Because the
program errs silently, the error can remain undetected for a long time.

If the analogous cut-and-paste error were made in conjunction with the preferred for loop
idiom, the resulting code wouldn't even compile. The loop variable from the first loop would
not be in scope at the point where the second loop occurred:

for (Iterator i = c.iterator(); i.hasNext(); ) { doSomething(i.next()); } ... // Compile-time error - the symbol i cannot be resolved for (Iterator i2 = c2.iterator(); i.hasNext(); ) { doSomething(i2.next()); }

Moreover, if you use the for loop idiom, it's much less likely that you'll make the cut-and-
paste error, as there's no incentive to use a different variable name in the two loops. The loops
are completely independent, so there's no harm in reusing the loop variable name. In fact, it's
stylish to do so.

Iterating over random access list: ( examples of random access lists: ArrayList, Vector etc. )

//Common Practice for (int i = 0; i < list.size(); i++) { doSomething(list.get(i)); } // High-performance idiom for iterating over random access lists for (int i = 0, list.size(); i < n; i++) { doSomething(list.get(i)); }

This idiom is useful for random access List implementations such as ArrayList and Vector
because it is likely to run faster than the “preferred idiom” above for such lists. The important
thing to notice about this idiom is that it has two loop variables, i and n, both of which have
exactly the right scope. The use of the second variable is essential to the performance of the
idiom. Without it, the loop would have to call the size method once per iteration, which
would negate the performance advantage of the idiom. Using this idiom is acceptable when
you're sure the list really does provide random access; otherwise, it displays quadratic
performance.

Printing the arrays in Java programming language

// Common practice of printing the array in Java for( int i = 0; i < array.length; i++) { System.out.println(array[i]); } // Best way of printing the array in Java System.out.println( Arrays.asList(array) ) ;

Loop over an Array in java:

// Loop through an Array using for each for( int intVal : array ) { doSomething(intVal); }

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 ;

checking the oddity of a integer number in java

From Jashua Bloch's "Java Puzzlers" book.

// Worng way to check the oddity
public boolean isOdd(int num){
return (num % 2 == 1) // Broken- for all -ve odd numbers
}

// Right Solution
public boolean isOdd(int num){
return (num % 2 != 0)
}

// Much better and Faster
public boolean isOdd(int num){
return (num & 1)
}

Binary Search in java by Joshua Bloch

1:     public static int binarySearch(int[] a, int key) {
2:         int low = 0;
3:         int high = a.length - 1;
4:
5:         while (low <= high) {
6:             int mid = (low + high) / 2;
7:             int midVal = a[mid];
8:
9:             if (midVal < key)
10:                 low = mid + 1
11:             else if (midVal > key)
12:                 high = mid - 1;
13:             else
14:                 return mid; // key found
15:         }
16:         return -(low + 1);  // key not found.
17:     }

The bug is in this line:   int mid =(low + high) / 2;

It
fails for large values of the int variables low and high. Specifically,
it fails if the sum of low and high is greater than the maximum
positive int value (pow(2 , 31) - 1). The sum overflows to a negative
value, and the value stays negative when divided by two. In C this
causes an array index out of bounds with unpredictable results. In
Java, it throws ArrayIndexOutOfBoundsException.

So what's the best way to fix the bug? Here's one way:

    int mid = low + ((high - low) / 2);

Probably faster, and arguably as clear is:

  int mid = (low + high) >>> 1;

How to design a good API and Why it matters

How to Design a Good API and Why it Matters by Joshua Bloach(author of Effective Java)

The Eight Fallacies of Distributed Computing

Fallacies I have seen at James Gosling's blog

1. The network is reliable
2. Latency is zero
3. Bandwidth is infinite
4. The network is secure
5. Topology doesn't change
6. There is one administrator
7. Transport cost is zero
8. The network is homogeneous