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

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

#include 
#include 

#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指令无法从分支预测中受益.

问题:

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

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

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

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

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

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

#include 
#include 
#include 
#include 
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(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和至多4.38x较快(p=1).当然,分支预测器的更糟糕的情况是在p=0.5代码比带有cmov指令的代码慢1.58倍的情况下.