c++ 比较是否意味着一个分支?

zzoitvuj  于 11个月前  发布在  其他
关注(0)|答案(4)|浏览(77)

我在阅读Wikibooks page on optimization,我遇到了这条线:
对于流水线处理器,比较比差异慢,因为它们意味着一个分支。
为什么比较意味着一个分支?例如:

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

字符串
这里面有分支吗?对我来说,用条件语句为if语句进行分支是有意义的,但我不明白为什么仅仅是比较就会导致分支。

g0czyy6m

g0czyy6m1#

  • 序言:现代的编译器能够以各种方式消除分支,因此,没有一个例子必然会在最终(汇编或机器)代码中产生分支。

那么,为什么逻辑基本上意味着分支?
代码

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;
}


这里显然有两个分支(第二个分支只有在第一个分支为true时才执行- * shortcircuit *),这可能会被分支预测器错误预测,从而导致管道的重新滚动。
Visual Studio 2013(优化为1)为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;
}


其仅包含单个分支但执行两个差异。
Visual Studio 2013的check_interval_diff生成的代码甚至不包含条件跳转。

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


(The这里的技巧是,根据进位标志,sbb所做的减法相差1,进位标志又被cmp指令设置为1或0。
实际上,您可以在这里看到三个差异(2x sub,1x sbb)。

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

参见Mysticals关于分支预测的答案。
您的代码int x = i<5;在逻辑上与

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


其再次包含分支(仅当i < 5时执行x = true)。

euoag5mw

euoag5mw2#

这只涉及一个分支:

unsigned(i – min_i) <= unsigned(max_i – min_i)

字符串
而这涉及两个:

min_i <= i && i <= max_i


当CPU遇到一个分支时,它会参考它的预测器,并遵循最有可能的路径。如果预测正确,那么这个分支在性能方面基本上是自由的。如果预测错误,CPU需要刷新流水线,从头开始。
这种优化是一把双刃剑--如果你的分支是高度可预测的,第一个分支实际上可能比第二个分支运行得更慢,这完全取决于你对数据的了解程度。

t1qtbnec

t1qtbnec3#

虽然这里给出的答案很好,但并不是所有的比较都被转换为分支指令(它们确实引入了数据依赖性,这也可能会降低性能)。
例如,下面的C代码

int main()
{
    volatile int i;
    int x = i<5;

    return x;
}

字符串
由gcc(x86-64,启用优化)编译为:

movl    -4(%rbp), %eax
    cmpl    $5, %eax
    setl    %al
    movzbl  %al, %eax


setl指令根据其前面的比较指令的结果设置AL的值。
当然,这是一个非常简单的示例--cmp/setl组合可能会引入一些依赖项,这些依赖项会阻止处理器并行执行它们,甚至可能会花费一些周期。
然而,在现代处理器上,并不是所有的比较都被转换成分支指令。

xsuvu9jc

xsuvu9jc4#

不管是谁写了那个页面,他都不能胜任程序员的工作。首先,比较 * 并不一定意味着一个分支;这取决于你对它们做了什么。这是否意味着分支取决于处理器和编译器。if通常需要一个分支,但即使这样,一个好的优化器有时可以避免它。whilefor通常需要一个分支,除非编译器可以展开循环,但是这个分支是高度可预测的,所以即使分支预测是一个问题,它也可能无关紧要。
更一般地说,如果你在编写代码时担心这个级别的任何事情,你就是在浪费时间,并且使维护变得更加困难。你唯一应该关心的是一旦你遇到性能问题,分析器显示这是你失去性能的地方。在这一点上,你可以尝试几种不同的编写代码的方法,以确定哪一个将导致更快的代码 * 为您的编译器和硬件的组合 *。(更改编译器或硬件,它可能不是同一个。)

相关问题