为什么处理未排序数组与使用现代 x86-64 clang 处理排序数组的速度相同？

手心的温柔

我发现这个大约9 岁的流行病SO 问题，并决定仔细检查结果。
所以，我有 AMD Ryzen 9 5950X、clang  10 和 Linux，我从问题中复制粘贴代码，这是我得到的:
' K. A9 m/ E7 W8 D排序 - 0.549702s：
0 U( Q% A' |+ H- Q4 l

~/d/so_sorting_faster$ cat main.cpp | grep "std::sort" && clang   -O3 main.cpp && ./a.out    std::sort(data,data   arraySize);0.549702sum = 314931600000

未分类 - 0.546554s：

~/d/so_sorting_faster $ cat main.cpp | grep "std::sort" && clang   -O3 main.cpp && ./a.out    // std::sort(data,data   arraySize);0.546554sum = 314931600000

我很确定 unsorted 版本比 3ms 快的事实只是噪音，但似乎不再慢了。
那么，CPU 的架构发生了什么变化？(让它不再慢一个数量级)？
以下是多次操作的结果：
' W- B  c* `3 {! |6 X

Unsorted: 0.543557 0.551147 0.541722 0.555599Sorted:   0.542587 0.559719 0.53938  0.557909
, a; G% J# p, ?- ^2 e! W9 k

以防万一，这是我的 main.cpp：

• #include #include #include int main()()()()()(///)()()()()()(()()()()()())()()(////)())()()()())()()()///////)()()()())())()())()())())()()()()()()()())()()()()()()())()()()())()()()()()()())()()())()()()())()()()()()()()()()()()()//////)/)/)/)()()()()()()()()()()())()())())())()())()())()())()())()())()()())()())()()()()()())()))()))()))()())())())())()()()())()))()))())())()))()()))()()()))()()()))())())()))())()()())())()))())))))())))()()))())))())))()))()())()())()))()))()()()()()))())))))())())()()()()()))))()))())))))()))))()))())()()))))())()()()()()()()())()))()////////)))))))))))))()))))))))()))))))()()()()()()()())))Generate data    const unsigned arraySize =   int data[arraySize];    for (unsigned c = 0; c =         sum  = data[c];         double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC;    std::cout 更新
  
• (627680)元素较多：[code]Unsortedcat main.cpp | grep "std::sort" && clang   -O3 main.cpp && ./a.out    // std::sort(data,data   arraySize);10.3814Sorted:cat main.cpp | grep "std::sort" && clang   -O3 main.cpp && ./a.out    std::sort(data,data   arraySize);10.6885
  : O4 I/ H9 V0 W4 ?) v% f" V

我认为这个问题仍然相关- 几乎没有区别。
                                                               
* k1 I5 d/ L$ x$ u( y    解决方案:                                                               
                                                                您链接中的几个答案是将代码重写为无分支，以避免任何分支预测。这就是你更新的编译器所做的。
具体来说，带-O3 矢量化内部循环clang   10 Godbolt 程序集上的代码是第 36-67 行。代码有点复杂，但你永远看不到的是data[c] >= 128测试中的任何条件分支。相反，它使用向量比较指令 ( pcmpgtd)，输出是一个掩码， 1 表示匹配元素，0 表示不匹配。pand带有此掩码的后续元素将不匹配元素替换为 0，因此当它们无条件地添加到总和时，它们不会做出任何贡献。
粗略的 C   等价物是

sum  = data[c] & -(data[c] >= 128);
- [. B- P- S. Q% u. H

代码实际上sum为数组的偶数和奇数元素保留了两个 64 位，使其并行累积，然后在循环结束时加入。
一些额外的复杂性是 32 位data元素符号扩展到 64 位置；这就是序列喜欢pxor xmm5,xmm5 ; pcmpgtd xmm5,xmm4 ; punpckldq xmm4,xmm完成的-mavx2.你会看到一个更简单的vpmovsxdq ymm5,xmm5的地方。
% e2 m5 P7 |0 w由于循环已经展开，代码看起来也很长，data 8 元素每次迭代处理。