title: How to speed up dynamic dispatch by 20% using computed gotos in standard C++
body: <h1>Before you down-vote or start saying that <code>goto</code>ing is evil and obsolete, please read the justification of why it is viable in this case. Before you mark it as duplicate, please read the full question.</h1>
  <p>I was reading about virtual machine interpreters, when <a href="https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables" rel="noreferrer">I stumbled across <em>computed gotos</em></a> . Apparently they allow significant performance improvement of certain pieces of code. The most known example is the main VM interpreter loop.</p>
  <p>Consider a (very) simple VM like this:</p>
  <pre><code>#include &lt;iostream&gt;
  
  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 &lt;&lt;= 1;
              break;
          case Opcode::BIT_RIGHT:
              result &gt;&gt;= 1;
              break;
          case Opcode::RET:
              std::cout &lt;&lt; result;
              return 0;
          }
      }
  }
  </code></pre>
  <p>All this VM can do is a few simple operations on one number of type <code>int</code> and print it. In spite of its doubtable usefullness, it illustrates the subject nonetheless.</p>
  <p>The critical part of the VM is obviously the <code>switch</code> statement in the <code>for</code> loop. Its performance is determined by many factors, of which the most inportant ones are most certainly <a href="https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-ansta-unsorted-array/11227902#11227902">branch prediction</a> and the action of jumping to the appropriate point of execution (the <code>case</code> labels).</p>
  <p>There is room for optimization here. In order to speed up the execution of this loop, one might use, so called, <em>computed gotos</em>.</p>
  <h1>Computed Gotos</h1>
  <p>Computed gotos are a construct well known to Fortran programmers and those using a certain (non-standard) GCC extension. I do not endorse the use of any non-standard, implementation-defined, and (obviously) undefined behavior. However to illustrate the concept in question, I will use the syntax of the mentioned GCC extension.</p>
  <p>In standard C++ we are allowed to define labels that can later be jumped to by a <code>goto</code> statement:</p>
  <pre><code>goto some_label;
  
  some_label:
      do_something();
  </code></pre>
  <p>Doing this isn't considered good code (<a href="https://stackoverflow.com/questions/3517726/what-is-wrong-with-using-goto">and for a good reason!</a>). Although there are good arguments against using <code>goto</code> (of which most are related to code maintainability) there is an application for this abominated feature. It is the improvement of performance.</p>
  <p><a href="https://stackoverflow.com/questions/14190274/are-goto-statements-efficient-when-compared-to-calling-functions">Using a <code>goto</code> statement can be faster than a function invocation.</a> This is because the amount of &quot;paperwork&quot;, like setting up the stack and returning  a value, that has to be done when invoking a function. Meanwhile a <code>goto</code> can sometimes be converted into a single <code>jmp</code> assembly instruction.</p>
  <p>To exploit the full potential of <code>goto</code> an extension to the GCC compiler was made that allows <code>goto</code> to be more dynamic. That is, the label to jump to can be determined at run-time.</p>
  <p>This extension allows one to obtain a <em>label pointer</em>, similar to a function pointer and <code>goto</code>ing to it:</p>
  <pre><code>    void* label_ptr = &amp;&amp;some_label;
      goto (*label_ptr);
  
  some_label:
      do_something();
  </code></pre>
  <p>This is an interesting concept that allows us to further enhance our simple VM. Instead of using a <code>switch</code> statement we will use an array of label pointers (a so called <em>jump table</em>) and than <code>goto</code> to the appropriate one (the opcode will be used to index the array):</p>
  <pre><code>// [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[] = {
          &amp;&amp;do_halt, &amp;&amp;do_inc, &amp;&amp;do_dec, &amp;&amp;do_mul2,
          &amp;&amp;do_div2, &amp;&amp;do_add7, &amp;&amp;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();
      }
  }
  </code></pre>
  <p>This version is about 25% faster than the one that uses a <code>switch</code> (the one on the linked blog post, not the one above). This is because there is only one jump performed after each operation, instead of two.</p>
  <p>Control flow with <code>switch</code>:
  <a href="https://i.stack.imgur.com/yUqqm.png" rel="noreferrer"><img src="https://i.stack.imgur.com/yUqqm.png" alt="2 jumps with switch" /></a>
  For example, if we wanted to execute <code>Opcode::FOO</code> and then <code>Opcode::SOMETHING</code>, it would look like this:
  <a href="https://i.stack.imgur.com/vsVvp.png" rel="noreferrer"><img src="https://i.stack.imgur.com/vsVvp.png" alt="enter image description here" /></a>
  As you can see, there are two jumps being performed after an instruction is executed. The first one is back to the <code>switch</code> code and the second is to the actual instruction.</p>
  <p>In contrary, if we would go with an array of label pointers (as a reminder, they are non-standard), we would have only one jump:
  <a href="https://i.stack.imgur.com/ns9cl.png" rel="noreferrer"><img src="https://i.stack.imgur.com/ns9cl.png" alt="enter image description here" /></a></p>
  <p>It is worthwhile to note that in addition to saving cycles by doing less operations, we also enhance the quality of branch prediction by eliminating the additional jump.</p>
  <p>Now, we know that by using an array of label pointers instead of a <code>switch</code> we can improve the performance of our VM significantly (by about 20%). I figured that maybe this could have some other applications too.</p>
  <p>I came to the conclusion that this technique could be used in any program that has a loop in which it sequentially indirectly dispatches some logic. A simple example of this (apart from the VM) could be invoking a <code>virtual</code> method on every element of a container of polymorphic objects:</p>
  <pre><code>std::vector&lt;Base*&gt; objects;
  objects = get_objects();
  for (auto object : objects)
  {
      object-&gt;foo();
  }
  </code></pre>
  <p>Now, this has much more applications.</p>
  <p>There is one problem though: There is nothing such as label pointers in standard C++. As such, the question is: Is there a way to simulate the behaviour of computed <code>goto</code>s in standard C++ <strong>that can match them in performance?</strong>.</p>
  <h1>Edit 1:</h1>
  <p>There is yet another down side to using the switch. I was reminded of it by <a href="https://stackoverflow.com/questions/58774170/speed-up-dynamic-dispatch-by-simulating-computed-goto-in-c#comment103834651_58774170">user1937198</a>. It is bound checking. In short, it checks if the value of the variable inside of the <code>switch</code> matches any of the <code>case</code>s. It adds redundant branching (this check is mandated by the standard).</p>
  <h1>Edit 2:</h1>
  <p><a href="https://stackoverflow.com/questions/58774170/speed-up-dynamic-dispatch-by-simulating-computed-goto-in-c#comment103834776_58774170">In response to cmaster</a>, I will clarify what is my idea on reducing overhead of virtual function calls. A dirty approach to this would be to have an id in each derived instance representing its type, that would be used to index the jump table (label pointer array). The problem is that:</p>
  <ol>
  <li>There are no jump tables is standard C++</li>
  <li>It would require as to modify all jump tables when a new derived class is added.</li>
  </ol>
  <p>I would be thankful, if someone came up with some type of template magic (or a macro as a last resort), that would allow to write it to be more clean, extensible and automated, like this:</p>