'switch'比'if'快吗？

Question

'switch'比'if'快吗？

Meh*_*dad 232 c performance assembly switch-statement jump-table

是一种switch说法实际上比更快的if声明？

我使用/Ox标志在Visual Studio 2010的x64 C++编译器上运行下面的代码:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_COUNT (1 << 29)
size_t counter = 0;

size_t testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        switch (counter % 4 + 1)
        {
            case 1: counter += 4; break;
            case 2: counter += 3; break;
            case 3: counter += 2; break;
            case 4: counter += 1; break;
        }
    }
    return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}

size_t testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = counter % 4 + 1;
        if (c == 1) { counter += 4; }
        else if (c == 2) { counter += 3; }
        else if (c == 3) { counter += 2; }
        else if (c == 4) { counter += 1; }
    }
    return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    printf("Starting...\n");
    printf("Switch statement: %u ms\n", testSwitch());
    printf("If     statement: %u ms\n", testIf());
}

Run Code Online (Sandbox Code Playgroud)

得到了这些结果:

Switch语句:5261 ms
如果语句:5196 ms

根据我所学到的,switch语句显然使用跳转表来优化分支.

问题:

在x86或x64中,基本跳转表会是什么样的？
这段代码是否使用跳转表？
为什么这个例子没有性能差异？有没有在其中有什么情况是一个显著的性能差异？

反汇编代码:

testIf:

13FE81B10 sub  rsp,48h 
13FE81B14 call qword ptr [__imp_clock (13FE81128h)] 
13FE81B1A mov  dword ptr [start],eax 
13FE81B1E mov  qword ptr [i],0 
13FE81B27 jmp  testIf+26h (13FE81B36h) 
13FE81B29 mov  rax,qword ptr [i] 
13FE81B2E inc  rax  
13FE81B31 mov  qword ptr [i],rax 
13FE81B36 cmp  qword ptr [i],20000000h 
13FE81B3F jae  testIf+0C3h (13FE81BD3h) 
13FE81B45 xor  edx,edx 
13FE81B47 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B4E mov  ecx,4 
13FE81B53 div  rax,rcx 
13FE81B56 mov  rax,rdx 
13FE81B59 inc  rax  
13FE81B5C mov  qword ptr [c],rax 
13FE81B61 cmp  qword ptr [c],1 
13FE81B67 jne  testIf+6Dh (13FE81B7Dh) 
13FE81B69 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B70 add  rax,4 
13FE81B74 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81B7B jmp  testIf+0BEh (13FE81BCEh) 
13FE81B7D cmp  qword ptr [c],2 
13FE81B83 jne  testIf+89h (13FE81B99h) 
13FE81B85 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B8C add  rax,3 
13FE81B90 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81B97 jmp  testIf+0BEh (13FE81BCEh) 
13FE81B99 cmp  qword ptr [c],3 
13FE81B9F jne  testIf+0A5h (13FE81BB5h) 
13FE81BA1 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81BA8 add  rax,2 
13FE81BAC mov  qword ptr [counter (13FE835D0h)],rax 
13FE81BB3 jmp  testIf+0BEh (13FE81BCEh) 
13FE81BB5 cmp  qword ptr [c],4 
13FE81BBB jne  testIf+0BEh (13FE81BCEh) 
13FE81BBD mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81BC4 inc  rax  
13FE81BC7 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81BCE jmp  testIf+19h (13FE81B29h) 
13FE81BD3 call qword ptr [__imp_clock (13FE81128h)] 
13FE81BD9 sub  eax,dword ptr [start] 
13FE81BDD imul eax,eax,3E8h 
13FE81BE3 cdq       
13FE81BE4 mov  ecx,3E8h 
13FE81BE9 idiv eax,ecx 
13FE81BEB cdqe      
13FE81BED add  rsp,48h 
13FE81BF1 ret

Run Code Online (Sandbox Code Playgroud)

testSwitch:

