何时，如果有必要的话，循环展开仍然是有用的？

Question

我一直在尝试通过循环展开来优化一些极其性能关键的代码（一个快速排序算法，在蒙特卡罗模拟中被调用数百万次）。

这里是我试图加速的内部循环：

// 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
}

这完全没有任何影响，所以我改回了更易读的形式。我尝试过其他几次展开循环也有类似的经历。考虑到现代硬件上分支预测器的质量，展开循环什么时候仍然是一个有用的优化方法呢？

- dsimcha

---

请问为什么您不使用标准库的快速排序例程？ - Peter Alexander

@Poita：因为我的程序包含了一些额外的功能，这些功能对我进行统计计算非常有用，并且我的程序经过高度优化以适应我的使用情况，因此比标准库快得可测。我正在使用D编程语言，它拥有一个过时的差劲优化器，而且对于大量随机浮点数数组，我仍然比GCC的C++ STL排序算法快10-20%。 - dsimcha

Answer 1

如果你可以打破依赖链，那么展开循环是有意义的。这使得乱序或超标量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可以并行执行这些依赖链。

（请参见Why does mulss take only 3 cycles on Haswell, different from Agner's instruction tables? (Unrolling FP loops with multiple accumulators) ，深入了解寄存器重命名如何帮助CPU查找并行性，以及现代x86-64 CPU上浮点SIMD FMA ALU的吞吐量与延迟特征的详细信息。隐藏FP加法或FMA的延迟是多个累加器的主要优点，因为延迟比整数更长，但SIMD吞吐量通常相似。）

- Nils Pipenbrinck

---

谢谢。我已经尝试了这种风格的循环展开，在库中其他计算总和等操作的地方也使用它，效果非常好。我几乎可以确定原因是它增加了指令级并行性，正如您所建议的那样。 - dsimcha

很好的回答和有启发性的例子。虽然我不明白缓存未命中时的停顿如何影响性能对于这个特定的例子。但是，我通过注意到第一个代码片段禁用了浮点通道中任何类型的指令级并行性，而第二个代码片段允许超标量CPU同时执行多达四个浮点加法来解释两个代码片段之间的性能差异（在我的机器上，第二个代码片段快2-3倍）。 - Toby Brull

请记住，使用这种方式计算总和时，结果不会与原始循环的数值完全相同。 - Bas

循环依赖是一个周期，加法操作。OoO核心可以胜任。在这里展开可能有助于浮点SIMD，但这与OoO无关。 - Veedrac

@Nils：并不是很多，主流的x86 OoO CPU仍然类似于Core2/Nehalem/K10。在高速缓存缺失之后的追赶仍然相当次要，隐藏FP延迟仍然是主要优点。 在2010年，能够每个时钟周期执行2个加载操作的CPU甚至更加稀少（只有AMD，因为SnB还未发布），因此对于整数代码而言，多个累加器肯定比现在不那么有价值（当然，这是应该自动矢量化的标量代码，所以谁知道编译器将把多个累加器转换为矢量元素还是多个向量累加器...） - Peter Cordes

Answer 2

这些方法都不会有任何区别，因为你进行的比较次数是相同的。这里有一个更好的例子，可以替代原来的方法：

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，编译器将为您优化到最佳状态。

基本上越来越少需要对编译器进行推测了。

- cletus

---

@Mike 当然，在困惑时关闭优化是一个好主意，但值得阅读Poita_发布的链接。编译器在这方面变得非常出色。 - dmckee --- ex-moderator kitten

“@Mike '我完全有能力决定何时做或不做那些事情'... 我怀疑这点，除非你是超人。” - Mr. Boy

@John: 我不知道你为什么这么说；人们似乎认为优化是某种只有编译器和猜测能力强的人才懂得的黑魔法。但实际上，它都归结于指令和时钟周期，以及它们被消耗的原因。就像我在SO上多次解释过的那样，很容易知道它们被消耗的方式和原因。如果我的一个循环必须使用大量时间，并且在循环开销方面花费了太多的时钟周期，相比之下内容较少，我可以看到并展开它。同样的道理也适用于代码提升。这不需要天才。 - Mike Dunlavey

