C 语言中的 switch 语句和跳转表

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语句，所以至少我增加了一些可读性。

- Daniel Miron

---

1. 这很可能取决于您使用的编译器。您用的是哪个？
2. 为什么在意呢？您应该信任编译器尽其所能地处理您编写的代码。跳转表并不一定在所有情况下都是最佳选择。虽然这并没有完全回答您的问题，但您可能会对http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf 感兴趣。

- BoBTFish

@BoBTFish：感谢你的指引，非常感激。 - FrankH.

@BoBTFish 感谢，看起来是一篇不错的文章，如果我有时间就好了 (: - Daniel Miron

你为什么要在意呢？编译器的作者可能比你更了解目标硬件，而且编译器通常会生成最优秀的代码，无论是跳转表、链式测试还是其他任何东西。 - Pete Becker

为什么？跳转表易于编写。如果需要，可以编写一个跳转表。switch/case清晰明了，对于少量的情况只需几个cmp/jmp指令。总的来说，相信你的编译器。 - ChuckCottrill

Answer 1

优秀的编译器可以并且会在跳转表、链接式if/else和二者的组合中进行选择。而设计不良的编译器可能不会做出这样的选择，甚至对于 switch-blocks 生成非常糟糕的代码。但是任何像样的编译器都应该能够为 switch-blocks 生成高效的代码。

这里的主要决策因素是：当数字相差很远时（而不是通过除以2、4、8、16、256等将其轻易地更改为较接近的值），编译器可以选择 if/else，例如：

 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语句的开头放置某些值，这样做会稍微好一些，但前提是在运行代码之前就能确定最常见的值。

如果性能对你的情况至关重要，那么你需要对两种方案进行基准测试。但我猜只需将代码编写为switch语句，不仅代码更清晰，而且至少与if-else语句一样快，甚至更快。

- Mats Petersson

Answer 2

编译器可以将任何C/C++开关转换为跳转表，但编译器会出于效率考虑执行此操作。如果你正在编写一个编译器，并且刚刚为开关/ case语句构建了解析树，那么你会怎么做呢？我学习过编译器设计和构建，以下是一些决策：

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

- case值是小整数（0,1,2,3，...）。 - case值在紧凑范围内（少量空洞，记住默认选项）。 - 有足够的case使优化值得（> N，请查看编译器源代码以找到常量）。 - 聪明的编译器可以在范围紧凑时从跳转表索引中减去/加上一个常数（例如：1000、1001、1002、1003、1004、1005等）。 - 避免落空和控制转移（goto、continue）。 - 每个case只有一个结束时的break。

虽然不同编译器之间的机制可能有所不同，但编译器本质上是创建未命名函数（好吧，也许不是函数，因为编译器可能使用跳入代码块并跳出代码块或者可能聪明地使用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}函数，所以编译器可以找到要调用的函数地址。

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

- ChuckCottrill