Развертывание циклов: техника оптимизации производительности

Loop transformation technique

Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as space–time tradeoff. The transformation can be undertaken manually by the programmer or by an optimizing compiler. On modern processors, loop unrolling is often counterproductive, as the increased code size can cause more cache misses; cf. Duff's device. The goal of loop unwinding is to increase a program's speed by reducing or eliminating instructions that control the loop, such as pointer arithmetic and "end of loop" tests on each iteration; reducing branch penalties; as well as hiding latencies, including the delay in reading data from memory. To eliminate this computational overhead, loops can be re written as a repeated sequence of similar independent statements. Loop unrolling is also part of certain formal verification techniques, in particular bounded model checking.

The overhead in "tight" loops often consists of instructions to increment a pointer or index to the next element in an array (pointer arithmetic), as well as "end of loop" tests. If an optimizing compiler or assembler is able to pre calculate offsets to each individually referenced array variable, these can be built into the machine code instructions directly, therefore requiring no additional arithmetic operations at run time. Significant gains can be realized if the reduction in executed instructions compensates for any performance reduction caused by any increase in the size of the program. Branch penalty is minimized. If the statements in the loop are independent of each other (i. e. where statements that occur earlier in the loop do not affect statements that follow them), the statements can potentially be executed in parallel. Can be implemented dynamically if the number of array elements is unknown at compile time (as in Duff's device). Optimizing compilers will sometimes perform the unrolling automatically, or upon request.

Increased program code size, which can be undesirable—particularly for embedded applications—can also cause an increase in instruction cache misses, which may adversely affect performance. Unless performed transparently by an optimizing compiler, the code may become less readable. If the code in the body of the loop involves function calls, it may not be possible to combine unrolling with inlining, since the increase in code size might be excessive. Thus, there can be a trade off between the two optimizations. Possible increased register usage in a single iteration to store temporary variables, which may reduce performance, though much will depend on possible optimizations. Apart from very small and simple code, unrolled loops that contain branches are even slower than recursions.

Manual (or static) loop unrolling involves the programmer analyzing the loop and interpreting the iterations into a sequence of instructions which will reduce the loop overhead. This is in contrast to dynamic unrolling which is accomplished by the compiler.

Since the benefits of loop unrolling are frequently dependent on the size of an array—which may often not be known until run time—JIT compilers (for example) can determine whether to invoke a "standard" loop sequence or instead generate a (relatively short) sequence of individual instructions for each element. This flexibility is one of the advantages of just in time techniques versus static or manual optimization in the context of loop unrolling. In this situation, it is often with relatively small values of n where the savings are still useful—requiring quite small (if any) overall increase in program size (that might be included just once, as part of a standard library). Assembly language programmers (including optimizing compiler writers) are also able to benefit from the technique of dynamic loop unrolling, using a method similar to that used for efficient branch tables. Here, the advantage is greatest where the maximum offset of any referenced field in a particular array is less than the maximum offset that can be specified in a machine instruction (which will be flagged by the assembler if exceeded).