c++ - 如何在标准C++中使用计算机Gotos将动态调度速度提高20％

Question

在您否决或开始说goto ing是邪恶和过时的之前，请阅读为什么在这种情况下可行的理由。在将其标记为重复项之前，请阅读完整的问题。
我在读虚拟机解释器I stumbled across computed gotos时。显然，它们可以显着提高某些代码的性能。最著名的示例是主VM解释器循环。
考虑一个(非常)简单的VM，如下所示:

#include <iostream>

enum class Opcode
{
    HALT,
    INC,
    DEC,
    BIT_LEFT,
    BIT_RIGHT,
    RET
};

int main()
{
    Opcode program[] = { // an example program that returns 10
        Opcode::INC,
        Opcode::BIT_LEFT,
        Opcode::BIT_LEFT,
        Opcode::BIT_LEFT,
        Opcode::INC,
        Opcode::INC,
        Opcode::RET
    };
    
    int result = 0;

    for (Opcode instruction : program)
    {
        switch (instruction)
        {
        case Opcode::HALT:
            break;
        case Opcode::INC:
            ++result;
            break;
        case Opcode::DEC:
            --result;
            break;
        case Opcode::BIT_LEFT:
            result <<= 1;
            break;
        case Opcode::BIT_RIGHT:
            result >>= 1;
            break;
        case Opcode::RET:
            std::cout << result;
            return 0;
        }
    }
}

该VM所能做的就是对几种类型的 int进行一些简单的操作并将其打印出来。尽管它的有用性令人怀疑，但仍然可以说明该主题。
VM的关键部分显然是 switch循环中的 for语句。它的性能取决于许多因素，其中最重要的因素当然是 branch prediction以及跳转到适当执行点的 Action ( case标签)。
这里有优化的空间。为了加快此循环的执行速度，可以使用所谓的计算的goto。
计算的Gotos
计算的Goto是Fortran程序员和使用某些(非标准)GCC扩展的程序员所熟知的结构。我不赞成使用任何非标准的，实现定义的(显然)未定义的行为。但是，为了说明问题的概念，我将使用提到的GCC扩展的语法。
在标准C++中，我们允许定义标签，以后可以通过 goto语句跳转到这些标签:

goto some_label;

some_label:
    do_something();

这样做不是很好的代码( and for a good reason!)。尽管有很多反对使用 goto的论点(其中大多数与代码可维护性有关)，但该可恶功能还是有一个应用程序。这是性能的提高。
Using a goto statement can be faster than a function invocation.这是因为调用函数时必须完成“文书工作”，例如设置堆栈和返回值。同时， goto有时可以转换为单个 jmp汇编指令。
为了充分发挥 goto的潜能，对GCC编译器进行了扩展，使 goto更具动态性。即，可以在运行时确定要跳转到的标签。
此扩展允许获取标签指针，类似于函数指针并对其进行 goto编码:

    void* label_ptr = &&some_label;
    goto (*label_ptr);

some_label:
    do_something();

这是一个有趣的概念，它使我们可以进一步增强简单的VM。而不是使用 switch语句，我们将使用标签指针数组(所谓的跳转表)，而不是使用 goto指向相应的指针(操作码将用于对数组进行索引):

// [Courtesy of Eli Bendersky][4]
// This code is licensed with the [Unlicense][5]

int interp_cgoto(unsigned char* code, int initval) {
    /* The indices of labels in the dispatch_table are the relevant opcodes
    */
    static void* dispatch_table[] = {
        &&do_halt, &&do_inc, &&do_dec, &&do_mul2,
        &&do_div2, &&do_add7, &&do_neg};
    #define DISPATCH() goto *dispatch_table[code[pc++]]

    int pc = 0;
    int val = initval;

    DISPATCH();
    while (1) {
        do_halt:
            return val;
        do_inc:
            val++;
            DISPATCH();
        do_dec:
            val--;
            DISPATCH();
        do_mul2:
            val *= 2;
            DISPATCH();
        do_div2:
            val /= 2;
            DISPATCH();
        do_add7:
            val += 7;
            DISPATCH();
        do_neg:
            val = -val;
            DISPATCH();
    }
}

