& # 39;开关# 39;比'if'?

小开

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

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

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

小开

最佳答案

编译器可以对开关进行了几种优化。我不认为经常提到的“跳跃表”是非常有用的，因为它只在输入可以以某种方式被限制时才有效。

C“跳转表”的伪代码类似这——注意，编译器在实践中需要在表周围插入某种形式的if测试，以确保输入在表中是有效的。还要注意，它只在输入是连续数字的特定情况下才有效。

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

回答您的具体问题:

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

I can say that it is not using a jump table -- 4 comparison instructions are clearly visible:

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)

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

要么是因为没有足够的分支导致编译器生成跳转表，要么是因为编译器根本没有生成它们。我不确定是哪个。

编辑2014:在其他地方有一些来自熟悉LLVM优化器的人的讨论，他们说跳转表优化在许多情况下都是重要的;例如，在枚举中有多个值和多个针对该枚举值的情况。也就是说，我坚持我在2011年所说的——我经常看到人们在想“如果我做了一个转换，不管我有多少病例，它都是一样的”——这是完全错误的。即使使用跳转表，你也会得到间接跳转成本，你需要为每种情况下的表项付费;内存带宽在现代硬件上是一个大问题。

为可读性编写代码。任何有价值的编译器都会看到一个if / else if阶梯，并将其转换为等效的开关，反之亦然，如果这样做会更快的话。

小开

我会回答2)并做一些一般性的评论。2)不，在你发布的汇编代码中没有跳转表。跳转表是一个包含跳转目的地的表，以及一个或两个直接从表跳转到索引位置的指令。当有许多可能的切换目的地时，跳转表更有意义。也许优化器知道简单的if else逻辑更快，除非目的地的数量大于某个阈值。再试一遍你的例子，假设是20种可能性而不是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);
}

< br > < p >开关:3740 如果:3980 < / p >

(多次尝试的结果相似)

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

小开

关于你的问题:

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  ................

其中00 b14538是指向跳转表的指针，而像D8 09 ab 00这样的值表示标签指针。

<强> 2。这段代码是否使用了跳转表?

3.为什么在这个例子中没有性能差异?

没有性能差异，因为这两种情况下的指令看起来是一样的，没有跳转表。

4.是否存在存在显著性能差异的情况?

如果你有很长的如果检查序列，在这种情况下，使用跳转表可以提高性能(分支/jmp指令是昂贵的，如果它们不能近乎完美地预测)，但要付出内存的代价。

所有比较指令的代码也有一定的大小，因此，特别是使用32位指针或偏移量时，单个跳转表查找在可执行文件中可能不会占用太多的大小。

结论:编译器是足够聪明的处理这种情况，并生成适当的指令:)

小开

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

counter += (4 - counter % 4);

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

小开

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

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

如果你使用的是0-3而不是1-4的情况，编译器可能已经使用了一个跳转表，编译器应该已经知道如何删除你的+1。也许是因为物品数量太少。例如，如果你把它设为0 - 15或0 - 31，它可能会用表格或其他快捷方式实现它。编译器可以自由选择实现的方式，只要它满足源代码的功能。这涉及到编译器的差异，版本的差异和优化的差异。如果你想要一个跳转表，就做一个跳转表，如果你想要一个If -then-else树，就做一个If -then-else树。如果你想让编译器来决定，使用switch/case语句。

小开

我对此很感兴趣，并查看了可以对您的示例进行哪些更改以使其更快地运行switch语句。

如果你有40个If语句，并添加一个0大小写，那么If块将比等效的switch语句运行得慢。我在这里有结果:https://www.ideone.com/KZeCz。

删除0大小写的效果可以在这里看到:https://www.ideone.com/LFnrX。

小开

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

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

在% 20版本中，第一个case/if总是命中的那个。现代cpu“学习”哪些分支通常被占用，哪些没有，所以它们可以很容易地预测这个分支在几乎每次循环迭代中的行为。这就解释了为什么“如果”版本会飞起来;它从来不需要执行第一次测试之后的任何事情，并且它(正确地)预测了大多数迭代的测试结果。显然，“切换”的实现略有不同——甚至可能是一个跳跃表，由于计算分支，它可能会很慢。

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

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

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

小开

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

一个简单的跳跃表，如果情况被安排在一个很好的长范围
如果有很多空隙，则使用稀疏(两级)跳转表
如果案例数量很小或值为不靠近
如果情况代表几组李的间隔太近范围。< / >

简而言之，如果转换看起来比一系列if慢，编译器可能会直接将它转换为一个if。它很可能不仅仅是每个情况下的比较序列，而是一个二叉搜索树。参见在这里的例子。

小开

注意，当一个switch没有编译到一个跳转表时，你经常可以写if比switch更有效…

(1)如果情况是有序的，而不是对所有N进行最坏的情况测试，你可以写你的if在上半部分或下半部分测试if，然后在每个一半，二分搜索风格…结果最坏的情况是logN而不是N

(2)如果某些情况/组比其他情况更频繁，那么设计你的if首先隔离这些情况可以加快平均时间

小开

以下是旧的(现在很难找到)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-way测试并不能真正告诉你多关于switch vs if/else的性能。如果你看一下这段代码中的数字，很容易插入一个事实，即对于4路测试，我们期望两者产生漂亮的相似的结果(if/else为~2.8纳秒，switch为~2.0纳秒)。

& # 39;开关# 39;比'if'?

问题:

更新: