你能用C++做一个计算后藤吗?

fxnxkyjh  于 2023-01-06  发布在  其他
关注(0)|答案(6)|浏览(123)

Fortran有一个高效的计算方法叫做'computed goto'。这个构造使用一个分支表的索引来执行直接goto。如果我没记错的话,语法是:

go to index (label1, label2, ...)

其中索引用于引用带括号的列表中的代码指针(标签)。
我有一个案例,计算的后藤比switch语句更好,我想构造一个,但我不知道如何构造。
现在,在jibes和slings到达之前,编译器可以优化计算的后藤,但我不能保证它会这样做。
switch语句总是可以使用的。在某些情况下,switch语句可以优化为跳转表(计算后藤的实现)。
但是,这仅在事例值的范围为几乎稠密覆盖时才有可能(对于低值到高值范围内的每个整数几乎都有一个case语句)。当不是这种情况时,这个实现可能是一个二叉树。2编译器的编写者可以选择在适当的时候优化到一个跳转表。二叉树总是满足switch语句的语义,有时一个跳转表就足够了,让我问一下我是否能保证在适当的时候有一个跳转表,我对编译器的编写者没有控制权。
举一个简单的例子,我经常编写lexer(FSMs),我使用三个数据结构,一个用于将输入Map到可接受的字母表,一个用于执行节点转换,一个用于根据当前状态和输入值执行某些代码。FSM的实现是Mealy machine,而不是Moore machine,因此操作是在弧(转换)上执行的,而不是在节点上执行的。
所执行的操作通常很小,通常不超过一行源代码。我认识到函数是可以使用的,并且它们的使用消除了对跳转表的需要。但是我相信我不能“指向”内联函数,因此函数是封闭形式的可调用过程。
在大多数情况下,这比使用或不使用跳转表优化的switch语句效率要低。如果我可以使用跳转表,那么我就可以避免编译器作者如何看待优化的问题,并且能够编写高效的代码。
至于下面提到的与Fortran计算的后藤相关的问题的一般情况:这并不是对那个/那些评论的批评。但是定性的问题,即使它们是真的,也没有回答这个问题。
下面是使用void* &&label;的答案,我想为此感谢您。但是,唉,正如您所指出的,这是非标准C/C++,将来可能不会出现。所以,最好不要这样做。
我希望我已经回答了“得到一个更好的编译器”的评论。我希望我至少已经解决了使用函数指针的问题。最后,这对我来说是一个好奇的时刻。我不认为我应该提供为什么我认为这个问题有一些承载力的杀菌历史。但现在我知道了。无论何时,我的意思是无论何时,我写信给这个小组我最好告诉你我所有的鸭子是什么,这样他们就可以被击落良好和适当的。

uujelgoq

uujelgoq1#

如果使用最新的**GCC编译器进行编译(例如,GCC 7或GCC 6)-对于C代码,甚至可以使用GCC的旧版本,您可以使用其labels as values扩展**(因此C++11C++14标准的 * 外部 *),它可以与C和C++一起工作。前缀&&操作符给出标签的 * 地址 *,如果goto后面跟有*间接操作符,则计算goto。您最好让目标标签开始一些块。
例如:

#include <map>

int foo (std::map<int,int>& m, int d, int x) {
    static const void* array[] = {&&lab1, &&lab2, &&lab3 };
    goto *array[d%3];
lab1: {
        m[d]= 1;
        return 0;
    };
lab2: {
        m[2*d]=x;
        return 1;
    }
lab3: {
    m[d+1]= 4*x;
    return 2;
    }
}

