为什么我不是分支预测的受害者？

Question

我正在编写一个函数来创建高斯滤波器（使用犰狳库），它可以是 2D 或 3D，具体取决于它接收到的输入的维数。这是代码：

template <class ty>
ty gaussianFilter(const ty& input, double sigma)
{
    // Our filter will be initialized to the same size as our input.
    ty filter = ty(input); // Copy constructor.

    uword nRows = filter.n_rows;
    uword nCols = filter.n_cols;
    uword nSlic = filter.n_elem / (nRows*nCols); // If 2D, nSlic == 1.

    // Offsets with respect to the middle.
    double rowOffset = static_cast<double>(nRows/2);
    double colOffset = static_cast<double>(nCols/2);
    double sliceOffset = static_cast<double>(nSlic/2);

    // Counters.
    double x = 0 , y = 0, z = 0;

for (uword rowIndex = 0; rowIndex < nRows; rowIndex++) {
      x = static_cast<double>(rowIndex) - rowOffset;
      for (uword colIndex = 0; colIndex < nCols; colIndex++) {
        y = static_cast<double>(colIndex) - colOffset;
        for (uword sliIndex = 0; sliIndex < nSlic; sliIndex++) {
          z = static_cast<double>(sliIndex) - sliceOffset;
          // If-statement inside for-loop looks terribly inefficient
          // but the compiler should take care of this.
          if (nSlic == 1){ // If 2D, Gauss filter for 2D.
            filter(rowIndex*nCols + colIndex) = ...
          }
          else
          { // Gauss filter for 3D. 
            filter((rowIndex*nCols + colIndex)*nSlic + sliIndex) = ...
          }
       }    
     }
 }

我们看到，在最内层的循环中有一个if语句，它检查第三维（nSlic）的大小是否等于1。一旦在函数的开头计算，nSlic就不会改变它的价值，所以编译器应该足够聪明来优化条件分支，我不应该失去任何性能。

但是...如果我从循环中删除 if 语句，我将获得性能提升。

if (nSlic == 1)
  { // Gauss filter for 2D.
    for (uword rowIndex = 0; rowIndex < nRows; rowIndex++) {
      x = static_cast<double>(rowIndex) - rowOffset;
      for (uword colIndex = 0; colIndex < nCols; colIndex++) {
        y = static_cast<double>(colIndex) - colOffset;
        for (uword sliIndex = 0; sliIndex < nSlic; sliIndex++) {
          z = static_cast<double>(sliIndex) - sliceOffset;
          {filter(rowIndex*nCols + colIndex) = ...
        }
      } 
    }
  }
else
  {
    for (uword rowIndex = 0; rowIndex < nRows; rowIndex++) {
      x = static_cast<double>(rowIndex) - rowOffset;
      for (uword colIndex = 0; colIndex < nCols; colIndex++) {
        y = static_cast<double>(colIndex) - colOffset;
        for (uword sliIndex = 0; sliIndex < nSlic; sliIndex++) {
          z = static_cast<double>(sliIndex) - sliceOffset;
          {filter((rowIndex*nCols + colIndex)*nSlic + sliIndex) = ...                                     
        }
      } 
    }
  }

使用 g++ -O3 -c -o main.o main.cpp 编译并测量两种代码变体的执行时间后，我得到以下结果：
（1000 次重复，大小为 2048 的二维矩阵）

if-inside:

66.0453 秒
64.7701 秒

如果-在外面：

64.0148 秒
63.6808 秒

如果 nSlic 的值甚至没有改变，为什么编译器不优化分支？我必须重构代码以避免 for-loop?

中的 if-statement

Answer 1

你的错误在这里：

optimise the conditional branch, and I shouldn't lose any performance

与实际执行与未知分支相关的流水线停顿相比，分支预测可能对您有很大帮助。但它仍然是管道中的额外指令，仍然有成本。处理器魔法减少了无用代码的成本...大大减少但不为零。

Answer 2

循环中有一个额外的变量会影响寄存器的使用，这可能会影响时序，即使分支预测工作正常。您需要查看生成的程序集才能知道。它还可能影响难以检测的缓存命中率。

Answer 3

编译器和硬件之间的相互作用是这样的——编译器可能能够优化分支，使代码本身得到优化，但正如您所看到的，这会产生大量代码膨胀，因为它有效地复制了整个环形。一些编译器可能默认包含此优化，而其他编译器可能需要明确要求它询问你是否已完成。

或者，如果编译器避免了这种优化，代码会保留分支，而硬件则尽可能地预测它。这涉及复杂的分支预测器，它们具有有限的表，因此它们可以达到的学习量有限。在此示例中，您没有太多竞争分支（循环、函数调用和 returns，以及我们正在讨论的 if），但我们看不到被调用函数的内部工作，它可能有更多的分支指令（刷新你在外面学到的东西），或者它可能足够长以刷新预测器可能正在使用的任何全局历史。没有看到代码就很难说，也不知道你的分支预测器到底做了什么（这取决于你使用的 CPU 版本等）。

再注意一点-它可能不一定与分支预测有关，像这样更改代码可能会更改代码缓存中的对齐方式或一些用于优化循环的内部循环缓冲区（例如this），这可能会导致性能发生巨大变化。唯一知道的方法是运行基于硬件计数器（perf、vtune 等）的一些分析，并测量分支和错误预测数量的变化。

为什么我不是分支预测的受害者？

Why am I not a victim of branch prediction?

c++

compiler-optimization

branch-prediction