查找 table 和跳转 table 之间的区别

Question

我知道jump tables主要用于在汇编中创建switch语句：

int a = 5;
switch (a){
  case 5:
  ...
   break;
  ...
}

在这种情况下，跳转只是一个指向内存地址的指针，该内存地址具有 instructions 来完成 case 5 工作。

如果我没记错的话，lookup table 在数组中有预先计算的结果？因此，与其编写代码来计算它们，不如 return 数组索引？有点像 HashMap.

上面两个和我很像，他们基本上是一回事吗？一个指向说明，另一个指向 returns 预先计算的结果？

Answer 1

If i'm not mistaking, a lookup table has pre calculated results in an array? so instead of writing code to calculate them you just return the array index? Sort of like a HashMap.

正确。存储在该索引处的可能是数据，或者指向数据的指针，或者指向函数的指针等。

跳转 table 只是一个查找 table，其中每个索引对应一个函数，最常在 C 中实现为函数指针数组。

Answer 2

Jump tables 是，正如您提到的，本机代码的排列方式很容易根据整数值跳转到。如果跳转 table 仅由短跳转指令组成，您可以将开关值乘以 3 并添加 table 和跳转（JMP 或 CALL) 到它。

另一方面，查找 table 只是原始数据。它仍然以打包格式存储，因此您可以通过对索引的线性操作 (size * index + offset) 访问它，但要使用它，您需要使用间接移动 (MOV dest, [expression]) 而不是物理跳转到它。

请记住，查找 table 只是一种优化，尽管是一个巨大的优化，您也可以使用跳转 table 将值加载到寄存器中。这是一个 is-a 关系。

Answer 3

引擎盖下发生的事情由编译器负责。但你的观察是对的。下面是一个片段，展示了编译器经常对 switch 语句执行的操作：

#include <stdio.h>

void foo(void) { printf("foo\n"); }
void bar(void) { printf("bar\n"); }

int main(void)
{
    // Array of size 2 of pointer to function without arguments returning void
    // Yes, declaring function pointers is not intuitive...
    void (*f[2])(void);

    f[0] = foo;
    f[1] = bar;

    int x;
    printf("Enter a number (0 or 1): ");
    scanf("%d", &x);

    printf("Using switch\n");
    switch(x) {
    case 0: foo(); break;
    case 1: bar(); break;
    }

    printf("Using array of function pointers\n");
    f[x]();
}

查找 table 和跳转 table 之间的区别

Difference between a lookup table and a jump table

c

lookup-tables

jump-table