Does Function pointer make the program slow?

Question

I read about function pointers in C. And everyone said that will make my program run slow. Is it true?

I made a program to check it. And I got the same results on both cases. (measure the time.)

So, is it bad to use function pointer? Thanks in advance.

To response for some guys. I said 'run slow' for the time that I have compared on a loop. like this:

int end = 1000;
int i = 0;

while (i < end) {
 fp = func;
 fp ();
}

When you execute this, i got the same time if I execute this.

while (i < end) {
 func ();
}

So I think that function pointer have no difference of time and it don't make a program run slow as many people said.

Solution 1

You see, in situations that actually matter from the performance point of view, like calling the function repeatedly many times in a cycle, the performance might not be different at all.

This might sound strange to people, who are used to thinking about C code as something executed by an abstract C machine whose "machine language" closely mirrors the C language itself. In such context, "by default" an indirect call to a function is indeed slower than a direct one, because it formally involves an extra memory access in order to determine the target of the call.

However, in real life the code is executed by a real machine and compiled by an optimizing compiler that has a pretty good knowledge of the underlying machine architecture, which helps it to generate the most optimal code for that specific machine. And on many platforms it might turn out that the most efficient way to perform a function call from a cycle actually results in identical code for both direct and indirect call, leading to the identical performance of the two.

Consider, for example, the x86 platform. If we "literally" translate a direct and indirect call into machine code, we might end up with something like this

// Direct call
do-it-many-times
  call 0x12345678

// Indirect call
do-it-many-times
  call dword ptr [0x67890ABC]

The former uses an immediate operand in the machine instruction and is indeed normally faster than the latter, which has to read the data from some independent memory location.

At this point let's remember that x86 architecture actually has one more way to supply an operand to the call instruction. It is supplying the target address in a register. And a very important thing about this format is that it is normally faster than both of the above. What does this mean for us? This means that a good optimizing compiler must and will take advantage of that fact. In order to implement the above cycle, the compiler will try to use a call through a register in both cases. If it succeeds, the final code might look as follows

// Direct call

mov eax, 0x12345678

do-it-many-times
  call eax

// Indirect call

mov eax, dword ptr [0x67890ABC]

do-it-many-times
  call eax

Note, that now the part that matters - the actual call in the cycle body - is exactly and precisely the same in both cases. Needless to say, the performance is going to be virtually identical.

One might even say, however strange it might sound, that on this platform a direct call (a call with an immediate operand in call) is slower than an indirect call as long as the operand of the indirect call is supplied in a register (as opposed to being stored in memory).

Of course, the whole thing is not as easy in general case. The compiler has to deal with limited availability of registers, aliasing issues etc. But is such simplistic cases as the one in your example (and even in much more complicated ones) the above optimization will be carried out by a good compiler and will completely eliminate any difference in performance between a cyclic direct call and a cyclic indirect call. This optimization works especially well in C++, when calling a virtual function, since in a typical implementation the pointers involved are fully controlled by the compiler, giving it full knowledge of the aliasing picture and other relevant stuff.

Of course, there's always a question of whether your compiler is smart enough to optimize things like that...

Solution 2

I think when people say this they're referring to the fact that using function pointers may prevent compiler optimizations (inlining) and processor optimizations (branch prediction). However, if function pointers are an effective way to accomplish something that you're trying to do, chances are that any other method of doing it would have the same drawbacks.

And unless your function pointers are being used in tight loops in a performance critical application or on a very slow embedded system, chances are the difference is negligible anyway.

Solution 3

And everyone said that will make my program run slow. Is it true?

Most likely this claim is false. For one, if the alternative to using function pointers are something like

if (condition1) {
        func1();
} else if (condition2)
        func2();
} else if (condition3)
        func3();
} else {
        func4();
}

this is most likely relatively much slower than just using a single function pointer. While calling a function through a pointer does have some (typically neglectable) overhead, it is normally not the direct-function-call versus through-pointer-call difference that is relevant to compare.

And secondly, never optimize for performance without any measurements. Knowing where the bottlenecks are is very difficult (read impossible) to know and sometimes this can be quite non-intuitively (for instance the linux kernel developers have started removing the inline keyword from functions because it actually hurt performance).

Solution 4

