switch语句真的比if语句快吗?

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

#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());
}

并得到了这些结果:

Switch语句:5261 ms If语句:5196毫秒

据我所知,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       

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       

更新:

有趣的结果。但不知道为什么一个更快,一个更慢。


当前回答

一个也没有。在大多数特定的情况下,当您进入汇编程序并进行真正的性能测量时,您的问题是错误的。对于给定的例子,你的想法显然太短了

counter += (4 - counter % 4);

在我看来,这是正确的增量表达式,你应该使用。

其他回答

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

差别非常小 只有一个结果,而不是一系列的结果 病例太少了

我的结果:

我添加:

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

到最后,这样它就不会优化循环,因为计数器在你的例子中从未使用过,那么为什么编译器要执行循环?立即,即使在这样的微观基准下,转换也总是获胜。

你代码的另一个问题是:

switch (counter % 4 + 1)

在你的开关循环中,相对

const size_t c = counter % 4 + 1; 

在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);
} 

开关:3740 如果:3980

(多次尝试的结果相似)

我还将case /if的数量减少到5,切换功能仍然获胜。

不,这些是if then跳转else if then跳转else。跳转表会有一个地址表或者使用散列之类的。

快或慢是主观的。例如,您可以将用例1作为最后一个而不是第一个,如果您的测试程序或实际应用程序在大多数情况下使用用例1,那么这种实现的代码将会变慢。因此,仅仅根据实现重新排列案例列表,就可以产生很大的不同。

If you had used cases 0-3 instead of 1-4 the compiler might have used a jump table, the compiler should have figured out removing your +1 anyway. Perhaps it was the small number of items. Had you made it 0 - 15 or 0 - 31 for example it may have implemented it with a table or used some other shortcut. The compiler is free to choose how it implements things so long as it meets the functionality of the source code. And this gets into compiler differences and version differences and optimization differences. If you want a jump table, make a jump table, if you want an if-then-else tree make an if-then-else tree. If you want the compiler to decide, use a switch/case statement.

但不知道为什么一个更快,一个更慢。

这其实不难解释……如果你还记得错误预测的分支比正确预测的分支贵几十到几百倍。

In the % 20 version, the first case/if is always the one that hits. Modern CPUs "learn" which branches are usually taken and which are not, so they can easily predict how this branch will behave on almost every iteration of the loop. That explains why the "if" version flies; it never has to execute anything past the first test, and it (correctly) predicts the result of that test for most of the iterations. Obviously the "switch" is implemented slightly differently -- perhaps even a jump table, which can be slow thanks to the computed branch.

在% 21版本中,分支基本上是随机的。因此,不仅每次迭代都有许多线程执行,CPU也无法猜测它们将朝哪个方向运行。在这种情况下,跳转表(或其他“切换”优化)可能会有所帮助。

很难预测一段代码在现代编译器和CPU上的表现,而且每一代都会变得更加困难。最好的建议是:“连试都不用试;总是概要”。每年,这种建议都会变得越来越好,而能够成功忽略它的人也会越来越少。

所有这些都是说,我上面的解释在很大程度上是一种猜测。: -)

一个也没有。在大多数特定的情况下,当您进入汇编程序并进行真正的性能测量时,您的问题是错误的。对于给定的例子,你的想法显然太短了

counter += (4 - counter % 4);

在我看来,这是正确的增量表达式,你应该使用。

编译器可以自由地将switch语句编译为相当于if-statement的代码,或者创建一个跳转表。它可能会根据你在编译器选项中指定的内容来选择一个执行最快的语句,或者生成最小的代码——所以最坏的情况下它将与if语句相同的速度

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

如果情况的数量变得非常大,那么跳转表将比一系列的If快得多。但是,如果值之间的步长非常大,那么跳转表可能会变得很大,编译器可能会选择不生成一个。