13FE81C00 sub  rsp,48h 
13FE81C04 call qword ptr [__imp_clock (13FE81128h)] 
13FE81C0A mov  dword ptr [start],eax 
13FE81C0E mov  qword ptr [i],0 
13FE81C17 jmp  testSwitch+26h (13FE81C26h) 
13FE81C19 mov  rax,qword ptr [i] 
13FE81C1E inc  rax  
13FE81C21 mov  qword ptr [i],rax 
13FE81C26 cmp  qword ptr [i],20000000h 
13FE81C2F jae  testSwitch+0C5h (13FE81CC5h) 
13FE81C35 xor  edx,edx 
13FE81C37 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C3E mov  ecx,4 
13FE81C43 div  rax,rcx 
13FE81C46 mov  rax,rdx 
13FE81C49 inc  rax  
13FE81C4C mov  qword ptr [rsp+30h],rax 
13FE81C51 cmp  qword ptr [rsp+30h],1 
13FE81C57 je   testSwitch+73h (13FE81C73h) 
13FE81C59 cmp  qword ptr [rsp+30h],2 
13FE81C5F je   testSwitch+87h (13FE81C87h) 
13FE81C61 cmp  qword ptr [rsp+30h],3 
13FE81C67 je   testSwitch+9Bh (13FE81C9Bh) 
13FE81C69 cmp  qword ptr [rsp+30h],4 
13FE81C6F je   testSwitch+0AFh (13FE81CAFh) 
13FE81C71 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C73 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C7A add  rax,4 
13FE81C7E mov  qword ptr [counter (13FE835D0h)],rax 
13FE81C85 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C87 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C8E add  rax,3 
13FE81C92 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81C99 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C9B mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81CA2 add  rax,2 
13FE81CA6 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81CAD jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81CAF mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81CB6 inc  rax  
13FE81CB9 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81CC0 jmp  testSwitch+19h (13FE81C19h) 
13FE81CC5 call qword ptr [__imp_clock (13FE81128h)] 
13FE81CCB sub  eax,dword ptr [start] 
13FE81CCF imul eax,eax,3E8h 
13FE81CD5 cdq       
13FE81CD6 mov  ecx,3E8h 
13FE81CDB idiv eax,ecx 
13FE81CDD cdqe      
13FE81CDF add  rsp,48h 
13FE81CE3 ret

Run Code Online (Sandbox Code Playgroud)

更新:

有趣的结果在这里.但不确定为什么一个更快,一个更慢.

Answer 1

Bil*_*eal 117

编译器可以在交换机上进行多种优化.我不认为经常提到的"跳转表"是一个非常有用的,因为只有当输入可以某种方式限制时它才起作用.

ç伪代码为"跳表"将像这样 -请注意,在实践中,编译器会需要插入某种形式的,如果围着桌子测试,以确保输入是在表中有效.另请注意,它仅适用于输入是连续数字运行的特定情况.

如果交换机中的分支数量非常大,编译器可以执行诸如对交换机的值使用二进制搜索之类的事情,这在我看来会是一个更有用的优化,因为它会显着提高某些部分的性能.场景,与交换机一样通用,并且不会导致更大的生成代码大小.但要看到这一点,您的测试代码将需要更多分支来查看任何差异.

回答您的具体问题:

Clang生成一个如下所示:

test_switch(char):                       # @test_switch(char)
        movl    %edi, %eax
        cmpl    $19, %edi
        jbe     .LBB0_1
        retq
.LBB0_1:
        jmpq    *.LJTI0_0(,%rax,8)
        jmp     void call<0u>()         # TAILCALL
        jmp     void call<1u>()         # TAILCALL
        jmp     void call<2u>()         # TAILCALL
        jmp     void call<3u>()         # TAILCALL
        jmp     void call<4u>()         # TAILCALL
        jmp     void call<5u>()         # TAILCALL
        jmp     void call<6u>()         # TAILCALL
        jmp     void call<7u>()         # TAILCALL
        jmp     void call<8u>()         # TAILCALL
        jmp     void call<9u>()         # TAILCALL
        jmp     void call<10u>()        # TAILCALL
        jmp     void call<11u>()        # TAILCALL
        jmp     void call<12u>()        # TAILCALL
        jmp     void call<13u>()        # TAILCALL
        jmp     void call<14u>()        # TAILCALL
        jmp     void call<15u>()        # TAILCALL
        jmp     void call<16u>()        # TAILCALL
        jmp     void call<17u>()        # TAILCALL
        jmp     void call<18u>()        # TAILCALL
        jmp     void call<19u>()        # TAILCALL
