javascript - switch case的跳转原理？
当有很多个case时，switch是怎样做到只要少数比较(只要1次？)就得出结果的？
就算有个跳转表也是需要经过多次的比较才可以找到相应的位置的不是吗？毕竟是dumb compute，当没有给一个明确的指令时，只有通过不断的比较才可以得到结果。
例如SQL的索引，索引的原理和switch差不多吧，只是原理到底是什么？
当有很多个case时，switch是怎样做到只要少数比较(只要1次？)就得出结果的？
就算有个跳转表也是需要经过多次的比较才可以找到相应的位置的不是吗？毕竟是dumb compute，当没有给一个明确的指令时，只有通过不断的比较才可以得到结果。
例如SQL的索引，索引的原理和switch差不多吧，只是原理到底是什么？
PHP中文网2017-04-11 12:56:43
我们可以直接通过汇编代码来看：
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
天蓬老师2017-04-11 12:56:43
我猜测，首先Switch底层是：Label + Goto
至于判断部分略过goto 1
Label 1:
xxx如果是字符串：
case "1"-->编译时进行参数转换-->goto 0xa12112，同时动态传入的参数Switch(a)中a会转化为0xa12112这个Key，通过这个Key查询HashTable，从而确定goto语句是否存在，不存在就执行default
goto 0xa12112
Label 0xa12112:
xxx
PHP中文网2017-04-11 12:56:43
关于跳转表的原理我大概理解了，谢谢各位的回答。原理是通过数组下标来跳转，当然如果case的值相差过大又没规律可能会采用以if为主的二分查找方法（数学真是伟大。）大概sql的索引也是相似的原理。
ps:附上两篇Google找到的关于跳转表的文章
http://www.programlife.net/sw...
http://www.voidcn.com/blog/si...。
巴扎黑2017-04-11 12:56:43
先不说JavaScript的情况。就C/C++和Java而言，case跟的必须是常量，这就为编译优化带来了空间。
至于编译器是如何优化的(JVM暂且不说)，写一段C语言的程序，编译时输出汇编语言，看下就知道了。
另外，Java 1.7+支持switch String，我猜原理可能跟HashTable类似吧。