为什么树矢量化使这种排序算法慢2倍？

Question

如果在gcc(4.7.2)中启用,则此问题的排序算法会快两倍(!-fprofile-arcs).该问题的大量简化的C代码(事实证明我可以用全零来初始化数组,奇怪的性能行为仍然存在,但它使得推理更加简单):

#include <time.h>
#include <stdio.h>

#define ELEMENTS 100000

int main() {
  int a[ELEMENTS] = { 0 };
  clock_t start = clock();
  for (int i = 0; i < ELEMENTS; ++i) {
    int lowerElementIndex = i;
    for (int j = i+1; j < ELEMENTS; ++j) {
      if (a[j] < a[lowerElementIndex]) {
        lowerElementIndex = j;
      }
    }
    int tmp = a[i];
    a[i] = a[lowerElementIndex];
    a[lowerElementIndex] = tmp;
  } 
  clock_t end = clock();
  float timeExec = (float)(end - start) / CLOCKS_PER_SEC;
  printf("Time: %2.3f\n", timeExec);
  printf("ignore this line %d\n", a[ELEMENTS-1]);
}

在使用优化标志很长一段时间之后,事实证明这-ftree-vectorize也产生了这种奇怪的行为,因此我们可以-fprofile-arcs解决这个问题.在进行剖析后,perf我发现唯一的相关区别是:

快速案例gcc -std=c99 -O2 simp.c(在3.1s内运行)

    cmpl    %esi, %ecx
    jge .L3
    movl    %ecx, %esi
    movslq  %edx, %rdi
.L3:

慢箱gcc -std=c99 -O2 -ftree-vectorize simp.c(在6.1s内运行)

    cmpl    %ecx, %esi
    cmovl   %edx, %edi
    cmovl   %esi, %ecx

至于第一个片段:假设数组只包含零,我们总是跳转到.L3.它可以从分支预测中大大受益.

我猜这些cmovl指令无法从分支预测中受益.

---

问题:

1. 以上所有猜测都是正确的吗？这会使算法变慢吗？

2. 如果是,我怎么能阻止gcc发出这条指令(-fno-tree-vectorization当然除了简单的解决方法),但仍然尽可能多地进行优化？

3. 这是什么-ftree-vectorization？文档很模糊,我需要更多解释来了解发生了什么.

---

更新:因为它出现在评论中:-ftree-vectorize标志的奇怪性能行为仍然是随机数据.正如Yakk指出的那样,对于选择排序,实际上很难创建一个会导致很多分支错误预测的数据集.

既然它也出现了:我有一个Core i5 CPU.

---

根据Yakk的评论,我创建了一个测试.下面的代码(在线没有提升)当然不再是排序算法; 我只拿出了内循环.它的唯一目标是检查分支预测的效果:我们以概率跳过循环中的if分支.forp

#include <algorithm>
#include <cstdio>
#include <random>
#include <boost/chrono.hpp>
using namespace std;
using namespace boost::chrono;
constexpr int ELEMENTS=1e+8; 
constexpr double p = 0.50;

int main() {
  printf("p = %.2f\n", p);
  int* a = new int[ELEMENTS];
  mt19937 mt(1759);
  bernoulli_distribution rnd(p);
  for (int i = 0 ; i < ELEMENTS; ++i){
    a[i] = rnd(mt)? i : -i;
  }
  auto start = high_resolution_clock::now();
  int lowerElementIndex = 0;
  for (int i=0; i<ELEMENTS; ++i) {
    if (a[i] < a[lowerElementIndex]) {
      lowerElementIndex = i;
    }
  } 
  auto finish = high_resolution_clock::now();
  printf("%ld  ms\n", duration_cast<milliseconds>(finish-start).count());
  printf("Ignore this line   %d\n", a[lowerElementIndex]);
  delete[] a;
}

感兴趣的循环:

这将被称为cmov

g++ -std=c++11 -O2 -lboost_chrono -lboost_system -lrt branch3.cpp

    xorl    %eax, %eax
.L30:
    movl    (%rbx,%rbp,4), %edx
    cmpl    %edx, (%rbx,%rax,4)
    movslq  %eax, %rdx
    cmovl   %rdx, %rbp
    addq    $1, %rax
    cmpq    $100000000, %rax
    jne .L30

---

