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());
}
并得到了这些结果:
Switch 语句:5261 毫秒 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
更新:
有趣的结果 here。不过,不知道为什么一个更快,一个更慢。
5196 vs. 5261 shouldn't be enough to actually care
-->我不确定您是否误解了这个问题,或者我是否误解了您的评论,但我的问题的重点不是要问为什么 没有 有区别? (我有没有声称这是一个值得关注的重大差异?)
编译器可以对开关进行多种优化。我不认为经常提到的“跳转表”是一个非常有用的,因为它只在输入可以以某种方式有界时才有效。
“跳转表”的 C 伪代码类似于 this - 请注意,编译器实际上需要在表周围插入某种形式的 if 测试,以确保输入在表中有效。另请注意,它仅适用于输入是一系列连续数字的特定情况。
如果开关中的分支数量非常大,编译器可以执行诸如对开关的值使用二进制搜索之类的操作,这(在我看来)将是一个更有用的优化,因为它确实在某些情况下显着提高了性能场景,与 switch 一样通用,并且不会导致更大的生成代码大小。但是要看到这一点,您的测试代码需要更多的分支才能看到任何差异。
要回答您的具体问题:
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_1_12 .quad .LBB0_1_12.四边形 .LBB0_14 .quad .LBB 0_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 13FE81C9Bh) 13FE81C69 cmp qword ptr [rsp+30h],4 13FE81C6F je testSwitch+0AFh (13FE81CAFh) 基于跳转表的解决方案根本不使用比较。没有足够的分支导致编译器生成跳转表,或者您的编译器根本不生成它们。我不确定是哪个。
编辑 2014:熟悉 LLVM 优化器的人在其他地方进行了一些讨论,称跳转表优化在许多情况下都很重要;例如,在存在具有许多值的枚举和许多针对所述枚举中的值的情况的情况下。也就是说,我坚持我在 2011 年所说的话——我经常看到人们在想“如果我做出改变,不管我有多少案例,它都会是同一时间”——这完全是错误的。即使使用跳转表,您也会获得间接跳转成本,并且您需要为每种情况下的表中的条目付费;内存带宽对现代硬件来说是一件大事。
对于你的问题:
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 ................
https://i.stack.imgur.com/RTTwM.png
其中 00B14538 是跳转表的指针,像 D8 09 AB 00 这样的值代表标签指针。
2.这段代码是否使用了跳转表?在这种情况下不。
3.为什么这个例子没有性能差异?
没有性能差异,因为两种情况的指令看起来相同,没有跳转表。
4.是否存在性能差异显着的情况?
如果您有很长的 if 检查序列,那么在这种情况下,使用跳转表可以提高性能(如果分支/jmp 指令不能近乎完美地预测,则它们会很昂贵)但会带来内存成本。
所有比较指令的代码也有一定的大小,因此特别是对于 32 位指针或偏移量,单个跳转表查找在可执行文件中可能不会花费更多的大小。
结论:编译器足够聪明地处理这种情况并生成适当的指令:)
gcc -S
输出会很好:一系列 .long L1
/ .long L2
表条目比一个 hexdump,对想要学习如何查看编译器的人更有用。 (虽然我猜你只是看看开关代码,看看它是间接 jmp 还是一堆 jcc)。
编译器可以自由地将 switch 语句编译为相当于 if 语句的代码,或者创建一个跳转表。它可能会根据您在编译器选项中指定的内容,根据最快的执行速度或生成最小的代码来选择另一个 - 所以最坏的情况下,它与 if 语句的速度相同
我相信编译器会做出最好的选择,并专注于使代码最易读的东西。
如果案例数量变得非常大,则跳转表将比一系列 if 快得多。但是,如果值之间的步长很大,那么跳转表可能会变大,编译器可能会选择不生成。
你怎么知道你的计算机在 switch 测试循环期间没有执行一些与测试无关的任务,而在 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
(多次尝试的类似结果)
我还将案例/ifs 的数量减少到 5 个,并且 switch 功能仍然获胜。
print
语句?我在整个程序的末尾添加了它,并没有发现任何区别。我也不明白另一个的“问题”是什么......介意解释“非常大的区别”是什么?
一个好的优化编译器比如 MSVC 可以生成:
一个简单的跳转表,如果案例被安排在一个很好的长范围内,一个稀疏(两级)跳转表,如果有很多间隙,如果案例数量很少或值不接近,则一系列 ifs 以上的组合如果这些案例代表几组紧密间隔的范围。
简而言之,如果开关看起来比一系列 if 慢,编译器可能只是将其转换为一个。而且它可能不仅仅是每个案例的一系列比较,而是一个二叉搜索树。有关示例,请参见 here。
以下是旧的(现在很难找到)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
从这里我们可以看到(在这台机器上,使用这个编译器——VC++ 9.0 x64),每个 if
测试大约需要 0.7 纳秒。随着测试数量的增加,时间几乎完全线性地缩放。
使用 switch 语句,只要值密集,2 路和 10 路测试之间的速度几乎没有差异。具有稀疏值的 10 路测试所花费的时间大约是具有密集值的 10 路测试的 1.6 倍 - 但即使使用稀疏值,仍然比 10 路 if
/else if
的速度快两倍.
底线:仅使用 4 路测试不会真正向您展示 switch
与 if
/else
的性能太多。如果您查看这段代码中的数字,很容易推断出这样一个事实:对于 4 路测试,我们预计两者会产生相当相似的结果(对于 { 约 2.8 纳秒2}/else
,对于 switch
约 2.0)。
if
/else
链的末端不匹配或仅匹配的值而不是分散它们等,那么很难知道该怎么做。可以t 在 10 分钟谷歌搜索后找到 bench++
来源。
我会回答 2) 并发表一些一般性评论。 2)不,您发布的汇编代码中没有跳转表。跳转表是一个跳转目标表,以及从表中直接跳转到索引位置的一个或两个指令。当有许多可能的切换目标时,跳转表会更有意义。也许优化器知道简单的 if else 逻辑更快,除非目的地的数量大于某个阈值。用 20 种可能性而不是 4 种可能性再次尝试您的示例。
我很感兴趣,并查看了我可以对您的示例进行哪些更改以使其更快地运行 switch 语句。
如果你达到 40 个 if 语句,并添加一个 0 案例,那么 if 块将比等效的 switch 语句运行得慢。我在这里有结果:https://www.ideone.com/KZeCz。
去掉 0 大小写的效果可以看这里:https://www.ideone.com/LFnrX。
请注意,当开关未编译为跳转表时,您通常可以编写 if's 比 switch 更有效...
(1)如果案例有一个排序,而不是所有N的最坏情况测试,你可以编写你的if来测试上半部分或下半部分,然后在每一半中,二进制搜索风格......导致最坏的情况是 logN 而不是 N
(2) 如果某些案例/组比其他案例更频繁,那么首先设计你的 if 来隔离这些案例可以加快平均时间
不,这些是 if then jump else if then jump else ...跳转表将有一个地址表或使用哈希或类似的东西。
更快或更慢是主观的。例如,您可以让案例 1 成为最后一件事而不是第一个,如果您的测试程序或现实世界的程序在大多数情况下使用案例 1,则此实现的代码会变慢。因此,仅根据实施情况重新排列案例列表就可以产生很大的不同。
如果您使用案例 0-3 而不是 1-4,编译器可能使用了跳转表,编译器应该已经想出删除您的 +1。也许这是少数项目。例如,如果您将其设为 0 - 15 或 0 - 31,它可能已经使用表格实现了它或使用了其他快捷方式。只要符合源代码的功能,编译器就可以自由选择实现方式。这涉及编译器差异和版本差异以及优化差异。如果你想要一个跳转表,就创建一个跳转表,如果你想要一个 if-then-else 树,就创建一个 if-then-else 树。如果您希望编译器做出决定,请使用 switch/case 语句。
不过,不知道为什么一个更快,一个更慢。
这实际上并不太难解释......如果您还记得错误预测的分支比正确预测的分支昂贵数十到数百倍。
在 % 20
版本中,第一个 case/if 始终是命中的那个。现代 CPU“学习”哪些分支通常被采用,哪些不被采用,因此它们可以轻松预测该分支在循环的几乎每次迭代中的表现。这就解释了为什么“如果”版本会成功;它永远不必在第一次测试之后执行任何操作,并且它(正确地)预测了大多数迭代的测试结果。显然,“开关”的实现方式略有不同——甚至可能是一个跳转表,由于计算分支,它可能会很慢。
在 % 21
版本中,分支基本上是随机的。因此,它们中的许多不仅每次迭代都执行,CPU 也无法猜测它们会走哪条路。在这种情况下,跳转表(或其他“切换”优化)可能会有所帮助。
很难预测一段代码将如何使用现代编译器和 CPU 执行,并且每一代都变得更加困难。最好的建议是“甚至不要费心去尝试;总是配置文件”。这个建议每年都会变得更好——并且能够成功忽略它的人越来越少。
所有这些都是说我上面的解释很大程度上是一个猜测。 :-)
没有任何。在大多数特殊情况下,当您进入汇编程序并进行实际性能测量时,您的问题完全是错误的。对于给定的例子,你的想法肯定太短了,因为
counter += (4 - counter % 4);
在我看来是您应该使用的正确增量表达式。
switch
退出。在阅读了这个答案后,索伦说了我想说的其他几件事。if
子句的顺序已经过手动调整以匹配频率和相对性能需求,而switch
传统上被视为公开邀请,以优化编译器选择的任何内容。好点重新跳过switch
:-)。代码大小取决于案例/范围 - 可能会更好。最后,一些枚举、位域和char
场景本质上是有效的/有界的 &免费的开销。