这个版本比使用 switch的版本(链接的博客文章中的版本，而不是上面的版本)快25％。这是因为每次操作后仅执行一次跳转，而不是两次。
用 switch控制流:

例如，如果我们要先执行 Opcode::FOO，然后再执行 Opcode::SOMETHING，则它将如下所示:

如您所见，在执行一条指令之后，将执行两次跳转。第一个返回到 switch代码，第二个返回到实际指令。
相反，如果我们使用一个标签指针数组(提醒一下，它们是非标准的)，那么我们将只有一个跳转:

值得注意的是，除了通过减少操作来节省周期外，我们还通过消除额外的跳跃来提高分支预测的质量。
现在，我们知道通过使用标签指针数组而不是 switch，我们可以显着提高VM的性能(大约20％)。我认为也许也可以有其他一些应用程序。
我得出的结论是，这种技术可以在任何具有循环的程序中使用，在该循环中，它顺序地间接调度一些逻辑。一个简单的示例(除了VM)可能是在多态对象容器的每个元素上调用 virtual方法:

std::vector<Base*> objects;
objects = get_objects();
for (auto object : objects)
{
    object->foo();
}

现在，这有更多的应用程序。
但是，存在一个问题:在标准C++中没有诸如标签指针之类的东西。因此，问题是:有没有一种方法可以模拟可以在性能上与标准++ 相匹配的goto s的行为？ 。
编辑1:
使用开关还有另一个缺点。 user1937198让我想起了它。它是绑定(bind)检查。简而言之，它检查 switch内部的变量的值是否与 case中的任何一个匹配。它添加了冗余分支(此检查是标准要求的)。
编辑2:
In response to cmaster，我将阐明减少虚拟函数调用开销的想法。对此的一种肮脏方法是在每个派生实例中都有一个代表其类型的ID，该ID将用于索引跳转表(标签指针数组)。问题是:

没有跳转表是标准的C++

添加新的派生类时，将要求as修改所有跳转表。

我将很感激，如果有人想出了某种类型的模板魔术(或万不得已的宏)，那将使其编写得更加干净，可扩展和自动化，如下所示:

Answer 1

在最新版本的MSVC上，关键是为优化器提供所需的提示，以便可以告诉仅索引到跳转表中是一种安全的转换。原始代码有两个约束可以阻止这种情况，从而使对由计算出的标签代码生成的代码的优化成为无效的变换。

首先，在原始代码中，如果程序计数器使程序溢出，则循环退出。在计算出的标签代码中，将调用未定义的行为(取消引用超出范围的索引)。因此，编译器必须对此进行插入检查，以使其生成循环头的基本块，而不是在每个切换块中内联该块。

其次，在原始代码中，不处理默认情况。尽管该开关覆盖了所有枚举值，因此没有分支匹配是不确定的行为，但msvc优化器不够智能，无法利用这一点，因此会生成不执行任何操作的默认情况。检查此默认情况需要有条件，因为它可以处理较大范围的值。在这种情况下，计算出的goto代码也会调用未定义的行为。

第一个问题的解决方案很简单。不要在循环中使用c++范围，而应在无条件的情况下使用while循环或for循环。不幸的是，第二种解决方案需要特定于平台的代码来告诉优化器，默认情况下是_assume(0)形式的未定义行为，但是大多数编译器中都有类似的东西(clang和gcc中的__builtin_unreachable())，并且可以在没有时可以有条件地编译为空等同存在，没有任何正确性问题。

因此，结果是:

#include <iostream>

enum class Opcode
{
    HALT,
    INC,
    DEC,
    BIT_LEFT,
    BIT_RIGHT,
    RET
};

int run(Opcode* program) {
    int result = 0;
    for (int i = 0; true;i++)
    {
        auto instruction = program[i];
        switch (instruction)
        {
        case Opcode::HALT:
            break;
        case Opcode::INC:
            ++result;
            break;
        case Opcode::DEC:
            --result;
            break;
        case Opcode::BIT_LEFT:
            result <<= 1;
            break;
        case Opcode::BIT_RIGHT:
            result >>= 1;
            break;
        case Opcode::RET:
            std::cout << result;
            return 0;
        default:
            __assume(0);
        }
    }
}

可以在 godbolt上验证生成的程序集