Can you make a computed goto in C++

Question

Fortran has a computationally efficient way called a 'computed goto'. The construct uses an index into a branch table to perform a direct goto. If I remember correctly the syntax is:

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

where the index is used to reference a code pointer (label) in the parenthesized list.

I have a case where a computed goto is a better solution than a switch statement and would like to construct one, but I can't figure out how.

Now before the jibes and slings arrive, it is possible for the compiler to optimize a computed goto, but I have no guarantee that it will.

---

A switch statement can always be used. In some cases a switch statement can be optimized to a jump table (the implementation of a computed goto).

However, this is only possible when the range of case values is an almost dense covering (there is almost a case statement for each integer in the range of low values to high values). When this is not the case, the implementation will probably be a binary tree. The compiler writer has a choice to optimize to a jump table when appropriate or not. Where a binary tree will always satisfy the semantics of a switch statement, where sometimes a jump table is sufficient lets me ask whether I can guarantee a jump table when appropriate. I have no control over the compiler writer.

As a simple case, I often write lexers (FSMs), and I use three data constructs, one to map the input into an acceptable alphabet, one to perform node transitions, and one to execute some code based on the current state and the input value. The implementation of the FSM is a Mealy machine, not a Moore machine, so actions are performed on arcs (transitions) and not on nodes.

The actions performed are typically small, often no more than a line of source code. I recognize that functions can be used, and that their use removes the need for a jump table. But I believe that I can not 'point' to an inline function, and therefore functions are closed-form callable procedures.

This is less efficient in most cases, than a switch statement with or without jump table optimization. If I can use a jump table then I avoid the issue of what the compiler writer thinks of optimization and am able to write efficient code.

As to the general case brought up below about the issues related to a Fortran computed goto: This is not a criticism of that/those comment. But the qualitative issues, even though they are true, does not answer the question.

There is an answer below using void* &&label; and I'd like to thank you for that. But, alas, as you pointed out this is non-standard C/C++ and is likely not to be present in the future. So, it's better not to do this.

I hope that I've answered the 'get a better compiler' comment. And I hope I've at least addressed the issues with using function pointers. And at last, this was a moment of curiosity for me. I didn't think that I should provide the germicidal history of why I thought the question had some carrying power. But now I know. Whenever, and I mean whenever, I write to this group I better tell you what all my duckies are so that they can be shot down good and proper.

Answer 1

If you compile with a recent GCC compiler (e.g., GCC 7 or GCC 6) - or even, for C code, older versions of GCC, you could use its labels as values language extension (so outside of C++11 or C++14 standards), which works with both C & C++. The prefix && operator gives the address of a label, and the goto is computed if followed by * indirection operator. You'll better have target labels starting some blocks.

For example:

#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 course, for the above code, a plain switch would be preferable, and probably as efficient)}

BTW, recent Clang (e.g., clang++-5.0) also accepts that extension.

^{(Computed gotos are not exception-friendly, so they could disappear in future versions of GCC for C++.)}

And with threaded code programming techniques, you could write some quite efficient (bytecode) interpreters using that, and in that particular case the code stays very readable (because it is very linear) and is quite efficient. BTW, you could hide such computed gotos with macros and conditional compilation - e.g., #if-s- (e.g., to use instead switch on compilers not supporting that extension); then your code would be quite portable. For an example in C, look into OCaml's runtime/interp.c.

Answer 2

... whether I can guarantee a jump table when appropriate. I have no control over the compiler writer.

No, you cannot. In fact, given that this is C, even if you were to cleverly implement your own jump table, you have no guarantees that the compiler won’t undo your efforts. If you want a guarantee, you have to write in assembly yourself. Compilers are only held to the "as-if" standard. They must do something which as-if they did what you told them to do.

Most compilers are very good at this sort of optimization. You aren't the first developer to develop parsers. In fact, I would expect them to use jump tables when efficient and not use jump tables when it is inefficient. You might accidentally make it do something less efficient. Compilers typically have a large database of CPU timings that they draw upon to decide how best to write opcodes.

Now, if you can't make your code into a garden variety switch statement, you might be able to emulate this with a custom switch statement.

To replace go to index (label1, label2, ...), try

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

}

It looks like those trampolines are "real," but I would expect any compiler worth its salt to do a pretty darn good job of optimizing this for you. Thus, this solution is compiler-specific, but it should work out in a wide variety of reasonable compilers. Statically-computable control flow is something compilers have been eating up for 30+ years. For instance, I know every compiler I've worked with can take

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

if (!found)
    return false;

doSomething();

And turn it into effectively

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

return false;

label1:
doSomething();

But in the end, no, there isn't any construct to guarantee beyond a shadow of a doubt that a particular Fortran-inspired method is used under the hood in C. You will always have to test against your compiler. However, trust the compiler. And profile. Make sure this is a hot spot before you choose to die on a pyre over it.

Answer 3

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]();
}

Test code:

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

outputs 101.

Live example

If you want large amounts of gaps, extra work will have to be done. Short "gaps" can be handled with invalid jump target:

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

which should segmentation fault if actually called.

For a really sparse table, you'd want to pass in compile-time constants for table size and compile time indexes of each target, then build the table up from that. Depending on how efficient you want to be, that may require reasonably fancy compile time programming.