与不使用if的测试相比,if语句的效率如何？(C++)

Question

我需要一个程序来获取两个数字中较小的一个,我想知道是否使用标准"如果x小于y"

int a, b, low;
if (a < b) low = a;
else low = b;

或多或少效率高于此:

int a, b, low;
low = b + ((a - b) & ((a - b) >> 31));

(或者放在int delta = a - b顶部并随之重新放置实例的变化a - b).

我只是想知道哪一个更有效(或者如果差异太小而不相关),以及if-else语句与一般的替代方案的效率.

Answer 1

(免责声明:以下内容涉及非常低级别的优化,这些优化通常不是必需的.如果您继续阅读,您放弃了投诉计算机速度快的权利,并且没有任何理由担心这类事情.)

消除if语句的一个优点是可以避免分支预测惩罚.

当分支不容易预测时,分支预测罚分通常只是一个问题.当几乎总是采用/不采用分支时,容易预测分支,或者它遵循简单的模式.例如,循环语句中的分支每次都被取出,除了最后一个,因此很容易预测.但是,如果你有像这样的代码

a = random() % 10
if (a < 5)
  print "Less"
else
  print "Greater"

然后,这个分支不容易预测,并且经常会产生与清除缓存和回滚在分支的错误部分中执行的指令相关的预测损失.

避免这种惩罚的一种方法是使用ternary(?:)运算符.在简单的情况下,编译器将生成条件移动指令而不是分支.

所以

int a, b, low;
if (a < b) low = a;
else low = b;

变

int a, b, low;
low = (a < b) ? a : b

在第二种情况下,不需要分支指令.此外,它比您的比特笨重的实现更清晰,更易读.

当然,这是一种微优化,不太可能对您的代码产生重大影响.

Answer 2

简单的答案:一个条件跳转比两个减法,一个加法,一个按位和一个移位操作组合起来更有效. 我已经在这一点上受到了充分的教育(见评论),我甚至不再自信地说它通常更有效率.

务实的答案:无论哪种方式,你都没有为程序员弄清楚第二个例子正在做什么所花费的额外CPU周期.程序的可读性首先,效率第二.

Answer 3

在gcc 4.3.4,amd64(core 2 duo)上编译,Linux:

int foo1(int a, int b)
{
    int low;
    if (a < b) low = a;
    else low = b;
    return low;
}

int foo2(int a, int b)
{
    int low;
    low = b + ((a - b) & ((a - b) >> 31));
    return low;
}

我明白了:

foo1:
    cmpl    %edi, %esi
    cmovle  %esi, %edi
    movl    %edi, %eax
    ret

foo2:
    subl    %esi, %edi
    movl    %edi, %eax
    sarl    $31,  %eax
    andl    %edi, %eax
    addl    %esi, %eax
    ret

...我非常肯定不会计算分支预测,因为代码不会跳转.此外,非if语句版本更长2个指令.我想我会继续编码,让编译器做它的工作.

Answer 4

最大的问题是你的第二个例子不适用于64位机器.

然而,即使忽略了这一点,现代编译器也足够聪明,可以在每种情况下考虑无分支预测,并比较估计的速度.所以,你的第二个例子很可能实际上更慢

if语句和使用三元运算符之间没有区别,因为即使是大多数愚蠢的编译器都足够聪明,可以识别这种特殊情况.

[编辑]因为我认为这是一个非常有趣的话题,所以我写了一篇博文.

Answer 5

与任何低级优化一样,在目标CPU /板设置上进行测试.

在我的编译器(x86_64上的gcc 4.5.1)上,第一个例子变为

cmpl    %ebx, %eax
cmovle  %eax, %esi

第二个例子变成了

subl    %eax, %ebx
movl    %ebx, %edx
sarl    $31, %edx
andl    %ebx, %edx
leal    (%rdx,%rax), %esi

不确定第一个在所有情况下是否更快,但我敢打赌它是.