为什么计算排序数组的直方图较慢？

Question

考虑以下代码：https://godbolt.org/z/1331dbz8q

目标是对简单的直方图函数进行基准测试：

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

基准测试测量当输入是随机数据以及输入已排序时直方图调用期间所用的平均时间。

这是该程序在我的机器上的输出：

g++ test.cpp -std=c++20 -O3 -march=native -o test.out && ./test.out 1000000 512 100 17
N (number of elements) = 1000000.
K (histogram size) = 512.
T (number of samples) = 100.
R (random seed) = 17.
time per element (random) : 0.751250 ns.
time per element (sorted) : 2.032259 ns.

我在 4 核 Sandy Bridge Intel 处理器 i5-2320 上运行此实验。 为什么直方图算法在输入排序后会慢2倍以上？

Answer 1

重复存储/重新加载相同的元素会创建一个串行依赖链，该链太长，以至于乱序执行无法完全重叠。

如果值范围不太大，则大多数增量的随机顺序可能仍会命中缓存，并且仅受吞吐量限制，而不受存储转发延迟瓶颈的限制。

• 预测现代超标量处理器上的操作延迟需要考虑哪些因素以及如何手动计算它们？
• 每条汇编指令需要多少个CPU周期？
• https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introduction-to-dataflow-graphs/

一些现代 CPU（至少 Zen 2、Zen 4 和 Ice Lake）在某些情况下具有零延迟存储转发，其中可能包括使用相同值重新加载索引的情况。

• https://www.agner.org/forum/viewtopic.php?t=41#p71
• https://gist.github.com/travisdowns/bc9af3a0aaca5399824cf182f85b9e9c
• https://pvk.ca/Blog/2020/02/01/too-much-locality-for-store-forwarding/

---

请参阅在 SIMD 中对直方图进行矢量化的方法？，了解一个有帮助的技巧：使用多个计数数组，并在最后对它们求和。（该部分可以使用 SIMD，实际计数不能，除非您有 AVX- 512 用于分散/聚集，即使如此，将多个元素映射到同一向量中的同一存储桶也会更慢。）

在这种情况下，对于内存重命名可以实现零延迟存储转发的 CPU 来说，这不是必需的，除非是在每个时钟可以执行一次以上加载 + 内存目标增量的非常宽的 CPU 上。

---

如果您知道数据已排序，您可以对同一元素的运行进行计数并执行一次

+= count

，尽管这很容易导致分支错误预测，除非您执行类似

_mm_cmpeq_epi32(load(ptr), set1(*ptr))

之类的操作；

_mm_movemask_ps

对于几个向量，并检查

popcnt

是

< 8

元素，因此运行时间比总是以相同方式分支要短。 （实际比较可以在

mask < 0xff

上进行，但您需要添加 popcount。或者

31-std::countl_zero

或

std::countr_zero(mask+1)

，这样您就可以使用

tzcnt

/

bsf

。