.LJTI0_0:
        .quad   .LBB0_2
        .quad   .LBB0_3
        .quad   .LBB0_4
        .quad   .LBB0_5
        .quad   .LBB0_6
        .quad   .LBB0_7
        .quad   .LBB0_8
        .quad   .LBB0_9
        .quad   .LBB0_10
        .quad   .LBB0_11
        .quad   .LBB0_12
        .quad   .LBB0_13
        .quad   .LBB0_14
        .quad   .LBB0_15
        .quad   .LBB0_16
        .quad   .LBB0_17
        .quad   .LBB0_18
        .quad   .LBB0_19
        .quad   .LBB0_20
        .quad   .LBB0_21

Run Code Online (Sandbox Code Playgroud)

我可以说它没有使用跳转表 - 4个比较指令清晰可见:

13FE81C51 cmp  qword ptr [rsp+30h],1 
13FE81C57 je   testSwitch+73h (13FE81C73h) 
13FE81C59 cmp  qword ptr [rsp+30h],2 
13FE81C5F je   testSwitch+87h (13FE81C87h) 
13FE81C61 cmp  qword ptr [rsp+30h],3 
13FE81C67 je   testSwitch+9Bh (13FE81C9Bh) 
13FE81C69 cmp  qword ptr [rsp+30h],4 
13FE81C6F je   testSwitch+0AFh (13FE81CAFh)

Run Code Online (Sandbox Code Playgroud)

基于跳转表的解决方案根本不使用比较.

没有足够的分支导致编译器生成跳转表,或者编译器根本不生成它们.我不确定哪个.

EDIT 2014:熟悉LLVM优化器的人在其他地方进行了一些讨论,他们说跳转表优化在很多情况下都很重要; 例如,在存在具有许多值的枚举的情况下,并且在所述枚举中存在针对值的许多情况.也就是说,我支持我在2011年所说的内容 - 我经常看到人们在想"如果我把它作为一个开关,那么无论我有多少例,它都会是同一时间" - 这完全是假的.即使使用跳转表,您也可以获得间接跳转成本,并为每个案例支付表格中的条目; 和内存带宽是现代硬件的重大优势.

编写代码以提高可读性.任何有价值的编译器都会看到if/else if梯形图,并将其转换为等效开关,反之亦然,如果这样做会更快.

+1实际回答问题,以及有用的信息.:-)然而,一个问题:根据我的理解,跳转表使用*间接*跳转; 那是对的吗？如果是这样,由于更难预取/流水线操作,通常不会更慢？ (2认同)
一些俏皮话 - “[switches] 仅在输入可以通过某种方式限制时才起作用”“需要在表周围插入某种形式的 if 测试以确保输入在表中有效。另请注意，它仅在特定情况下有效输入是连续数字的情况。”：完全有可能有一个稀疏填充的表，其中读取潜在指针并且仅当执行非 NULL 时才执行跳转，否则默认情况（如果有跳转），然后`switch`退出。读完这个答案后，索伦说了我想说的其他几件事。 (2认同)
"任何有价值的编译器都会看到if/else if梯形图并将其转换为等效开关,反之亦然" - 对此断言的任何支持？编译器可能会假设你的`if`子句的顺序已经过手动调整以匹配频率和相对性能需求,其中`switch`传统上被视为一个开放的邀请来优化编译器选择.好点重新跳过`switch` :-).代码大小取决于案例/范围 - 可能更好.最后,一些枚举,位字段和`char`场景本质上是有效/有界和无开销的. (2认同)

Answer 2

cry*_*ted 43

对于你的问题:

1.在x86或x64中,基本跳转表看起来是什么样的？

跳转表是一个内存地址,用于保存指向数组结构等标签的指针.以下示例将帮助您了解跳转表的外观

00B14538  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 D8 09 AB 00  Ø.«.Ø.«.Ø.«.Ø.«.
00B14548  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 00 00 00 00  Ø.«.Ø.«.Ø.«.....
00B14558  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00B14568  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

Run Code Online (Sandbox Code Playgroud)

其中00B14538是指向Jump表的指针,而值D8 09 AB 00表示标签指针.

2.这个代码使用跳转表吗？ 在这种情况下不.

3.为什么这个例子没有性能差异？

没有性能差异,因为两种情况的指令看起来都相同,没有跳转表.

4.是否存在显着性能差异的情况？

