Do deep inheritance trees degrade efficiency?

[Mike Howard]

On Mar 19, 7:24 am, Anthra Norell <anthra.nor... at bluewin.ch> wrote:
> Bruno Desthuilliers wrote:
> > Chris Rebert a écrit :
> >> On Wed, Mar 18, 2009 at 6:09 AM, Anthra Norell
> >> <anthra.nor... at bluewin.ch> wrote:
> >>> Would anyone who knows the inner workings volunteer to clarify
> >>> whether or
> >>> not every additional derivation of a class hierarchy adds an
> >>> indirection to
> >>> the base class's method calls and attribute read-writes. In C++, I
> >>> suppose,
> >>> a three-level inheritance would resolve into something like
> >>> *(*(*(*(base_class_method ())))).
>
> >> There's no effect on attribute read-writes as they all take place
> >> within the single __dict__ of the instance.
>
> > Except when:
> > - the attribute is a computed one (property or other descriptor)
> > - (for read access) the attribute is not set in the instance's dict.
>
> >> As for method lookup, it
> >> doesn't
>
> > make much difference - the very same lookup rules apply, and it's the
> > descriptor protocol (as implemented by the 'function' type) that takes
> > care of returning a method object (mostly a partial application of the
> > function to the instance or class) when appropriate.
>
> > (snip)
>
> >> However, you shouldn't really worry about the inefficiency of a deep
> >> inheritance tree as Python
>
> > is probably not the right tool for the job if one have such efficiency
> > concerns.
>
> > (snip)
>
> >> [Note: I'm purposefully ignoring the fact that methods and attributes
> >> are in reality looked up in the exact same way for
> >> simplicity/clarity.]
>
> > Ah, ok - then please don't take the above remarks as a personal
> > offense !-)
>
> > (still posting this since it might be of interest to the OP or someone
> > else).
> > --
> >http://mail.python.org/mailman/listinfo/python-list
>
> The OP (that's me) thankfully acknowledges all contributions. The upshot
> of it all seems to be that there are countless ways for a compiler or
> interpreter to handle access through class hierarchies. I did a very
> crude test myself, like this:
>
>  >>> class A:
>          def do (self): pass
>  >>> class B (A): pass
>  >>> class C (B): pass
>  >>> class D (C): pass
>  >>> class E (D): pass   # Got to stop somewhere
>
>  >>> a = A ()
>  >>> for i in xrange (1000000):
>             a.do ()
> 11 seconds
>
>  >>> e = E ()
>  >>> for i in xrange (1000000):
>              e.do ()
> 14 seconds
>
> No significant difference indeed !
>
> Frederic

I rewrote your example using timeit and ran under 2.5.4, 2.6.1 and
3.0.1.
The runs under 2.5.4 track your results, but 2.6.1 and 3.0.1 both show
no degradation with inheritance depth. Inheritance depth has become
negligible
w.r.t. method calls. I expect, but haven't confirmed, attribute access
as well.
<a href="http://www.clove.com/downloads/inheritance_test.py">[code is
here]</a>

The output is the timeit result for 10 repetitions of 1,000,000
executions of
<instance>.do() divided by the base * 100 - to get a rough percentage
increase.

This tracks your result except that there is quite a bit of variation
between
runs. [This is on a MacBook running Mac OS 10.5.x]

here are the results for 2.5.4:

Python: 2.5.4 - pass 0
('average of 10 repetitions of a.do() 1M times:', 0.28618097305297852)
('c/a: ', 114.78015753690045)
('e/a: ', 132.05789049508232)
('g/a: ', 149.00435700713106)
('i/a: ', 158.03297538214326)
Python: 2.5.4 - pass 1
('average of 10 repetitions of a.do() 1M times:', 0.28112134933471677)
('c/a: ', 113.20292730186013)
('e/a: ', 128.56302159497105)
('g/a: ', 141.51935315931576)
('i/a: ', 157.80126593427318)
Python: 2.5.4 - pass 2
('average of 10 repetitions of a.do() 1M times:', 0.28900878429412841)
('c/a: ', 114.52610798504281)
('e/a: ', 126.51857991809983)
('g/a: ', 140.42839384656821)
('i/a: ', 163.86294715533046)
Python: 2.5.4 - pass 3
('average of 10 repetitions of a.do() 1M times:', 0.30324285030364989)
('c/a: ', 114.82044166297946)
('e/a: ', 126.28557829362819)
('g/a: ', 147.32277854431973)
('i/a: ', 160.36867136570748)

Result for 2.6.1

Python: 2.6.1 - pass 0
foo.py:28: DeprecationWarning: reduce() not supported in 3.x; use
functools.reduce()
  f = lambda l: reduce(lambda x,y:x+y, l, 0) / len(l)
('average of 10 repetitions of a.do() 1M times:', 0.27728290557861329)
('c/a: ', 100.37490148910786)
('e/a: ', 102.16833651811277)
('g/a: ', 101.04577539537046)
('i/a: ', 94.932756427197361)
Python: 2.6.1 - pass 1
('average of 10 repetitions of a.do() 1M times:', 0.28833901882171631)
('c/a: ', 101.00927061660381)
('e/a: ', 100.60117582151531)
('g/a: ', 101.21841767147875)
('i/a: ', 99.756374270826313)
Python: 2.6.1 - pass 2
('average of 10 repetitions of a.do() 1M times:', 0.27523901462554934)
('c/a: ', 101.39272522343434)
('e/a: ', 101.13560136859272)
('g/a: ', 101.7675204062686)
('i/a: ', 99.196638894243506)


Result for 3.0.1

Python: 3.0.1 - pass 0
average of 10 repetitions of a.do() 1M times: 0.258784985542
c/a:  97.0095581514
e/a:  99.436644712
g/a:  99.7741309446
i/a:  98.7775609432
Python: 3.0.1 - pass 1
average of 10 repetitions of a.do() 1M times: 0.25830578804
c/a:  99.7809586174
e/a:  102.091022482
g/a:  99.9929745087
i/a:  98.4210309889