为什么处理未排序数组的速度与处理排序数组的速度相同？

Question

我发现了这个流行的9岁左右的问题，并决定重新检查它的结果。

所以，我有AMD Ryzen 9 595 0x、Clang++10和Linux，我从问题中复制粘贴了代码，下面是我得到的：

分类-0.549702秒：

~/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

我很确定的事实是，未经排序的版本被证明是快了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

可能是在对数据进行排序之后，它们（其中一些）仍然在缓存中，因此在下面的代码中可以更快地访问它们。

Answer 2

您链接的问题中的几个答案谈到将代码改写为无分支，从而避免任何分支预测问题。这就是您更新的编译器正在做的事情。

具体地说，clang++10和-o3对内部循环进行矢量化。请参阅godbolt上的代码，程序集的第36-67行。代码有点复杂，但有一点您绝对看不到，那就是data[c]>=128测试上的任何条件分支。相反，它使用向量比较指令(pcmpgtd)，其输出是一个掩码，其中1表示匹配元素，0表示不匹配元素。带有此掩码的后续pand将不匹配的元素替换为0，这样它们在无条件添加到和中时就不会贡献任何东西。

C++的大致等价物是

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

代码实际上保留了两个运行的64位sums，用于数组的偶数和奇数元素，这样它们就可以并行累加，然后在循环结束时相加在一起。

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

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