现代x86-64 clang环境下，为何有序与无序数组处理性能基本无差异？

本次测试参考Stack Overflow上一道存在近9年的经典技术问题——「为何处理有序数组比无序数组速度更快」的实验逻辑，在当前软硬件环境下复现原测试流程，验证传统性能结论在现代平台的适用性。

测试环境 #

• 硬件：AMD Ryzen 9 5950X 处理器
• 软件：clang++ 10 编译器、Linux 操作系统
• 编译配置：直接采用原问题提供的示例测试代码，以 -O3 优化等级编译运行

基础规模首轮测试 #

首轮测试参数设置为：数组规模32768，外层循环累计遍历10万次，对满足data[c] >= 128分支条件的元素做累加统计耗时，对比开启预排序、关闭预排序两个版本的运行表现：

• 开启std::sort对数组预排序的版本：总耗时0.549702s，最终累加和为314931600000，对应运行输出：

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

• 注释掉std::sort、直接处理未排序数组的版本：总耗时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
  

为消除随机波动干扰，对两个版本多次重复运行的耗时统计如下：

未排序版本：0.543557 0.551147 0.541722 0.555599
已排序版本：0.542587 0.559719 0.53938  0.557909

从统计结果可见，未排序版本与排序版本的耗时差仅3ms，属于随机测试噪声范围，并未复现原问题中“无序数组处理速度比有序数组慢一个数量级”的经典结论。

本次测试使用的核心源码如下：

#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个元素后重新运行对比测试，结果如下：

未排序版本
cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    // std::sort(data, data + arraySize);
10.3814

已排序版本：
cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    std::sort(data, data + arraySize);
10.6885

测试结果显示，两种处理方式的耗时依然无显著差异，排序版本甚至略慢于未排序版本。

待解释的核心问题 #

基于以上实测结果，需要厘清的核心技术问题为：现代CPU架构发生了哪些演进，使得原问题中因分支预测失效带来的数组处理性能差异基本消失？

内容的提问来源于stack exchange，提问作者DimanNe