如何在标准C ++中使用计算的Goto将动态调度速度提高20％

Question

[在您否决或开始说goto邪恶和过时之前，请先阅读为什么在这种情况下可行的理由。在将其标记为重复之前，请阅读完整的问题。

[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和跳转到适当执行点的动作（case标签）。

这里有优化的空间。为了加快此循环的执行，可以使用所谓的computed gotos。

计算的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有时可以转换成单个goto汇编指令。

为了充分发挥jmp的潜力，对GCC编译器进行了扩展，使goto更具动态性。也就是说，可以在运行时确定要跳转到的标签。

此扩展名允许获得标签指针，类似于函数指针并对其进行goto处理：

goto

这是一个有趣的概念，它使我们可以进一步增强我们的简单VM。代替使用

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

some_label:
    do_something();

语句，我们将使用标签指针数组，而不是使用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();
    }
}

的版本（链接的博客文章中的版本，而不是上面的版本）快25％。这是因为每次操作后仅执行一次跳转，而不是两次。

[switch的控制流：switch例如，如果我们要先执行，然后再执行Opcode::FOO，则如下所示：Opcode::SOMETHING如您所见，在执行一条指令后，将执行两次跳转。第一个返回到代码，第二个返回到实际指令。

相反，如果我们要使用一组标签指针（提醒一下，它们是非标准的），那么我们将只有一个跳转：switch

值得注意的是，除了通过减少操作来节省周期外，我们还通过消除额外的跳跃来提高分支预测的质量。

现在，我们知道通过使用标签指针数组而不是，我们可以显着提高VM的性能（大约20％）。我认为也许也可以有其他一些应用程序。

我得出的结论是，该技术可以在任何具有循环的程序中使用，在该循环中，它顺序地间接调度一些逻辑。一个简单的示例（除了VM）可能是在多态对象容器的每个元素上调用switch方法：

virtual

现在，这有更多的应用程序。

但是存在一个问题：在标准C ++中，没有诸如标签指针之类的东西。因此，问题是：有没有一种方法可以模拟标准C ++中计算出的

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

的行为可以在性能上与它们匹配？。

编辑1：

使用开关还有另一个缺点。 goto使我想起了它。它是绑定检查。简而言之，它检查user1937198内部变量的值是否与任何switch相匹配。它添加了冗余分支（此检查是标准要求的）。

编辑2：

case，我将阐明减少虚拟函数调用开销的想法。应该是这样的：

In response to cmaster

不幸的是，我没有时间对其进行测试（明天会做）。

Answer 1

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

首先在原始代码中，如果程序计数器使程序溢出，则循环退出。在计算出的标签代码中，将调用未定义的行为（取消引用超出范围的索引）。因此，编译器必须为此插入一个检查，从而导致它为循环头生成一个基本块，而不是在每个switch块中内联。

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

第一个问题的解决方案很简单。不要在循环中使用c ++范围，而应在无条件的情况下使用while循环或for循环。不幸的是，第二个解决方案需要特定于平台的代码来告诉优化器默认为

#include <iostream>
#include <vector>
#include <cstdlib>
#include <memory>
#include <ctime>
using namespace std;

class Base
{
public:
    const int type_id = -1;
};

class D0 : public Base
{
public:
    const int type_id = 0;
};

class D1 : public Base
{
public:
    const int type_id = 1;
};

vector<unique_ptr<Base*>> gen_objects(int count)
{
    srand(time(0));

    vector<Base*> result;
    result.reserve(count);

    if (rand() & 1)
        result.emplace_back(new D1());
    else
        result.emplace_back(new D0);
}

int main()
{
    vector<unique_ptr<Base*>> objects = gen_objects(100);
    int pc = 0;

    void* ptrs[] = {&&d0_print, &&d1_print};

    #define NEXT *ptrs[objects[pc++]->type_id]

    goto NEXT;

    d0_print:
        cout << "I am D0!";
        goto NEXT;
    d1_print:
        cout << "I am D1!";
        goto NEXT;
}

形式的未定义行为，但是大多数编译器（clang和gcc中的_assume(0)）都存在类似现象，并且可以有条件地进行编译当没有等效项而没有任何正确性问题时，则为零。

因此，结果是：

__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);
        }
    }
}
上验证