Branching optimization

Question

What is the best implementation, from a performance point of view, of branched function calls?

In the naive case we have a rather large switch statement that interprets bytecode and executes a function call depending on code.

In the normal case we have computed gotos and labels that do the same thing.

What is the absolute best way to do this?

An abstract example,

schedule: 
    swap_entity();
    goto *entity_start();

lb_code1:
    do_stuff();
    goto *next_code_item();

lb_code2:
    do_stuff();
    goto *next_code_item();

...

Edit: My reference to "branched function calls" was perhaps somewhat erroneous. Branched code execution.

Answer 1

Maybe an array of function pointers, at a guess:

void dispatch(Message* message)
{
  //MessageType is a finite enum
  MessageType messageType = message->messageType;
  int index = (int)messageType;
  //there's an array element for each enum value
  FunctionPointer functionPointer = arrayOfFunctionPointers[index];
  (*functionPointer)(message);
}

The actual answer is hardware-dependent, and depends on things like the size of the problem and the CPU's cache.

Answer 2

It depends. Some table driven approach will normally be fastest, but you may well find that is what your switch statement is implemented as. Certainly, you should not take it as read that ANY recommendation in this area from SO users is the best. If we suggest something, you need to implement it and measure the performance in a build with all compiler optimisations turned on.

Answer 3

If you're looking for a speed boost here, you should look at other bytecode dispatch mechanisms. There was a question which sort-of asked that before.

Basically, you now have a goto which is probably incorrectly predicted every time, followed by a function call. With a technique like direct threading, you can probably reduce your interpreter overhead significantly. Inline threading is harder, but with greater benefit.

I gave some further resources in the other question.