A lot of people have put in some good answers, but I still think there's a point being missed. Function pointers do add an extra dereference which makes them several cycles slower, that number can increase based on poor branch prediction (which incidentally has almost nothing to do with the function pointer itself). Additionally functions called via a pointer cannot be inlined. But what people are missing is that most people use function pointers as an optimization.

The most common place you will find function pointers in c/c++ APIs is as callback functions. The reason so many APIs do this is because writing a system that invokes a function pointer whenever events occur is much more efficient than other methods like message passing. Personally I've also used function pointers as part of a more-complex input processing system, where each key on the keyboard has a function pointer mapped to it via a jump table. This allowed me to remove any branching or logic from the input system and merely handle the key press coming in.

Solution 5

Calling a function via a function pointer is somewhat slower than a static function call, since the former call includes an extra pointer dereferencing. But AFAIK this difference is negligible on most modern machines (except maybe some special platforms with very limited resources).

Function pointers are used because they can make the program much simpler, cleaner and easier to maintain (when used properly, of course). This more than makes up for the possible very minor speed difference.

View more solutions

Comments

[kidsid49]

Suppose the dereference takes a CPU cycle. On a 2GHz machine, that's 500 picoseconds (or 0.5 nanoseconds). Even if it takes more than one cycle, it would still be way less than a millisecond.

[Péter Török]

@Peter K. Thanks - I was really not sure whether it is in the micro- or nanosecond range :-)

[Admin]

+1, I agree, the slowdown will be negligible compared to just about any other piece of code in there.

[Cameron]

The bottom most answer is always the most relevant.

[Nawaz]

How about the possibility of inlining of a function call? This possibility is marginally higher in case of direct call than indirect call, I think.

[weiweishuo]

Yes, I think the overhead many people care about is not the time-waste of dereferencing, but its unfriendly to Predictive execution(compared to a constant address value). But nobody uses function pointer for no reason. A jump table(an array of function pointers) is often generated by compiler when we wrote a long switch-case, for slow prediction is better than wrong prediction.

[Peter Cordes]

This is nonsense. Compilers won't turn a direct call into a register-indirect call (using a call-preserved register like ebx, not eax). call rel32 is just as fast in the correctly-predicted case, has a lower mispredict penalty, and probably consumes fewer branch-prediction resources. Neither Agner Fog's optimization guide, nor Intel's optimization manual (links in the x86 tag wiki) mention this technique, and in fact compilers devirtualize whenever possible (opposite of this), even if they choose not to inline.

[Peter Cordes]

At least a function pointer in a tight loop will predict well. The cost of not inlining can be high, though, especially if the function is small, has multiple args, and/or passes / returns anything by reference.

[Peter Cordes]

The only time you'd choose call reg when you didn't have to is code-size optimization for multiple calls to a helper function from one function. Shorter x86 call instruction

[Peter Cordes]

Branch prediction + speculative execution means the CPU doesn't actually have to wait for a load from memory (or L1d cache) before following a call reg or call [mem] indirect branch. But it does increase the branch-mispredict penalty if the target address can't be checked as early.

[Peter Cordes]

Most modern CPUs have good prediction for indirect branches, as well as for conditional branches. Some older / low-power CPUs have weaker prediction for indirect branches, though. But often they still do ok if a call-site uses the function pointer every time.

[Peter Cordes]

Yes blocking inlining is bad, but the rest of this is wrong. All modern x86 CPUs use out-of-order execution with register renaming which completely avoids all WAW and WAR hazards. An independent write to eax will start a new dependency chain. See agner.org/optimize, and Why does mulss take only 3 cycles on Haswell, different from Agner's instruction tables?.

[HCSF]

Hi, you stated "Function pointers do add an extra dereference which makes them several cycles slower, that number can increase based on poor branch prediction". So it sounds like invoking a function pointer would require a branch prediction? But then you said, " Personally I've also used function pointers...each key on the keyboard has a function pointer mapped to it via a jump table. This allowed me to remove any branching...", implying using a jump table to invoke function pointers can avoid branch prediction miss. Aren't two statement contradicting to each other? Thanks!

[SO_fix_the_vote_sorting_bug]

Even if your claims are true (which they are not, as pointed out by Peter Cordes) the point is whether the program runs faster or slower, not the call instruction. And what about if the memory is out of cache? Shirley, a 200 cycle lag and pipelining penalties would dwarf anything mentioned in this answer, no?