我相信这并不难，但我还是怀疑你能否像编译器一样快速地完成。反正编译器为什么不能帮你做呢？如果你不喜欢它，就把优化关闭，像1990年那样浪费时间吧！ - Mr. Boy

循环展开带来的性能提升与你所节省的比较无关，完全没有任何关系。 - bobbogo

Answer 3

在现代硬件上，无论分支预测如何，大多数编译器都会为您执行循环展开。

了解一下编译器为您做了多少优化是值得的。

我发现Felix von Leitner的演讲对这个主题非常有启发性。我建议您阅读一下。总结：现代编译器非常聪明，因此手动优化几乎永远不会有效。

- Peter Alexander

---

这是一篇不错的文章，但我认为仅有一部分准确，就是他谈到保持数据结构简单的那部分。其余内容虽然准确，但建立在一个未经声明的巨大假设之上——即正在执行的代码必须存在。在我所做的调优中，我发现人们会在寻找寄存器和缓存未命中时烦恼，而实际上大量的时间都浪费在了无用的抽象代码堆积中。 - Mike Dunlavey

“手动优化几乎从来不起作用” → 如果你完全是新手的话，这可能是正确的。否则就不是真的。 - Veedrac

在2019年，我仍然手动展开循环，相比编译器的自动尝试，取得了实质性的收益。因此，让编译器全部处理并不可靠。它似乎并不经常展开循环。至少对于C#来说，我不能代表所有语言发表意见。 - WDUK

Answer 4

据我所了解，现代编译器已经可以在适当的情况下展开循环 - 例如gcc，如果传递了优化标志，则手册中表示它将：

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

因此，在实践中，您的编译器很可能会为您处理简单的情况。因此，您需要确保尽可能多的循环易于让编译器确定需要多少次迭代。

- Rich Bradshaw

---

即时编译器通常不会进行循环展开，因为启发式算法的成本太高。静态编译器可以花更多时间来处理它，但两种主要方式之间的差异很重要。 - Abel

Answer 5

无论是手动展开循环还是编译器展开循环，循环展开通常都不是一个好的选择，特别是对于更近期的x86 CPU（Core 2，Core i7）而言。最重要的是：在计划部署此代码的任何CPU上，都应该进行有和无循环展开的代码基准测试。

- Paul R

---

为什么特别是在最近的x86 CPU上？ - JohnTortugo

@JohnTortugo: 现代x86 CPU 对于小循环有一些优化 - 例如在Core和Nehalem架构上的Loop Stream Detector（循环流检测器） - 将一个循环展开以使其不再小到适合LSD缓存，会破坏这种优化。参见例如http://www.tomshardware.com/reviews/Intel-i7-nehalem-cpu,2041-3.html - Paul R

Answer 6

不知道就试着做并不是正确的方法。
这种排序算法占总时间的比例高吗？

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

这里有一个如何获得最大性能的示例。

- Mike Dunlavey

Answer 7

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

例如，它可以允许标量替换、有效地插入软件预取等...实际上，你会惊讶地发现它可以非常有用（即使使用-O3，你也可以轻松获得大多数循环的10%加速），通过积极地展开。

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

- Kamchatka

Answer 8

循环展开完全取决于问题的规模。它完全依赖于您的算法能够将大小减小为较小的工作组。您上面所做的似乎不是这样。我不确定蒙特卡洛模拟是否可以展开。

循环展开的一个好场景是旋转图像。因为您可以旋转独立的工作组。要使其正常工作，您需要减少迭代次数。

- jwendl

---

我正在展开一个快速排序，它被从模拟的内部循环调用，而不是模拟的主循环。 - dsimcha

Answer 9

如果循环中有许多本地变量，循环展开仍然很有用。可以更多地重复使用这些寄存器，而不是为循环索引保存一个寄存器。

在您的示例中，您使用了少量的本地变量，没有过度使用寄存器。

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

循环展开还有助于增加CPU对分支预测的意识，但这些情况无论如何都会发生。

- LiraNuna