optimizing calling an array of function pointers

Question

I have the following loop which calls all function pointers in an array:

for(auto f : program) {
   f();
}

I'd like to optimize this. So far, I've tried two methods:

1. Tail recursion
2. JITting threaded code

Here is the complete test code: https://coliru.stacked-crooked.com/a/d639f024b1222c54

The timing results on my machine (iMac Pro 8-Core) are:

naive: 0.530534
tail recursion: 0.265192
JIT threaded: 0.125106

Of course the functions all have to be modified to facilitate tail recursion, but that's ok. What would be less pleasant in terms of code cleanliness would be to put everything in one function and use something like computed goto (I've tried that too, actually, and computed goto is only slightly faster than tail recursion on my machine.)

Can I do better than tail recursion without JITting? (on iOS, JITting is not allowed)

Note that the functions cannot be re-ordered.

Answer 1

Yes. We can in fact beat the threaded code without JITting.

The test code consists of 100 possible functions. I wrote a little program to generate code for a 100x100 array of functions which call pairs of those 100 functions. The optimizer inlines the original 100 into the pairs. We now have:

naive: 0.534162
tail recursion: 0.269307
JIT threaded: 0.124608
pairs: 0.085922

This technique could be generalized to real-world cases by analyzing common sequences of function calls, rather than generating all possible pairs.

This could be combined with tail recursion for even faster dispatch.