On Tue, 27 Sep 2005, Dan Sommers wrote:
On Wed, 28 Sep 2005 00:38:23 +0200,
Lucas Lemmens <ll******@gmx.n et> wrote:
On Tue, 27 Sep 2005 13:56:53 -0700, Michael Spencer wrote:
Lucas Lemmens wrote: Why isn't the result of the first function-lookup cached so that
following function calls don't need to do the function-lookup at all?
I guess because the function name may be re-bound between loop
iterations. Are there good applications of this? I don't know.
Yuk I'd hate that. I think it would be extremely rare.
With duck typing, I think it would be fairly common:
def process_list_of _things_to_proc ess( list_of_things_ to_process ):
for x in list_of_things_ to_process:
x.process( )
That's not what's being talked about here. In this code, x.process would
be a different method each time through, and wouldn't be cached (this
isn't C++, you know!).
We're talking about this case:
class Foo:
def process(self):
return "foo's version of process"
def bar(foo):
foo.process = lambda: "bar's version of process"
x = Foo()
print x.process()
bar(x)
print x.process()
Naive local method cacheing would get this wrong. Worldly-wise method
cacheing that would get this right would be a nightmare to implement.
A better bet might be to speed up method lookup. I should say that i know
bugger all about how python's method lookup is implemented now, but i
believe that it's basically a dict lookup in a per-object feature
dictionary (ie self.__dict__). It might be possible to instead use a sort
of vtable, with a translucent layer of indirection wrapped round it to
allow for python's dynamism.
Okay, thinking out loud follows. The following is pseudocode showing how
the interpreter is implemented; any resemblance to an actual programming
language, living or dead, is purely coincidental.
The current implementation looks something like this:
def classmembers(cl ):
<returns an iterator over the members of a class>
def new(cl):
"Make a new instance of a class cl. An object is a pair (cl,
members), where cl is its class and members is a dict of its members."
members = {}
for name, member in classmembers(cl ):
members[name] = member
obj = (cl, members)
return obj
def lookup(obj, name):
members = obj[1]
member = members[name]
return member
def bind(obj, name, member):
members = obj[1]
members[name] = member
Since the members dict is mutable, there's nothing that can be cached
here. This is what i'd suggest ...
type mtuple:
<a mutable tuple - fixed length, but mutable; basically a C array>
def new(cl):
index = {}
members = [cl, index]
for name, member in classmembers(cl ):
index[name] = len(members)
members.append( member)
obj = (cl, index, mtuple(members) )
return obj
# the index dict is *never* modified by any code anywhere
def lookup(obj, name):
index = obj[1]
offset = index[name]
value = obj[offset]
return value
def bind(obj, name, value):
index = obj[1]
offset = index[name]
obj[offset] = value
So far, this wouldn't be any faster; in fact, it would be slightly slower,
due to the extra layer of indirection.
However, now we can expose a little of the lookup mechanism to the
execution machinery:
def offset(obj, name):
index = obj[1]
offset = index[name]
return offset
def load(obj, offset):
value = obj[offset]
return value
And refactor:
def lookup(obj, name):
offset = offset(obj, name)
value = load(obj, offset)
return value
We now have something cachable. Given code like:
while (foo()):
x.bar()
The compiler can produce code like:
_bar = offset(x, "bar")
while (foo()):
load(x, _bar)()
It has to do the lookup in the dict once, and after that, just has to do a
simple load. The crucial thing is, if the method gets rebound, it'll be
rebound into exactly the same slot, and everything keeps working fine.
Note that the code above doesn't handle binding of members to names that
weren't defined in the class; it thus doesn't support dynamic extension of
an object's interface, or, er, member variables. However, these are fairly
simple to add, via an extra members dict (which i create lazily):
def new(cl):
index = {}
extras = None
members = [cl, index, extras]
for name, member in classmembers(cl ):
index[name] = len(members)
members.append( member)
obj = (cl, index, mtuple(members) )
return obj
def lookup(obj, name):
index = obj[1]
try:
offset = index[name]
value = obj[offset]
except KeyError:
extras = obj[2]
if (extras == None): raise KeyError, name
value = extras[name]
return value
def bind(obj, name, value):
index = obj[1]
try:
offset = index[name]
obj[offset] = value
except KeyError:
extras = obj[2]
if (extras == None):
extras = {}
obj[2] = extras
extras[name] = value
It also doesn't call __init__ on new objects, or do metaclasses properly,
or support __slots__, or any of that jazz, but that would all be fairly
easy to add. __slots__ would be a big performance win here.
It would be really nice if the object could somehow be put together after
__init__ has run; that way, the member variables set there could be
included in the members which are stored in the mtuple and indexed, which
is a big performance and compactness win over having them as extras. This
is probably possible, using objects which can invisibly change their
implementation, but i'm not going to think about it now!
Also, as a memory optimisation, you'd want to arrange for all instances of
a class to share the same index dictionary instance. That would be pretty
trivial. You could also split the members which are likely to be constant
across all instances - the class reference, index, and the methods, but
not the extras - into a separate table, and share that too; you would have
to handle rebinding of members on individual objects with a copy-on-write
policy applied to this table. This is fairly straightforward to do, but
i'm not going to do it here; the result would be something very close to
C++-style vtables, but supporting python's object model.
Did that make any sense?
Speaking of __slots__, can you use slots for methods? Does it speed up
lookup at all?
tom
--
Children are born true scientists. -- R. Buckminster Fuller
