84669 personnes étudient
152542 personnes étudient
20005 personnes étudient
5487 personnes étudient
7821 personnes étudient
359900 personnes étudient
3350 personnes étudient
180660 personnes étudient
48569 personnes étudient
18603 personnes étudient
40936 personnes étudient
1549 personnes étudient
1183 personnes étudient
32909 personnes étudient
当有很多个case时,switch是怎样做到只要少数比较(只要1次?)就得出结果的?就算有个跳转表也是需要经过多次的比较才可以找到相应的位置的不是吗?毕竟是dumb compute,当没有给一个明确的指令时,只有通过不断的比较才可以得到结果。例如SQL的索引,索引的原理和switch差不多吧,只是原理到底是什么?
小伙看你根骨奇佳,潜力无限,来学PHP伐。
我们可以直接通过汇编代码来看:
void bob() { int a = 1; switch(a) { case 1: std::cout<<"case 1"<<std::endl; break; case 2: std::cout<<"case 2"<<std::endl; break; case 3: std::cout<<"case 3"<<std::endl; break; default: std::cout<<"default case"<<std::endl; } }
汇编其中关键代码如下:可以看到case实际的比较顺序是2->3->1, 并不是代码的编写顺序:
0000000000400846 <_Z3bobv>: 400846:>..55 >..push %rbp 400847:>..48 89 e5 >..mov %rsp,%rbp 40084a:>..48 83 ec 10 >..sub $0x10,%rsp 40084e:>..c7 45 fc 01 00 00 00 >..movl $0x1,-0x4(%rbp) 400855:>..8b 45 fc >..mov -0x4(%rbp),%eax //先比较是否等于2, 如果是,则跳转到0x400885指令地址, 即case的输出语句; 400858:>..83 f8 02 >..cmp $0x2,%eax 40085b:>..74 28 >..je 400885 <_Z3bobv+0x3f> //否则,继续比较是否等于3, 40085d:>..83 f8 03 >..cmp $0x3,%eax 400860:>..74 41 >..je 4008a3 <_Z3bobv+0x5d> //最后比较是否等于1 400862:>..83 f8 01 >..cmp $0x1,%eax 400865:>..75 5a >..jne 4008c1 <_Z3bobv+0x7b> 400867:>..be d4 09 40 00 >..mov $0x4009d4,%esi 40086c:>..bf 60 10 60 00 >..mov $0x601060,%edi 400871:>..e8 9a fe ff ff >..callq 400710 <_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_> 400876:>..be 30 07 40 00 >..mov $0x400730,%esi 40087b:>..48 89 c7 >..mov %rax,%rdi 40087e:>..e8 9d fe ff ff >..callq 400720 <_ZNSolsEPFRSoS_E@plt> 400883:>..eb 58 >..jmp 4008dd <_Z3bobv+0x97> 400885:>..be db 09 40 00 >..mov $0x4009db,%esi 40088a:>..bf 60 10 60 00 >..mov $0x601060,%edi 40088f:>..e8 7c fe ff ff >..callq 400710 <_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_> 400894:>..be 30 07 40 00 >..mov $0x400730,%esi 400899:>..48 89 c7 >..mov %rax,%rdi 40089c:>..e8 7f fe ff ff >..callq 400720 <_ZNSolsEPFRSoS_E@plt> 4008a1:>..eb 3a >..jmp 4008dd <_Z3bobv+0x97> 4008a3:>..be db 09 40 00 >..mov $0x4009db,%esi 4008a8:>..bf 60 10 60 00 >..mov $0x601060,%edi 4008ad:>..e8 5e fe ff ff >..callq 400710 <_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_> 4008b2:>..be 30 07 40 00 >..mov $0x400730,%esi 4008b7:>..48 89 c7 >..mov %rax,%rdi 4008ba:>..e8 61 fe ff ff >..callq 400720 <_ZNSolsEPFRSoS_E@plt> 4008bf:>..eb 1c >..jmp 4008dd <_Z3bobv+0x97> 4008c1:>..be e2 09 40 00 >..mov $0x4009e2,%esi 40092c: c9 leaveq 40092d: c3 retq
至于为什么是这个顺序,没有研究过,这是编译器层面的处理了,可以一起学习下,
第二次修改@felix ,这里上面特意没有开启优化,因为是要看原理,所以优化就没有什么意思,下面是开始O2选项的结果:
00000000004009a0 <_Z3bobv>: 4009a0: 53 push %rbx 4009a1: ba 06 00 00 00 mov $0x6,%edx // switch case 直接被优化成了下面三句, esi和edi是ostream的两个参数, 4009a6: be b4 0a 40 00 mov $0x400ab4,%esi //这个是rodata段的"case 1"字符串 4009ab: bf 80 10 60 00 mov $0x601080,%edi //std::cout对象 //直接调用输出语句 4009b0: e8 6b fe ff ff callq 400820 <_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l@plt> 4009b5: 48 8b 05 c4 06 20 00 mov 0x2006c4(%rip),%rax # 601080 <_ZSt4cout@@GLIBCXX_3.4> 4009bc: 48 8b 40 e8 mov -0x18(%rax),%rax 4009c0: 48 8b 98 70 11 60 00 mov 0x601170(%rax),%rbx 4009c7: 48 85 db test %rbx,%rbx 4009ca: 74 4a je 400a16 <_Z3bobv+0x76> 4009cc: 80 7b 38 00 cmpb $0x0,0x38(%rbx) 4009d0: 74 1e je 4009f0 <_Z3bobv+0x50> 4009d2: 0f be 73 43 movsbl 0x43(%rbx),%esi 4009d6: bf 80 10 60 00 mov $0x601080,%edi 4009db: e8 60 fe ff ff callq 400840 <_ZNSo3putEc@plt> 4009e0: 5b pop %rbx 4009e1: 48 89 c7 mov %rax,%rdi 4009e4: e9 47 fe ff ff jmpq 400830 <_ZNSo5flushEv@plt> 4009e9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax) 4009f0: 48 89 df mov %rbx,%rdi 4009f3: e8 d8 fd ff ff callq 4007d0 <_ZNKSt5ctypeIcE13_M_widen_initEv@plt> 4009f8: 48 8b 03 mov (%rbx),%rax 4009fb: be 0a 00 00 00 mov $0xa,%esi 400a00: 48 8b 40 30 mov 0x30(%rax),%rax 400a04: 48 3d 20 0a 40 00 cmp $0x400a20,%rax 400a0a: 74 ca je 4009d6 <_Z3bobv+0x36> 400a0c: 48 89 df mov %rbx,%rdi 400a0f: ff d0 callq *%rax 400a11: 0f be f0 movsbl %al,%esi 400a14: eb c0 jmp 4009d6 <_Z3bobv+0x36> 400a16: e8 a5 fd ff ff callq 4007c0 <_ZSt16__throw_bad_castv@plt> 400a1b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
下面是rodata中保存的要输出的“case 1”字符串, 在不优化的情况下,rodata中是会有"case 2" , "case 3", "default case"的。
Contents of section .rodata: 400ab0 01000200 63617365 203100 ....case 1.
第三次修改
@felix ,谢谢, 当case语句增加到10条(具体多少开启,可以测一下)时,编译器(debug和O2)开启了case 的匹配优化,也就是大家所谓的jump table:
.LC0: 6 >....string>"case 1" 7 .LC1: 8 >....string>"case 2" 9 .LC2: 10 >....string>"case 3" 11 .LC3: 12 >....string>"case 4" 13 .LC4: 14 >....string>"case 5" 15 .LC5: 16 >....string>"case 6" 17 .LC6: 18 >....string>"case 7" 19 .LC7: 20 >....string>"case 8" 21 .LC8: 22 >....string>"case 9" 23 .LC9: 24 >....string>"case 10" 25 .LC10: 26 >....string>"default case" 27 >....text 28 >....globl>._Z3bobv 29 >....type>.._Z3bobv, @function 30 _Z3bobv: 31 .LFB1021: 32 >....cfi_startproc 33 >...pushq>..%rbp 34 >....cfi_def_cfa_offset 16 35 >....cfi_offset 6, -16 36 >...movq>...%rsp, %rbp 37 >....cfi_def_cfa_register 6 38 >...subq>...$16, %rsp 39 >...movl>...$1, -4(%rbp) // 如果输入的参数 大于10, 直接进入default的处理 40 >...cmpl>...$10, -4(%rbp) 41 >...ja>..L2 // 将输入参数存入eax寄存器中, 然后通过L4段,计算出匹配case的地址,进行跳转 42 >...movl>...-4(%rbp), %eax 43 >...movq>....L4(,%rax,8), %rax 44 >...jmp>*%rax 45 >....section>....rodata 46 >....align 8 47 >....align 4 //这部分就是jump table, 根据case的参数进行偏移 48 .L4: 49 >....quad>...L2 //default 50 >....quad>...L3 //case 1 51 >....quad>...L5 52 >....quad>...L6 53 >....quad>...L7 54 >....quad>...L8 55 >....quad>...L9 56 >....quad>...L10 57 >....quad>...L11 58 >....quad>...L12 59 >....quad>...L13 60 >....text 61 .L3: 62 >...movl>...$.LC0, %esi 63 >...movl>...$_ZSt4cout, %edi 64 >...call>..._ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc 65 >...movl>...$_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_, %esi 66 >...movq>...%rax, %rdi 67 >...call>..._ZNSolsEPFRSoS_E 68 >...jmp>.L14
我猜测,首先Switch底层是:Label + Goto 至于判断部分略过goto 1
goto 1
Label 1: xxx
如果是字符串:case "1"-->编译时进行参数转换-->goto 0xa12112,同时动态传入的参数Switch(a)中a会转化为0xa12112这个Key,通过这个Key查询HashTable,从而确定goto语句是否存在,不存在就执行default
goto 0xa12112
Label 0xa12112: xxx
关于跳转表的原理我大概理解了,谢谢各位的回答。原理是通过数组下标来跳转,当然如果case的值相差过大又没规律可能会采用以if为主的二分查找方法(数学真是伟大。)大概sql的索引也是相似的原理。ps:附上两篇Google找到的关于跳转表的文章http://www.programlife.net/sw...http://www.voidcn.com/blog/si...。
先不说JavaScript的情况。就C/C++和Java而言,case跟的必须是常量,这就为编译优化带来了空间。
至于编译器是如何优化的(JVM暂且不说),写一段C语言的程序,编译时输出汇编语言,看下就知道了。
另外,Java 1.7+支持switch String,我猜原理可能跟HashTable类似吧。
我们可以直接通过汇编代码来看:
汇编其中关键代码如下:可以看到case实际的比较顺序是2->3->1, 并不是代码的编写顺序:
至于为什么是这个顺序,没有研究过,这是编译器层面的处理了,可以一起学习下,
第二次修改
@felix ,这里上面特意没有开启优化,因为是要看原理,所以优化就没有什么意思,下面是开始O2选项的结果:
下面是rodata中保存的要输出的“case 1”字符串, 在不优化的情况下,rodata中是会有"case 2" , "case 3", "default case"的。
第三次修改
@felix ,谢谢, 当case语句增加到10条(具体多少开启,可以测一下)时,编译器(debug和O2)开启了case 的匹配优化,也就是大家所谓的jump table:
我猜测,首先Switch底层是:Label + Goto
至于判断部分略过
goto 1
如果是字符串:
case "1"-->编译时进行参数转换-->goto 0xa12112,同时动态传入的参数Switch(a)中a会转化为0xa12112这个Key,通过这个Key查询HashTable,从而确定goto语句是否存在,不存在就执行default
goto 0xa12112
关于跳转表的原理我大概理解了,谢谢各位的回答。原理是通过数组下标来跳转,当然如果case的值相差过大又没规律可能会采用以if为主的二分查找方法(数学真是伟大。)大概sql的索引也是相似的原理。
ps:附上两篇Google找到的关于跳转表的文章
http://www.programlife.net/sw...
http://www.voidcn.com/blog/si...。
先不说JavaScript的情况。就C/C++和Java而言,case跟的必须是常量,这就为编译优化带来了空间。
至于编译器是如何优化的(JVM暂且不说),写一段C语言的程序,编译时输出汇编语言,看下就知道了。
另外,Java 1.7+支持switch String,我猜原理可能跟HashTable类似吧。