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

Question

我发现了这个受欢迎的 ~9 岁 SO question 并决定仔细检查它的结果。

所以，我有 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

我很确定未排序的版本快了 3 毫秒这一事实只是噪音，但它似乎不再慢了。

那么，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

您 link 问题中的几个答案谈到重写代码以使其无分支，从而避免任何分支预测问题。这就是您更新后的编译器正在做的事情。

具体来说，clang++ 10 与 -O3 vectorizes the inner loop. See the code on godbolt，程序集的第 36-67 行。代码有点复杂，但您绝对看不到的一件事是 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。

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

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

Why is processing an unsorted array the same speed as processing a sorted array with modern x86-64 clang?

c++

performance

cpu-architecture

clang

branch-prediction