c切换和跳转表 [英] c switch and jump tables

问题描述

我的理解是，c / c ++中的switch语句有时会编译为跳转表。

It is my understanding that a switch statement in c/c++ will sometimes compile to a jump table. My question is, are there any thumb rules to assure that?

在我的例子中，我做了这样的事情：

In my case I'm doing something like this:

enum myenum{
MY_CASE0= 0,
MY_CASE0= 1, 
.
.
.
};

switch(foo)
{
  case MY_CASE0:
  //do stuff
  break;
  case MY_CASE1:
  //do stuff
  break;
 .
 .
 .
}

我按顺序覆盖从1到n的所有情况。是否可以安全地假设它将编译为跳转表？
原来的代码是一个长而乱的如果else 语句，所以至少我获得一些可读性。

I cover all the cases from 1 to n by order. Is safe to assume it will compile to a jump table? The original code was a long and messy if else statement, so at the very least I gain some readability.

推荐答案

一个好的编译器可以并且将在跳转表，链接if / else或组合之间进行选择。设计不良的编译器可能不会做出这样的选择，甚至可能产生非常坏的代码为交换块。但任何体面的编译器应该产生开关块的有效代码。 T

A good compiler can and will choose between a jump table, a chained if/else or a combination. A poorly designed compiler may not make such a choice - and may even produce very bad code for switch-blocks. But any decent compiler should produce efficient code for switch-blocks. T

这里的主要决定因素是，编译器可以选择if / else当数字相隔很远[而不是简单的（例如除以2,4,8， 16，256等）改变为更接近的值]，例如

he major decision factor here is that the compiler may choose if/else when the numbers are far apart [and not trivially (e.g. dividing by 2, 4, 8, 16, 256 etc) changed to a closer value], e.g.

 switch(x)
 {
    case 1:
     ...
    case 4912:
     ...
    case 11211:
     ...
    case 19102:
     ...
 }

需要至少19102 * 2字节的跳转表。

would require a jump table of at least 19102 * 2 bytes.

另一方面，如果数字接近，编译器通常会使用可跳转。

On the other hand, if the numbers are close together, the compiler will typically use a jumptable.

即使它是一个 if / else 类型的设计，它通常会做一个二分搜索我们采用上面的例子：

Even if it's a if/else type of design, it will typically do a "binary search" - if we take the above example:

 if (x <= 4912)
 {
     if (x == 1)
     {
        ....
     }
     else if (x == 4912)
     {
         .... 
     }
 } else {
     if (x == 11211)
     {
         ....
     }
     else if (x == 19102)
     {
         ...
     }
 }

如果我们有LOTS的情况下，这种方法将嵌套相当深，人类可能会在三或四级深度后丢失（要记住，每个如果开始在范围的MIDDLE的某一点），但它减少由log2（n）的测试数目，其中n是选择的数目。这肯定比天真的方法更有效率

If we have LOTS of cases, this approach will nest quite deep, and humans will probably get lost after three or four levels of depth (bearing in mind that each if starts at some point in the MIDDLE of the range), but it reduces the number of tests by a log2(n) where n is the number of choices. It is certainly a lot more efficient than the naive approach of

if (x == first value) ... 
else if (x == second value) ... 
else if (x == third value) ... 
..
else if (x == nth value) ... 
else ... 

如果某些值放在if-else链的开头，但是假设你可以确定在运行代码之前最常见的是什么。

This can be slightly better if certain values are put at the beginning of the if-else chain, but that assumes you can determine what is the most common before running the code.

如果性能对您的案例至关重要，那么您需要对两个备选方案进行基准测试。但我的猜测是，只是写代码作为一个开关将使代码更清晰，同时运行至少一样快，如果不是更快。

If performance is CRITICAL to your case, then you need to benchmark the two alternatives. But my guess is that just writing the code as a switch will make the code much clearer, and at the same time run at least as fast, if not faster.

这篇关于c切换和跳转表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！