Dim*_*nNe 153 c++ performance cpu-architecture clang branch-prediction
我发现了这个流行的大约 9 岁的SO 问题，并决定仔细检查其结果。
所以，我有 AMD Ryzen 9 5950X、clang++ 10 和 Linux，我从问题中复制粘贴了代码，这是我得到的：
排序 - 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
未分类 - 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
我很确定 unsorted 版本比 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
我认为这个问题仍然相关 - 几乎没有区别。
Nat*_*dge 156
您链接的问题中的几个答案谈到将代码重写为无分支，从而避免任何分支预测问题。这就是您更新的编译器正在做的事情。
具体来说，带有-O3 矢量化内部循环的clang++ 10 。 请参阅 Godbolt 上的代码，程序集的第 36-67 行。代码有点复杂，但是您绝对看不到的一件事是data[c] >= 128测试中的任何条件分支。相反，它使用向量比较指令 ( pcmpgtd)，其输出是一个掩码，其中 1 表示匹配元素，0 表示不匹配。pand带有此掩码的后续元素将不匹配的元素替换为 0，因此当它们无条件地添加到总和时，它们不会做出任何贡献。
粗略的 C++ 等价物是
sum += data[c] & -(data[c] >= 128);
代码实际上sum为数组的偶数和奇数元素保留了两个运行的 64 位，以便它们可以并行累加，然后在循环结束时相加。
一些额外的复杂性是将 32 位data元素符号扩展到 64 位；这就是序列喜欢pxor xmm5, xmm5 ; pcmpgtd xmm5, xmm4 ; punpckldq xmm4, xmm5完成的。打开-mavx2，你会看到一个更简单vpmovsxdq ymm5, xmm5的地方。
代码看起来也很长，因为循环已经展开，data每次迭代处理 8 个元素。