In programming, unwinding a loop ( eng. Loop unwinding ) or unwinding a loop ( eng. Loop unrolling ) is a technique for optimizing computer programs that consists in artificially increasing the number of instructions executed during one iteration of a loop . As a result of applying this optimization, the number of instructions that can potentially be executed in parallel increases, and more intensive use of registers , data cache and execution devices becomes possible.
Example
int i ;
for ( i = 1 ; i < n ; i ++ )
{
a [ i ] = ( i % b [ i ]);
}
converted to the following code:
int i ;
for ( i = 1 ; i < n - 3 ; i + = 4 )
{
a [ i ] = ( i % b [ i ]);
a [ i + 1 ] = (( i + 1 ) % b [ i + 1 ]);
a [ i + 2 ] = (( i + 2 ) % b [ i + 2 ]);
a [ i + 3 ] = (( i + 3 ) % b [ i + 3 ]);
}
for (; i < n ; i ++ )
{
a [ i ] = ( i % b [ i ]);
}
This type of optimization is considered in detail, for example, in Generalized Loop-Unrolling [1] . It (together with splitting the body of the cycle ) under certain conditions (the absence of dependencies according to the data between the instructions in the new cycle) allows you to run the cycle on multiple processors .
There is also an unusual way to unwind a loop, called the " Duff device " - this method uses little-known and unobvious features of the C language syntax.
Weaknesses
One of the drawbacks of this optimization method when it is used in conjunction with splitting the loop body for further parallelization is that the data is retrieved from memory out of order, which can adversely affect cache performance. Another, more appropriate kind of optimization that makes better use of the processor cache is loop parallelization .
In addition, during the unwinding of the loop, the number of instructions executed at each iteration increases. If this number exceeds the capacity of the command cache, then instead of the expected increase in the efficiency of the loop, it can significantly decrease.
Notes
- ↑ JC Huang, T. Leng, Generalized Loop-Unrolling: a Method for Program Speed-Up, 1998