102

我一直在尝试通过循环展开来优化一些对性能至关重要的代码（一种在蒙特卡罗模拟中被调用数百万次的快速排序算法）。这是我试图加速的内部循环：

// Search for elements to swap.
while(myArray[++index1] < pivot) {}
while(pivot < myArray[--index2]) {}

我尝试展开到类似的内容：

while(true) {
    if(myArray[++index1] < pivot) break;
    if(myArray[++index1] < pivot) break;
    // More unrolling
}


while(true) {
    if(pivot < myArray[--index2]) break;
    if(pivot < myArray[--index2]) break;
    // More unrolling
}

这完全没有区别，所以我把它改回更易读的形式。其他时候我也有过类似的经历，我尝试过循环展开。考虑到现代硬件上分支预测器的质量，循环展开何时（如果有的话）仍然是一种有用的优化？

4

9 回答 9

136

如果您可以打破依赖链，那么循环展开是有意义的。这使无序或超标量 CPU 有可能更好地安排事情，从而运行得更快。

一个简单的例子：

for (int i=0; i<n; i++)
{
  sum += data[i];
}

这里参数的依赖链非常短。如果您因为数据阵列上的缓存未命中而出现停顿，则 cpu 只能等待。

另一方面，这段代码：

for (int i=0; i<n-3; i+=4)  // note the n-3 bound for starting i + 0..3
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;
// if n%4 != 0, handle final 0..3 elements with a rolled up loop or whatever

可以跑得更快。如果您在一次计算中遇到缓存未命中或其他停顿，则仍有三个其他依赖链不依赖于停顿。一个乱序的 CPU 可以并行执行这些。

（请参阅为什么 mulss 在 Haswell 上只需要 3 个周期，与 Agner 的指令表不同？（展开具有多个累加器的 FP 循环）以深入了解寄存器重命名如何帮助 CPU 找到并行性，并深入了解现代 x86-64 CPU 上 FP 点积的详细信息，以及流水线浮点 SIMD FMA ALU 的吞吐量与延迟特性。隐藏 FP 加法或 FMA 的延迟是多个累加器的主要好处，因为延迟比整数长，但SIMD 吞吐量通常相似。）

于 2010-02-27T22:54:50.723 回答
27

这些不会有任何区别，因为您正在进行相同数量的比较。这是一个更好的例子。代替：

for (int i=0; i<200; i++) {
  doStuff();
}

写：

for (int i=0; i<50; i++) {
  doStuff();
  doStuff();
  doStuff();
  doStuff();
}

即使那样，它也几乎肯定没关系，但您现在正在进行 50 次比较而不是 200 次（想象比较更复杂）。

然而，手动循环展开通常在很大程度上是历史的产物。这是一个好的编译器在重要的时候会为你做的越来越多的事情之一。例如，大多数人都懒得写x <<= 1或x += x代替x *= 2. 您只需编写代码x *= 2，编译器就会为您优化到最佳状态。

基本上，对编译器进行二次猜测的需求越来越少。

于 2010-02-27T22:44:29.153 回答
15

不管现代硬件上的分支预测如何，大多数编译器都会为你循环展开。

找出编译器为您做了多少优化是值得的。

我发现Felix von Leitner 的演讲在这个主题上非常有启发性。我建议你阅读它。简介：现代编译器非常聪明，因此手动优化几乎从不有效。

于 2010-02-27T22:48:39.083 回答
2

据我了解，现代编译器已经在适当的地方展开循环 - 一个例子是 gcc，如果传递了优化标志，手册说它将：

展开循环，其迭代次数可以在编译时或进入循环时确定。

因此，在实践中，您的编译器很可能会为您处理琐碎的案例。因此，您需要确保尽可能多的循环便于编译器确定需要多少次迭代。

于 2010-02-27T22:50:09.437 回答
2

循环展开，无论是手动展开还是编译器展开，通常会适得其反，特别是对于更新的 x86 CPU（Core 2、Core i7）。底线：在您计划部署此代码的任何 CPU 上使用和不使用循环展开对您的代码进行基准测试。

于 2010-02-27T23:40:26.700 回答
1

在不知不觉中尝试不是做到这一点的方法。
这种排序是否占总时间的高比例？

所有循环展开所做的都是减少递增/递减、比较停止条件和跳转的循环开销。如果你在循环中所做的事情比循环开销本身需要更多的指令周期，那么你不会看到多少百分比的改进。

以下是如何获得最佳性能的示例。

于 2010-02-28T16:41:19.333 回答
1

在特定情况下，循环展开可能会有所帮助。唯一的收获是没有跳过一些测试！

例如，它可以允许标量替换、软件预取的有效插入……通过积极展开，它实际上是多么有用（即使使用 -O3，您也可以轻松地在大多数循环上获得 10% 的加速）。

正如之前所说，它在很大程度上取决于循环，编译器和实验是必要的。很难制定规则（或者展开的编译器启发式将是完美的）

于 2010-03-01T20:38:44.220 回答
0

循环展开完全取决于您的问题大小。这完全取决于您的算法能够将大小减少到更小的工作组中。你上面所做的看起来不像那样。我不确定是否可以展开蒙特卡罗模拟。

我循环展开的好场景是旋转图像。因为您可以轮换不同的工作组。要使其正常工作，您必须减少迭代次数。

于 2010-02-27T22:45:37.543 回答
0

如果在循环中和循环中都有很多局部变量，则循环展开仍然很有用。更多地重用这些寄存器，而不是为循环索引保存一个。

在您的示例中，您使用少量局部变量，而不是过度使用寄存器。

如果比较繁重（即非test指令），比较（到循环结束）也是一个主要缺点，特别是如果它依赖于外部函数。

循环展开也有助于提高 CPU 对分支预测的意识，但无论如何都会发生。

于 2010-02-27T22:49:40.687 回答