跳台开关盒问题

一 跳转表 是用于 转移控制 去另一个地方。goto、continue和break类似,只是它们总是转移到特定的位置,而不是从多个位置转移一个可能性。特别是,此控制流与函数调用不同。(维基百科关于 branch tables 是相关的。)

一 switch语句 是如何在C/C++中编写跳转表的。在这种常见的情况下,只提供有限的形式(只能打开整型),以使实现更容易和更快。(对于整型,如何有效地实现跳转表的研究比一般情况下的要多得多。)一个经典的例子是 Duff's Device .

然而, 跳台的全部功能通常不需要 例如,当每个案例都有一个中断语句时。这些“有限跳台”是 不同花样 它只利用了跳跃表的良好学习效率,并且在每个“动作”都独立于其他动作时很常见。

跳转表的实际实现形式不同,主要是索引到索引的映射方式不同。这种映射就是“字典”和“哈希表”这样的术语出现的地方,这些技术可以独立于跳转表使用。说一些代码“使用跳转表”本身并不意味着您有O(1)查找。

编译器可以自由地为每个switch语句选择查找方法,并且不能保证您会得到一个特定的实现;但是,应考虑编译器选项,如速度优化和大小优化。

你应该 研究数据结构 来处理他们强加的不同的复杂性需求。简而言之,如果“dictionary”的意思是平衡二叉树,那么它是O(log n);哈希表取决于它的哈希函数和冲突策略。在switch语句的特定情况下,由于编译器具有完整的信息,因此它可以生成 perfect hash function 这意味着o(1)查找。但是,不要仅仅看整个算法的复杂性就迷路了:它隐藏了重要的因素。

跳转表基本上是指向代码块的指针数组,用于处理switch语句中的各种情况。它最有可能是在您的事例密集时生成的(即,对于一个范围内的每个可能值都有一个事例)。例如,给出如下语句:

switch (i) {
   case 1: printf("case 1"); break;
   case 2: printf("case 2"); break;
   case 3: printf("case 3"); break;
}

它可以生成大致相当于以下内容的代码:

void case1() { printf("case 1"); }
void case2() { printf("case 2"); }
void case3() { printf("case 3"); }

typedef void (*pfunc)(void);

pfunc functions[3] = {case1, case2, case3};

if ((unsigned)i<3)    
    functions[i]();

这很复杂。典型的哈希表也大致有O(k) 预期 复杂性,尽管最坏的情况通常是O(N)。跳转表通常更快,但通常只在表非常密集的情况下使用,而哈希表/字典即使在情况非常稀疏的情况下也能很好地工作。

假设您有一系列的过程:

void fa() { 
 printf("a\n");
}

...

void fz() { 
 printf("it's z!\n");
}



typedef void (*F)();
F table[26]={fa,fb,...,fz};

假设您接受来自用户的输入字符(来自a-z),并运行fc:

char c;
switch(c) {
   case 'a': fa();break;
   case 'b': fb();break;
   ...
   case 'z': fz();break;       
   default: exit(-1);
}

理想情况下,这将被以下内容取代:

if (c<'a' || c>'z') exit(-1);
else (*table[c-'a'])();

当然,你可以把桌子调大,这样就不需要进行范围检查了。

编译器可以对任意代码执行此操作,而不一定只执行函数调用,并且可以通过存储要跳转到的地址(本质上是goto)来执行此操作。C不直接支持任何类型的计算goto(索引到表中或其他类型),但是它的CPU指令非常简单。

编译switch语句可以采用多种形式,具体取决于具体情况。如果两个箱子靠得很近,那就不用费心了:用跳台。如果案例相距很远,请使用if(case==value)或使用map。或者编译器可以使用一个组合:由跳转表范围的if检查确定的跳转表孤岛。

跳转表是一个简单的函数指针数组,您可以大致这样描述跳转表:

int (*functions[10])(); /* Array of 10 Function Pointers */

据我所知,这与类似于so的case语句一起使用:每个条件case将是该数组的索引,例如:

switch( a ) {
    case 1:  // (*functions[1])() // Call function containing actions in case of 1
        ...  
    case 2:  // (*functions[2])() // Call function containing actions in case of 2
        ...

每种情况下,转换成简单的函数[A]。这意味着访问函数[9]和访问函数[1]一样快。给你你你提到的O(1)时间。

显然,如果您有case 1和case 4907,这将不是一个好方法,并且您提到的哈希表/字典方法可能会起作用。

进一步阐述 Jerry's answer 及其他

鉴于:

int x=1;
switch (i) {
   case 1: x=6; break;
   case 2: x++;
   // Fall through
   case 3: x+=7; break;
}

您可以有如下内容:

int f1() {return 6;}
int f2() {return 1+f3();}
int f3() {return 8;}

编译器可以使用跳转表进行索引 {f1, f2, f3}

编译器可以在创建具有 f1, f2, f3 设置 x 直接到 6,9,8

但是如果你编写了函数,并滚动了你自己的跳转表, f1,f2,f3 可能在任何地方,但编译器会知道将它们放在 switch 创建比您可以更好的代码位置。

注意,在许多情况下,编译器将生成一个保护来检查 i 在范围内(或处理 default )如果你确定总是这样,你可以跳过这一点。

有趣的是,对于少数情况,在不同的编译器标志(依赖于编译器)下, 转换 不会使用表格,但只会使用ifs,类似于:

if (i==1) x=f1();
else if (i==2) x=f2();
else if (i==3) x=f3();

或者它可以优化这个(简单的测试是一条指令),以:

x=(i==1) ? f1()
: (i==2) ? f2()
: (i==3) ? f3()
: x;

最好的建议是查看生成的程序集,看看编译器对您的体系结构上的代码做了什么,如果存在跳转表,Linux/Intel上的G++将生成类似以下内容的程序集

( 注意我必须去5 case 语句强制跳转表,它使用低于该数量的ifs 案例 声明 )

注意,小洞将在跳台上做 违约

int foo(int i)
{
   int x=1;
   switch (i) {
       case 1: x=6; break;
       case 2: x++;
        // Fall through
       case 3: x+=7; break;
       case 4: x+=2; break;
       case 5: x+=9; break;
    }
  return x;
}

将生成以下程序集代码( //注释是我的 ):

        cmp     edi, 5                     //make sure it is not over 5
        ja      .L2                        //jump to default case
        mov     edi, edi
        jmp     [QWORD PTR .L4[0+rdi*8]]   // use the jump table at label L4:
.L4:
        .quad   .L2                        // if i=0, set x=1 (default)
        .quad   .L9                        // f1() see below
        .quad   .L10                       // f2() see below
        .quad   .L6                        // f3() see below
        .quad   .L7                        // f4() see below
        .quad   .L8                        // f5() see below
.L10:
        mov     eax, 9                     // x=9
        ret
.L9:
        mov     eax, 6                     // x=6
        ret
.L8:
        mov     eax, 10                    // x=10
        ret
.L6:
        mov     eax, 8                     // x=8
        ret
.L7:
        mov     eax, 3                     // x=3
        ret
.L2:
        mov     eax, 1                     // default, x was 1, noop is: x=1
        ret