📚 Study Notes

3.12 switch语句

6分钟阅读

3.12 switch 语句

C 语言的 switch 语句提供多路分支选择。当分支数量较多且 case 值密集分布时，编译器使用跳转表（jump table）实现 O(1) 的分支复杂度，比嵌套 if-else 链更高效。

跳转表原理

跳转表是一张存储代码地址的数组，根据 switch 表达式值直接索引到对应分支代码。

跳转表结构：
        ┌─────────────────┐
 $index=0│ &.Lcase0        │────→ case 0$的代码
        ├─────────────────┤
 $index=1│ &.Lcase1        │────→ case 1$的代码
        ├─────────────────┤
 $index=2│ &.Lcase2        │────→ case 2$的代码
        ├─────────────────┤
   ...  │ ...             │
        └─────────────────┘

vs 条件分支链

// 使用 if-else 链（O(n) 复杂度）
if (x == 0) { /* case 0 */ }
else if (x == 1) { /* case 1 */ }
else if (x == 2) { /* case 2 */ }
// ...
 
// 使用 switch + 跳转表（O(1) 复杂度）
switch (x) {
    case 0: /* case 0 */ break;
    case 1: /* case 1 */ break;
    case 2: /* case 2 */ break;
    // ...
}

完整示例

// C 源代码
void switch_demo(long x, long *dest) {
    switch (x) {
        case 0:
            *dest = 100;
            break;
        case 1:
            *dest = 200;
            break;
        case 3:
        case 5:
            *dest = 300;
            break;
        case 4:
            *dest = 400;
            break;
        default:
            *dest = 0;
            break;
    }
}

编译器生成的汇编

switch_demo:
    # 跳转表存储在 .rodata 段（只读数据）
    # .Ljump_table 是跳转表的起始地址
 
    cmpq    $5, %rdi            # 检查 x 是否超出 [0, 5] 范围
    ja      .Ldefault           # 如果 x > 5，跳转到 default
 
    # 间接跳转：从跳转表加载目标地址
    jmp     *.Ljump_table(, %rdi, 8)   # 跳转到跳转表[x] 中的地址
 
.Lcase0:
    movq    $100, (%rsi)        # *dest = 100
    ret
 
.Lcase1:
    movq    $200, (%rsi)        # *dest = 200
    ret
 
.Lcase3_5:                      # case 3 和 case 5 共用代码
    movq    $300, (%rsi)        # *dest = 300
    ret
 
.Lcase4:
    movq    $400, (%rsi)        # *dest = 400
    ret
 
.Ldefault:
    movq    $0, (%rsi)          # *dest = 0
    ret

跳转表内容

.section .rodata               # 只读数据段
.align 8                       # 8 字节对齐
.Ljump_table:
    .quad    .Lcase0            # index 0
    .quad    .Lcase1            # index 1
    .quad    .Ldefault          # index 2 (无 case 2)
    .quad    .Lcase3_5          # index 3
    .quad    .Lcase4            # index 4
    .quad    .Lcase3_5          # index 5

跳转表的完整执行流程

假设 x = 3：

1. cmpq $5, %rdi       → 3 ≤ 5，不跳转到 default
2. jmp *.Ljump_table(, %rdi, 8)
   $→$地址 $= .Ljump_table + 3 × 8$
   $→$读取表中第 3项的地址：.Lcase3_5
   $→$跳转到 .Lcase3_5
3. movq $300, (%rsi)   → *dest = 300
4. ret

跳转表的适用条件

适用场景

条件说明
case值密集例如 0,1,2,3,4,5（表大小 项）
case 数量较多通常 > 4 个 case 时跳转表才值得
值范围可映射可通过减去最小值和边界检查确定索引

不适用的场景

//值过于稀疏 $→$跳转表产生大量空白项
switch (x) {
    case 0:     ...
    case 1000:  ...
    case 2000:  ...
    // 跳转表需要 2001 项，大部分是 default
}

对于稀疏 case，编译器退化为 if-else 链。

switch 的边界检查

    cmpq    $5, %rdi            # 检查 x > 5
    ja      .Ldefault           #超出范围 $→ default$
 
    #由于 cmpq结果保证了 $x ∈ [0, 5]$
    # 可以安全地使用跳转表
    jmp     *.Ljump_table(, %rdi, 8)

ja（无符号高于）的巧妙之处在于负数在无符号比较中会被视为非常大的正数，因此也会进入 default。

// 假如 x = -1（二进制 0xFFFF...FF）
//无符号比较：$0xFFFF...FF > 5 → ja$成立 $→$跳转到 default ✓

fall-through（贯穿）行为

switch (x) {
    case 0:
        a();          // fall-through 到 case 1
    case 1:
        b();          // 如果 x=0, 执行 a() 然后 b()
        break;
}

fall-through 在汇编中体现为不插入跳转指令：

.Lcase0:
    call    a                    # 调用 a()
    # 没有跳转，自然过渡到 case 1 的代码
.Lcase1:
    call    b                    # 调用 b()
    jmp     .Lswitch_end         # break

switch 的几种翻译模式总结

场景编译器策略复杂度
case少（）if-else链 $O(n)
case 密集（范围小）跳转表 + 间接跳转O(1)
case 稀疏（范围大但有聚集）两级跳转表 / 二分查找O(log n)
case 值范围可分段决策树 + 跳转表混合混合

两级跳转表

当 case 值范围很大但集中在几个”簇”时，编译器可能使用两级跳转：

第一级：按簇划分
        │
  ┌─────┼─────┬─────┐
簇0   簇1   簇2  default
  │     │     │
  ▼     ▼     ▼
跳转表0 跳转表1 跳转表2

相关笔记

    • 间接跳转 jmp *%reg
    • if-else 链与 switch 对比
    • 循环中的 switch

链接到

关系图谱