如何处理似乎取决于机器代码位置的分支错误预测？

Question

在尝试以 CSC 格式对简单稀疏单元下三角后向求解的实现进行基准测试时，我观察到奇怪的行为。性能似乎有很大差异，具体取决于汇编指令在可执行文件中的最终位置。我在同一问题的许多不同变体中观察到这一点。一个最小的例子是获取重复的实施指令

void lowerUnitTriangularTransposedBacksolve(const EntryIndex* col_begin_indices,
                                            const Index* row_indices,
                                            const Value* values,
                                            const Index dimension, Value* x) {
  if (dimension == 0) return;

  EntryIndex entry_index = col_begin_indices[dimension];
  Index col_index = dimension;
  do {
    col_index -= 1;
    const EntryIndex col_begin = col_begin_indices[col_index];

    if (entry_index > col_begin) {
      Value x_temp = x[col_index];
      do {
        entry_index -= 1;
        x_temp -= values[entry_index] * x[row_indices[entry_index]];
      } while (entry_index != col_begin);
      x[col_index] = x_temp;
    }
  } while (col_index != 0);
}

在两个函数中benchmarkBacksolve1和benchmarkBacksolve2（使用google/benchmark 的源代码）。两个相同功能（除了偏移之外）的性能差异也会显示在fast-bench.com上。这并非侥幸；始终比 慢 10% 。保持相同的执行顺序，但通过定义before交换可执行文件中机器代码的位置，也交换了性能差异。benchmarkBacksolve1benchmarkBacksolve2benchmarkBacksolve2benchmarkBacksolve1

在我的本地计算机（gcc 9.4.0、-O3AMD Ryzen 7 PRO 4750U）上，差异更加极端：

--------------------------------------------------------------
Benchmark                    Time             CPU   Iterations
--------------------------------------------------------------
benchmarkBacksolve1       1919 ns         1907 ns       364269
benchmarkBacksolve2        918 ns          908 ns       773814

首先定义的函数速度要慢两倍。仅运行其中一项功能的基准测试--benchmark_filter或使用--benchmark_enable_random_interleaving=truewith--benchmark_repetitions=n仅确认测量结果。

我在分析过程中发现的最显着的观察结果是分支未命中的巨大差异：

--------------------------------------------------------------
Benchmark                    Time             CPU   Iterations
--------------------------------------------------------------
benchmarkBacksolve1       1919 ns         1907 ns       364269
benchmarkBacksolve2        918 ns          908 ns       773814

几乎 8% 的分支似乎对最先定义的函数进行了错误预测，而对于最后定义的函数只有 0.2% 的预测错误。

---

在不同的机器上，我必须稍微修改设置才能看到这种效果。但其他实验证实了这在大多数机器上似乎是多么脆弱。偏移量的任何变化都可能完全改变基准测量结果。再举一个例子，__attribute__((always_inline))在我的机器上删除 会导致两个函数的时间相等，但它既不是比以前更快也不是更慢的时间，它是一个明显的新函数1250 ns。

---

通过对 Emery Berger的采访和演讲，我意识到链接顺序和环境变量等意外因素会影响性能。尽管如此，我还是想更好地理解这个例子。

• 为什么这段代码中的分支预测似乎受代码位置的影响如此之大？
• 我可以做些什么来避免这些偏差，以便能够正确评估不同的实现？观察这些影响后，我担心我在优化稀疏下三角线性系统的向后求解中的答案是测量任何东西而不是真正的性能改进
• 在实现过程中是否需要注意一些事项，以避免大多数现代 CPU 的分支预测器出现此类问题？

Answer 1

现代 CPU 具有分支预测器，可以通过记住过去的结果来学习分支的行为。但大多数代码在一个循环中都有多个分支，因此为了有机会工作，CPU 必须有多个分支预测器，并通过某种方式让不同的分支使用不同的预测器，以便它们可以分别学习每个分支的行为。

一种简单的方法是使用地址的最后几位或地址的简单散列来选择分支预测器。但是，按顺序排列代码可能会导致冲突，其中两个分支选择相同的预测器，而不同的顺序则使分支使用单独的预测器。而这显然可以改变每个分支的预测的成功率。

你应该做的一件事（至少在 gcc 中）是不要盲目使用-O3. -O3包括通常会损害性能或仍处于实验阶段的优化。只有在检查它确实有好处之后才可以选择性地使用它。为了判断它是否有好处，您必须对二进制文件进行大量模糊测试，测量代码、堆栈和数据的大量不同对齐方式以及代码的不同顺序。