算术运算与布尔运算

Question

我在某个论坛上偶然发现了这段代码：

if ( a * b * c * d == 0 ) ....

车主声称这比

if (a == 0 || b == 0 || c == 0 || d == 0)

这些变量的定义如下：

int a, b, c, d;

并且保证它们的绝对值小于或等于100。(所以我们可以忽略溢出的可能性)

如果我们忽略readability，只关注性能，那么这种说法真的是正确的吗？

在我看来，第二种方法实际上可能更快，因为你有时可以利用“短路”的优势。但是，我知道什么？！

Answer 1

C标准并没有提到性能。这个问题是

if ( a * b * c * d == 0 )

的速度比

if (a == 0 || b == 0 || c == 0 || d == 0)

只有在特定编译器生成在特定计算机上运行的代码的上下文中才有意义。比较它们的唯一真正方法是在您自己的系统上或在您感兴趣的任何系统上测量性能。

尽管如此，我们仍然可以推测性能可能是什么。

正如您所说的，a、b、c和d都是int类型的对象。您还说它们在-100，+100的范围内，但是编译器不一定知道这一点。

编译器可以自由地将任何表达式替换为执行相同操作的代码。

乘法是一种相对复杂的操作，可能比加法或比较慢。编译器可以识别出，如果四个变量中的任何一个变量的值为0，则第一个条件将为真，并将乘法替换为恰好更快的乘法。但是编译器执行的每个优化都必须由编译器的开发人员显式编程，而且这种特定的模式不太可能足够常见，因此不值得花时间去识别它。

您说这些值足够小，所以溢出不是问题。事实上，您不能轻而易举地做出这种假设；INT_MAX可以像32767一样小。但是编译器知道它为其生成代码的系统上的int有多大。但是，除非它有关于a、b、c和d的值的信息，否则它不能假定没有溢出。

除了，是的，实际上，它可以做出这样的假设。带符号整数溢出的行为未定义。这使得优化编译器可以假定不会发生溢出(如果溢出发生了，程序表现出的任何行为都是有效的)。

所以，是的，编译器可以用更简单的东西替换乘法，但它不太可能这样做。

对于另一个表达式a == 0 || b == 0 || c == 0 || d == 0，||操作符具有短路语义；如果左操作数为真(非零)，则不计算右操作数。由于CPU管道问题，这种条件代码可能会产生性能问题。由于子表达式都没有副作用(假设没有一个变量被声明为volatile)，编译器可以并行地计算所有四个子表达式，如果这样更快的话。

快速实验表明，用于x86的gcc -O3不会执行这两种优化。对于第一个表达式，它生成执行三次乘法的代码。对于第二个，它生成条件分支，实现规范的短路评估(我不知道避免这样做是否会更快)。

最好的办法是编写尽可能简单的合理代码，这既是因为它使源代码更易于阅读和维护，也是因为它可能给编译器更好的机会来识别模式和执行优化。如果您试图在源代码中进行花哨的微优化，那么您很可能会阻碍编译器的优化，因为您可能会提供帮助。

不要过于担心你的代码有多快，除非你测量过它并发现它太慢了。如果你需要你的代码更快，首先专注于改进的算法和数据结构。只有在失败的情况下，才能考虑源码级别的微优化。

程序优化的第一条规则:不要这样做。程序优化的第二条规则(仅限专家！)：先别这么做。

-- Michael A. Jackson

Answer 2

这两者是不等价的。例如，在我的机器(32位x86 MSVC)上，如果a、b、c和d都等于0x100，则第一个测试将通过，但第二个条件不会通过。

还要注意，乘法是一种代价高昂的操作，因此第一个版本不一定会更快。

编辑:为第一个版本生成的代码：

00401000 8B 44 24 04      mov         eax,dword ptr [esp+4] 
00401004 0F AF 44 24 08   imul        eax,dword ptr [esp+8] 
00401009 0F AF 44 24 0C   imul        eax,dword ptr [esp+0Ch] 
0040100E 0F AF 44 24 10   imul        eax,dword ptr [esp+10h] 
00401013 85 C0            test        eax,eax 
00401015 75 07            jne         f1+1Eh (40101Eh) 
00401017 ...

为第二个版本生成的代码：

