what is the fastest way of calling and executing a function in C?

Question

I have a lot of functions(huge list) defined and compiled. And I use function pointers to call and execute the functions by sending arguments dynamically during runtime. It is an iterative process involving more than hundred thousand function calls every iteration. I want to know which is the efficient way of calling an compiled function. I feel my way is slower.

Answer 1

You need to profile your program to know if this is a problem. If you're spending 99% of your time in the individual functions, the best improvement you can hope for is 1%, and even that would be unlikely.

Answer 2

Well you could create your own function linker that can link together certain function "fragments" call orders and cache them to avoid overheads. It probably won't help you much though.

A lot depends on the size of the functions. How close they are to each other in memory and all sorts of other things. There would be little point in removing function pointers, for example, if the 2nd function call was right after the first in memory as the start of that function would likely already be cached.

Its not a simple question to answer even if you DID give us a few more details.

As Mark says ... A profiler is your friend.

Answer 3

The only way you can speed up function calls is if the compiler knows what function it will be calling.

That is, something like:

void foo(void)
{
    /* do some stuff */
}

int main(void)
{
    foo();
}

Could be inlined to:

int main(void)
{
    /* do some stuff */
}

But if the compiler doesn't know which one to call:

void foo(void)
{
    /* do some stuff */
}

void bar(void)
{
    /* do some other stuff */
}

typedef void(*Function)(void);

int main(void)
{
    Function func = /* choose a function at runtime */
    func();
}

The compiler cannot possibly predict which function will be called, and therefore cannot inline it.

If your compiler supports it, you might try using __fastcall, but you need to profile your code and see if it made a positive difference.

This one level of indirection isn't going to make a huge difference. Profile your code and find where the real slowdowns are.

Answer 4

This depends on how you're determining which of these hundreds of thousands of functions to call. If you're doing a linear search through your function pointer list, then yes, you're probably wasting a lot of time. In this case, you should look into putting the function pointers into a hash table, or at least storing them in a sorted list so you can do a binary search. Without more information about what you are doing, and how you're doing it, it's difficult to give you useful advice.

Also you definitely need to profile, as others have pointed out. It sounds like you don't know if what you're doing is slow, in which case you also don't know whether it's worth trying to optimize it.

Answer 5

The overhead of calling functions is mostly a combination of:

• the function call itself
• the parameters you pass
• the retun value
• the number of times you need to call the function

So to start with, ask questions:

• can you change the algorithm to require fewer function calls?
• can you reduce the amount of data you have to pass back and forth?
• can you change the algorithm to batch its calls to each function (so that you can process a group of values in one call, or at least call the same function repeatedly for a group of values so that all the code stays in the CPU's cache memory)?

Once you have a good algorithm and an efficient implementation, you would have to move down to lower level optimisation methods - you could use assembler to do your own function calling protocol that requires less data to be pushed on the stack. If they are "leaf functions" (that don't call other functions) you may not even need to use a stack, so can avoid a few instructions of overhead on every call. (Some of this could possibly be done in C by replacing function calls with gotos - it's very ugly though)

Lastly, you can get into the realms of self-modifying code - build new machine code out of snippets representing the functions and then call the generated code. This can get very processor specific and tricky though - it's pretty low level.

Answer 6

You should use a tool like QProf, Valgrind, or gprof to profile your code and see where the most execution time is being spent. Based on the results, you should optimize the function(s) that are taking up the most time.

If the list iteration procedure really is taking up most of the code's time, then you should try to optimize the calls. If you're searching through the list to find a given function, you might try making a list of the most frequently used functions, or ordering them by call frequency so that your search algorithm doesn't have to look as far into the list to find the function it's looking for.

Answer 7

The number of extra instructions required to dereference a function pointer should be a very small fraction of the number of instructions that make up the body of the function. Aggressively inlining every function call will not make a huge difference. As suggested by the earlier answers, you really need to use a profiler to determine the bottlenecks.

In the big scheme of things, shaving off a few instructions here or there will not make any significant improvements. The big wins will come from improving your algorithms.