跳转表是如何工作的？

Question

在以下文档中，第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，然后介绍了这个“跳表”。显然，它是这三种方法中实现速度最快的。它到底是什么？我看不出它是怎么工作的？

Answer 1

跳转表是一种将一些输入整数映射到操作的方法。这是因为您可以使用输入整数作为数组的索引。

代码设置了一个指向函数的指针数组。然后，您的输入整数用于选择这些函数指针中的一个。一般来说，它看起来像是指向函数CaseError的指针。然而，每隔一段时间，它都会是一个不同的函数。

它的设计目的是为了

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

因此，选择正确的函数调用是恒定的时间...使用if-elses和select，选择正确函数所需的时间取决于输入的整数...假设编译器本身没有优化select到跳转表...如果它是针对嵌入式代码的，那么这种优化可能已经被禁用了……你得去检查一下。

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

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 */

Answer 2

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

例如，jumptable0将执行第一个函数，传递参数。jumptable1将执行第二个函数，依此类推。

如果你不了解函数指针，你就不应该使用这个技巧。它们非常方便，在一个狭窄的领域内。

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

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

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

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

这可能不值得去做。

我把它们用在了一个玩具FORTH语言解释器中，在那里它们是无价的，但在大多数情况下，你不会看到让它们值得使用的速度优势。如果它们能让你的程序逻辑更清晰，而不是为了优化，那就使用它们。

Answer 3

此跳转表通过其索引返回指向函数的指针。定义该表的方式是，无效索引指向返回一些无效代码的函数(如本例中的-1 )，有效索引指向需要调用的函数。

施工

jumptable[index]

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

jumptable[index](param)

其中param是一些自定义参数。