switch语句中的case的顺序是否会影响性能？

Question

我有一个switch案例程序:

升序订单开关案例:

int main()
{
        int a, sc = 1;
        switch (sc)
        {
                case 1:
                        a = 1;
                        break;
                case 2:
                        a = 2;
                        break;
        }
}

汇编代码:

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 1
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, 1
        je      .L3
        cmp     eax, 2
        je      .L4
        jmp     .L2
.L3:
        mov     DWORD PTR [rbp-8], 1
        jmp     .L2
.L4:
        mov     DWORD PTR [rbp-8], 2
        nop
.L2:
        mov     eax, 0
        pop     rbp
        ret

降序开关案例:

int main()
{
        int a, sc = 1;
        switch (sc)
        {
                case 2:
                        a = 1;
                        break;
                case 1:
                        a = 2;
                        break;
        }
}

汇编代码:

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 1
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, 1
        je      .L3
        cmp     eax, 2
        jne     .L2
        mov     DWORD PTR [rbp-8], 1
        jmp     .L2
.L3:
        mov     DWORD PTR [rbp-8], 2
        nop
.L2:
        mov     eax, 0
        pop     rbp
        ret

这里,升序顺序生成的组件多于降序.

那么,如果我有更多的切换案例,那么案例的顺序会影响性能吗？

Answer 1

您正在研究未经优化的代码,因此研究它的性能并不是很有意义.如果您查看示例的优化代码,您会发现它根本不进行比较!优化器注意到switch变量sc始终具有该值1,因此它删除了unreachable case 2.

优化器还会看到变量a在分配后未使用,因此它case 1也会删除代码,并保留main()空函数.并且它删除了操作的函数prolog/epilog,rbp因为该寄存器未被使用.

因此,对于任一版本的main()函数,优化代码的结果都相同:

main:
    xor eax, eax
    ret

简而言之,对于问题中的代码,将case语句放在哪个顺序并不重要,因为根本不会生成任何代码.

请问case在一个更真实的例子为了身在何处的代码实际上是生成和使用？可能不是.请注意,即使在未经优化的生成代码中,两个版本都会case按数字顺序测试这两个值,先检查1然后检查2,而不管源代码中的顺序如何.很明显,即使在未经优化的代码中,编译器也在进行一些排序.

请务必注意Glenn和Lundin的评论:这两个部分的顺序case并不是两个例子之间的唯一变化,实际代码也不同.在其中一个中,大小写值与设置的值匹配a,但在另一个中不匹配.

编译器根据使用的实际值对switch/ casestatement 使用各种策略.他们可以使用这些示例中的一系列比较,或者可能使用跳转表.研究生成的代码可能很有意思,但与往常一样,如果性能很重要,请观察优化设置并在现实情况下对其进行测试.

Answer 2

编译器优化的switch语句是棘手的.当然,您需要启用优化(例如,尝试gcc -O2 -fverbose-asm -S使用GCC编译代码并查看生成的.s汇编程序文件).BTW在你的两个例子中我在Debian/Sid/x86-64上的GCC 7简单地给出了:

        .type   main, @function
main:
.LFB0:
        .cfi_startproc
# rsp.c:13: }
        xorl    %eax, %eax      #
        ret
        .cfi_endproc

^{(所以switch在那个生成的代码中没有任何痕迹)}

如果您需要了解编译器如何优化switch,那么有一些关于该主题的论文,例如本文.

如果我有更多的开关案例,那么案例的顺序会影响性能？

不是在一般情况下,如果你使用的是一些优化的编译器,并要求其进行优化.另请参见本.

如果这对你很重要(但它不应该对你的编译器进行微优化!),你需要进行基准测试,剖析并研究生成的汇编代码.顺便说一句,缓存未命中和寄存器分配可能比case-s的顺序更重要,所以我认为你根本不应该打扰.请记住最近计算机的大致时序估计.将cases放在最可读的顺序中(对于处理相同源代码的下一个开发人员).阅读有关线程代码的信息.如果您有客观(与性能相关)的原因来重新排序case-s(这是非常不可能的,并且在您的有生之年最多只能发生一次),请写一些解释这些原因的好评.

如果您非常关心性能,请务必进行基准测试和分析,并选择一个好的编译器并将其与相关的优化选项一起使用.也许可以尝试几种不同的优化设置(也许是几种编译器).您可能想要添加-march=native(除了-O2或-O3).你可以考虑编译和链接以-flto -O2使链接时优化,等等.你可能还需要配置文件基于优化.

顺便说一下,许多编译器都是巨大的自由软件项目(特别是GCC和Clang).如果你那么在意性能,你可能会修补编译器,通过添加一些额外的优化过程(通过扩展它分叉的源代码,通过添加一些插件GCC或一些GCC MELT扩展).这需要数月或数年的工作(特别是要了解该编译器的内部表示和组织).

^{(不要忘记考虑开发成本;在大多数情况下,它们的成本要高得多)}

Answer 3

性能主要取决于给定数据集的分支未命中数,而不是案例总数.而这又很大程度上取决于实际数据和编译器如何选择实施的开关(调度表,链接条件表达式,条件的树 - 不知道你甚至可以从C控制这一点).

Answer 4

switch语句通常是通过跳转表而不是简单的comparaisons 编译的.

因此,如果您置换案例陈述,则性能不会有任何损失.

但是,有时以连续顺序保留更多个案并且不在某些条目中使用中断/返回是有用的,以便执行流程转到下一个案例并避免重复代码.

当数字的情况之间的差异number是很大的,从一个案件到另一个,这样在case 10:和case 200000:编译器肯定不会产生跳表,因为它应该朝向指针填补约20万项,几乎所有的default:情况下,在这种情况下,它会使用comparaisons.

Answer 5

在大多数案例标签是连续的情况下,编译器通常会处理switch语句以使用跳转表而不是比较.编译器决定使用何种形式的计算跳转(如果有的话)的确切方法将因不同的实现而异.有时在switch语句中添加额外的case可以通过简化编译器生成的代码来提高性能(例如,如果代码使用案例4-11,而案例0-3以默认方式处理,则在case 0:; case 1:; case 2:; case 3:;之前添加显式default:可能会导致编译器比较操作数对12,如果不是,则使用12项跳转表.省略这些情况可能会导致编译器在将差值与8进行比较之前减去4,然后使用8项表.

尝试优化switch语句的一个难点是编译器通常比程序员更了解在给定某些输入时不同方法的性能如何变化,但程序员可能比编译器更了解程序将接收的输入分布.给出如下内容:

if (x==0)
  y++;
else switch(x)
{
  ...
}

"智能"编译器可能会认识到将代码更改为:

switch(x)
{
  case 0:
    y++;
    break;
  ...
}

可以在所有x非零的情况下消除比较,以零计算的跳跃为代价x.如果x在大多数情况下非零,那将是一个很好的交易.x然而,如果99.9%的时间为零,那可能是一个糟糕的交易.不同的编译器编写者在尝试优化前者到后者的构造方面的程度不同.