(of当然,对于上面的代码,普通的switch将是优选的,并且可能同样有效)
顺便说一句,最近的Clang(例如,clang++-5.0)也接受该扩展。
(计算的goto不是异常友好的,所以它们可能会在GCC for C++的未来版本中消失。)
利用threaded code编程技术,您可以编写一些非常高效的(字节码)解释器使用它,在这种特殊情况下,代码保持可读性(因为它是非常线性的)并且非常高效。顺便说一句,你可以用宏和条件编译来隐藏这样的计算goto-例如,#if-s-(例如,在不支持该扩展的编译器上使用switch);那么你的代码将是相当可移植的。举个c语言的例子,看看OCamlruntime/interp.c
对于reference Eli Bendersky,计算的goto版本更快,原因有两个:
1.由于边界检查的原因,开关在每次迭代中执行的操作更多。
1.硬件分支预测的影响。
编译器可以实现switch的许多变体。
1.使用if结构对交换空间进行二分搜索。
1."case"位置的表(类似于计算的goto)。
1.一种计算转移,要求所有用例具有相同的代码大小,从而形成一个"代码数组"。
对于OP状态机调度,项2是最好的情况。它是唯一不需要返回到主switch调度位置的构造。因此,break;可以将控制转移到下一个case。这就是为什么该机制对于分支预测更有效的原因。

a64a0gku

a64a0gku2#

是(不是直接),通过使用switch或创建函数指针或函数对象表。
大多数编译器会将switch转换为计算的goto(也称为跳转表)。
函数指针数组也是一样的,通过解引用数组槽来执行函数。
您还可以使用std::map或其他带有函数指针的容器。

编辑1:使用数组计算goto的示例

typedef (void) (*Pointer_To_Function)();
void Hello()
{
  cout << "Hello\n";
}

void Bye()
{
  cout << "Bye\n";
}

static const Pointer_To_Function function_table[] =
{
  Hello,
  Bye,
}

int main()
{
  (*function_table[0])();
  (*function_table[1])();

  // A "computed goto" based on a variable
  unsigned int i = 0;
  (*function_table[i])();
  return 0;
}

编辑2:使用switch计算 * 后藤

int main()
{
  int i = 1;
  switch (i)
  {
    case 0: Hello(); break;
    case 1: Bye(); break;
  }
  return 0;
}

告诉编译器为上面的每个示例生成一个汇编语言列表。
最有可能的是,它们看起来像一个计算的goto或一个 jump 表。
若要对switch或数组进行良好的优化,条件值应在一个范围内连续。对于选择有孔的范围,std::map可能更有效(或对较小数量使用表)。

lstz6jyr

lstz6jyr3#

using jump_func_t = void(*)(void const*);
template<class F>
jump_func_t jump_func() {
    return [](void const*ptr){ (*static_cast<F const*>(ptr))(); };
}
template<class...Fs>
void jump_table( std::size_t i, Fs const&...fs ) {
  struct entry {
    jump_func_t f;
    void const* data;
    void operator()()const { f(data); }
  };
  const entry table[] = {
    {jump_func<Fs>(), std::addressof(fs)}...
  };
  table[i]();
}

试验代码:

int x = 0, y = 0, z = 0;
jump_table( 3,
    [&]{ ++x; },
    [&]{ ++y; },
    [&]{ ++z; },
    [&]{ ++x; ++z; }
);
std::cout << x << y << z << "\n";

输出端101。
Live example
如果你想要大量的间隙,额外的工作将不得不做。短的“间隙”可以用无效的跳转目标处理:

using action = void();
static action*const invalid_jump = 0;

如果实际调用,则应该是segmentation fault
对于一个真正稀疏的表,您可能希望传入表大小的编译时常量和每个目标的编译时索引,然后根据这些常量构建表。根据您希望达到的效率,这可能需要相当复杂的编译时编程。

46qrfjad

46qrfjad4#

