“开关”比“如果”更快？
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()); }
并得到这些结果：
开关语句：5261毫秒
如果声明：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
更新：
这里和这里有趣的结果。 不知道为什么一个更快，一个更慢。
编译器可以在交换机上进行几种优化。 我不认为经常提到的“跳转表”是一个非常有用的跳转表，因为它只有在input可以被限制的情况下才起作用。
C“跳转表”的伪代码应该是这样的 – 请注意，编译器在实践中需要插入某种forms的if test来确保表中的input有效。 还要注意，它只适用于input是连续数字的特定情况。
如果交换机中的分支数量非常大，编译器可以做一些事情，比如在交换机上使用二进制search，这在我看来是一个更有用的优化，因为它可以显着提高一些性能场景，与交换机一样通用，并且不会导致更大的生成代码大小。 但是要看到这一点，你的testing代码将需要很多分支来看看有什么不同。
回答你的具体问题：
-
铿锵生成一个看起来像这样的 ：
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 -
我可以说，它不使用跳转表 – 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)基于跳转表的解决scheme根本不使用比较。
- 没有足够的分支导致编译器生成跳转表，或者编译器根本不生成它们。 我不确定哪个。
2014年编辑 ：在其他地方已经有人从熟悉LLVM优化器的人那里进行了一些讨论，他们认为跳转表优化在很多情况下都很重要; 例如在所述列举中存在许多值的情况下枚举并且存在许多情况下的值。 也就是说，我坚持2011年以上所说的话 – 我经常看到有人在思考：“如果我把它变成一个开关，不pipe我有多less个案子，都是一样的 – 这完全是错误的。 即使有跳台，您也可以获得间接跳转成本，并为每种情况支付表中的条目; 内存带宽是现代硬件上的一大难题。
编写可读性代码。 任何值得使用的编译器都会看到一个if / else if梯形图，并将其转换为等效的开关，反之亦然，如果这样做会更快。
对你的问题：
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 ................
其中00B14538是指向跳转表的指针，像D8 09 AB 00这样的值代表标签指针。
2.这个代码使用跳转表吗？ 没有在这种情况下。
3.为什么这个例子没有性能差异？
没有性能差异，因为两种情况下的指令看起来都一样，没有跳转表。
4.是否存在显着的性能差异？
如果检查的时间很长， 那么使用跳转表会降低性能而不是内存的成本。
座右铭：编译器是足够聪明的处理这种情况下:)
编译器可以自由地将switch语句编译为等价于if语句的代码，或者创build一个跳转表。 它可能会根据执行速度最快的代码来select一个，或者根据您在编译器选项中指定的内容，在某种程度上生成最小的代码 – 最坏的情况下，它将与if语句的速度相同
我相信编译器会做出最好的select，并专注于使代码具有最高可读性的原因。
如果案例数量变得非常大，跳转表将比一系列if快得多。 但是，如果值之间的步骤非常大，则跳转表可能变大，编译器可能会select不生成一个跳转表。
您如何知道您的计算机在切换testing循环期间没有执行与testing无关的任务，并且在testing循环期间执行的任务较less？ 您的testing结果不显示任何内容：
- 差别非常小
- 只有一个结果，而不是一系列的结果
- 这种情况太less了
我的结果：
我补充说：
printf("counter: %u\n", counter);
到最后，所以它不会优化掉循环，因为计数器从来没有在你的例子中使用，那么为什么编译器会执行循环？ 即使这样一个微型基准，转换器总是赢得胜利。
你的代码的另一个问题是：
switch (counter % 4 + 1)
在你的开关循环中，与
const size_t c = counter % 4 + 1;
在你的循环中。 如果你解决这个问题，那么这个差别会非常大 我相信把这个语句放在switch语句中会引起编译器直接把值发送到CPU寄存器，而不是先把它放在堆栈上。 因此，这有利于交换声明，而不是一个平衡的testing。
哦，我想你也应该在testing之间重置计数器。 事实上，你可能应该使用某种随机数而不是+1，+2，+3等，因为它可能会优化那里的东西。 例如，以随机数字表示基于当前时间的数字。 否则，编译器可以将你的两个函数变成一个长math运算，甚至不会打扰任何循环。
我修改了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
（多次尝试的结果类似）
我也把案例数量减less到5个，交换机function还是赢了。
我会回答2）并提出一些一般性意见。 2）不，在您发布的汇编代码中没有跳转表。 跳转表是一个跳转目标表，以及一个或两个指令直接跳转到表中的索引位置。 当有许多可能的切换目标时，跳转表会更有意义。 也许优化器知道这么简单，否则逻辑速度更快，除非目标的数量大于某个阈值。 再说20个可能性而不是4个例子。
一个好的优化编译器如MSVC可以生成：
- 一个简单的跳转表，如果案件安排在一个很好的远程
- 一个稀疏的（两级）跳转表，如果有很多的差距
- 如果案例数量小或者数值不紧密，则为一系列if
- 如果情况代表几组紧密间隔的范围，则为上述的组合。
总之，如果交换机看起来比一系列的if要慢，编译器可能会把它转换成一个。 它可能不仅仅是每个案例的一个比较序列，而是一个二叉search树。 看这里的例子。
我很好奇，看看我可以改变你的例子，让它更快地运行switch语句。
如果你得到了40个if语句，并且增加了一个0的话，那么if语句块的运行速度将比等效的switch语句慢。 我在这里有结果： https ： //www.ideone.com/KZeCz 。
删除0的情况的效果可以在这里看到： https ： //www.ideone.com/LFnrX 。
没有这些是如果然后跳其他如果然后跳其他…跳转表将有地址表或使用散列或类似的东西。
更快或更慢是主观的。 例如，您可以将案例1作为最后一件事情，而不是第一件事情，如果您的testing程序或现实世界程序使用案例1，则大多数情况下代码在此实施中会比较慢。 所以只要根据实施情况重新安排案例列表就可以发挥很大的作用。
如果你使用的是0-3而不是1-4，那么编译器可能使用了一个跳转表，编译器应该已经find了删除你的+1的方法。 也许这是less数的项目。 例如，你可以用0到15或0到31来实现它，或者使用其他的快捷方式。 只要编译器符合源代码的function，编译器就可以自由select它是如何实现的。 这会导致编译器差异和版本差异以及优化差异。 如果你想要一个跳转表，build立一个跳转表，如果你想要一个if-then-else树，就build立一个if-then-else树。 如果你想编译器来决定，使用switch / case语句。
不知道为什么一个更快，一个更慢。
这实际上不难解释…如果您记得错误预测的分支比正确预测的分支要贵几十到几百倍。
在% 20版本中，第一个case / if总是打的。 现代的CPU可以“学习”哪些分支通常被采用，哪些不是，因此他们可以很容易地预测这个分支在几乎每一次循环中的performance。 这解释了为什么“如果”版本飞行; 它不必执行任何超过第一个testing的任何事情，并且（大部分迭代）它（正确地）预测该testing的结果。 很显然，“开关”的实现方式略有不同 – 甚至可能是一个跳转表，由于计算的分支，跳转表可能会很慢。
在% 21版本中，分支本质上是随机的。 所以不仅他们中的许多人执行每一次迭代，CPU不能猜测他们将走哪条路。 跳转表（或其他“开关”优化）可能会有所帮助。
预测现代编译器和CPU如何执行一段代码是非常困难的，每一代都会变得越来越困难。 最好的build议是“不要打扰尝试，总是configuration文件”。 这个build议变得越来越好了 – 那些可以忽略它的人每年都会变得越来越小。
所有这些都是说我上面的解释在很大程度上是一个猜测。 🙂
请注意，当一个开关没有被编译到一个跳转表中时，你可以经常写入if比开关更有效率。
（1）如果案例有一个sorting，而不是所有N的最坏情况下的testing，你可以写你的if来testing，如果在上半部分或下半部分，然后在每一半的二分search风格…导致最坏的情况是logN而不是N
（2）如果某些个案/群体比其他个案更为频繁，那么devise你的if来隔离这些个案可以加快平均时间
没有。 在大多数情况下，如果您进入汇编程序并对性能进行实际测量，您的问题就是错误的。 对于给定的例子，你的想法自那时以来确定得太短了
counter += (4 - counter % 4);
在我看来是你应该使用的正确的增量expression式。
以下是一些旧的（现在很难find的）bench ++基准testing结果：
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
从这里我们可以看到（在这台机器上，用这个编译器 – VC ++ 9.0 x64），每个testing需要大约0.7纳秒。 随着testing次数的增加，时间尺度几乎完美地线性化。
使用switch语句，只要值很密集，2路和10路testing的速度几乎没有区别。 具有稀疏值的10路testing的时间约为密度值的10路testing的1.6倍，但即使是稀疏值，仍然比10路if / else if的速度的两倍还要好。
底线：只使用4路testing并不能真正显示您对switch和vs / else的性能。 如果从这个代码看数字，插入这样一个事实非常容易：对于一个4路testing，我们希望两者产生非常相似的结果（对于一个if / else〜2.8纳秒，对于switch ）。
