Does several levels of base classes slow down a cl

Question

Does having several levels of base classes slow down a class? A derives B derives C derives D derives F derives G, ...

Does multiple inheritance slow down a class?

Answer 1

There is no speed difference between virtual calls at different levels since they all get flattened out into the vtable (pointing to the most derived versions of the overridden methods). So, calling ((A*)inst)->Method() when inst is an instance of B is the same overhead as when inst is an instance of D.

Now, a virtual call is more expensive than a non-virtual call, but this is because of the pointer dereference and not a function of how deep the class hierarchy actually is.

Answer 2

Non-virtual function-calls have absolutely no performance hit at run-time, in accordance with the c++ mantra that you shouldn't pay for what you don't use. In a virtual function call, you generally pay for an extra pointer lookup, no matter how many levels of inheritance, or number of base classes you have. Of course this is all implementation defined.

Edit: As noted elsewhere, in some multiple inheritance scenarios, an adjustment to the 'this' pointer is required before making the call. Raymond Chen describes how this works for COM objects. Basically, calling a virtual function on an object that inherits from multiple bases can require an extra subtraction and a jmp instruction on top of the extra pointer lookup required for a virtual call.

Answer 3

Almost all answers point toward whether or not virtual methods would be slower in the OP's example, but I think the OP is simply asking if having several level of inheritance in and of itself is slow. The answer is of course no since this all happens at compile-time in C++. I suspect the question is driven from experience with script languages where such inheritance graphs can be dynamic, and in that case, it potentially could be slower.

Answer 4

Calling a virtual function is slightly slower than calling a nonvirtual function. However, I don't think it matters how deep your inheritance tree is.

But this is not a difference that you should normally be worried about.

Answer 5

Virtual calls themselves are more time consuming than normal calls because it has to lookup the address of the actual function to call from the vtable

Additionally compiler optimizations like inlining might be hard to perform due to the lookup requirement. Situations where inlining is not possible itself can lead to quite a high overhead due to stack pop and push and jump operations

Here is a proper study which says the overhead can be as high as 50% http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf

Here is another resource that looks at a side effect of having a large library of virtual classes http://keycorner.org/pub/text/doc/kde-slow.txt

The dispatching of the virtual calls with multiple inheritances is compiler specific, so the implementation will also have an effect in this case.

Regarding your specific question of having a large no of base classes, usually the memory layout of a class object would have the vtbl ptrs for all the other constituent classes within it.

Check this page for a sample vtable layout - http://www.codesourcery.com/public/cxx-abi/cxx-vtable-ex.html

So a call to a method implemented by a class deeper into the heierarchy would still only be a single indirection and not multiple indirections as you seem to think. The call does not have to navigate from class to class to finally find the exact function to call.

However if you are using composition instead of inheritance each pointer call would be a virtual call and that overhead would be present and if within that virtual call if that class uses more compositio,n more virtual calls would be made. That kindof a design would be slower depending on the amount of calls you made.

Answer 6

As pointed out by Corey Ross the vtable is known at compile time for any leaf derived class, and so the cost of the virtual call really should be the same irrespective of the structure of the hierarchy.

This, however, cannot be said for dynamic_cast. If you consider how you might implement dynamic_cast, a basic approach will be have an O(n) search through your hierarchy!

In the case of a multiple inheritance hierarchy, you are also paying a small cost to convert between different classes in the hierarchy:

sturct A { int i; };
struct B { int j; };

struct C : public A, public B { int k ; };

// Let's assume that the layout of C is:  { [ int i ] [ int j ] [int k ] }

void foo (C * c) {
  A * a = c;                // Probably has zero cost
  B * b = c;                // Compiler needed to add sizeof(A) to 'c'
  c = static_cast<B*> (b);  // Compiler needed to take sizeof(A)' from 'b'
}