循环展开和优化

Question

给定代码：

for (int i = 0; i < n; ++i) 
{ 
  A(i) ; 
  B(i) ; 
  C(i) ; 
}

优化版本如下：

for (int i = 0; i < (n - 2); i+=3) 
{ 
  A(i) 
  A(i+1) 
  A(i+2) 
  B(i) 
  B(i+1) 
  B(i+2) 
  C(i) 
  C(i+1) 
  C(i+2)
}

有一件事情我不是很清楚：哪个更好？我没有看到使用另一个版本能使任何东西更快。这里我错过了什么吗？

我看到的是每个指令都依赖于先前的指令，这意味着我需要等待先前的指令完成才能开始下一个...

谢谢

- JAN

---

维基百科有一篇关于循环展开的好文章，供参考：http://en.wikipedia.org/wiki/Loop_unwinding - Stuart Golodetz

一般来说，它们并不相等。应该是 A(i); B(i); C(i); A(i+1); B(i+1); 等等。 - gnasher729

Answer 1

在语言的高层视图中，你看不到优化。速度增强来自编译器对你所拥有的内容的处理。

在第一种情况下，它是这样的：

LOCATION_FLAG;
DO_SOMETHING;
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false

在第二个方案中，类似的情况是：

LOCATION_FLAG;
DO_SOMETHING;
DO_SOMETHING;
DO_SOMETHING;
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false

在后一种情况下，您可以看到测试和跳转的开销仅为每3个指令1个。在前一种情况下，它是每1个指令1个；因此它发生得更频繁。

因此，如果您有可靠的不变量（例如模3的数组），则展开循环更加高效，因为底层汇编代码编写得更直接。

- Nathaniel Ford

Answer 2

循环展开是用来减少跳转和分支指令数量的，这有可能使循环更快，但会增加二进制文件的大小。根据实现和平台的不同，两种方法都有可能更快。

- P.P

Answer 3

那么，这段代码是“更好”还是“更差”完全取决于A、B和C的实现，您期望n有哪些值，您正在使用哪个编译器以及您正在运行的硬件。

通常情况下，循环展开的好处在于减少循环的开销（也就是增加i并将其与n进行比较）。在这种情况下，可以减少三分之一的开销。

- Johan Kotlinski

Answer 4

只要函数A()、B()和C()不修改相同的数据集，第二个版本提供了更多的并行化选项。

在第一个版本中，三个函数可以同时运行，假设没有互相依赖。在第二个版本中，假设您有足够的执行单元，并且再次没有相互依赖，所有三个函数都可以同时使用所有三个数据集运行。

- Baldy

Answer 5

通常情况下，试图“发明”优化并不是一个好主意，除非你有确凿的证据表明你会获得提高，因为很多时候你可能会引入恶化。通常获得这样的证据的最佳方式是使用良好的分析器。我建议使用分析器测试此代码的两个版本以查看差异。

此外，许多时候循环展开并不是非常可移植，如前所述，这在很大程度上取决于平台、编译器等。

你还可以尝试调整编译器选项。一个有趣的gcc选项是“-floop-optimize”，它会自动与“-O，-O2，-O3和-Os”一起使用。

另外，注意“-funroll-loops”编译器选项。

- Brady

---

此外，看看这个相当简洁但令人惊叹的展开循环示例：达夫设备。 - Brady