如果条件语句比乘法和赋值更快吗?

7

我有一个快速问题,假设我有以下代码,并且类似的方式重复了10次。

if blah then
    number = number + 2^n
end if

评估以下哪个更快:

number = number + blah*2^n?

这也带来了一个问题,您能否将布尔值乘以整数(虽然我不确定2^n返回的类型是整数还是无符号整数等)?(我在Ada语言中工作,但让我们尝试通用化这个问题?)
编辑:抱歉,我应该澄清一下,我正在看2的n次方,并且我在那里放置了c,因为我对未来学习中是否会遇到这个问题感兴趣,如果我遇到这个问题,我认为会有更多的c程序员在这些版面上(我猜想,您知道这意味着什么),然而,我的当前问题是在Ada语言中,但是这个问题应该是相当独立于编程语言的(我希望如此)。

4
在C语言中,符号^表示异或运算,记住这一点即可。 - chrisaycock
2
请注意,由于C语言没有内置的布尔类型,因此不能保证blah等于1或0。一些返回true或false的函数可能会选择在true的位置返回其他值而不是1。 - Brian
1
@Brian 谢谢,我没意识到 boolean 不总是表示 0 和 1,不然这可能会成为一个艰难的教训。 - onaclov2000
1
@Marc C - 这很棒。我只是手动检查一下。他说得对,这确实是一个与语言无关的问题。Ada添加的唯一变化是它的编译器具有更多信息,可以允许更好的优化工作。因此,对于C来说是正确的(不要像这样进行微观优化),对于Ada来说更加正确。 - T.E.D.
@R..: 你说得对,C99引入了显式的布尔类型。不过我仍然会小心谨慎。我之前就曾经遇到过这个问题,在不同编程语言之间交互时尤其如此。 - Brian
显示剩余4条评论
10个回答

10

没有一般性的答案,这取决于您的编译器和CPU。现代CPU具有条件移动指令,因此任何操作都是可能的。

唯一的方法是检查产生的汇编代码(通常使用-S编译器选项)和进行测量。


8
如果我们在讨论C语言且blah不受你的控制,那么可以这样做:
if(blah) number += (1<<n);
在C语言中并没有布尔类型,也不需要,false是0,true不是0,所以不能假设非零就是1,这正是你需要的解决方案,也不能假设blah的任何特定位被设置了,例如:
number += (blah&1)<<n;
这也不一定起作用,因为任何非零值中清除了第零位的都被视为真。通常情况下,你会发现使用0xFFF...FFFF(减1或全1)表示真,但是你不能依赖于典型情况。 现在,如果你完全控制blah的值,并且将其严格保持为0表示false,1表示true,那么你可以做你想要的事情:
number += blah<<n;
并避免分支、额外的高速缓存行填充等潜在问题。 回到通用情况,采用以下通用解决方案:
unsigned int fun ( int blah, unsigned int n, unsigned int number )
{
    if(blah) number += (1<<n);
    return(number);
}
并编译为两个最流行/使用的平台:
    testl   %edi, %edi
    movl    %edx, %eax
    je  .L2
    movl    $1, %edx
    movl    %esi, %ecx
    sall    %cl, %edx
    addl    %edx, %eax
.L2:
以上使用了条件分支。 下面的代码使用条件执行,没有分支,没有流水线刷新,是确定性的:
  cmp   r0,#0
  movne r3,#1
  addne r2,r2,r3,asl r1
  mov   r0,r2
  bx    lr
通过重新排列函数调用中的参数,可以节省mov r0,r2指令,但这是学术问题,在正常情况下不会在此上浪费函数调用。 编辑: 如建议所述:
unsigned int fun ( int blah, unsigned int n, unsigned int number )
{
    number += ((blah!=0)&1)<<n;
    return(number);
}
  subs  r0, r0, #0
  movne r0, #1
  add   r0, r2, r0, asl r1
  bx    lr
当然更便宜,代码看起来也不错,但我不会假设blah!= 0的结果总是具有lsbit设置为零或编译器定义为真。编译器不必为生成工作代码而设置该位。也许标准规定了true的具体值。通过重新排列函数参数,if(blah)number + = ...也将导致三个单时钟指令,而不做出任何假设。
编辑2:
查看我所理解的C99标准:
“==(等于)和!=(不等于)运算符类似于关系运算符,除了它们的优先级较低。每个运算符如果指定的关系为真则产生1,如果为假则产生0。”
这解释了为什么上面的编辑有效,并且为什么你得到movne r0,#1而不是其他随机数。
发帖者提出了关于C的问题,但还指出ADA是当前语言,从独立于语言的角度来看,您不应该假设像C特性一样的“功能”,而是使用if(blah)number = number +(1 << n)。但是,这是在C标记下询问的,因此C的通用(与处理器无关)最快结果是我认为,number + =(blah!= 0)<< n;因此,Steven Wright的评论是正确的,他应该得到这个荣誉。
发帖者的假设基本上是正确的,如果您可以将blah转换为0或1形式,则在数学中使用它比分支更快。让它进入该形式而不比分支更昂贵是诀窍。

