473,320 Members | 1,921 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Silly function call lookup stuff?

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.


Sep 27 '05 #1
8 1999
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?

And if the context changes (an import-statement say) reset the
cached 'function-lookups'.
import isn't the only way for the "context" to change. how many
other ways can you think of ?
This way any function would only need to be looked up once.


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

</F>

Sep 27 '05 #2
Lucas Lemmens wrote:
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?
I guess because the function name may be re-bound between loop iterations. Are
there good applications of this? I don't know.
And if the context changes (an import-statement say) reset the
cached 'function-lookups'.
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.

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

L.

Would you apply this optimization to all lookups in outer scopes, or just
callables? Why? ;-)

Michael

Sep 27 '05 #3
On Tue, 27 Sep 2005 22:41:22 +0200, Fredrik Lundh 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?

And if the context changes (an import-statement say) reset the cached
'function-lookups'.
import isn't the only way for the "context" to change. how many other
ways can you think of ?


So myLocalFunc = hisRemoteFunc may break if you're not carefull you mean.
If not then there's room for improvement.
This way any function would only need to be looked up once.


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

</F>


You haven't really answered my questions have you?
L.
Sep 27 '05 #4
On Tue, 27 Sep 2005 13:56:53 -0700, Michael Spencer wrote:
Lucas Lemmens wrote:
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?
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.

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.
And if the context changes (an import-statement say) reset the cached
'function-lookups'.
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.


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

So optimizing for not having them ...
This way any function would only need to be looked up once.

L.
Would you apply this optimization to all lookups in outer scopes, or just
callables? Why? ;-)


Hmmm callables have probably the highest chance of being recalled.

Michael


Sep 27 '05 #5
On Wed, 28 Sep 2005 00:38:23 +0200,
Lucas Lemmens <ll******@gmx.net> 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_process( 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.
Would the myLocalFunc = hisRemoteFunc optimization break in such a
case?
Trying to cache x.process in the above loop would be nothing short of a
complete disaster.
Would you apply this optimization to all lookups in outer scopes, or
just callables? Why? ;-)

Hmmm callables have probably the highest chance of being recalled.


def print_the_results( list_of_things_with_results ):
for x in list_of_things_with_results:
print x.results

Regards,
Dan

--
Dan Sommers
<http://www.tombstonezero.net/dan/>
Sep 28 '05 #6
Lucas Lemmens wrote:
This way any function would only need to be looked up once.


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


You haven't really answered my questions have you?


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>

Sep 28 '05 #7
> > I guess because the function name may be re-bound between loop iterations.
Are there good applications of this? I don't know.

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.

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


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

Sw.

Sep 28 '05 #8
On Tue, 27 Sep 2005, Dan Sommers wrote:
On Wed, 28 Sep 2005 00:38:23 +0200,
Lucas Lemmens <ll******@gmx.net> 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_process( 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
Sep 28 '05 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

34
by: Jacek Generowicz | last post by:
I have a program in which I make very good use of a memoizer: def memoize(callable): cache = {} def proxy(*args): try: return cache except KeyError: return cache.setdefault(args,...
11
by: John Collyer | last post by:
Hi, In assembly language you can use a lookup table to call functions. 1. Lookup function address in table 2. Call the function Like: CALL FUNCTION
3
by: Steven T. Hatton | last post by:
I stumbled upon this blog while googling for something. I have to say, I really don't understand what Lippman is trying to tell me here. I included the first paragraph for context, but the second...
8
by: Falc2199 | last post by:
Hi, Does anyone know how to make this work? var sectionId = 5; repeat_section_sectionId(); function repeat_section_5(){ alert("firing"); }
15
by: Eirik | last post by:
This is a little function I wrote, inspired by the thread "Urgent HELP! required for Caesar Cipher PLEASE" $ cat /home/keisar/bin/c/ymse/rot13.h char rot13(char character) { int changed;...
1
by: slugster | last post by:
Hi, i originally posted this via another portal, but after giving it time to propagate it still hasn't shown up. My apologies for the multiposting. This might be a very simple question, but i...
19
by: Riko Wichmann | last post by:
hi everyone, I'm googeling since some time, but can't find an answer - maybe because the answer is 'No!'. Can I call a function in python inline, so that the python byte compiler does...
17
by: Kevin Blount | last post by:
I have a system that I want to try, which requires me, from an aspx page, to call a generic function to work perform one task, then i want to call another function with the results of that task. ...
15
by: asm23 | last post by:
Hi, everyone, I'm studying the <<Thinking in C++>volume Two. In Chapter One, the example code : Auto_ptr.cpp //------------------------------------------------------- #include <memory> #include...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.