循环展开,英文中称(Loop unwinding或loop unrolling),是一种牺牲程序的尺寸来加快程序的执行速度的优化方法。可以由程序员完成,也可由
编译器自动优化完成。
定义
可以由程序员完成,也可由
编译器自动优化完成。循环展开通过将
循环体代码复制多次实现。循环展开能够增大指令调度的空间,减少循环分支指令的开销。循环展开可以更好地实现数据预取技术。
优缺点
展开循环的好处
由于展开能够消除分支以及一些管理归纳变量的代码,因此可以摊销一些分支开销。
展开可以积极调度(或管道化)循环以掩盖一些延迟。如果有足够的空闲寄存器使变量保持活动状态,因为通过展开相关性链展露了关键路径,这将非常有用。
如果迭代次数是可预测的,并且循环中没有条件分支,则英特尔(R) 奔腾(R) 4 处理器可以正确预测迭代次数为 16 次或更少的内部循环的退出分支。因此,如果循环体不是太大,并且已知可探测的迭代次数,则可以展开内部循环,直到它们的迭代次数达到最大值 16。对于奔腾 III 或奔腾 II 处理器,请不要展开迭代次数大于 4 的循环。
展开循环的可能开销
通常增加程序代码大小可能是不合需要的,特别是对于嵌入式应用程序。 也可能导致指令缓存未命中增加,这可能会对性能产生负面影响。
除非优化编译器透明地执行,否则代码可能会变得不那么可读。
如果循环体中的代码涉及函数调用,则可能无法将展开与内联组合,因为代码大小的增加可能过多。 因此,可以在两个优化之间进行权衡。
在单次迭代中可能增加寄存器使用以存储临时变量,这可能会降低性能,尽管很大程度上取决于可能的优化。
除了非常小而简单的代码之外,包含分支的展开循环甚至比递归更慢。
静态循环展开
手动(或静态)循环展开涉及程序员分析循环并将迭代解释为一系列指令,这将减少循环开销。 这与由编译器完成的动态展开形成对比。
C中的简单手动示例
计算机程序中的过程是从集合中删除100个项目。 这通常是通过调用函数delete(item_number)的for循环来完成的。 如果要优化程序的这一部分,并且与delete(x)循环相比,循环的开销需要大量资源,则可以使用展开来加速它。
正常循环
循环展开后
这种修改的结果,新程序只需要进行20次迭代,而不是100次。之后,只需要采用20%的跳转和条件分支,并且在多次迭代中表示可能显着减少。循环管理开销。为了产生最佳效益,不应在需要指针运算的展开代码中指定变量。这通常需要“基础加偏移”寻址,而不是索引引用。
另一方面,这个手动循环展开将源代码大小从3行扩展到7,必须生成,检查和调试,并且编译器可能必须分配更多寄存器来在扩展循环迭代中存储变量。此外,必须仔细选择循环控制变量和展开的循环结构内的操作数,以便结果确实与原始代码中的相同(假设这是对已经工作的代码的后续优化)。例如,考虑迭代计数不能被5整除的含义。如果测试条件是变量,则所需的手动修正也会变得更复杂。另见Duff的设备。
动态展开
由于循环展开的好处经常取决于数组的大小 - 这通常在运行时才知道 -
JIT编译器(例如)可以确定是否调用“标准”循环序列或者生成(相对较短) )每个元素的单个指令序列。这种灵活性是即时技术与循环展开环境中的静态或手动优化相比的优势之一。在这种情况下,它通常具有相对较小的n值,其中节省仍然有用 - 需要非常小的(如果有的话)整体增加程序大小(可能仅包括一次,作为标准库的一部分)。
汇编语言程序员(包括优化编译器编写器)也能够从动态循环展开技术中受益,使用类似于用于高效分支表的方法。这里的优势是最大的,其中特定数组中任何引用字段的最大偏移量小于可在机器指令中指定的最大偏移量(如果超出则将由汇编程序标记)。
下面的示例演示了用C编写的简单程序的动态循环展开。与上面的汇编程序示例不同,在此示例中,编译器仍然生成指针/索引算法,因为变量(i)仍用于寻址数组元素。 只有在替换语句中使用绝对索引时,才能进行完全优化。