如果你有很长的if检查序列,那么在这种情况下使用跳转表会降低性能,但这会带来内存成本.

座右铭:编译器很聪明处理这种情况:)

Answer 3

Sor*_*ren 31

编译器可以自由地将switch语句编译为等同于if语句的代码,或者创建跳转表.根据什么将在一定程度取决于你在你的编译器选项中指定执行最快或产生最小的代码另一方面,它可能会选择一个 - 所以最坏的情况下这将是相同的速度,if语句

我相信编译器会做出最好的选择,并专注于使代码最具可读性的原因.

如果案例数量变得非常大,跳转表将比一系列if快得多.但是,如果值之间的步骤非常大,则跳转表可能会变大,编译器可能会选择不生成一个.

我不认为这回答了OP的问题.完全没有. (13认同)
@Soren:作为OP问题的一部分,我看到至少有3个**编号的**子问题.你只是大肆宣扬适用于所有"表现"问题的完全相同的答案 - 即你必须首先衡量.考虑一下Mehrdad可能已经测量过,并且已经将这段代码隔离开来作为热点.在这种情况下,你的答案比无价值更糟糕,这是噪音. (8认同)
@Soren:如果这是"基本问题",那么我不会对问题中的其他179条线路感到困扰,它只是一条线.:-) (5认同)
跳转表与不依赖于您的定义的内容之间存在模糊界限.我提供了关于子问题第3部分的信息. (2认同)
@wnoise:如果这是唯一正确的答案,那么永远不会有理由提出任何性能问题.然而,现实世界中有些人测量我们的软件,有时我们不知道如何测量一段代码.显而易见,Mehrdad在提出这个问题之前就已经付出了一些努力; 我认为他的具体问题不仅仅是回答问题. (2认同)

Answer 4

Bob*_*rbo 14

您如何知道您的计算机在交换机测试循环期间没有执行与测试无关的任务,并且在if测试循环期间执行的任务较少？您的测试结果不显示任何内容:

差异很小
只有一个结果,而不是一系列结果
案件太少了

我的结果:

我补充说:

printf("counter: %u\n", counter);

Run Code Online (Sandbox Code Playgroud)

到最后,以便它不会优化掉循环,因为在你的例子中从未使用过计数器,为什么编译器会执行循环？即使有这样的微基准,交换机也很快就会获胜.

您的代码的另一个问题是:

switch (counter % 4 + 1)

Run Code Online (Sandbox Code Playgroud)

在您的交换机循环中,与

const size_t c = counter % 4 + 1;

Run Code Online (Sandbox Code Playgroud)

在你的if循环中.如果你解决这个问题会有很大的不同我相信将语句放在switch语句中会激发编译器将值直接发送到CPU寄存器而不是先将它放在堆栈中.因此,这有利于switch语句而不是平衡测试.

哦,我想你也应该在测试之间重置计数器.事实上,你可能应该使用某种随机数而不是+1,+ 2,+ 3等,因为它可能会优化那些东西.作为随机数,我的意思是基于当前时间的数字.否则,编译器可以将您的两个函数转换为一个长数学运算,甚至不用任何循环.

我已经修改了Ryan的代码,足以确保编译器在代码运行之前无法解决问题:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_COUNT (1 << 26)
size_t counter = 0;

long long testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;

        switch (c)
        {
                case 1: counter += 20; break;
                case 2: counter += 33; break;
                case 3: counter += 62; break;
                case 4: counter += 15; break;
                case 5: counter += 416; break;
                case 6: counter += 3545; break;
                case 7: counter += 23; break;
                case 8: counter += 81; break;
                case 9: counter += 256; break;
                case 10: counter += 15865; break;
                case 11: counter += 3234; break;
                case 12: counter += 22345; break;
                case 13: counter += 1242; break;
                case 14: counter += 12341; break;
                case 15: counter += 41; break;
                case 16: counter += 34321; break;
                case 17: counter += 232; break;
                case 18: counter += 144231; break;
                case 19: counter += 32; break;
                case 20: counter += 1231; break;
        }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

