c++ - 比较是否意味着分支？

Question

我正在阅读有关优化的维基百科页面: http://en.wikibooks.org/wiki/Optimizing_C%2B%2B/Code_optimization/Pipeline 我遇到了这条线:

For pipelined processors, comparisons are slower than differences, because they imply a branch.

为什么比较意味着分支？ 例如如果:

int i = 2;
int x = i<5;

这里面有分支吗？对带有条件的 if 语句进行分支对我来说很有意义，但我不明白为什么单独比较会导致分支。

Answer 1

序言:现代编译器能够以各种方式消除分支。因此，所有示例都不一定会在最终(汇编程序或机器)代码中产生分支。

那么为什么逻辑基本上暗示分支？

代码

bool check_interval_branch(int const i, int const min_i, int const max_i)
{
  return min_i <= i && i <= max_i;
} 

逻辑上可以重写为:

bool check_interval_branch(int const i, int const min_i, int const max_i)
{
  if (min_i <= i) 
  { 
    if (i < max_i) return true; 
  }
  return false;
} 

这里你显然有两个分支(其中第二个只有在第一个为真时才执行 - 短路)这可能会被分支预测器错误预测，从而导致重新滚动管道。

Visual Studio 2013(经过优化)生成以下程序集，其中包含 check_interval_branch 的两个分支:

  push  ebp
  mov   ebp, esp
  mov   eax, DWORD PTR _i$[ebp]
  cmp   DWORD PTR _min_i$[ebp], eax    // comparison
  jg    SHORT $LN3@check_inte          // conditional jump
  cmp   eax, DWORD PTR _max_i$[ebp]    // comparison
  jg    SHORT $LN3@check_inte          // conditional jump
  mov   al, 1
  pop   ebp
  ret   0
$LN3@check_inte:
  xor   al, al
  pop   ebp
  ret   0

代码

bool check_interval_diff(int const i, int const min_i, int const max_i)
{
  return unsigned(i - min_i) <= unsigned(max_i - min_i);
}

在逻辑上等同于

bool check_interval_diff(int const i, int const min_i, int const max_i)
{
  if (unsigned(i – min_i) <= unsigned(max_i – min_i)) { return true; }
  return false;
}

它只包含一个分支但执行两个差异。

check_interval_diff 的生成代码Visual Studio 2013 甚至不包含条件跳转。

  push  ebp
  mov   ebp, esp
  mov   edx, DWORD PTR _i$[ebp]
  mov   eax, DWORD PTR _max_i$[ebp]
  sub   eax, DWORD PTR _min_i$[ebp]
  sub   edx, DWORD PTR _min_i$[ebp]
  cmp   eax, edx                    // comparison
  sbb   eax, eax
  inc   eax
  pop   ebp
  ret   0

(这里的技巧是，根据进位标志，sbb 完成的减法相差 1，进位标志又被 cmp 指令设置为 1 或 0。)

事实上，您在这里看到了三个差异(2x sub，1x sbb)。

这可能取决于您的数据/用例，哪个更快。

参见 Mysticals answer here关于分支预测。

您的代码 int x = i<5;在逻辑上等同于

int x = false;
if (i < 5)
{
  x = true;
}

它再次包含一个分支( x = true 仅在 i < 5 时执行。)