这将被称为no cmov,Turix在他的回答中-fno-if-conversion指出了这面旗帜.

g++ -std=c++11 -O2 -fno-if-conversion -lboost_chrono -lboost_system -lrt branch3.cpp

    xorl    %eax, %eax
.L29:
    movl    (%rbx,%rbp,4), %edx
    cmpl    %edx, (%rbx,%rax,4)
    jge .L28
    movslq  %eax, %rbp
.L28:
    addq    $1, %rax
    cmpq    $100000000, %rax
    jne .L29

---

差异并排

cmpl    %edx, (%rbx,%rax,4) |     cmpl  %edx, (%rbx,%rax,4)
movslq  %eax, %rdx          |     jge   .L28
cmovl   %rdx, %rbp          |     movslq    %eax, %rbp
                            | .L28:

---

执行时间是伯努利参数的函数 p

带cmov指令的代码绝对不敏感p.该代码没有的cmov指令是赢家,如果p<0.26还是0.81<p和至多4.38x较快(p=1).当然,分支预测器的更糟糕的情况是在p=0.5代码比带有cmov指令的代码慢1.58倍的情况下.

Answer 1

注意:图表更新之前已回答问题; 这里的一些汇编代码引用可能已经过时了.

(从我们上面的聊天中进行了改编和扩展,这足以激励我做更多的研究.)

首先(根据我们的上述聊天),您的第一个问题的答案似乎是"是".在矢量"优化的"码中,最优化(带负)影响性能是分支predic 一个和灰,而在原始代码的性能是(正)受分支预测.(注意前者的额外' a '.)

回答你的第三个问题:即使在你的情况下,实际上没有进行矢量化,从步骤11("条件执行")开始,似乎与矢量化优化相关的步骤之一是在目标循环内"展平"条件,喜欢循环中的这一点:

if (a[j] < a[lowerElementIndex]
    lowerElementIndex = j;

显然,即使没有矢量化,也会发生这种情况.

这解释了编译器使用条件移动指令(cmovl)的原因.目标是完全避免分支(而不是试图正确预测).相反,两个cmovl指令将在前一个结果cmpl已知之前沿管道发送,然后比较结果将被"转发"以在其回写之前(即,在它们实际生效之前)启用/阻止移动.

注意,如果循环已被矢量化,那么这可能是值得的,以便能够有效地并行完成循环的多次迭代.

但是,在您的情况下,优化尝试实际上是逆火,因为在展平循环中,两个条件移动通过循环每次都通过管道发送.这本身也可能不是那么糟糕,除了有一个RAW数据危险导致第二个move(cmovl %esi, %ecx)必须等到数组/内存访问(movl (%rsp,%rsi,4), %esi)完成,即使结果最终会被忽略.因此,花在这个特定上的时间很长cmovl.(我希望这是一个问题,你的处理器没有足够复杂的逻辑内置到其预测/转发实现中来处理危险.)

另一方面,在非优化的情况下,正如您所理解的那样,分支预测可以帮助避免必须等待相应的阵列/存储器访问的结果(movl (%rsp,%rcx,4), %ecx指令).在这种情况下,当处理器正确地预测一个被采用的分支(对于一个全0的数组将是每一次,但在随机数组中[均匀]应该[仍然]大致超过 [编辑每@ Yakk的评论]一半的时间),它不必等待内存访问完成继续并在循环中排队接下来的几条指令.因此,在正确的预测中,您会获得提升,而在不正确的预测中,结果并不比"优化"情况更差,而且更好,因为有时能够避免cmovl在管道中使用2"浪费" 指令.

[由于我根据您的评论错误地假设您的处理器,因此删除了以下内容.]
回到你的问题,我建议查看上面的链接,了解更多有关矢量化的标志,但最后,我很确定忽略优化,因为你的Celeron无法使用它(在这种情况下)无论如何.

[删除上面后添加]
重新提出你的第二个问题(" ......我怎么能阻止gcc发出这条指令... "),你可以尝试-fno-if-conversion和-fno-if-conversion2标志(不确定这些是否总是有效 - 它们不再起作用在我的Mac上),虽然我不认为你的问题是cmovl一般的指令(即​​,我不会总是使用这些标志),只是在这个特定的上下文中使用它(其中分支预测将是非常有用的给定@ Yakk关于排序算法的观点).