c++ - C++中使用跳转表实现switch语句

Question

我正在努力提高解析器的速度。还有 switch-case，有时它很有用，但我发现它仍然很慢。不确定 - 如果 C++ 支持此功能(地址检查点(带有附加参数))，那就太好了!

简单的例子:

enum Transport //MOTORBIKE = 1, CAR = 2,  ...  SHIP = 10
Transport foo = //unknown

    switch(foo)
{
    case MOTORBIKE : /*do something*/ break;
    case CAR : /*do something*/ break;
    //////////////////////////
    case SHIP : /*do something*/ break;
}

如果变量foo是SHIP，至少程序要重新校验一下值到十倍! -> 它仍然很慢。

如果 C++ 支持检查点:

Transport foo = //unknown
__checkpoint smart_switch;

goto (smart_switch + foo); //instant call!!!

smart_switch + MOTORBIKE : /*do something*/ goto __end;
smart_switch + CAR : /*do something*/ goto __end;
smart_switch + [...] : /*do something*/ goto __end;
////////////////////////////////////////////////////////////
smart_switch + SHIP : /*do something*/ goto __end;

__end : return 0;

它不生成任何跳转表，然后检查每个值。也许它不适用于 default 大小写。唯一的事情是 smart_switch + CAR -> smart_switch + SHIP 可能有不同的地址，所以如果 C++ 将它们评估为真实地址，该过程将失败。所以在编译时，编译器只需要将它们转换为真实地址。

C++ 是否支持此功能？它是否大大提高了速度和性能？

Answer 1

你说的这个叫跳表。跳转表通常是一个相对地址数组，程序执行控制可以在其中转移。下面是一个如何实现的示例:

#include <ctime>
#include <cstdlib>
#include <cstdio>

int main()
{
    static constexpr void* jump_table[] =
    {
        &&print_0, &&print_1, &&print_2,
        &&print_3, &&print_4, &&print_5
    };

    std::srand(std::time(nullptr));
    int v = std::rand();

    if (v < 0 || v > 5)
        goto out;

    goto *jump_table[v];

print_0:
    std::printf("zero\n");
    goto out;
print_1:
    std::printf("one\n");
    goto out;
print_2:
    std::printf("two\n");
    goto out;
print_3:
    std::printf("three\n");
    goto out;
print_4:
    std::printf("four\n");
    goto out;
print_5:
    std::printf("five\n");
    goto out;
out:
    return EXIT_SUCCESS;
}

但是，我严重怀疑两件事。第一个疑问是使用跳转表会让你的程序更快。间接跳转成本相对较高，并且硬件无法准确预测。很有可能，如果您只有三个值，那么您最好使用“if-then-else”语句简单地比较它们中的每一个。对于很多稀疏值(即 1、100、250、500 等)，最好进行二分查找而不是扩大表的大小。无论哪种情况，这都只是 switch 语句的冰山一角。因此，除非您知道所有细节并且知道编译器在您的特定情况下哪里做错了，否则不要费心尝试将 switch 更改为其他东西——您永远不会比编译器更聪明，只会让您的程序变慢。

第二个疑惑其实是切换是你解析器的瓶颈。很可能不是。因此，为了节省大量宝贵时间，请先尝试分析您的代码，以确定程序中最慢的部分是什么。通常它按如下步骤进行:

1. 剖析并找出瓶颈。
2. 弄清楚为什么这是一个瓶颈，并想出一个合理的想法来提高代码的速度。
3. 尝试改进代码。
4. 转到第 1 步。

而且这个循环没有导出。优化是您可以花费一生去做的事情。在某些时候，您将不得不假设程序足够快并且没有瓶颈 :)

此外，我还编写了一份更全面的分析，其中深入(或多或少)详细介绍了编译器如何实现 switch 语句，以及何时和何时不尝试以智取胜。请找文章here .