Silly function call lookup stuff?

[Lucas Lemmens]

Dear pythonians,

I've been reading/thinking about the famous function call speedup
trick where you use a function in the local context to represent
a "remoter" function to speed up the 'function lookup'.

"This is especially usefull in a loop where you call the function a
zillion time" they say.

I think this is very odd behavior.

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?

And if the context changes (an import-statement say) reset the
cached 'function-lookups'.

This way any function would only need to be looked up once.

L.

[Fredrik Lundh]

Re: Silly function call lookup stuff?

Lucas Lemmens wrote:
[color=blue]
> 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?
>
> And if the context changes (an import-statement say) reset the
> cached 'function-lookups'.[/color]

import isn't the only way for the "context" to change. how many
other ways can you think of ?
[color=blue]
> This way any function would only need to be looked up once.[/color]

you haven't really thought this over, have you?

</F>

[Michael Spencer]

Re: Silly function call lookup stuff?

Lucas Lemmens wrote:[color=blue]
> Dear pythonians,
>
> I've been reading/thinking about the famous function call speedup
> trick where you use a function in the local context to represent
> a "remoter" function to speed up the 'function lookup'.
>
> "This is especially usefull in a loop where you call the function a
> zillion time" they say.
>
> I think this is very odd behavior.
>
> 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?
>[/color]
I guess because the function name may be re-bound between loop iterations. Are
there good applications of this? I don't know.
[color=blue]
> And if the context changes (an import-statement say) reset the
> cached 'function-lookups'.[/color]

In general an object doesn't know what names are bound to it and there are many
ways besides an import statement of binding/re-binding, so "if the context
changes" is easier said than done.
[color=blue]
>
> This way any function would only need to be looked up once.
>
> L.
>[/color]
Would you apply this optimization to all lookups in outer scopes, or just
callables? Why? ;-)

Michael

[Lucas Lemmens]

Re: Silly function call lookup stuff?

On Tue, 27 Sep 2005 22:41:22 +0200, Fredrik Lundh wrote:
[color=blue]
> Lucas Lemmens wrote:
>[color=green]
>> 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?
>>
>> And if the context changes (an import-statement say) reset the cached
>> 'function-lookups'.[/color]
>
> import isn't the only way for the "context" to change. how many other
> ways can you think of ?[/color]

So myLocalFunc = hisRemoteFunc may break if you're not carefull you mean.
If not then there's room for improvement.
[color=blue]
>[color=green]
>> This way any function would only need to be looked up once.[/color]
>
> you haven't really thought this over, have you?
>
> </F>[/color]

You haven't really answered my questions have you?
L.

[Lucas Lemmens]

Re: Silly function call lookup stuff?

On Tue, 27 Sep 2005 13:56:53 -0700, Michael Spencer wrote:
[color=blue]
> Lucas Lemmens wrote:[color=green]
>> Dear pythonians,
>>
>> I've been reading/thinking about the famous function call speedup trick
>> where you use a function in the local context to represent a "remoter"
>> function to speed up the 'function lookup'.
>>
>> "This is especially usefull in a loop where you call the function a
>> zillion time" they say.
>>
>> I think this is very odd behavior.
>>
>> 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?
>>[/color]
> I guess because the function name may be re-bound between loop iterations.
> Are there good applications of this? I don't know.[/color]

Yuk I'd hate that. I think it would be extremely rare.

Would the myLocalFunc = hisRemoteFunc optimization break in such a case?

If not then why not auto-add a local hisRemoteFunc that points to the
remote hisRemoteFunc to the local context when hisRemoteFunc
is executed for the first time.
[color=blue]
>[color=green]
>> And if the context changes (an import-statement say) reset the cached
>> 'function-lookups'.[/color]
>
> In general an object doesn't know what names are bound to it and there are
> many ways besides an import statement of binding/re-binding, so "if the
> context changes" is easier said than done.
>[/color]

