C切换和跳转表

Question

根据我的理解，c/c++中的switch语句有时会编译成跳转表。我的问题是，有没有什么经验法则可以保证这一点?

在我的例子中，我是这样做的:

enum myenum{
MY_CASE0= 0,
MY_CASE0= 1, 
.
.
.
};
switch(foo)
{
  case MY_CASE0:
  //do stuff
  break;
  case MY_CASE1:
  //do stuff
  break;
 .
 .
 .
}

按顺序涵盖了从1到n的所有情况。假设它将编译为跳转表是否安全?原始代码是一个冗长而混乱的if else语句，因此至少我获得了一些可读性。

Answer 1

一个好的编译器可以并且将在跳转表，链接if/else或组合之间进行选择。设计糟糕的编译器可能不会做出这样的选择——甚至可能为开关块生成非常糟糕的代码。但是任何像样的编译器都应该为开关块生成高效的代码。T

这里的主要决策因素是编译器可能会选择if/else当数字相差很大[而不是简单地(例如除以2,4,8,16,256等)改变为更接近的值]，例如

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

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

另一方面，如果两个数字靠得很近，编译器通常会使用跳表。

即使它是一个if/else类型的设计，它通常会做一个"二进制搜索"——如果我们以上面的例子为例:

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

如果我们有很多情况，这种方法将嵌套得相当深，人类可能会在三到四个层次的深度后迷失方向(记住，每个If都是从范围的中间点开始的)，但它减少了log2(n)的测试次数，其中n是选择的数量。这当然比

的简单方法要有效得多。

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

如果将某些值放在if-else链的开头，这可能会稍微好一些，但前提是您可以在运行代码之前确定哪些是最常见的。

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

Answer 2

编译器当然可以将任何C/c++切换转换为跳转表，但编译器会为了效率而这样做。问问你自己，如果我正在编写一个编译器，并且我刚刚为switch/case语句构建了一个解析树，我会怎么做?我研究了编译器的设计和构造，下面是一些决定，

如何帮助编译器决定实现一个跳转表:

• 大小写值为小整数(0,1,2,3，…)
• 大小写值在一个紧凑的范围内(很少的洞，记住默认值是一个选项)
• 有足够的情况使优化值得(> N，检查编译器源代码以找到常数)
• 聪明的编译器可以在跳跃表索引中减去/添加一个常量，如果范围很紧凑(例如:1000,1001,1002,1003,1004,1005等)
• 避免跌落和转移控制(转到，继续)
• 只在每个case结束时换行一次

虽然编译器之间的机制可能不同，但编译器本质上是创建未命名的函数(好吧，可能不是函数，因为编译器可能使用跳转到代码块并跳转到代码块，或者可能更聪明，使用jsr和返回)

获得跳转表的特定方法是编写它。它是一个指向函数的指针数组，以你想要的值为索引。

如何?

为你的函数指针定义一个typedef，理解C语言中函数指针的类型，

typepedef void (*FunkPtr)(double a1, double a2);

FunkPtr JumpTable[] = {
    function_name_0,
    function_name_1,
    function_name_2,
    ...
    function_name_n
};

当然，您已经定义了function_name {0..N}，这样编译器就可以找到要调用的函数的地址。

我将把函数指针的调用和边界检查留给读者作为练习。