......我是否能保证在适当的时候有一个跳转表。我无法控制编译器的编写者。
不,你不能。事实上,考虑到这是C语言,即使你巧妙地实现了你自己的跳转表,你也不能保证编译器不会撤销你的努力。如果你想要保证,你必须自己用汇编语言编写。编译器只遵循“as-if”标准。它们必须做一些事情,就好像它们做了你告诉它们做的事情。
大多数编译器都非常擅长这种优化。你不是第一个开发解析器的开发人员。事实上,我希望他们在高效的时候使用跳转表,而在低效的时候不使用跳转表。你可能会不小心让它做一些效率较低的事情。编译器通常有一个大型的CPU计时数据库,他们利用这些数据库来决定如何最好地编写操作码。
现在,如果您不能将代码转换为普通的switch语句,那么您可以使用自定义switch语句来模拟它。
要替换go to index (label1, label2, ...),请尝试

switch(index) {
    case trampoline1:
        goto label1;
    case trampoline2:
        goto label2;
    ...

}

看起来这些蹦床是“真实的的”,但是我希望任何一个称职的编译器都能为你做好优化工作。因此,这个解决方案是特定于编译器的,但是它应该在各种各样合理的编译器中工作。静态可计算控制流是编译器30多年来一直在消化的东西。例如,我知道我使用过的每一个编译器都可以

bool found = false;
for(int i = 0; i < N; i++)
{
    if (matches(i))
    {
        found = true;
        break;
    }
}

if (!found)
    return false;

doSomething();

并有效地将其转化为

for(int i = 0; i < N; i++)
{
    if (match(i))
       goto label1;
}

return false;

label1:
doSomething();

但最终,不,没有任何结构可以毫无疑问地保证某个特定的受Fortran启发的方法在C中被使用。你总是必须对你的编译器进行测试。然而,相信编译器。和配置文件。在你选择在它上面的柴堆上死去之前,确保这是一个热点。

tzcvj98z

tzcvj98z5#

