"Inlining" (kind of) functions at runtime in C

Question

Hi,

I was thinking about a typical problem that is very JIT-able, but hard to approach with raw C. The scenario is setting up a series of function pointers that are going to be "composed" (as in maths function composition) once at runtime and then called lots and lots of times.

Doing it the obvious way involves many virtual calls, that are expensive, and if there are enough nested functions to fill the CPU branch prediction table completely, then the performance with drop considerably.

In a language like Lisp, I could probably process the code and substitute the "virtual" call by the actual contents of the functions and then call compile to have an optimized version, but that seems very hacky and error prone to do in C, and using C is a requirement for this problem ;-)

So, do you know if there's a standard, portable and safe way to achieve this in C?

Cheers

Answer 1

You might want to look at LLVM. They have a library that allows for JITing code (and much more things) from C, it supports many platforms and it's an open source project: http://llvm.org/

Answer 2

I have two suggestions on eliminating your virtual function calls, if necessary for performance. For the sake of illustration, suppose you have a function taking a function pointer as an argument:

void my_algorithm(int (*func)(...), ...)
{
    /* ... */
}

And also suppose you know in advance all possible values the function pointer can take. For example:

my_algorithm(func_1, ...);
//...
my_algorithm(func_2, ...);

First convert your original my_algorithm() into a macro:

#define MY_ALGORITHM(func, ...)       \
{                                     \
    /* ... */                         \
}

Then rewrite my_algorithm() as:

extern int func_1(...);
extern int func_2(...);

void my_algorithm(int (*func)(...), ...)
{
    if (func == func_1)
        MY_ALGORITHM(func_1, ...)
    else if (func == func_2)
        MY_ALGORITHM(func_2, ...)
    else
        assert(0 && "Unexpected function arg to my_algorithm()");
}

This will of course double the size of the compiled object file. And, on the surface, it removes only one level of indirection. But if func_1 and/or func_2 are inlined, you could get a considerable speed-up.

And you can even 'pass' macros, as in:

#define HYPOT_Y(x) hypot(x, y)
MY_ALGORITHM(HYPOT_Y, ...);     //assumes y is known

The second suggestion is a variation of this, using X Macros ( http://en.wikipedia.org/wiki/C_preprocessor#X-Macros ). Instead of the #define, put the body of the original my_algorithm() into a separate file, my_algorithm.h. Then rewrite my_algorithm() as:

void my_algorithm(int (*func)(...), ...)
{
    if (func == func_1)
        #define func func_1
        #include "my_algorithm.h"
        #undef func
    else if (func == func_2)
        #define func func_2
        #include "my_algorithm.h"
        #undef func
    else
        assert(0 && "Unexpected function arg to my_algorithm()");
}

I would probably use X macros if the code is more than a couple of dozen lines. Its advantages include (no pun intended):

• No ugly backslashes
• Easier debugging (e.g. back traces and single-stepping).

This is all standard C. But rather old school.

Answer 3

If you're ok with supporting x86 only, you could try embedding TCC:

http://bellard.org/tcc/