My guess (but I'm not a python programmer) is that context changes would
be the odd case.

So optimizing for not having them ...
[color=blue]
>[color=green]
>> This way any function would only need to be looked up once.
>>
>> L.
>>[/color]
> Would you apply this optimization to all lookups in outer scopes, or just
> callables? Why? ;-)[/color]

Hmmm callables have probably the highest chance of being recalled.
[color=blue]
>
> Michael[/color]

[Dan Sommers]

Re: Silly function call lookup stuff?

On Wed, 28 Sep 2005 00:38:23 +0200,
Lucas Lemmens <llemmens@gmx.n et> wrote:
[color=blue]
> On Tue, 27 Sep 2005 13:56:53 -0700, Michael Spencer wrote:[/color]
[color=blue][color=green]
>> Lucas Lemmens wrote:[/color][/color]
[color=blue][color=green][color=darkred]
>>> 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?[/color][/color][/color]
[color=blue][color=green]
>> I guess because the function name may be re-bound between loop
>> iterations. Are there good applications of this? I don't know.[/color][/color]
[color=blue]
> Yuk I'd hate that. I think it would be extremely rare.[/color]

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( )

As long as list_of_things_ to_process is sufficiently list-like, this
function has no way of knowing what's in it, or what any particular
x.process function might do.

Think of the possibilities if the list is really the output of some
generator with a feedback mechanism that can add new elements to the end
of the list before the list is exhausted. Yes, this case is a stretch;
no, I can't say that I'll never implement anything like it, or that I
wouldn't marvel at the elegance of such an implementation.
[color=blue]
> Would the myLocalFunc = hisRemoteFunc optimization break in such a
> case?[/color]

Trying to cache x.process in the above loop would be nothing short of a
complete disaster.
[color=blue][color=green]
>> Would you apply this optimization to all lookups in outer scopes, or
>> just callables? Why? ;-)[/color][/color]
[color=blue]
> Hmmm callables have probably the highest chance of being recalled.[/color]

def print_the_resul ts( list_of_things_ with_results ):
for x in list_of_things_ with_results:
print x.results

Regards,
Dan

--
Dan Sommers
<http://www.tombstoneze ro.net/dan/>

[Fredrik Lundh]

Re: Silly function call lookup stuff?

Lucas Lemmens wrote:
[color=blue][color=green][color=darkred]
>>> This way any function would only need to be looked up once.[/color]
>>
>> you haven't really thought this over, have you?[/color]
>
> You haven't really answered my questions have you?[/color]

no, because you proposed a major change to the Python semantics,
without spending any effort whatsoever researching how things work,
thinking about the consequences, or studying existing code to see how
it would be affected. next time, you can at least do a little homework
before suggesting that a dynamically typed language should no longer
be dynamic.

</F>

[simonwittber@gmail.com]

Re: Silly function call lookup stuff?

> > I guess because the function name may be re-bound between loop iterations.[color=blue][color=green]
> > Are there good applications of this? I don't know.[/color][/color]

I have iterator like objects which dynamically rebind the .next method
in order to different things. When I want a potentially infinite
iterator to stop, I rebind its .next method to another method which
raises StopIteration. This saves lots of messy if/elif state checking
in the .next method, which I _need_ to be very fast.
[color=blue]
>
> Yuk I'd hate that. I think it would be extremely rare.
>[/color]

I use it all the time. Dynamically rebinding methods is a nice way to
change and maintain state between calls.

Sw.

[Tom Anderson]

Re: Silly function call lookup stuff?

On Tue, 27 Sep 2005, Dan Sommers wrote:
[color=blue]
> On Wed, 28 Sep 2005 00:38:23 +0200,
> Lucas Lemmens <llemmens@gmx.n et> wrote:
>[color=green]
>> On Tue, 27 Sep 2005 13:56:53 -0700, Michael Spencer wrote:[/color]
>[color=green][color=darkred]
>>> Lucas Lemmens wrote:[/color][/color]
>[color=green][color=darkred]
>>>> 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.[/color]
>>
>> Yuk I'd hate that. I think it would be extremely rare.[/color]
>
> 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( )[/color]

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