1

在以下文档的第 4-5 页中：

http://www.open-std.org/jtc1/sc22/wg21/docs/ESC_Boston_01_304_paper.pdf

typedef int (* jumpfnct)(void * param); 
static int CaseError(void * param) 
{ 
  return -1; 
} 
static jumpfnct const jumptable[] = 
{ 
  CaseError, CaseError, ... 
  . 
  . 
  . 
  Case44,    CaseError, ... 
  . 
  . 
  . 
  CaseError, Case255 
}; 
  result = index <= 0xFF ? jumptable[index](param) : -1;

它正在比较 IF-ELSE 和 SWITCH，然后介绍这个“跳转表”。显然，这是三者中最快的实现。它到底是什么？我看不出它是如何工作的？

4

5 回答 5

3

jumptable 是一种将某些输入整数映射到动作的方法。它源于您可以使用输入整数作为数组的索引这一事实。

该代码设置了一个指向函数的指针数组。然后使用您的输入整数来选择这些函数指针。一般来说，它看起来像是一个指向函数的指针CaseError。但是，时不时地，它会被指向一个不同的功能。

它的设计是这样的

  jumptable[62] = Case62;
  jumptable[95] = Case95;
  jumptable[35] = Case35;
  jumptable[34] = CaseError; /* For example... and so it goes on */

因此，选择要调用的正确函数是恒定的时间......使用 if-elses 和选择，选择正确函数所花费的时间取决于输入整数......假设编译器没有将选择优化为jumptable 本身......如果它用于嵌入式代码，那么这种优化有可能被禁用......你必须检查。

一旦找到正确的函数指针，最后一行简单地调用它：

result = index <= 0xFF ? jumptable[index](param) : -1;

变成

result = index <= 0xFF  /* Check that the index is within
                           the range of the jump table */

         ? jumptable[index](param) /* jumptable[index] selects a function
                                      then it gets called with (param) */

         : -1; /* If the index is out of range, set result to be -1
                  Personally, I think a better choice would be to call
                  CaseError(param) here */
于 2012-12-21T23:46:57.603 回答
2

Jumpfnct 是指向函数的指针。Jumptable 是一个由许多 jumpfnc 组成的数组。这些函数可以通过引用它们在数组中的位置来调用。

例如， jumptable0 将执行第一个函数，传递参数。jumptable1 将执行第二个函数，等等。

如果您不了解函数指针，则不应使用此技巧。它们非常方便，在一个狭窄的领域。

当您正在做的是在大量类似的函数调用之间切换时，它非常快速且节省空间。您正在添加 switch 语句不一定具有的函数调用开销，因此它可能不适用于所有情况。如果您的代码是这样的：

switch(x) {
  case 1:
    function1();
    break;
  case 2:
    function2();
    break;
...
}

跳转表可能是一个很好的替代品。但是，如果您的开关是这样的：

switch(x) {
  case 1:
    y++;
    break;
  case 1023:
    y--;
    break;
...
}

这可能不值得做。

我已经在玩具 FORTH 语言解释器中使用它们，它们在其中非常宝贵，但在大多数情况下，您不会看到使它们值得使用的速度优势。如果它使您的程序逻辑更清晰，而不是为了优化，请使用它们。

于 2012-12-21T23:58:26.510 回答
1

这个跳转表通过它的索引返回一个指向函数的指针。您以这样一种方式定义此表：无效索引指向返回一些无效代码的函数（如示例中的 -1），而有效索引指向您需要调用的函数。

建造

jumptable[index]

返回指向函数的指针并调用此函数

jumptable[index](param)

param一些自定义参数在哪里。

于 2012-12-21T23:45:33.950 回答
1

Jump-Table 是一种显而易见但很少使用的优化，由于某种原因似乎已经失宠。

简而言之，不是测试一个值并退出 switch/case 或 if-else 块以分支到函数或代码路径，而是创建一个数组，其中填充了程序可以分支到的函数的地址。

一旦完成，这种安排就消除了 if-else 和 switch/case 块伴随的无情的 if 测试。该代码使用否则将使用 if 测试的变量作为函数指针数组的下标，并直接继续执行适当的代码 - 没有任何 if 测试。一个完美高效的分支。汇编代码实际上应该是一个跳转。

如果您分析代码，并找到程序花费大量时间的热点，请查看这种优化以提高性能。如果它是代码热点的一部分，那么其中的一点点可能会有很长的路要走。

感谢您的链接。很好的发现！

于 2012-12-22T00:00:25.187 回答
0

正如上面评论中提到的，这种解决方案是否比例如 switch 语句更有效或更不有效，取决于每种情况需要完成的工作量。

为要处理的值编写一个常规的 switch 语句肯定是一种更清晰的方式来查看代码的作用。因此，除非空间或速度要求要求更复杂的解决方案，否则我建议这不是一个“更好”的解决方案。

然而，函数指针表是解决某些问题的有效且好方法。我经常在表中使用函数指针来执行诸如“对问题进行基准测试 11 种不同的解决方案”之类的事情，其中​​我有一个带有函数名称和函数名称的结构，也许还有一些参数。然后我有一个函数来计时和循环代码几百万次（或者任何需要足够长的测量才能有意义的东西）

于 2012-12-21T23:55:50.727 回答