My Tech notes: Loop Unrolling or Loop unwinding in C

Unix Documentation

Free Online Unix Training Materials

Lists many links to free Unix training materials.

Pointers and Arrays Materials

Pointers and Arrays materials Explained for C beginners

C FAQ and General Questions C Interview Questions

Powered By

Free XML Skins for Blogger

Powered by Blogger

Thursday, March 5, 2009

Loop Unrolling or Loop unwinding in C

What is Loop Unrolling or Loop unwinding in C?
Loop unwinding, also known as loop unrolling, is a loop transformation technique that attempts optimize a program's execution speed at the expense of its size.
The goal of loop unwinding is to increase the program's speed by reducing (or eliminating) the "end of loop" test on each iteration. Loops can be re-written as a sequence of independent statements which eliminates the loop controller overhead.
The major side effects of loop unrolling is The increased register usage in a single iteration to store temporary variables (though much will depend on possible optimizations), which may hurt performance.
The code size expansion after the unrolling, which is undesirable for embedded applications and for purposes of code readability. Large code can also cause an increase in instruction cache misses, which may adversely affect performance.
A simple example
A procedure in a computer program is to delete 100 items from a collection. This is accomplished by means of a for-loop which calls the function delete(item_number):

for (int x = 0; x <>

If this part of the program is to be optimized, and the overhead of the loop requires significant resources compared to that for delete(x), loop unwinding can be used to speed it up. This will result in an optimized code fragment like:

for (int x = 0; x <>

As a result of this modification, the new program has to make only twenty loops, instead of a hundred.

check example here.

No comments:

Post a Comment