我在某个论坛遇到过这段代码：
if ( a * b * c * d == 0 ) ....
业主声称这比
if (a == 0 || b == 0 || c == 0 || d == 0)
这些变量定义为：
int a, b, c, d;
并且它们的绝对值保证小于等于100。（所以我们可以忽略溢出的可能性）
如果我们只是忽略readability并只关注性能，那么这种说法真的正确吗？
在我看来，第二种方法实际上可能更快，因为您有时可以利用“短路”。但是，我知道什么？！
问问题
3751 次
5 回答
10
C 标准没有说明性能。是否的问题
if ( a * b * c * d == 0 )
比
if (a == 0 || b == 0 || c == 0 || d == 0)
仅在特定编译器生成在特定机器上运行的代码的上下文中才有意义。比较它们的唯一真正方法是在您自己的系统或您感兴趣的任何系统上测量性能。
不过，我们可以推测性能可能是什么。
正如你所说，a, b,c和d是类型的对象int。您还说它们在 [-100,+100] 范围内——但编译器不一定知道这一点。
编译器可以自由地将任何表达式替换为执行相同操作的代码。
乘法是一个相对复杂的运算，并且可能比加法或比较慢。如果四个变量中的任何一个具有 value ，编译器可以识别出第一个条件为真0，并将乘法替换为碰巧更快的任何值。但是编译器执行的每个优化都必须由编译器的开发人员显式编程，而且这种特定的模式可能不够普遍，以至于值得努力识别它。
您说这些值足够小，溢出不是问题。事实上，你不能轻易做出这样的假设。INT_MAX可以小到32767。int但是编译器知道它在生成代码的系统上有多大。尽管如此，除非它有关于 、 、 和 的值的信息，否则它a不能b假设c不会d有溢出。
除了是的，实际上，它可以做出这样的假设。有符号整数溢出的行为是未定义的。这为优化编译器提供了假设不会发生溢出的权限（如果发生，则程序表现出的任何行为无论如何都是有效的）。
所以是的，编译器可以用更简单的东西代替乘法，但不太可能这样做。
至于另一个表达式，a == 0 || b == 0 || c == 0 || d == 0，||运算符具有短路语义；如果左操作数为真（非零），则不计算右操作数。由于 CPU 管道问题，这种条件代码会产生性能问题。由于没有一个子表达式有副作用（假设没有声明任何变量volatile），编译器可以计算所有四个子表达式，也许是并行的，如果这样更快的话。
一个快速的实验表明gcc -O3对于 x86 不执行任何优化。对于第一个表达式，它生成执行三个乘法的代码。其次，它生成条件分支，实现规范的短路评估（我不知道避免这种情况是否会更快）。
最好的办法是编写尽可能简单明了的合理代码，既因为它使您的源代码更易于阅读和维护，又因为它可能使编译器有更好的机会识别模式和执行优化。如果您尝试在源代码中进行花哨的微优化，那么您很可能会阻碍编译器的优化，就像您要提供帮助一样。
不要太担心你的代码有多快，除非你已经测量过它并发现它太慢了。如果您需要更快的代码，请首先专注于改进的算法和数据结构。只有当失败时，才考虑源代码级别的微优化。
程序优化的第一条规则：不要这样做。程序优化的第二条规则（仅限专家！）：不要这样做。
——迈克尔·杰克逊
于 2012-08-04T21:57:40.977 回答
8
两者不等价。例如，在我的机器（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% 的分支。
于 2012-08-04T20:28:26.017 回答
1
所以像往常一样，哪个问题更快，到目前为止你尝试了什么？你编译和反汇编，看看会发生什么？
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 一个编译器给出了这个
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
所以 equals 和 ors 有短路（它们本身很昂贵），但最坏的路径需要更长的时间，因此性能不稳定，乘法性能更具确定性且不那么不稳定。通过检查，上述代码的乘法解决方案应该更快。
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 和 ors 看起来更快。
开放式 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 和 divide 仍然很昂贵，当然不仅限于这些，但它们确实在帐篷中制造了关于零件性能、时钟速率的长杆，人们想要单时钟操作却没有意识到这一点指令可能会减慢整个芯片的速度，使其成为多时钟可能会提高您的整体时钟频率。帐篷里的很多东西都是长杆，所以移除 mul 可能不会改变性能，这完全取决于......
于 2012-08-04T21:13:54.470 回答
0
是的，当 if 指令失败时，因为在这种情况下，我们at most 4 comparisons (Operations)在第二条指令中执行，而对于第一条指令，我们总是执行4 operations。
编辑：解释
第二个 if 指令总是比第一个快：
假设：a = 1，b =2，c =0 和 d = 4，在这种情况下：
对于第一条指令：我们有 3 次乘法和一次比较 = 4 次操作
对于第二个 if 指令：我们将 a 与 0（结果 KO）进行比较，然后将 b 与 0（再次 KO）和 c 与 0（OK）进行比较 = 3 次操作。
这是一个输出这 2 条指令的执行时间的简单程序，您可以修改 a、b、c 和 d，并将指令的编号作为参数传递。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* This is a test program to demonstrate that the second if is faster always than the first one*/
int main(int argc, char **argv)
{
int i;
int a = 1;
int b = 2;
int c = 0;
int d = 4;
int instruction_number;
clock_t begin, end;
double time_spent;
begin = clock();
if (argc != 2)
{
fprintf(stderr, "Usage : ./a.out if_instruction_number (1 or 2)\n");
exit(EXIT_FAILURE);
}
instruction_number = atoi(argv[1]);
for (i = 1; i < 100000; i++)
{
switch (instruction_number)
{
case 1:
fprintf(stdout, "First if instruction : \n");
if (a * b * c * d == 0)
fprintf(stdout, "1st instruction\n");
break;
case 2:
fprintf(stdout, "Second if instruction : \n");
if (a == 0 || b == 0 || c == 0 || d == 0)
fprintf(stdout, "2nd instruction\n");
break;
default:
break;
}
}
end = clock();
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
fprintf(stdout, "Time to accomplish %d instruction ---> %f\n", instruction_number, time_spent);
return 0;
}
希望这有帮助。
问候。
于 2012-08-04T20:26:04.847 回答
0
if ( a * b * c * d == 0 )编译为（没有优化）
movl 16(%esp), %eax
imull 20(%esp), %eax
imull 24(%esp), %eax
imull 28(%esp), %eax
testl %eax, %eax
jne .L3
并if (a == 0 || b == 0 || c == 0 || d == 0)编译为
cmpl $0, 16(%esp)
je .L2
cmpl $0, 20(%esp)
je .L2
cmpl $0, 24(%esp)
je .L2
cmpl $0, 28(%esp)
jne .L4
于 2012-08-04T20:32:48.517 回答