long long testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;
        if (c == 1) { counter += 20; }
        else if (c == 2) { counter += 33; }
        else if (c == 3) { counter += 62; }
        else if (c == 4) { counter += 15; }
        else if (c == 5) { counter += 416; }
        else if (c == 6) { counter += 3545; }
        else if (c == 7) { counter += 23; }
        else if (c == 8) { counter += 81; }
        else if (c == 9) { counter += 256; }
        else if (c == 10) { counter += 15865; }
        else if (c == 11) { counter += 3234; }
        else if (c == 12) { counter += 22345; }
        else if (c == 13) { counter += 1242; }
        else if (c == 14) { counter += 12341; }
        else if (c == 15) { counter += 41; }
        else if (c == 16) { counter += 34321; }
        else if (c == 17) { counter += 232; }
        else if (c == 18) { counter += 144231; }
        else if (c == 19) { counter += 32; }
        else if (c == 20) { counter += 1231; }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    srand(time(NULL));
    printf("Starting...\n");
    printf("Switch statement: %lld ms\n", testSwitch()); fflush(stdout);
    printf("counter: %d\n", counter);
    counter = 0;
    srand(time(NULL));
    printf("If     statement: %lld ms\n", testIf()); fflush(stdout);
    printf("counter: %d\n", counter);
}

Run Code Online (Sandbox Code Playgroud)

开关:3740
if:3980

(多次尝试的结果相似)

我还将case/ifs的数量减少到5并且开关功能仍然获胜.

@BobTurbo：45983493 已经超过 12 个小时了。这是一个错字吗？ (2认同)
太好了，现在我得再去一次:) (2认同)

Answer 5

Igo*_*sky 7

一个好的优化编译器,如MSVC可以生成:

如果案件布置在一个很好的长距离范围内,一个简单的跳转表
如果有很多间隙,则为稀疏(两级)跳转表
如果案例数量很少或者值不相近,则会产生一系列ifs
如果案例代表几组紧密间隔范围,则为上述组合.

简而言之,如果开关看起来比一系列ifs慢,编译器可能只是将其转换为1.并且它可能不仅仅是每种情况的一系列比较,而是二元搜索树.请看这里的例子.

Answer 6

Jer*_*fin 7

以下是旧的（现在很难找到）bench++ 基准测试的一些结果：

Test Name:   F000003                         Class Name:  Style
CPU Time:       0.781  nanoseconds           plus or minus     0.0715
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way if/else if statement
 compare this test with F000004

Test Name:   F000004                         Class Name:  Style
CPU Time:        1.53  nanoseconds           plus or minus     0.0767
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way switch statement
 compare this test with F000003

Test Name:   F000005                         Class Name:  Style
CPU Time:        7.70  nanoseconds           plus or minus      0.385
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way if/else if statement
 compare this test with F000006

Test Name:   F000006                         Class Name:  Style
CPU Time:        2.00  nanoseconds           plus or minus     0.0999
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way switch statement
 compare this test with F000005

Test Name:   F000007                         Class Name:  Style
CPU Time:        3.41  nanoseconds           plus or minus      0.171
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way sparse switch statement
 compare this test with F000005 and F000006

Run Code Online (Sandbox Code Playgroud)

从这里我们可以看到（在这台机器上，使用这个编译器——VC++ 9.0 x64），每个if测试大约需要 0.7 纳秒。随着测试数量的增加，时间几乎完美地线性扩展。

使用 switch 语句，只要值是密集的，2 路测试和 10 路测试之间的速度几乎没有区别。使用稀疏值的 10 向测试花费的时间大约是使用密集值的 10 向测试的 1.6 倍——但即使使用稀疏值，仍然比 10 向if/的速度好两倍else if。

底线：只使用了4路测试将不能真正告诉你很多关于性能switchVS if/ else。如果您查看此代码中的数字，很容易推断出以下事实：对于 4 路测试，我们希望两者产生非常相似的结果（对于if/约 2.8 纳秒，对于else约 2.0纳秒switch）。

Answer 7

Bil*_*ter 6

我会回答2)并做一些一般性评论.2)不,您发布的汇编代码中没有跳转表.跳转表是一个跳转目标表,以及一个或两个从表中直接跳转到索引位置的指令.当有许多可能的切换目的地时,跳转表会更有意义.也许优化器知道简单的if else逻辑更快,除非目标的数量大于某个阈值.再说一次你说的20个可能性,而不是4个.

归档时间：	14 年，3 月前
查看次数：	52118 次
最近记录：	6 年，5 月前