老生常谈之：switch-case VS if-else
“在同等条件下，使用 switch-case 与 if-else 哪一个可以在 C/C++ 中生成质量更好、性能更高的目标代码呢？”这似乎是一个老生常谈的问题，今天我们就来深入研究一下。
仅从 C/C++ 代码层面来看，if-else 在进行条件选择时，需要从上到下依次判断每一个条件分支是否成立；而 switch-case 由于 case 表达式只能够使用编译时常量，且类型必须为 integral 或 enum。因此从某种意义上来讲可以使用类似“索引表”的结构来进行优化。我们用如下一段代码作为测试用例：
#include <stdio.h>
int foo(int v) {
if (v == 10 || v == 20) {
return 1;
} else if (v == 30 || v == 40) {
return 2;
} else if (v == 50 || v == 60) {
return 3;
} else if (v == 70 || v == 80) {
return 4;
} else {
return 5;
}
}
int bar(int v) {
switch (v) {
case 10:
case 20: { return 1; break; }
case 30:
case 40: { return 2; break; }
case 50:
case 60: { return 3; break; }
case 70:
case 80: { return 4; break; }
default: return 5;
}
}
int main(int argc, char** argv) {
printf("%d %d\n", foo(10), bar(40));
return 0;
}
默认零优化情况
然后我们使用 Clang 的默认优化等级来编译上述这段代码。接着使用 GDB 调试：
(gdb) file main
...
(gdb) set disassembly-flavor intel
(gdb) disas /m foo
对函数 foo 的反汇编结果如下：
Dump of assembler code for function foo:
0x0000000000401130 <+0>: push rbp ; Prologue;
0x0000000000401131 <+1>: mov rbp,rsp
0x0000000000401134 <+4>: mov DWORD PTR [rbp-0x8],edi
; 存放在栈上的局部变量 v："x /w $rbp-0x8" -> 0xa;
; "} else if (v == 30 || v == 40) {"
0x0000000000401137 <+7>: cmp DWORD PTR [rbp-0x8],0xa
0x000000000040113b <+11>: je 0x40114b
0x0000000000401141 <+17>: cmp DWORD PTR [rbp-0x8],0x14
0x0000000000401145 <+21>: jne 0x401157
0x000000000040114b <+27>: mov DWORD PTR [rbp-0x4],0x1
0x0000000000401152 <+34>: jmp 0x4011be
; "} else if (v == 30 || v == 40) {"
0x0000000000401157 <+39>: cmp DWORD PTR [rbp-0x8],0x1e
0x000000000040115b <+43>: je 0x40116b
0x0000000000401161 <+49>: cmp DWORD PTR [rbp-0x8],0x28
0x0000000000401165 <+53>: jne 0x401177
0x000000000040116b <+59>: mov DWORD PTR [rbp-0x4],0x2
0x0000000000401172 <+66>: jmp 0x4011be
; "} else if (v == 50 || v == 60) {"
0x0000000000401177 <+71>: cmp DWORD PTR [rbp-0x8],0x32
0x000000000040117b <+75>: je 0x40118b
0x0000000000401181 <+81>: cmp DWORD PTR [rbp-0x8],0x3c
0x0000000000401185 <+85>: jne 0x401197
0x000000000040118b <+91>: mov DWORD PTR [rbp-0x4],0x3
0x0000000000401192 <+98>: jmp 0x4011be
; "} else if (v == 70 || v == 80) {"
0x0000000000401197 <+103>: cmp DWORD PTR [rbp-0x8],0x46
0x000000000040119b <+107>: je 0x4011ab
0x00000000004011a1 <+113>: cmp DWORD PTR [rbp-0x8],0x50
0x00000000004011a5 <+117>: jne 0x4011b7
0x00000000004011ab <+123>: mov DWORD PTR [rbp-0x4],0x4
0x00000000004011b2 <+130>: jmp 0x4011be
; "} else {"
0x00000000004011b7 <+135>: mov DWORD PTR [rbp-0x4],0x5
0x00000000004011be <+142>: mov eax,DWORD PTR [rbp-0x4]
0x00000000004011c1 <+145>: pop rbp ; Epilogue;
0x00000000004011c2 <+146>: ret
End of assembler dump.
然后我们再以同样的方式来反汇编使用 switch-case 结构的函数 bar 对应的汇编代码：
Dump of assembler code for function bar:
0x00000000004011d0 <+0>: push rbp ; Prologue;
0x00000000004011d1 <+1>: mov rbp,rsp
0x00000000004011d4 <+4>: mov DWORD PTR [rbp-0x8],edi
0x00000000004011d7 <+7>: mov eax,DWORD PTR [rbp-0x8]
0x00000000004011da <+10>: add eax,0xfffffff6
0x00000000004011dd <+13>: mov ecx,eax
0x00000000004011df <+15>: sub eax,0x46
0x00000000004011e2 <+18>: mov QWORD PTR [rbp-0x10],rcx
0x00000000004011e6 <+22>: ja 0x40122a
0x00000000004011ec <+28>: mov rax,QWORD PTR [rbp-0x10]
0x00000000004011f0 <+32>: mov rcx,QWORD PTR [rax*8+0x402008] ; 从“跳表”中找到对应 case 的入口地址；
0x00000000004011f8 <+40>: jmp rcx
; "{ return 1; break; }"
0x00000000004011fa <+42>: mov DWORD PTR [rbp-0x4],0x1
0x0000000000401201 <+49>: jmp 0x401231
; "{ return 2; break; }"
0x0000000000401206 <+54>: mov DWORD PTR [rbp-0x4],0x2
0x000000000040120d <+61>: jmp 0x401231
; "{ return 3; break; }"
0x0000000000401212 <+66>: mov DWORD PTR [rbp-0x4],0x3
0x0000000000401219 <+73>: jmp 0x401231
; "{ return 4; break; }"
0x000000000040121e <+78>: mov DWORD PTR [rbp-0x4],0x4
0x0000000000401225 <+85>: jmp 0x401231
; "{ return 5; break; }"
0x000000000040122a <+90>: mov DWORD PTR [rbp-0x4],0x5
0x0000000000401231 <+97>: mov eax,DWORD PTR [rbp-0x4]
0x0000000000401234 <+100>: pop rbp ; Epilogue;
0x0000000000401235 <+101>: ret
End of assembler dump.
众所周知，默认情况下编译器会为 switch-case 生成对应的“跳表”结构来以“空间换时间”的方式加快该结构对应 case 子句的查询速度。接下来我们在位置 “0x4011f0” 设置断点，并查看 “[rax*8+0x402008]” 的值以检验实际的跳转地址是否正确（对应函数参数 40 的子句入口应该为 “0x401206”）。
(gdb) break *0x00000000004011f0
Breakpoint 1 at 0x4011f0
(gdb) run
Starting program: /home/osboxes/Repo/linux/main
Breakpoint 1, 0x00000000004011f0 in bar ()
(gdb) x /g $rax*8+0x402008
0x4020f8: 0x0000000000401206
可以看到，结果是正确的。接下来，我们再以 “0x401206” 为入口，来推算一下 “0x401212” 这个分支入口地址在跳表的位置。因为我们的输入为 “40”，距离这个分支入口还有 “10” 的距离。因此该入口地址应该存放于偏移 “0x4020f8” 位置 0x50（0xa * 0x8）的地方，即位置 “0x402148”。我们可以来检验一下：
(gdb) x /11xg 0x4020f8
0x4020f8: 0x0000000000401206 0x000000000040122a
0x402108: 0x000000000040122a 0x000000000040122a
0x402118: 0x000000000040122a 0x000000000040122a
0x402128: 0x000000000040122a 0x000000000040122a
0x402138: 0x000000000040122a 0x000000000040122a
0x402148: 0x0000000000401212
需要注意的是，在位置 “0x4020f8” 与 “0x402148” 之间接连存放的是 switch-case 中 default 语句的入口地址。在《C++ Footprint and Performance Optimization》一书中，作者曾在一定条件下做过测试，得出了以下结论：“在 5 个分支（包括 default）的情况下，switch-case 与 if-else 的性能基本相同，而低于 5 个分支时，if-else 较快，反之 switch-case 较快”。由于该书出版较为久远，再加上编译器的优化在这些年里也有了较大的提升，因此该结论仅供参考。
-O3 优化情况
我们尝试重新编译上述 C/C++ 代码，并添加优化等级 “-O3”。得出结果发现编译器通过编译时求值直接计算出了 printf 中 foo 与 bar 函数的调用结果。不仅如此，对应的 foo 中的 if-else 结构也被优化为了同 switch-case 一模一样的“跳表”结构。
(gdb) disas /m foo
Dump of assembler code for function foo:
0x0000000000401130 <+0>: add edi,0xfffffff6
0x0000000000401133 <+3>: cmp edi,0x46
0x0000000000401136 <+6>: ja 0x401156
0x0000000000401138 <+8>: mov eax,0x1
0x000000000040113d <+13>: jmp QWORD PTR [rdi*8+0x402008]
0x0000000000401144 <+20>: mov eax,0x2
0x0000000000401149 <+25>: ret
0x000000000040114a <+26>: mov eax,0x3
0x000000000040114f <+31>: ret
0x0000000000401150 <+32>: mov eax,0x4
0x0000000000401155 <+37>: ret
0x0000000000401156 <+38>: mov eax,0x5
0x000000000040115b <+43>: ret
End of assembler dump.
switch-case “大跨度”情况
为了验证编译器在 switch-case 中遇到 case 条件的值在跨度较大时的处理情况，我们将上述 C/C++ 代码做出如下更改：
#include <stdio.h>
int foo(int v) {
if (v == 10000 || v == 20000) {
return 1;
} else if (v == 30000 || v == 40000) {
return 2;
} else if (v == 50000 || v == 60000) {
return 3;
} else if (v == 70000 || v == 80000) {
return 4;
} else {
return 5;
}
}
int bar(int v) {
switch (v) {
case 10000:
case 20000: {
return 1; break;
}
case 30000:
case 40000: {
return 2; break;
}
case 50000:
case 60000: {
return 3; break;
}
case 70000:
case 80000: {
return 4; break;
}
default: return 5;
}
}
int main(int argc, char** argv) {
printf("%d %d\n", foo(10000), bar(40000));
return 0;
}
在默认优化等级下，对于使用了 if-else 结构的 foo 函数来说，产生的目标代码结构是一样的，这里不再做介绍。而对于使用了 switch-case 的 bar 函数则有所不同：
Dump of assembler code for function bar:
0x00000000004011e0 <+0>: push rbp
0x00000000004011e1 <+1>: mov rbp,rsp
0x00000000004011e4 <+4>: mov DWORD PTR [rbp-0x8],edi
0x00000000004011e7 <+7>: mov eax,DWORD PTR [rbp-0x8]
0x00000000004011ea <+10>: mov ecx,eax
; 存放在栈上的局部变量 v："x /dw $rbp-0xc" -> 40000；
0x00000000004011ec <+12>: sub ecx,0x2710 ; 10000;
0x00000000004011f2 <+18>: mov DWORD PTR [rbp-0xc],eax
0x00000000004011f5 <+21>: je 0x401285
0x00000000004011fb <+27>: jmp 0x401200
0x0000000000401200 <+32>: mov eax,DWORD PTR [rbp-0xc]
; 比较 v 与 20000；
0x0000000000401203 <+35>: sub eax,0x4e20
0x0000000000401208 <+40>: je 0x401285
0x000000000040120e <+46>: jmp 0x401213
0x0000000000401213 <+51>: mov eax,DWORD PTR [rbp-0xc]
; 比较 v 与 30000；
0x0000000000401216 <+54>: sub eax,0x7530
0x000000000040121b <+59>: je 0x401291
0x0000000000401221 <+65>: jmp 0x401226
0x0000000000401226 <+70>: mov eax,DWORD PTR [rbp-0xc]
; 比较 v 与 40000；
0x0000000000401229 <+73>: sub eax,0x9c40
0x000000000040122e <+78>: je 0x401291
0x0000000000401234 <+84>: jmp 0x401239
0x0000000000401239 <+89>: mov eax,DWORD PTR [rbp-0xc]
; 比较 v 与 50000；
0x000000000040123c <+92>: sub eax,0xc350
0x0000000000401241 <+97>: je 0x40129d
0x0000000000401247 <+103>: jmp 0x40124c
0x000000000040124c <+108>: mov eax,DWORD PTR [rbp-0xc]
; 比较 v 与 60000；
0x000000000040124f <+111>: sub eax,0xea60
0x0000000000401254 <+116>: je 0x40129d
0x000000000040125a <+122>: jmp 0x40125f
0x000000000040125f <+127>: mov eax,DWORD PTR [rbp-0xc]
; 比较 v 与 70000；
0x0000000000401262 <+130>: sub eax,0x11170
0x0000000000401267 <+135>: je 0x4012a9
0x000000000040126d <+141>: jmp 0x401272
0x0000000000401272 <+146>: mov eax,DWORD PTR [rbp-0xc]
; 比较 v 与 80000；
0x0000000000401275 <+149>: sub eax,0x13880
0x000000000040127a <+154>: je 0x4012a9
0x0000000000401280 <+160>: jmp 0x4012b5
0x0000000000401285 <+165>: mov DWORD PTR [rbp-0x4],0x1
0x000000000040128c <+172>: jmp 0x4012bc
0x0000000000401291 <+177>: mov DWORD PTR [rbp-0x4],0x2
0x0000000000401298 <+184>: jmp 0x4012bc
0x000000000040129d <+189>: mov DWORD PTR [rbp-0x4],0x3
0x00000000004012a4 <+196>: jmp 0x4012bc
0x00000000004012a9 <+201>: mov DWORD PTR [rbp-0x4],0x4
0x00000000004012b0 <+208>: jmp 0x4012bc
0x00000000004012b5 <+213>: mov DWORD PTR [rbp-0x4],0x5
0x00000000004012bc <+220>: mov eax,DWORD PTR [rbp-0x4]
0x00000000004012bf <+223>: pop rbp
0x00000000004012c0 <+224>: ret
End of assembler dump.
可以看到，此时的 switch-case 并没有采用“跳表”的方式，而是退化到了与 if-else 结构类似的顺序条件判断结构。因此，可以得到的一个优化方式是：将命中率较高的 case 语句摆放在 switch-case 结构的最前面，可以减少需要判断的分支情况，加速目标分支的命中。接下来，我们同样查看在使用了 -O3 参数优化之后生成的目标 switch-case 结构：
Dump of assembler code for function bar:
0x00000000004011b0 <+0>: cmp edi,0xc34f ; 49999;
0x00000000004011b6 <+6>: jg 0x4011d6
0x00000000004011b8 <+8>: cmp edi,0x752f ; 29999;
0x00000000004011be <+14>: jg 0x4011f4
0x00000000004011c0 <+16>: mov eax,0x1
0x00000000004011c5 <+21>: cmp edi,0x2710 ; 10000;
0x00000000004011cb <+27>: je 0x4011d5
0x00000000004011cd <+29>: cmp edi,0x4e20 ; 20000;
0x00000000004011d3 <+35>: jne 0x401220
0x00000000004011d5 <+37>: ret
0x00000000004011d6 <+38>: cmp edi,0x1116f ; 69999;
0x00000000004011dc <+44>: jg 0x40120a
0x00000000004011de <+46>: cmp edi,0xc350 ; 50000;
0x00000000004011e4 <+52>: je 0x4011ee
0x00000000004011e6 <+54>: cmp edi,0xea60 ; 60000;
0x00000000004011ec <+60>: jne 0x401220
0x00000000004011ee <+62>: mov eax,0x3
0x00000000004011f3 <+67>: ret
0x00000000004011f4 <+68>: cmp edi,0x7530 ; 30000;
0x00000000004011fa <+74>: je 0x401204
0x00000000004011fc <+76>: cmp edi,0x9c40 ; 40000;
0x0000000000401202 <+82>: jne 0x401220
0x0000000000401204 <+84>: mov eax,0x2
0x0000000000401209 <+89>: ret
0x000000000040120a <+90>: cmp edi,0x11170 ; 70000;
0x0000000000401210 <+96>: je 0x40121a
0x0000000000401212 <+98>: cmp edi,0x13880 ; 80000;
0x0000000000401218 <+104>: jne 0x401220
0x000000000040121a <+106>: mov eax,0x4
0x000000000040121f <+111>: ret
0x0000000000401220 <+112>: mov eax,0x5
0x0000000000401225 <+117>: ret
End of assembler dump.
此时如果再查看 foo 函数内的 if-else 结构，会发现它同 switch-case 结构一样，被优化为了同一种形式，即：使用 “Binary Decision Tree” 的方式来查找目标分支语句。
评论 | Comments