为什么处理一个未排序的数组的速度与处理一个排序的数组与现代x86-64 clang相同?

Question

我发现了这个流行了9年的问题，并决定再次验证它的结果。

所以，我有AMD Ryzen 9 5950X, clang++ 10和Linux，我从问题中复制粘贴代码，这是我得到的:

Sorted - 0.549702s:

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

Unsorted - 0.546554s:

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

我很确定，事实证明，未排序的版本比3ms更快，这只是噪音，但它似乎不再慢了。

那么，CPU的体系结构发生了什么变化(这样它就不会再慢一个数量级了)?

以下是多次运行的结果:

Unsorted: 0.543557 0.551147 0.541722 0.555599
Sorted:   0.542587 0.559719 0.53938  0.557909

为了以防万一，这里是我的main.cpp:

#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! With this, the next loop runs faster.
// std::sort(data, data + arraySize);
// Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
return 0;
}

元素数较大(627680):

Unsorted
cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
// std::sort(data, data + arraySize);
10.3814
Sorted:
cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
std::sort(data, data + arraySize);
10.6885

我认为这个问题仍然是相关的——几乎没有区别。

Answer 1

您链接的问题中的几个答案讨论了将代码重写为无分支，从而避免任何分支预测问题。这就是你更新后的编译器正在做的。

具体来说，clang++ 10与-O3向量化了内部循环。请参阅汇编的第36-67行godbolt的代码。代码有点复杂，但是您肯定看不到data[c] >= 128测试上的任何条件分支。相反，它使用向量比较指令(pcmpgtd)，其输出是一个掩码，其中1表示匹配元素，0表示不匹配元素。随后的pand用这个掩码将不匹配的元素替换为0，这样当它们无条件地加到和中时就没有贡献了。

c++中大致等价的是

sum += data[c] & -(data[c] >= 128);

代码实际上为数组中的偶数和奇数元素保留了两个运行的64位sum，以便它们可以并行累积，然后在循环结束时加在一起。

一些额外的复杂性是要注意将32位data元素的符号扩展到64位;这就是像pxor xmm5, xmm5 ; pcmpgtd xmm5, xmm4 ; punpckldq xmm4, xmm5这样的序列所完成的。打开-mavx2，您将看到一个更简单的vpmovsxdq ymm5, xmm5。

代码看起来也很长，因为循环已经展开，每次迭代处理8个data元素。