这里已经有一些有用的答案了,但是我有点惊讶还没有人提到尾部调用优化,因为根据你如何构造你的实现,编译器可能已经在做你所希望的了!
从本质上讲,如果你把每条指令写成一个单独的函数,并把"下一条指令"函数作为最后一件事调用,那么你就能以一种安全和结构化的方式得到一个计算的goto,只要在调用之后不需要任何处理,并且实现操作的函数都具有相同的签名(以及与"next instruction"函数相同的签名),则调用应自动优化为计算的goto。
当然,优化必须被启用---O2用于GCC或者/O2用于MSVC---否则函数调用将递归并且消耗堆栈。这至少在功能上是正确的,并且如果你的执行跟踪很短,比如少于10k的顺序操作,你应该能够在现代机器和操作系统上禁用优化进行调试。
尾调用消除至少在LISP时代就已经被很好地理解了。据我所知,至少从2000年左右开始,它就可以在大多数C/C ++编译器上使用,而且肯定可以在LLVM、GCC、MSVC和ICC上使用。如果你用LLVM编译,你可以使用__attribute__((musttail))来请求这个优化,即使优化通常是禁用的--GCC似乎还没有赶上,但如果必须这样做,即使禁用了其他优化,也可以传递"-foptimize-sibling-calls"。
(This关于GCC中该属性的实现状态的评论与其对尾部调用在替换计算的goto的特定用例中的优点的讨论特别相关:https://gcc.gnu.org/pipermail/gcc/2021-April/235891.html
强制性具体示例:

#include <stdio.h>
#include <stdint.h>

using operation_t = void (*)();

static void op_add();
static void op_print();
static void op_halt();

// Test program
operation_t program[] = { op_add, op_print, op_halt };

// VM registers
int32_t ra = 5, rb = 3;
operation_t const * rpp = program;

static void exec_next_op() {
    // Call the next operation function -- since nothing is
    // returned from our stack frame and no other code needs to
    // run after the function call returns, the compiler can
    // destroy (or repurpose) this stack frame and then jump
    // directly to the code for the next operation.

    // If you need to stop execution prematurely or do debug
    // stuff, this is probably where you'd hook that up.

    (*(rpp++))();
}

static void op_add() {
    ra += rb;
    // EVERY operation besides halt must call exec_next_op as
    // the very last thing it does.
    exec_next_op();
}

static void op_print() {
    printf("%d\n", ra);
    // EVERY operation besides halt must call exec_next_op as
    // the very last thing it does.
    exec_next_op();
}

static void op_halt() {
    // DON'T exec_next_op(), and the notional call chain unwinds
    // -- notional because there is no call chain on the stack
    // if the compiler has done its job properly.
}

int main(int argc, char const * argv[]) {
    // Kick off execution
    exec_next_op();
    return 0;
}

在编译器资源管理器上:https://godbolt.org/z/q8M1cq7W1
注意,在x86 - 64上使用-O2时,GCC内联exec_next_op()调用,并且op_*(halt除外)以间接的"jmp rax"指令结束。
为了完整起见,我经历了相当多的体系结构,对主要的体系结构的支持很好--MSVC、GCC和x86/x86 - 64上的Clang、ARM/ARM64和RISC-V,但是一些更老和更模糊的体系结构没有优化。
针对ESP32的GCC是当前开发人员唯一可能感到困扰的,但我注意到针对SPARC的GCC也不能做到这一点。我怀疑他们会处理静态尾递归,但调用函数指针确实意味着额外级别的特殊情况处理,这确实是不寻常的需要。
如果您有兴趣阅读这里的人们对兼容性的看法,可以看看Which, if any, C++ compilers do tail-recursion optimization?
GCC也能够优化C++指向成员的指针版本:

#include <stdint.h>
#include <stdio.h>

class Interpreter {
   public:
    using operation_t = void (Interpreter::*)();

    operation_t program[3];

    // VM registers
    int32_t ra = 5, rb = 3;
    operation_t const* rpp = program;

    Interpreter()
        : program{&Interpreter::op_add, &Interpreter::op_print,
                  &Interpreter::op_halt} {}

    void exec_next_op() { (this->**(rpp++))(); }

    void op_add() {
        ra += rb;
        exec_next_op();
    }

    void op_print() {
        printf("%d\n", ra);
        exec_next_op();
    }

    void op_halt() {}
};

int main(int argc, char const* argv[]) {
    // Kick off execution
    Interpreter interp;
    interp.exec_next_op();
    return 0;
}

https://godbolt.org/z/n43rYP81r

v1uwarro

v1uwarro6#

使用现代的编译器,你不需要计算后藤。
我创建了以下代码:

void __attribute__((noinline)) computed(uint8_t x)
{
        switch (x)
        {
                case 0:
                        goto lab0;
                case 1:
                        goto lab1;
                case 2:
                        goto lab2;
                case 3:
                        goto lab3;
                case 4:
                        goto lab4;
                case 5:
                        goto lab5;
                default:
                        abort();
        }
lab0:
        printf("A\n");
        return;
lab1:
        printf("B\n");
        return;
lab2:
        printf("C\n");
        return;
lab3:
        printf("D\n");
        return;
lab4:
        printf("E\n");
        return;
lab5:
        printf("F\n");
        return;
}
int main(int argc, char **argv)
{
        computed(3);
        return 0;
}

使用gcc(9.4.0)和clang(10.0.0),在优化级别0下,我检查了汇编代码,它确实在优化级别0下使用了calculated后藤(在更高的优化级别下,clang发现printfs非常相似,只是调用其中一个变量作为参数)。
你只需要创建一个足够长的switch case表,它从0开始,有连续的索引,并且每个case都有一个后藤(除了默认的case),它会自动转换成一个计算的goto。
显式使用calculated后藤的问题在于它是一个非标准的语言扩展,使你的代码只能在非标准的编译器上编译,在标准编译器上编译会更好。即使一个非常糟糕的编译器不能判断出计算后藤是最好的方法,并且反复检查x和一长串常量以判断出正确的分支(其将仅包含单个跳转指令)。

相关问题