Silly function call lookup stuff?

Discussion in 'Python' started by Lucas Lemmens, Sep 27, 2005.

  1. 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.
    Lucas Lemmens, Sep 27, 2005
    #1
    1. Advertising

  2. 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>
    Fredrik Lundh, Sep 27, 2005
    #2
    1. Advertising

  3. 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
    Michael Spencer, Sep 27, 2005
    #3
  4. 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.
    Lucas Lemmens, Sep 27, 2005
    #4
  5. 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
    Lucas Lemmens, Sep 27, 2005
    #5
  6. Lucas Lemmens

    Dan Sommers Guest

    On Wed, 28 Sep 2005 00:38:23 +0200,
    Lucas Lemmens <> 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/>
    Dan Sommers, Sep 28, 2005
    #6
  7. 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>
    Fredrik Lundh, Sep 28, 2005
    #7
  8. Lucas Lemmens

    Guest

    > > 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, 2005
    #8
  9. Lucas Lemmens

    Tom Anderson Guest

    On Tue, 27 Sep 2005, Dan Sommers wrote:

    > On Wed, 28 Sep 2005 00:38:23 +0200,
    > Lucas Lemmens <> 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
    Tom Anderson, Sep 28, 2005
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. grbgooglefan
    Replies:
    2
    Views:
    402
    Pascal Bourguignon
    Jan 30, 2008
  2. grbgooglefan
    Replies:
    4
    Views:
    425
    Kenny McCormack
    Jan 30, 2008
  3. grbgooglefan
    Replies:
    0
    Views:
    374
    grbgooglefan
    Jan 30, 2008
  4. Alok
    Replies:
    3
    Views:
    233
  5. THAKUR PRASHANT SINGH

    Class Function call vs Normal Function call

    THAKUR PRASHANT SINGH, Feb 26, 2010, in forum: Ruby
    Replies:
    7
    Views:
    164
    THAKUR PRASHANT SINGH
    Feb 27, 2010
Loading...

Share This Page