11

Is there any efficiency disadvantage associated with deep inheritance trees (in c++), i.e, a large set of classes A, B, C, and so on, such that B extends A, C extends B, and so one. One efficiency implication that I can think of is, that when we instantiate the bottom most class, say C, then the constructors of B and A are also called, which will have performance implications.

5
  • 1
    Your example doesn't make much sense: if C -> B -> A, then presumably C requires all of the functionality of A and B, so if it wasn't derived from them, its constructor would have to do the same work that the constructors of A and B do. Nov 5, 2011 at 6:43
  • @James Is there no overhead associated with constructor "calls"?, in my example there are 3 "calls" but in yours only one
    – SegFault
    Nov 5, 2011 at 6:48
  • 3
    Please tell me you're not trying to do some awful C#/Java style thing where every class is derived from some single, unifying base class. Nov 5, 2011 at 6:48
  • @Nicol tell me why it is awful
    – SegFault
    Nov 5, 2011 at 6:50
  • 2
    @SegFault: The question is why do you think it is a good idea. There is no need for it. Nov 5, 2011 at 7:21

3 Answers 3

18

Let's enumerate the operations we should consider:

Construction/destruction

Each constructor/destructor will call its base class equivalents. However, as James McNellis pointed out, you were obviously going to do that work anyway. You didn't derived from A just because it was there. So the work is going to get done one way or another.

Yes, it will involve a few more function calls. But function call overhead will be nothing compared to the actual work any significantly deep class hierarchy will have to actually do. If you're at the point where function call overhead is actually important for performance, I would strongly suggest that calling constructors at all is probably not what you want to be doing in that code.

Object Size

In general, the overhead for a derived class is nothing. The overhead for virtual members is a pointer or for virtual inheritance.

Member Function Calls, Static

By this, I mean calling non-virtual member functions, or calling virtual member functions with class names (ClassName::FunctionName syntax). Both of these allow the compiler to know at compile time which function to call.

The performance of this is invariant with the size of the hierarchy, since it's compile-time determined.

Member Function Calls, Dynamic

This is calling virtual functions with the full and complete expectation of runtime calls.

Under most sane C++ implementations, this is invariant with the size of the object hierarchy. Most implementations use a v-table for each class. Each object has a v-table pointer as a member. For any particular dynamic call, the compiler accesses the v-table pointer, picks out the method, and calls it. Since the v-table is the same for each class, it won't be any slower for a class that has a deep hierarchy than one with a shallow one.

Virtual inheritance plays a bit with this.

Pointer Casts, Static

This refers to static_cast or any equivalent operation. This means the implicit cast from a derived class to a base class, the explicit use of static_cast or C-style casts, etc.

Note that this technically includes reference casting.

The performance of static casts between classes (up or down) is invariant with the size of the hierarchy. Any pointer offsets will be compile-time generated. This should be true for virtual inheritance as well as non-virtual inheritance, but I'm not 100% certain of that.

Pointer Casts, Dynamic

This obviously refers to the explicit use of dynamic_cast. This is typically used when casting from a base class to a derived one.

The performance of dynamic_cast will likely change for a large hierarchy. But sane implementations should only check the classes between the current class and the requested one. So it's simply linear in the number of classes between the two, not linear in the number of classes in the hierarchy.

Typeof

This means the use of the typeof operator to fetch the std::type_info object associated with an object.

The performance of this will be invariant with the size of the hierarchy. If the class is a virtual one (has virtual functions or virtual base classes), then it will simply pull it out of the vtable. If it's not virtual, then it's compile-time defined.

Conclusion

In short, most operations are invariant with the size of the hierarchy. But even in the cases where it has an impact, it's not a problem.

I'd be more concerned with some design ethic where you felt the need to build such a hierarchy. In my experience, hierarchies like this come from two lines of design.

  1. The Java/C# ideal of having everything derived from a common base class. This is a horrible idea in C++ and should never be used. Each object should derive from what it needs to, and only that. C++ was built on the "pay for what you use" principle, and deriving from a common base works against that. In general, anything you could do with such a common base class is either something you shouldn't be doing period, or something that could be done with function overloading (using operator<< to convert to strings, for example).

  2. Misuse of inheritance. Using inheritance when you should be using containment. Inheritance creates an "is a" relationship between objects. More often than not, "has a" relationships (one object having another as a member) are far more useful and flexible. They make it easier to hide data, and you don't allow the user to pretend one class is another.

Make sure that your design does not fall afoul of one of these principles.

1
  • Do you have any references or examples for C++ libraries that make good use of "has a" instead of "is a"?
    – sandover
    Dec 10, 2014 at 18:33
2

There will be but not as bad as the programmer performance implications.

2
  • 2
    Throw in a heaping dose of multiple inheritance, and your inheritance tree will become a hedge. Once it's sufficiently thick it will keep all other programmers out of your code ;) Nov 5, 2011 at 7:10
  • @JeremyFriesner: Agreed, though honestly I find judicious use of multiple inheritance easier to understand than a large inheritance tree. Nov 5, 2011 at 7:16
0

As @Nicol points out, it may be doing a number of things. If those are things that you require to be done, regardless of design, because they are all precisely necessary steps in getting the program from call main to exit within the fewest possible cycles, then your design is simply a matter of coding clarity (or maybe lack of it :).

In my experience performance tuning, as in this example, what I often see as a huge source of wasted time is over-design of data (i.e. class) structures. Wierdly enough, the justification for the data structures is often (guess what?) - performance!

In my experience, the thing to do with data structure is keep it as simple as possible and as normalized as possible. If it is completely normalized, then any single change to it can't make it inconsistent. You can't always achieve complete normality, in which case you have to deal with the possibility that the data can be temporarily inconsistent. This is why people write notification handlers, and this is encouraged in OOP. The idea is, if you change something in one place, that can trigger notifications that "automatically" propagate the change to other places, trying to maintain consistency.

The problem with notifications is they can run away. Simply changing some boolean property from true to false can cause a fire-storm of notifications ripping through the data structure in ways no one programmer understands, updating databases, painting windows, zipping files, etc. etc. I often find this is where most clock cycles go.

I think it is simpler and far more efficient to temporarily tolerate inconsistency, and periodically repair it with some kind of sweeping process.

Another way data structures go along with huge inefficiency is if the data is effectively being interpreted by some process to produce some output. This is very common in graphics. If the data changes at a very slow rate, it may make sense to "compile" it rather than "interpret" it. In other words, translate it into a simpler instruction set, or source code which is compiled "on the fly", which can then execute far more quickly to produce the desired output.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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