为何排序数组的直方图计算速度比随机数组慢2倍以上？

测试代码与结果 #

测试的直方图核心函数：

[[gnu::noinline]] static void histogram(int const *a, int n, int *h) {
  for (int i = 0; i < n; ++i)
    h[a[i]]++;
}

在Intel Sandy Bridge i5-2320处理器上的测试输出：

g++ test.cpp -std=c++20 -O3 -march=native -o test.out && ./test.out 1000000 512 100 17
N (元素数量) = 1000000.
K (直方图大小) = 512.
T (样本数量) = 100.
R (随机种子) = 17.
每元素耗时（随机）: 0.751250 ns.
每元素耗时（排序）: 2.032259 ns.

核心原因分析 #

这种性能差距完全由CPU硬件的缓存行为和指令并行特性决定，结合Sandy Bridge的架构特性，具体拆解如下：

1. 串行依赖链限制了指令并行

h[a[i]]++本质是读-改-写操作：先加载h[a[i]]的值，加1，再写回原地址。

• 随机数组场景：每次修改的是h中不同的位置，操作之间无数据依赖关系，CPU的超标量流水线可以同时调度多个独立的读-改-写操作，充分利用并行计算能力。
• 排序数组场景：连续多次修改同一个h[x]，每一次递增都依赖前一次的计算结果，CPU只能串行执行这些操作，完全无法发挥超标量架构的优势。

2. 写合并缓冲区无法生效

Sandy Bridge处理器的写合并缓冲区可以将多个分散的小写操作合并为单次总线事务，大幅减少内存访问开销：

• 随机场景下，写入操作分散在不同缓存行，写合并缓冲区能批量处理这些操作，降低总线事务次数。
• 排序场景下，连续写入同一个缓存行的同一位置，写合并完全失效——因为每次写操作都依赖前一次的结果，必须等待前一次读-改-写完成才能执行下一次，无法批量合并，每个操作都要经历完整的缓存读写周期。

3. 缓存行独占性的串行开销

h数组仅2048字节，完全能放进L1d缓存（Sandy Bridge的L1d缓存为32KB），所以缓存命中率不是问题。但排序场景中：

• 连续修改同一缓存行时，CPU需要持续持有该缓存行的独占（Modified）状态，串行执行读-改-写操作；而随机场景下，多个缓存行的修改可以并行进行，充分利用缓存带宽。

简单总结：随机数组的直方图计算能充分利用CPU的并行优化和写合并特性，而排序数组的连续同位置修改形成了串行依赖链，完全浪费了这些硬件优势，最终导致性能差距超过2倍。

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