00401020 83 7C 24 04 00   cmp         dword ptr [esp+4],0 
00401025 74 15            je          f2+1Ch (40103Ch) 
00401027 83 7C 24 08 00   cmp         dword ptr [esp+8],0 
0040102C 74 0E            je          f2+1Ch (40103Ch) 
0040102E 83 7C 24 0C 00   cmp         dword ptr [esp+0Ch],0 
00401033 74 07            je          f2+1Ch (40103Ch) 
00401035 83 7C 24 10 00   cmp         dword ptr [esp+10h],0 
0040103A 75 07            jne         f2+23h (401043h) 
0040103C ...

在我的机器上进行基准测试(以纳秒为单位)：第一个版本运行时间约为1.83 ns，第二个版本运行时间约为1.39 ns。a，b，c和d的值在每次运行期间都没有变化，所以显然分支预测器可以预测100%的分支。

Answer 3

因此，像往常一样，更快的问题是，到目前为止，你尝试了什么？你有没有编译和反汇编，看看会发生什么？

unsigned int mfun ( unsigned int a, unsigned int b, unsigned int c, unsigned int d )
{
    if ( a * b * c * d == 0 ) return(7);
    else return(11);
}

unsigned int ofun ( unsigned int a, unsigned int b, unsigned int c, unsigned int d )
{
    if (a == 0 || b == 0 || c == 0 || d == 0) return(7);
    else return(11);
}

对于arm，one编译器给出了这一点

00000000 <mfun>:
   0:   e0010190    mul r1, r0, r1
   4:   e0020291    mul r2, r1, r2
   8:   e0110293    muls    r1, r3, r2
   c:   13a0000b    movne   r0, #11
  10:   03a00007    moveq   r0, #7
  14:   e12fff1e    bx  lr

00000018 <ofun>:
  18:   e3500000    cmp r0, #0
  1c:   13510000    cmpne   r1, #0
  20:   0a000004    beq 38 <ofun+0x20>
  24:   e3520000    cmp r2, #0
  28:   13530000    cmpne   r3, #0
  2c:   13a0000b    movne   r0, #11
  30:   03a00007    moveq   r0, #7
  34:   e12fff1e    bx  lr
  38:   e3a00007    mov r0, #7
  3c:   e12fff1e    bx  lr

因此，等于和或有短路(这本身是昂贵的)，但最坏的路径需要更长的时间，所以性能是不稳定的，乘法性能更确定，更少不稳定。通过检查，上述代码的乘法解决方案应该更快。

mips给了我这个

00000000 <mfun>:
   0:   00a40018    mult    a1,a0
   4:   00002012    mflo    a0
    ...
  10:   00860018    mult    a0,a2
  14:   00002012    mflo    a0
    ...
  20:   00870018    mult    a0,a3
  24:   00002012    mflo    a0
  28:   10800003    beqz    a0,38 <mfun+0x38>
  2c:   00000000    nop
  30:   03e00008    jr  ra
  34:   2402000b    li  v0,11
  38:   03e00008    jr  ra
  3c:   24020007    li  v0,7

00000040 <ofun>:
  40:   10800009    beqz    a0,68 <ofun+0x28>
  44:   00000000    nop
  48:   10a00007    beqz    a1,68 <ofun+0x28>
  4c:   00000000    nop
  50:   10c00005    beqz    a2,68 <ofun+0x28>
  54:   00000000    nop
  58:   10e00003    beqz    a3,68 <ofun+0x28>
  5c:   00000000    nop
  60:   03e00008    jr  ra
  64:   2402000b    li  v0,11
  68:   03e00008    jr  ra
  6c:   24020007    li  v0,7

除非分支开销太大，否则equals和or看起来更快。

Openrisc 32

00000000 <mfun>:
   0:   e0 64 1b 06     l.mul r3,r4,r3
   4:   e0 a3 2b 06     l.mul r5,r3,r5
   8:   e0 c5 33 06     l.mul r6,r5,r6
   c:   bc 26 00 00     l.sfnei r6,0x0
  10:   0c 00 00 04     l.bnf 20 <mfun+0x20>
  14:   9d 60 00 0b     l.addi r11,r0,0xb
  18:   44 00 48 00     l.jr r9
  1c:   15 00 00 00     l.nop 0x0
  20:   44 00 48 00     l.jr r9
  24:   9d 60 00 07     l.addi r11,r0,0x7

