Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Can anyone explain in detail, how exactly the virtual table works & what pointers are associated when virtual functions are called. If they are actually slower, can you show the time that the virtual function takes to execute is more than normal class methods? It is easy to lose track of how/what is happening without seeing some code.

share|improve this question
2  
Looking up the correct method call from a vtable is obviously going to take longer than calling the method directly, since there is more to do. How much longer, or whether that additional time is significant within the context of your own program, is another question. en.wikipedia.org/wiki/Virtual_method_table –  Robert Harvey Mar 22 '13 at 22:47
4  
Slower than what exactly? I've seen code that had a broken, slow implementation of dynamic behavior with lots of switch statements just because some programmer had heard that virtual functions are slow. –  Christopher Creutzig Mar 22 '13 at 23:06
3  
Often times, it's not that virtual calls themselves are slow, but that the compiler has no ability to inline them. –  Kevin Hsu Mar 23 '13 at 0:40
1  
@Kevin Hsu: yes this is it absolutely. Almost any time someone tells you they got a speed up from eliminating some "virtual function call overhead", if you look into it where all the speedup has actually come from will be from optimisations which are now possible because the compiler couldn't optimise across the indeterminate call previously. –  timday Mar 23 '13 at 1:26
3  
Even a person who can read the assembly code cannot accurately predict its overhead in actual CPU execution. Desktop-based CPU makers have invested in decades of research in not only branch prediction, but also value prediction and speculative execution for the primary reason of masking the latency of virtual functions. Why? Because desktop OSes and software uses them a lot. (I wouldn't say the same about mobile CPUs.) –  rwong Mar 23 '13 at 4:44

4 Answers 4

up vote 20 down vote accepted

Virtual methods are commonly implemented via so-called virtual method tables (vtable for short), in which function pointers are stored. This adds indirection to the actual call (gotta fetch the address of the function to call from the vtable, then call it -- as opposed to just calling it right ahead). Of course, this takes some time and some more code.

However, it is not necessarily the primary cause of slowness. The real problem is that the compiler (generally/usually) cannot know which function will be called. So it can't inline it or perform any other such optimizations. This alone might add a dozen pointless instructions (preparing registers, calling, then restoring state afterwards), and might inhibit other, seemingly unrelated optimizations. Moreover, if you branch like crazy by calling many different implementations, you suffer the same hits you'd suffer from branching like crazy via other means: The cache and branch predictor won't help you, the branches will take longer than a perfectly predictable branch.

Big but: These performance hits are usually too tiny to matter. They're worth considering if you want to create a high-performance code and consider adding a virtual function that would be called at alarming frequency. However, also keep in mind that replacing virtual function calls with other means of branching (if .. else, switch, function pointers, etc.) won't solve the fundamental issue -- it may very well be slower. The problem (if it exists at all) isn't virtual functions but (unnecessary) indirection.

Edit: The difference in the call instructions is described in other answers. Basically, the code for a static ("normal") call is:

  • Copy some registers on the stack, to allow the called function to use those registers.
  • Copy the arguments into predefined locations, so that the called function can find them regardless from where it is called.
  • Push the return address.
  • Branch/jump to the function's code, which is a compile-time address and hence hardcoded in the binary by the compiler/linker.
  • Get the return value from a predefined location and restore registers we want to use.

A virtual call does exactly the same thing, except that the function address is not known at compile time. Instead, a couple of instructions ...

  • Get the vtable pointer, which points to an array of function pointers (function addresses), one for each virtual function, from the object.
  • Get the right function address from the vtable into a register (the index where the correct function address is stored is decided at compile-time).
  • Jump to the address in that register, rather than jumping to a hardcoded address.

As for branches: A branch is anything which jumps to another instruction instead of just letting the next instruction execute. This includes if, switch, parts of various loops, function calls, etc. and sometimes the compiler implements things that don't seem to branch in a way that actually needs a branch under the hood. See Why is processing a sorted array faster than an unsorted array? for why this may be slow, what CPUs do to counter this slowdown, and how this isn't a cure-all.

share|improve this answer
1  
BTW: I really don't understand why the C++ community so adamantly ignores all of the 5 decades of research that the Lisp, Smalltalk, Java and JavaScript communities have been doing in making virtual dispatch blazingly fast. Stuff like Polymorphic Inline Caching and Speculative Inlining, just the entire field of Adaptive Optimizations in general. –  Jörg W Mittag Mar 23 '13 at 2:12
    
@JörgWMittag they are all interpreter stuff, and they are still slower than the binary code generated by C++ compilers –  vasile Mar 23 '13 at 7:36
3  
@JörgWMittag These optimizations primarily exist to make indirection/late binding (almost) free when it isn't needed, because in those languages every call is technically late-bound. If you really do call lots of different virtual methods from one place over a short time, these optimizations don't help or actively hurt (create lots of code for naught). C++ guys aren't very interested in those optimizations because they're in a very different situation ... –  delnan Mar 23 '13 at 10:41
3  
@JörgWMittag ... C++ guys aren't very interested in those optimizations because they're in a very different situation: The AOT-compiled vtable way is already pretty fast, very few calls are actually virtual, many cases of polymorphism are early-bound (via templates) and hence amendable to AOT optimization. Finally, doing these optimizations adaptively (instead of just speculating at compile time) requires run-time code generation, which introduces tons of headache. JIT compilers have already solved those problems for other reasons, so they don't mind, but AOT compilers want to avoid it. –  delnan Mar 23 '13 at 10:44
1  
great answer, +1. One thing to note though is sometimes the results of branching are known at compile time, for example when you write framework classes that need to support different uses but once application code interacts with those classes the specific use is already known. In this case, the alternative to virtual functions, could be C++ templates. Good example would be CRTP, which emulates virtual function behavior without any vtables: en.wikipedia.org/wiki/Curiously_recurring_template_pattern –  DXM Mar 23 '13 at 17:26

Here's some actual disassembled code from a virtual function call and a non-virtual call, respectively:

mov    -0x8(%rbp),%rax
mov    (%rax),%rax
mov    (%rax),%rax
callq  *%rax

callq  0x4007aa

You can see that the virtual call requires three additional instructions to look up the correct address, whereas the address of the non-virtual call can be compiled in.

However, note that most of the time that extra lookup time can be considered negligible. In situations where the lookup time would be significant, like in a loop, the value can usually be cached by doing the first three instructions before the loop.

The other situation where the lookup time becomes significant is if you have a collection of objects and you're looping through calling a virtual function on each of them. However, in that case, you're going to need some means of selecting which function to call anyway, and a virtual table lookup is as good a means as any. In fact, since the vtable lookup code is so widely used it is heavily optimized, so trying to work around it manually has a good chance of resulting in worse performance.

share|improve this answer
1  
The thing to understand is that the vtable lookup and indirect call will in almost all cases have negligible impact on the total running time of the method being called. –  John R. Strohm Mar 23 '13 at 5:46
4  
@JohnR.Strohm One man's negligible is another man's bottleneck –  James Mar 23 '13 at 17:00
    
-0x8(%rbp). oh my... that AT&T syntax. –  Abyx Mar 24 '13 at 17:22

Slower than what?

Virtual functions solve a problem that cannot be solved by direct function calls. In general, you can only compare two programs which compute the same thing. "This ray tracer is faster than that compiler" doesn't make sense, and this principle generalizes even to small things like individual functions or programming language constructs.

If you don't use a virtual function to dynamically switch to a piece of code based on a datum, such as an object's type, then you will have to use something else, like a switch statement to accomplish the same thing. That something else has its own overheads, plus implications on the organization of the program which influence its maintainability and global performance.

Note that in C++, calls to virtual functions are not always dynamic. When calls are made on an object whose exact type is known (because the object isn't a pointer or reference, or because its type can otherwise be statically inferred) then the calls are just regular member function calls. That not only means that there isn't dispatch overhead, but also that these calls can be inlined in the same way as ordinary calls.

In other words, your C++ compiler can work out when virtual functions do not require virtual dispatch, so there is usually no reason to worry about their performance relative to non-virtual functions.

share|improve this answer
1  
"Slower than what?" - if you make a method virtual that doesn't have to be, you have pretty good comparison material. –  tdammers Mar 23 '13 at 13:03

because a virtual call is equivalent to

res_t (*foo)(arg_t);
foo = (obj->vtable[foo_offset]);
foo(obj,args)

where with a non-virtual function the compiler can constant-fold the first line, this is a dereference an addition and a dynamic call transformed into just a static call

this also lets it inline the function (with all due optimization consequences)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.