Re: Do deep inheritance trees degrade efficiency?
Terry Reedy
> 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.
More potential search layers rather than pointer indirection. But I
doubt this is a bottleneck in very many programs. So I would more
concern myself first with quickly writing correct code.
tjr
Chris Rebert
> Would anyone who knows the inner workings volunteer to clarify whether or
> not every additional derivation of a class hierarchy adds an indirection to
> 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. As for method lookup, it
doesn't add an indirection per se, but rather the list of classes to
look thru to find a method gets longer, making base-class method
lookups slower. IIRC, a typical method lookup does something like the
following pseudocode:
for klass in the_object.__mro__:
if method_name in klass.__dict__:
return klass.__dict__[method_name]
raise AttributeError # no such attribute
The __mro__ being the Method Resolution Order, a list containing
the_object's class and that class' superclasses. __dict__ is the
namespace dictionary of an individual class.
However, you shouldn't really worry about the inefficiency of a deep
inheritance tree as Python's dictionary implementation (used for
namespace lookup) is super-optimized, and in any case the inefficiency
ought to be negligible compared to the actual work done in the program
(if it's not, there's something wrong with how the program has been
coded).
[Note: I'm purposefully ignoring the fact that methods and attributes
are in reality looked up in the exact same way for
simplicity/clarity.]
Cheers,
Chris
--
I have a blog:
http://blog.rebertia.com
Christian Heimes
> There's no effect on attribute read-writes as they all take place
> within the single __dict__ of the instance. As for method lookup, it
> doesn't add an indirection per se, but rather the list of classes to
> look thru to find a method gets longer, making base-class method
> lookups slower. IIRC, a typical method lookup does something like the
> following pseudocode:
>
> for klass in the_object.__mro__:
> if method_name in klass.__dict__:
> return klass.__dict__[method_name]
> raise AttributeError # no such attribute
Your assumption is no longer true. Starting with Python 2.6 and 3.0 the
lookup of attributes is cached. You can find detailed information by
searching for VERSION_TAG in the source code.
Christian
Chris Rebert
Very interesting. Now that's a smart optimization; sounds a bit
similar to what V8 does for JavaScript.
Bruno Desthuilliers
> On Wed, Mar 18, 2009 at 6:09 AM, Anthra Norell <anthra...@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).
Anthra Norell
> 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
Terry Reedy
> Anthra Norell 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.
>
> doubt this is a bottleneck in very many programs. So I would more
> concern myself first with quickly writing correct code.
I should add that when object access time matters and the object is
accessed repeatedly, a common solution is to bind it to a local name
*once* and then access it via the local (which is the fastest way
possible for CPython and, I expect, for other implementation). This
works for all slower access methods.
tjr
Mike Howard
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