2
number += ((blah!=0)&1)<<n; 这个怎么样? - Simon Wright
blah!=0 的结果是不确定的,可能是0表示假,也可能是1表示真。 - old_timer
阅读类似SO问题的答案,标准可能要求中间比较返回1或0,如果确实如此并且编译器在所有地方都符合该标准,则只需执行number += (blah!=0)<<n;我仍在等待一个好的标准出台和一个真正满足任何标准的编译器,所以我宁愿保险起见。 (blah!=0)<<n; 在ARM上应该有三个指令,因此对于该架构与 if(blah) number += 1<<n; 相比速度不会更快。在x86上应该会快得多。 - old_timer
谢谢,记得给Simon的贡献点个赞。并且要回报社区(帮助其他StackOverflow用户)。 - old_timer

5
在Ada中...
原始表述:

原始表述:

if Blah then
  Number := Number + (2 ** N);
end if;

另一种常见的表达方式,假设Blah是布尔类型和数字类型,N是适当类型:

Number := Number + (Boolean'pos(Blah) * (2 ** N));
< p>(对于用户自定义的整数或浮点类型NNumber,可能需要适当的定义和类型转换,关键点在于 Boolean'pos()构造,Ada保证为预定义的布尔类型提供0或1。)

至于这是否更快,我同意@Cthutu的看法:

我会使用条件语句。 您不应该担心低级优化细节。 编写最能描述您算法的代码并信任您的编译器。


很好的点子,我没有想到。如果blah是一个可预测的值,我可以理解你和Cthutu所说的编译器部分,但由于这是从硬件设备传入的离散值,我不确定编译器如何进一步优化它,你(或Cthutu)能否详细说明一下? - onaclov2000
Ada是否真的保证布尔类型的值为0和1?LRM中唯一对此的评论是False < True。然而,我期望大多数(全部?)编译器都是这样的。当然,偏执者可以定义自己的派生布尔类型表示,以保证0和1是其值 :) - Schedler
是的,对于预定义的布尔值,这是有保证的。这是因为“Pos属性”的定义,它返回枚举的位置编号,即Boolean'Pos(False)为0,Boolean'Pos(True)为1。即使底层表示为0和非0,'Pos属性仍将保持不变(要获取实际表示,您必须使用Unchecked_Conversion实例化来获取它)。 - Marc C
1
如果编译器生成布尔值,它肯定会具有相应的“Pos行为”。然而,如果您使用某种形式的未经检查的转换(例如从C中导入)生成“布尔”值,则可能无效,并且大多数押注都无效。例如,对于GCC Ada编译器,在某些情况下,42可以看作是假的(因为其LSB清除),在其他情况下是真的,或者导致Constraint_Error。与往常一样,如果您从外部环境导入,请在接口处进行验证。 - Simon Wright
Simon:感谢你的输入。现在重新阅读 LRM,这很清楚了。我混淆了“Pos”和内部表示的概念。这是一个有用的新信息。 - Schedler

4

我建议仍然使用条件语句。你现在不需要担心低级别的优化细节,写出最能描述算法的代码,并相信编译器的能力。在某些CPU上,乘法的速度会很慢(例如ARM处理器,在每个指令上都有一个条件)。你也可以使用?:表达式,这在一些编译器下进行优化效果更好。例如:

number += (blah ? 2^n : 0);

如果由于某些原因,在分析之后发现这个小计算是应用程序的瓶颈,请考虑进行低级别优化。


在进行嵌入式系统的代码审查时,我通常从这样的角度来看待书面代码:是否可以通过一些小调整使其更快。我不打算进行任何大规模的重写或花费数周时间来微调细节,只是希望能够发现一些明显的小问题,但也许编译器会处理这些问题。虽然我认为它无法优化掉这些问题,因为在这种情况下布尔值中的数据是离散的,所以直到运行时才知道。 - onaclov2000
我强烈建议,如果您的逻辑在条件为真时被触发,那么最好坚持使用布尔检查,而不是使用整数/浮点数并将其乘以。这样,在6个月后回到代码时,对您来说会更加明显。 - Cthutu
非常小心地进行优化调整。你可能会让代码更难读懂,更糟糕的是使其变得更慢。在优化方面,直觉并不总是你最好的朋友。 - Cthutu
根据运行此代码的函数相关注释,我会惊讶地发现无法轻松阅读代码,但我确实理解你的观点。我想一个快速的方法来确定这是更快还是更慢(即使有编译器设置),就是运行类似的“函数”多次并进行大量时间测量,这应该可以告诉我在我们特定的系统上它是更快还是更慢。 - onaclov2000
我试图解释,你不应该在那个层面上担心优化问题,而是描述一种通用的方法,而不是针对示例代码的任何具体内容。经常对你的代码进行分析,并将其作为指导,确定你应该集中优化的方向,如果你的应用需要的话。 - Cthutu

4

关于在C语言中的blah*2^n:你有没有理由相信blah只有取0和1两个值?该语言只承诺0和TRUE等价,而其他所有值则等价于TRUE。C允许你将“布尔”临时变量乘以另一个数字,但结果未定义,除非result=0等价于bool为false或数字为零。

在Ada语言中,关于blah*2^n: 该语言没有在布尔类型上定义乘法运算符。因此,blah不能是布尔类型并进行乘法操作。


我和一位同事交谈时,他提到布尔值不能与数字相乘。这很有道理,但我不确定这是否只是Ada的限制,还是大多数编程语言都不允许这样做。 - onaclov2000
Eric:这个答案是误导性的。在C语言中,逻辑/比较运算符的结果始终为0或1。这在标准中已经定义明确。你可以在条件语句中使用其他非零值,但这与你暗示的“true”随机取非零值是完全不同的。 - R.. GitHub STOP HELPING ICE
@R..:嗯...现在你让我想起来了,在哪个环境中我曾经惊讶地发现true(可见)被实现为-1。我记得这个“双关语”,即!true==false和~true==false。 - Eric Towers

1

对于所述问题,C语言中确实有简单的表达式可以产生高效的代码。

n个2的幂可以使用<<运算符计算,如1 << n,只要n小于一个int中的值位数。

如果blah是一个布尔值,即一个值为01int,你的代码片段可以这样写:

number += blah << n;

如果blah是可以测试其真值的任何标量类型,如if (blah),则表达式稍微复杂一些:
number += !!blah << n;

这相当于number += (blah != 0) << n;。测试仍然存在,但对于现代架构,生成的代码将不会有任何跳转,可以使用 Godbolt的编译器浏览器在线验证。

很高兴你决定回答这个问题。我之前也差点给出了同样的答案,但那时候这个问题已经很老了。不过不知怎么的,它仍然保持着活跃状态,所以应该会有一个最优解答案。 - technosaurus

1
如果你的编程语言允许布尔值和数字做乘法,那么是比条件语句更快的。条件语句需要分支,这可能会使 CPU 的流水线无效。而且如果分支够大,甚至会导致指令缓存未命中,不过在你的小例子中这种情况不太可能发生。

有趣,我正在思考整个分支的事情。我忘记了流水线(真丢脸,我们在学校已经反复讲解过了,我应该知道得更好)。 - onaclov2000

1
通常情况下,特别是在使用Ada编程时,您不应该担心微观优化问题。编写清晰易懂的代码,只有当您遇到性能问题并将其追踪到代码的某个部分时,才需要关注性能。
不同的CPU有不同的需求,它们可能非常复杂。例如,在这种情况下,哪种方法更快取决于您的CPU的流水线设置、当前缓存中的内容以及分支预测单元的工作方式。编译器的一部分工作就是成为这些方面的专家,并且它会比所有除了最好的汇编程序员之外的人做得更好。肯定比您(或我)做得更好。
因此,您只需要关注编写良好的代码,让编译器负责将其转换为高效的机器码即可。

0

这段代码显示它们的表现相似,但乘法通常略快。

@Test
public void manual_time_trial()
{
    Date beforeIfElse = new Date();
    if_else_test();
    Date afterIfElse = new Date();
    long ifElseDifference = afterIfElse.getTime() - beforeIfElse.getTime();
    System.out.println("If-Else Diff: " + ifElseDifference);

    Date beforeMultiplication = new Date();
    multiplication_test();
    Date afterMultiplication = new Date();
    long multiplicationDifference = afterMultiplication.getTime() - beforeMultiplication.getTime();
    System.out.println("Mult Diff   : " + multiplicationDifference);

}

private static long loopFor = 100000000000L;
private static short x = 200;
private static short y = 195;
private static int z;

private static void if_else_test()
{
    short diff = (short) (y - x);
    for(long i = 0; i < loopFor; i++)
    {
        if (diff < 0)
        {
            z = -diff;
        }
        else
        {
            z = diff;
        }
    }
}

private static void multiplication_test()
{
    for(long i = 0; i < loopFor; i++)
    {
        short diff = (short) (y - x);
        z = diff * diff;
    }
}

0
无论哪种情况,你都无法避免一个分支(在内部),所以不要试图这样做!

number = number + blah*2^n

完整的表达式始终需要进行评估,除非编译器足够聪明以在blah为0时停止。如果是这样,您将会得到一个分支,如果blah为0。如果不是,则总是会得到一个昂贵的乘法。如果blah为false,则还会得到不必要的加法和赋值。

在“if then”语句中,当blah为true时,该语句只会执行加法和赋值。

简而言之,在这种情况下,您的问题的答案是“是”。


1
为什么大家都没有意识到这个乘法并不昂贵,而且几乎是免费的?(提示:它是2的幂。) - R.. GitHub STOP HELPING ICE
仅仅因为它是2的幂次方,并不意味着比根本不这样做更快。 - kes
你可以根据架构避免分支。但是,除非blah已知不仅是一个通用布尔值而且具体为1或0,否则无法避免某种条件执行。 - old_timer

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接