switch case的跳转原理？

Question

当有很多个case时，switch是怎样做到只要少数比较(只要1次？)就得出结果的？
就算有个跳转表也是需要经过多次的比较才可以找到相应的位置的不是吗？毕竟是dumb computer，当没有给一个明确的指令时，只有通过不断的比较才可以得到结果。
例如SQL的索引，索引的原理和switch差不多吧，只是原理到底是什么？

Answer 1

我们可以直接通过汇编代码来看：

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

Answer 2

我猜测，首先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

Answer 3

关于跳转表的原理我大概理解了，谢谢各位的回答。原理是通过数组下标来跳转，当然如果case的值相差过大又没规律可能会采用以if为主的二分查找方法（数学真是伟大。）大概sql的索引也是相似的原理。
ps:附上两篇Google找到的关于跳转表的文章
http://www.programlife.net/sw...
http://www.voidcn.com/blog/si...。

Answer 4

先不说JavaScript的情况。就C/C++和Java而言，case跟的必须是常量，这就为编译优化带来了空间。

至于编译器是如何优化的(JVM暂且不说)，写一段C语言的程序，编译时输出汇编语言，看下就知道了。

另外，Java 1.7+支持switch String，我猜原理可能跟HashTable类似吧。