c# upc-a Java Example of a Loop That Can Be Unrolled in C#.NET

Drawer UPC - 13 in C#.NET Java Example of a Loop That Can Be Unrolled

Normally, you d probably use a for loop for a job like this, but to optimize, you d have to convert to a while loop. For clarity, a while loop is shown here.

} i = 0; while ( i < count ) { a[ i ] = i; i = i + 1;

To unroll the loop partially, you handle two or more cases in each pass through the loop instead of one. This unrolling hurts readability but doesn t hurt the generality of the loop. Here s the loop unrolled once:

i = 0; while ( i < count - 1 ) { a[ i ] = i; a[ i + 1 ] = i + 1; i = i + 2; } if ( i == count ) { a[ count - 1 ] = count - 1; }

8 These lines pick up the case 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. When five lines of straightforward code expand to nine lines of tricky code, the code becomes harder to read and maintain. Except for the gain in speed, its quality is poor. Part of any design discipline, however, is making necessary trade-offs. So, even though a particular technique generally represents poor coding practice, specific circumstances may make it the best one to use. Here are the results of unrolling the loop:

Time Savings 34% 43% 16% -27%

A gain of 16 to 43 percent is respectable, although again you have to watch out for hurting performance, as the Python benchmark shows. The main hazard of loop unrolling is an off-by-one error in the code after the loop that picks up the last case. What if you unroll the loop even further, going for two or more unrollings Do you get more benefit Here s the code for a 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; }

Here are the results of unrolling the loop the second time:

Language Straight Time 1.75 1.01 5.33 2.51 Single Unrolled Time 1.15 0.581 4.49 3.21 Double Unrolled Time 1.01 0.581 3.70 2.79 Time Savings 42% 43% 31% -12%

The results indicate that further loop unrolling can result in further time savings, but not necessarily so, as the Java measurement shows. The main concern is how

Byzantine your code becomes. When you look at the code above, you might not think it looks incredibly complicated, but when you realize that it started life a couple of pages ago as a five-line loop, you can appreciate the trade-off between performance and readability.

One key to writing effective loops is to minimize the work done inside a loop. If you can evaluate a statement or part of a statement outside a loop so that only the result is used inside the loop, do so. It s good programming practice, and, in some cases, it improves readability. Suppose you have a complicated pointer expression inside a hot loop that looks like this: