为什么无分支 Heapsort 比分支快 1.5 倍？

Question

我知道 CPU 分支预测错误的惩罚等，让代码无分支会更快地改进代码。

我试图理解为什么 [1] 中的补丁进行了以下更改，使代码速度提高了 1.5 倍？ （对比例如快 1.1 倍）

[1] https://github.com/rust-lang/rust/pull/107894/files

（PR 的作者在 Zen 3 上的速度提高了 1.5 倍，我在 Zen 3（Ryzen 3900x）上的速度稍微提高了）

- if child + 1 < v.len() && is_less(&v[child], &v[child + 1]) {
-     child += 1;
+ if child + 1 < v.len() {
+     child += is_less(&v[child], &v[child + 1]) as usize;
}

一些注意事项：

• 我看了汇编代码，

  child += 1

  里面的

  if

  被翻译成了简单的寄存器间移动。编译器生成的汇编代码在 2 个寄存器中维护 child & child+1。所以在

  if

  块内没有发生内存访问。
• PR 的作者（和我）使用了一个包含 10k 元素的数组，适合我的 CPU 的 L1 缓存。

我目前对这种剧烈加速的理解是：

1. 我用 AMD uProf 分析了代码：
   1. 运行branchless版本时，CPI约为0.45。运行带有分支版本的 CPI 约为 0.9.
   2. 在无分支版本中，误预测率为0.5%。在分支版本中，它大约是 10%（对于所有分支，不仅仅是我们优化的分支。但其他分支很容易预测）。
2. 在汇编代码中，整个循环是 24 条指令。因此，在 CPI=0.45 的情况下，完美预测应该需要大约 11-12 个周期。
3. 给定 1.1，并且假设我们有很多分支，并且对于其中大多数 cpu 的预测接近完美，我猜我们正在优化的分支有大约 25%-30%（或可能更多）的错误预测率。
4. 根据 Andrew Fog 的指南 [2]，Zen 3 的错误预测惩罚是 18 个周期。因此，对于 30% 的错误预测，这会为每个循环增加大约 6 个周期，这会使循环速度降低 33% (=6 / (12+6))。

[2] https://www.agner.org/optimize/microarchitecture.pdf

我的理解对吗？我错过了什么吗？有没有其他工具可以帮助我了解正在发生的事情的细节？