什么时候,如果循环展开仍然有用？

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
}

这完全没有区别所以我把它改成了更易读的形式.我曾经尝试过循环展开,但我有类似的经历.鉴于现代硬件上的分支预测器的质量,何时(如果有的话)循环展开仍然是一个有用的优化？

Answer 1

如果你可以打破依赖链,循环展开是有意义的.这使得无序或超标量CPU可以更好地安排事情并因此运行得更快.

一个简单的例子:

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

这里参数的依赖链非常短.如果因为数据阵列上有缓存未命中而导致停顿,那么cpu除了等待之外什么也做不了.

另一方面这段代码:

for (int i=0; i<n; i+=4)
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;

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

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,编译器就会为你优化它.

基本上,对猜测编译器的猜测越来越少.

Answer 3

无论现代硬件上的分支预测如何,大多数编译器都会为您循环展开.

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

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