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或组合之间进行选择.设计糟糕的编译器可能无法做出这样的选择 - 甚至可能会为开关块产生非常糟糕的代码.但任何体面的编译器都应该为switch-blocks生成有效的代码.Ť

这里的主要决策因素是编译器可以选择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)
     {
         ...
     }
 }

如果我们有很多情况,这种方法会陷入很深的深度,人类可能会在三到四个深度之后迷失(请记住每一个如果从范围的MIDDLE中的某个点开始),但它会减少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 语句构建了一个解析树，我会怎么做？我研究了编译器的设计和构造，以下是一些决定，

如何帮助编译器决定实现跳转表：

• case 值为小整数（0,1,2,3,...）
• case 值在一个紧凑的范围内（很少有漏洞，记住默认值是一个选项）
• 有足够的情况使优化值得（> N，检查编译器源代码以找到常量）
• 如果范围很紧凑，聪明的编译器可能会在跳转表索引中减去/添加一个常量（例如：1000、1001、1002、1003、1004、1005 等）
• 避免失败和控制权转移（转到、继续）
• 每个案例结束时只有一次休息

尽管编译器之间的机制可能有所不同，但编译器本质上是在创建未命名的函数（好吧，也许不是函数，因为编译器可能会使用跳转到代码块并跳出代码块，或者可能会聪明地使用 jsr 并返回）

获得跳转表的唯一方法是编写它。它是一个指向函数的指针数组，由所需的值索引。

如何？

为函数指针定义 typedef，了解 C 中函数指针的 typedef，

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

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

当然，您已经定义了 function_name_{0..n}，因此编译器可以找到要调用的函数的地址。

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