为什么树矢量化使这种排序算法慢2倍？
如果在gcc（4.7.2）中启用-fprofile-arcs则此问题的排序算法会快两倍（！）。 该问题的大量简化的C代码（事实certificate我可以用全零来初始化数组，奇怪的性能行为仍然存在，但它使得推理更加简单）：
#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]); }
在使用优化标志很长一段时间之后，事实certificate-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的评论 ，我创建了一个测试。 下面的代码（ 在线没有提升 ）当然不再是排序算法; 我只取出了内循环。 它的唯一目标是检查分支预测的效果： 我们以概率p跳过for循环中的if分支。
#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<ELEMENTS; ++i) { if (a[i] < a[lowerElementIndex]) { lowerElementIndex = i; } } auto finish = high_resolution_clock::now(); printf("%ld ms\n", duration_cast(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完全不敏感。 如果p<0.26或0.81<p并且最多快4.38倍（ p=1 ），则没有 cmov指令的代码是获胜者。 当然，分支预测器的最坏情况是在p=0.5左右，其中代码比使用cmov指令的代码慢cmov 。
注意：图表更新之前已回答问题; 这里的一些汇编代码引用可能已经过时了。
（从上面的聊天中进行了改编和扩展，这足以激励我做更多的研究。）
首先（根据我们上面的聊天），您的第一个问题的答案似乎是“是”。 在矢量“优化”代码中，影响性能的优化（负面）是分支预测 ，而在原始代码中，性能受到分支预测的影响（正面）。 （注意前者的额外’ a ‘。）
回答你的第三个问题：即使在你的情况下，实际上没有进行矢量化，从步骤11（“条件执行”） 开始 ，似乎与矢量化优化相关的步骤之一是在目标循环内“展平”条件，喜欢循环中的这一点：
if (a[j] < a[lowerElementIndex] lowerElementIndex = j;
显然，即使没有矢量化，也会发生这种情况。
这解释了编译器使用条件移动指令（ cmovl ）的原因。 目标是完全避免分支（而不是试图正确预测 ）。 相反，两个cmovl指令将在前一个cmpl的结果已知之前从管道向下发送，然后比较结果将被“转发”以在它们的回写之前启用/阻止移动（即，在它们实际生效之前） ）。
注意，如果循环已经被矢量化，那么这可能是值得的，以便能够有效地并行完成循环的多次迭代。
但是，在您的情况下，优化尝试实际上是逆火，因为在扁平循环中，两个条件移动通过循环每次都通过管道发送。 这本身可能也不是那么糟糕，除了有一个RAW数据危险导致第二次移动（ cmovl %esi, %ecx ）必须等到数组/内存访问（ movl (%rsp,%rsi,4), %esi ）完成，即使结果最终会被忽略。 因此，在特定的cmovl上花费了大量的时间。 （我希望这是一个问题，你的处理器没有足够复杂的逻辑内置到其预测/转发实现中来处理危险。）
另一方面，在非优化的情况下，正如您所理解的那样，分支预测可以帮助避免必须等待相应的数组/内存访问的结果（ movl (%rsp,%rcx,4), %ecx指令）。 在这种情况下，当处理器正确地预测一个被采用的分支（对于一个全0的数组将是每一次，但在随机数组中[均匀]应该[仍然] 大致 超过 [编辑每@ Yakk的评论]一半的时间），它不必等待内存访问完成继续并在循环中排队接下来的几条指令。 因此，在正确的预测中，您会获得提升，而在不正确的预测中，结果并不比“优化”情况更差，而且更好，因为有时能够避免在管道中使用2“浪费的” cmovl指令。
[由于我根据您的评论错误地假设您的处理器，因此删除了以下内容。] 回到你的问题，我建议查看上面的链接，了解更多有关矢量化的标志，但最后，我很确定忽略优化，因为你的Celeron无法使用它（在这种情况下）无论如何。
[删除上面后添加]
回答你的第二个问题（“ ......我怎么能阻止gcc发出这条指令... ”），你可以尝试-fno-if-conversion和-fno-if-conversion2标志（不确定这些是否总能正常工作 - - 它们不再适用于我的mac），虽然我不认为你的问题通常是cmovl指令（即，我不会总是使用那些标志），只是在这个特定的上下文中使用它（其中分支预测是鉴于@ Yakk关于排序算法的观点，将会非常有用。