if-else对比switch-case


if-else对比switch-case

在听CSAPP的Lecture 06 Machine Level Programming || Control的时候,里面老师回答学生问题时,说到switch-case在汇编层面会建立一个表,然后好奇这个表是什么样子的,查询了一些资料,发现也挺有趣的。

代码片段

这里对比使用的代码片段

https://godbolt.org/z/7ahx7aaxT

if-else分析

foo_ifelse(char):
        push    rbp
        mov     rbp, rsp
        mov     eax, edi
        mov     BYTE PTR [rbp-4], al
        cmp     BYTE PTR [rbp-4], 48
        je      .L2
        cmp     BYTE PTR [rbp-4], 49
        jne     .L3
.L2:
        movzx   eax, BYTE PTR [rbp-4]
        add     eax, 1
        mov     BYTE PTR [rbp-4], al
        jmp     .L4
.L3:
        cmp     BYTE PTR [rbp-4], 97
        je      .L5
        cmp     BYTE PTR [rbp-4], 98
        jne     .L6
.L5:
        movzx   eax, BYTE PTR [rbp-4]
        add     eax, 2
        mov     BYTE PTR [rbp-4], al
        jmp     .L4
.L6:
        cmp     BYTE PTR [rbp-4], 65
        je      .L7
        cmp     BYTE PTR [rbp-4], 66
        jne     .L8
.L7:
        movzx   eax, BYTE PTR [rbp-4]
        add     eax, 3
        mov     BYTE PTR [rbp-4], al
        jmp     .L4
.L8:
        movzx   eax, BYTE PTR [rbp-4]
        add     eax, 4
        mov     BYTE PTR [rbp-4], al
.L4:
        movsx   eax, BYTE PTR [rbp-4]
        pop     rbp
        ret

从上面可以看出,if-else是按照值一个一个的对比,重复使用cmp、je、jne等指令,如果满足条件就跳转,否则处理下一个值的分支,并不会对整个对比分支的选项进行整理与优化。

可以看出,如果处理1000个,甚至10000个连续分支的话,效率是非常低的(并不对其采用二分法、哈希表的优化),这时候还需要注意把命中率高的分支放在前面。

switch-case分析

foo_switch1(char)分析:

foo_switch1(char):
        push    rbp
        mov     rbp, rsp
        mov     eax, edi
        mov     BYTE PTR [rbp-4], al
        movsx   eax, BYTE PTR [rbp-4]
        cmp     eax, 98
        jg      .L11
        cmp     eax, 97
        jge     .L12
        cmp     eax, 49
        jg      .L13
        cmp     eax, 48
        jge     .L14
        jmp     .L11
.L13:
        sub     eax, 65
        cmp     eax, 1
        ja      .L11
        jmp     .L18
.L14:
        movzx   eax, BYTE PTR [rbp-4]
        add     eax, 1
        mov     BYTE PTR [rbp-4], al
        jmp     .L16
.L12:
        movzx   eax, BYTE PTR [rbp-4]
        add     eax, 2
        mov     BYTE PTR [rbp-4], al
        jmp     .L16
.L18:
        movzx   eax, BYTE PTR [rbp-4]
        add     eax, 3
        mov     BYTE PTR [rbp-4], al
        jmp     .L16
.L11:
        movzx   eax, BYTE PTR [rbp-4]
        add     eax, 4
        mov     BYTE PTR [rbp-4], al
        nop
.L16:
        movsx   eax, BYTE PTR [rbp-4]
        pop     rbp
        ret

首先编译器分析各个分支后,先与最大值进行对比,如果比它大,则直接跳转到default分支;否则,处理其他分支。在同时处理大小写字符时,编译器还有.L13的分支,将小写字母sub 65转化为处理大写字母,这也是一种优化策略。

foo_switch2(char)分析

.LC0:
        .string "a = 1"
.LC1:
        .string "a = 2"
.LC2:
        .string "a = 3"
.LC3:
        .string "a = 4"
.LC4:
        .string "a = 5"
.LC5:
        .string "a = 6"
.LC6:
        .string "other number"
foo_switch2(char):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 32
        mov     eax, edi
        mov     BYTE PTR [rbp-20], al
        mov     DWORD PTR [rbp-4], 2
        cmp     DWORD PTR [rbp-4], 6
        ja      .L20
        mov     eax, DWORD PTR [rbp-4]
        mov     rax, QWORD PTR .L22[0+rax*8]
        jmp     rax
.L22:
        .quad   .L20
        .quad   .L27
        .quad   .L26
        .quad   .L25
        .quad   .L24
        .quad   .L23
        .quad   .L21
.L27:
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:std::cout
        call    std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)
        mov     esi, OFFSET FLAT:std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)
        mov     rdi, rax
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(std::basic_ostream<char, std::char_traits<char> >& (*)(std::basic_ostream<char, std::char_traits<char> >&))
        jmp     .L28
......
......
.L20:
        mov     esi, OFFSET FLAT:.LC6
        mov     edi, OFFSET FLAT:std::cout
        call    std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)
        mov     esi, OFFSET FLAT:std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)
        mov     rdi, rax
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(std::basic_ostream<char, std::char_traits<char> >& (*)(std::basic_ostream<char, std::char_traits<char> >&))
        nop
.L28:
        nop
        leave
        ret

省略号部分和.L27部分类似,只是将开始的.LC0做替换。

首先与switch-case语句的最大值比较,如果大于可以直接跳转到default语句;否则,加载局部变量的值到eax中,根据这个值作为索引,计算跳转的地址。

标记.L22.quad表示当前位置分配了8个字节的存储空间,后面跟着的数值(或标签)会被放置在这 8 个字节的内存空间中,通常用于定义 64 位整数或指针类型的数据。此处7个.quad代表这段代码包含了7 个 64 位值的数据表,用于实现之前提到的 switch-case 结构中的跳转表。

总结

如果if-else不进行二分、哈希等优化,switch-case结构的执行效率高,是以空间(跳转表)换时间的一种策略。

巨人的肩膀

https://www.jeremyjone.com/546/

https://www.eet-china.com/mp/a19622.html


文章作者: AllenMirac
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 AllenMirac !
  目录