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

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）。然后，两个相同函数（偏移量除外）的性能差异也显示在 quick-bench.com 上。这不是侥幸;benchmarkBacksolve1 始终比 benchmarkBacksolve2 慢 10%。保持相同的执行顺序，但通过在 benchmarkBacksolve1 之前定义 benchmarkBacksolve2 来交换机器代码在可执行文件中的位置，也会交换性能差异。

在我的本地机器（gcc 9.4.0，-O3， AMD Ryzen 7 PRO 4750U）上，差异更加极端：

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

首先定义的函数会慢一倍。使用< code> - benchmark_filter或使用< code >-benchmark _ enable _ random _ interleaving = true 和< code >-benchmark _ replications = n 只对其中一个函数运行基准测试只会确认测量结果。

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

$ perf stat ./a.out --benchmark_filter=benchmarkBacksolve1
                        ...
     1.231.964.948      branches                  #    1,354 G/sec                    (83,31%)
        97.548.817      branch-misses             #    7,92% of all branches          (83,22%)
                        ...
$ perf stat ./a.out --benchmark_filter=benchmarkBacksolve2
                        ...
     2.241.666.453      branches                  #    2,779 G/sec                    (83,64%)
         3.751.915      branch-misses             #    0,17% of all branches          (83,41%)
                        ...

对于第一个定义的函数，几乎8%的分支似乎被错误预测，而对于最后定义的函数，只有0.2%。

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

通过Emery Berger的采访和谈话，我意识到链接排序和环境变量等意外因素会影响性能。不过，我还是想更好地理解这个例子。

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

Answer 1

现代CPU有分支预测器，它通过记忆过去的结果来学习分支的行为。但是大多数代码在一个循环中有不止一个分支，所以为了有机会工作，CPU必须有多个分支预测器，并且有一些方法使不同的分支使用不同的预测器，这样它们可以分别学习每个分支的行为。

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

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