Comparing Inheritance-as-Delegation to traditional Inheritance in terms of Runtime Performance


Randy Smith

smithr AT cs DOT wisc DOT edu
30 September 2004


Introduction

Recently, the PL reading group at UW-Madison read the paper "Automated Delegation is a Viable Alternative to Multiple Inheritance in Class Based Languages" by Viega, Tutt, and Behrends. ( ftp link)

As a group, we came to the following conclusions:
1. (PRO) delegation provides the ability to change the delegated object at runtime.
2. (PRO) decouples multiple subclassing from multiple subtyping.
3. (CON) delegation will be slower than inheritance, potentially too slow to be practical.

I walked away from discussion curious about how much slower delegation actually is. So, I wrote up some code to compare inheritance-as-delegation running times with traditional inheritance running times.

The end result:  "it depends".  For average everyday use, the results in the table below indicate that delegation has acceptable performance (and in some cases performance is better than inheritance, although the assumptions might not be especially realistic).  I've got the test results along with my test methodology below.  Disclaimer:  This started out as a quick test just to see some concrete numbers and grew a bit.  My methodology might be all screwed up, but I think it gives a general idea of the performance differences.

Methodology

(for inheritance)

My test methodology for doing this with inheritance was as follows:
  1. Define a base class containing a single private variable with public get/set methods.
  2. Create Inheritance hierarchies of various heights, from 2 to 13 (not including base). Each subclass defined get/set methods that simply called the get/set methods of the parent.
  3. For most of the tests, the get/set methods were declared virtual (for test 7 they were not).
  4. Create an instance of the class at the bottom of the of the hierarchy (the {great}+-grandchild of the base), and repeatedly called the get/set methods in a loop.

(for containment)

The test methodology for containment is similar:
  1. Define a "base" class containing a single private variable with public get/set methods.
  2. Successively define wrapper classes to wrap the base class. Each wrapper class contains get/set methods that call the get/set methods of the contained class.
  3. As with the inheritance test, I instantiated an object of the "most enclosing" class and repeatedly called the get/set methods in a loop.

Experiments

With this setup, I ran multiple tests:
  1. Testing containment running times with statically allocated objects of various hierarchy sizes (e.g., D12 d12obj).
  2. Repeating the test with -O2 gcc optimization on.
  3. Testing containment running times with dynamically allocated objects (e.g., D12 *d12obj).
  4. Repeating the test with -O2 gcc optimization.
  5. Testing inheritance running times of various hierarchy sizes.
  6. Repeating the test with -O2 gcc optimization.
  7. Repeating test 6 with "virtual" keyword removed.
  8. Repeat inheritance tests, insert "virtual", and call functions in base object rather than immediate parent.
The columns in the table below show the results of the running times of each of the tests above. Each entry is the average of 3 runs. "DX" refers to the Delegation test of "width" X+1 and corresponds to columns 1-4. "IX" refers to the Inheritance test of "height" X+1 and corresponds to columns 5-8. All tests were performed on one of the 3.0GHZ machines in the department that was otherwise idle. The main loop executing get/set was executed 10 Billion times.




 1 2 3 4
Type Static/NoOpt Static/O2 Dynamic/NoOpt Dynamic/O2
D2 2.646 0.169 3.525 0.169
D3 3.533 0.168 3.641 0.169
D8 7.932 0.169 12.297 0.171
D13 12.321 0.170 16.837 0.169











5 6 7 8

Inher/NoOpt inher/O2 inher/O2/novirt inher/NoOpt/jump to Base
I2 2.815 1.258 0.054 0.881
I3 3.701 1.286 0.051 0.883
I8 8.137 1.598 0.053 0.883
I13 12.554 1.399 0.052 0.883


Legend

NoOpt==no compiler optimization
O2== g++ -O2 optimization used.
static==static object creation
dynamic==dynamic object creation (e.g., through new)
All running times computed in seconds.


Notes and Conclusions

notes:
  1. Without optimization, static delegation (column 1) performs equivalently to inheritance (col. 5).
  2. Dynamic delegation (column 3), provides increased run-time flexibility at a slight cost to overhead.
  3. Using -O2 optimization,  col. 2 and col. 4 perform similarly, and both are much better than inheritance.
  4. Eliminating "virtual" qualifiers to base functions results in much improved performance, although this is a bit odd, since I'm not actually overriding anything.
  5. Calling base functions directly (col 8) saves a lot of time.  Can probably interpolate to estimate running times for function calls to objects that are part way up the hierarchy.
  6. Virtual functions create a fair amount of overhead, even if I'm not overriding the virt functions.

Assumptions:
  1. I'm using simple get/set functions that do nothing fancy. Most real apps that use big inheritance trees, it seems, will have methods that call functions part-way up the inheritance hierarchy.
  2. I'm mostly modelling worst case scenarios.  It would be interesting sometime to try to accurate model average case situations.
Conclusions:
  1. In terms of *performance only*, Delegation does not seem to impose an unacceptably high performance overhead.
  2. Under optimized conditions and given my assumptions, optimized inheritance performed best by a factor of ~3.

You may download the code.
Comments welcome. Please direct to smithr AT cs DOT wisc DOT edu.