'switch'比'if'快吗？

12 回答

• 42

  编译器可以在交换机上进行多种优化 . 我不认为经常提到的"jump-table"是非常有用的，因为只有当输入可以某种方式限制时它才有效 .

  "jump table"的C伪代码类似于this - 请注意，实际编译器需要在表格中插入某种形式的if测试，以确保输入在表格中有效 . 另请注意，它仅适用于输入是连续数字运行的特定情况 .

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

  回答您的具体问题：

  • Clang生成一个看起来像this的：

  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)
  

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

  • 要么没有足够的分支来使编译器生成跳转表，要么编译器根本不确定哪个跳转表 .

  EDIT 2014 ：熟悉LLVM优化器的人在其他地方进行了一些讨论，他们说跳转表优化在许多情况下都很重要;例如在存在具有许多值的枚举的情况下，并且在所述枚举中存在针对值的许多情况 . 也就是说，我支持我在2011年所说的内容 - 我经常看到人们在想"if I make it a switch, it'll be the same time no matter how many cases I have" - 这完全是假的 . 即使使用跳转表，您也可以获得间接跳转成本，并为每个案例支付表格中的条目;和内存带宽是现代硬件的重大优势 .

  编写代码以提高可读性 . Any compiler worth its salt is going to see an if / else if ladder and transform it into equivalent switch or vice versa if it would be faster to do so.

  回复于 2024-04-27T01:44:21+08:00
• 2

  对于你的问题：

  1.What would a basic jump table look like, in x86 or 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 是指向Jump表的指针，而 D8 09 AB 00 之类的值表示标签指针 .

  2.Is this code using a jump table? 在这种情况下不 .

  3.Why is there no performance difference in this example?

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

  4.Is there any situation in which there is a significant performance difference?

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

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

  回复于 2024-04-27T01:44:21+08:00
• 2

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

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

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

  回复于 2024-04-27T01:44:21+08:00
• 1

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

  • 差异很小

  • 只有一个结果，而不是一系列结果

  • 案件太少了

  我的结果：

  我补充说：

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

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

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

  switch (counter % 4 + 1)
  

  在您的交换机循环中，与

  const size_t c = counter % 4 + 1;
  

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

  哦，我想你也应该在测试之间重置计数器 . 事实上，你可能应该使用某种随机数而不是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 / ifs的数量减少到5并且开关功能仍然获胜 .

  回复于 2024-04-27T01:44:21+08:00
• 5

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

  • 一个简单的跳转表，如果案例排列在一个很好的长距离
    如果有很多间隙，

  • 稀疏（两级）跳转表

  • 一系列ifs，如果案例数量很少或者值不是很接近

  • 如果案例代表几组紧密间隔的范围，则为上述组合 .

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

  回复于 2024-04-27T01:44:21+08:00
• 7

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

  回复于 2024-04-27T01:44:21+08:00
• 4

  我很好奇，并看看我可以改变你的例子，让它更快地运行switch语句 .

  如果你得到40个if语句，并添加一个0 case，那么if块将比等效的switch语句运行得慢 . 我的结果如下：https://www.ideone.com/KZeCz .

  删除0案例的效果可以在这里看到：https://www.ideone.com/LFnrX .

  回复于 2024-04-27T01:44:21+08:00
• 116

  如果然后跳转到其他地方则不会跳过其他...跳转表将有一个地址表或使用哈希或类似的东西 .

  更快或更慢是主观的 . 例如，您可以将案例1作为最后一件事而不是第一件事，如果您的测试程序或真实世界程序在大多数情况下使用案例1，则此实现的代码会更慢 . 因此，根据实施情况重新安排案例列表可以产生很大的不同 .

  如果您使用了0-3而不是1-4的情况，编译器可能已经使用了跳转表，编译器应该已经找到了删除1的情况 . 也许这是少数项目 . 如果您将其设置为0 - 15或0 - 31，例如它可能已使用表格实现了它或使用了其他一些快捷方式 . 只要符合源代码的功能，编译器就可以自由选择如何实现它 . 这会导致编译器差异和版本差异以及优化差异 . 如果你想要一个跳转表，可以制作一个跳转表，如果你想要一个if-then-else树，那就制作一个if-then-else树 . 如果您希望编译器决定，请使用switch / case语句 .

  回复于 2024-04-27T01:44:21+08:00
• 31

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

  这实际上并不难解释......如果你记得错误预测的分支比正确预测的分支贵几十到几百倍 .

  在 % 20 版本中，第一个case / if始终是命中的 . 现代CPU "learn"通常采用哪些分支，哪些不是，因此它们很容易预测此分支在循环的几乎每次迭代中的行为方式 . 这就解释了为什么"if"版本过得很快;它永远不必执行第一次测试之后的任何事情，并且（正确地）预测大多数迭代的测试结果 . 显然"switch"的执行方式略有不同 - 甚至可能是跳转表，由于计算分支，它可能会很慢 .

  在 % 21 版本中，分支基本上是随机的 . 因此，它们中的许多不仅执行每次迭代，CPU无法猜测它们将以何种方式运行 . 这是跳转表（或其他"switch"优化）可能有帮助的情况 .

  很难预测一段代码将如何使用现代编译器和CPU执行，并且每一代都会变得更难 . 最好的建议是“不要打扰尝试;总是简介” . 这个建议变得更好 - 每年都能成功地忽略它的人群变得越来越小 .

  所有这些都是说我上面的解释很大程度上是猜测 . :-)

  回复于 2024-04-27T01:44:21+08:00
• 2

  请注意，当交换机未编译为跳转表时，您通常可以写入比交换机更高效的...

  （1）如果案例有一个排序，而不是对所有N的最坏情况测试，你可以写你的if来测试是在上半部分还是下半部分，然后在每一半中，二元搜索样式......导致最坏的情况是logN而不是N.

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

  回复于 2024-04-27T01:44:21+08:00
• 12

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

  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语句，只要值很密集，双向和10向测试之间的速度几乎没有差异 . 具有稀疏值的10路测试所需的时间约为具有密集值的10路测试的1.6倍 - 但即使使用稀疏值，仍然优于10路 if / else if 的两倍速度 .

  结论：仅使用4方式测试并不能真正向您展示 switch vs if / else 的性能 . 如果你看看这段代码中的数字，那么's pretty easy to interpolate the fact that for a 4-way test, we' d期望两者产生非常相似的结果（ if / else 约为2.8纳秒， switch 约为2.0） .

  回复于 2024-04-27T01:44:21+08:00
• 2

  没有 . 在大多数特殊情况下，如果你进入汇编程序并对性能进行真正的测量，那么你的问题就是错误的 . 对于给定的例子，你的想法明确地过于短暂

  counter += (4 - counter % 4);
  

  看起来我是你应该使用的正确增量表达式 .

  回复于 2024-04-27T01:44:21+08:00