00000028 <ofun>:
  28:   e0 e0 20 02     l.sub r7,r0,r4
  2c:   e0 87 20 04     l.or r4,r7,r4
  30:   bd 64 00 00     l.sfgesi r4,0x0
  34:   10 00 00 10     l.bf 74 <ofun+0x4c>
  38:   e0 80 18 02     l.sub r4,r0,r3
  3c:   e0 64 18 04     l.or r3,r4,r3
  40:   bd 63 00 00     l.sfgesi r3,0x0
  44:   10 00 00 0c     l.bf 74 <ofun+0x4c>
  48:   e0 60 30 02     l.sub r3,r0,r6
  4c:   e0 c3 30 04     l.or r6,r3,r6
  50:   bd 66 00 00     l.sfgesi r6,0x0
  54:   10 00 00 08     l.bf 74 <ofun+0x4c>
  58:   e0 60 28 02     l.sub r3,r0,r5
  5c:   e0 a3 28 04     l.or r5,r3,r5
  60:   bd 85 00 00     l.sfltsi r5,0x0
  64:   0c 00 00 04     l.bnf 74 <ofun+0x4c>
  68:   9d 60 00 0b     l.addi r11,r0,0xb
  6c:   44 00 48 00     l.jr r9
  70:   15 00 00 00     l.nop 0x0
  74:   44 00 48 00     l.jr r9
  78:   9d 60 00 07     l.addi r11,r0,0x7

这取决于乘法的实现，如果它是一个时钟，那么乘法就有它。

如果您的硬件不支持乘法，那么您必须调用它来进行模拟

00000000 <mfun>:
   0:   0b 12           push    r11     
   2:   0a 12           push    r10     
   4:   09 12           push    r9      
   6:   09 4d           mov r13,    r9  
   8:   0b 4c           mov r12,    r11 
   a:   0a 4e           mov r14,    r10 
   c:   0c 4f           mov r15,    r12 
   e:   b0 12 00 00     call    #0x0000 
  12:   0a 4e           mov r14,    r10 
  14:   0c 49           mov r9, r12 
  16:   b0 12 00 00     call    #0x0000 
  1a:   0a 4e           mov r14,    r10 
  1c:   0c 4b           mov r11,    r12 
  1e:   b0 12 00 00     call    #0x0000 
  22:   0e 93           tst r14     
  24:   06 24           jz  $+14        ;abs 0x32
  26:   3f 40 0b 00     mov #11,    r15 ;#0x000b
  2a:   39 41           pop r9      
  2c:   3a 41           pop r10     
  2e:   3b 41           pop r11     
  30:   30 41           ret         
  32:   3f 40 07 00     mov #7, r15 ;#0x0007
  36:   39 41           pop r9      
  38:   3a 41           pop r10     
  3a:   3b 41           pop r11     
  3c:   30 41           ret         

0000003e <ofun>:
  3e:   0f 93           tst r15     
  40:   09 24           jz  $+20        ;abs 0x54
  42:   0e 93           tst r14     
  44:   07 24           jz  $+16        ;abs 0x54
  46:   0d 93           tst r13     
  48:   05 24           jz  $+12        ;abs 0x54
  4a:   0c 93           tst r12     
  4c:   03 24           jz  $+8         ;abs 0x54
  4e:   3f 40 0b 00     mov #11,    r15 ;#0x000b
  52:   30 41           ret         
  54:   3f 40 07 00     mov #7, r15 ;#0x0007
  58:   30 41    

你会希望这两个是等价的，从纯数学意义上来说，它们应该是相等的，才能得到乘法的结果为零，一个操作数需要为零。问题是这是一个用于处理器的软件，你可以很容易地在乘法上溢出，并且有非零的操作数，但是仍然得到零，所以为了正确地实现代码，乘法必须发生。

由于mul和divide的成本，你应该在你的软件中尽可能地避免它们，你的乘法解决方案在这种情况下，为了使两个解决方案等价，将需要更多的代码来检测或防止可能导致误报的溢出情况。是的，许多处理器在一个时钟内执行mul，也执行除法，为什么你看不到除法，有时也看不到mul在指令集中实现，是因为所需的芯片占地面积，现在的费用是功率，热量，部分的成本，等等。所以mul和除法仍然昂贵，当然不限于这些，但他们确实在帐篷中创造了很长的极点，如部分的性能，时钟频率，人们希望单时钟操作没有意识到一条指令可能会减慢整个芯片的速度，允许它是多时钟可能会使你的整体时钟频率上升。很多东西都是长杆，所以移除mul可能不会改变性能，这完全取决于……