Function unrolling (was Re: Speed: bytecode vz C API calls)

[Jacek Generowicz]

aahz at pythoncraft.com (Aahz) writes:

> In article <tyfd6ayylhy.fsf at pcepsft001.cern.ch>,
> Jacek Generowicz  <jacek.generowicz at cern.ch> wrote:
> >aahz at pythoncraft.com (Aahz) writes:
> >>
> >> I think you're going to need to write a solution that doesn't call
> >> functions (function unrolling, so to speak).  Instead of returning a
> >> memoizer function, just use a dict of dicts.
     ^^^^^^^^

(Maybe this is where we are misunderstanding eachother. On first
reading, I thought that "memoizer" was just a typo. I don't return a
memoizer function, I return a memoized function.)

> >Sounds interesting. But how do I get the dictionary to use the
> >function which it is memoizing, to calculate values which haven't been
> >cached yet?
> 
> Same way you decide which function to call currently.

The way I decide which function to call currently is to type its name
directly into the source at the call site. Deciding which function to
call is not the problem: calling any function at all, once I've
reduced myself to having _just_ a dictionary, is the problem.

Maybe I didn't make the use of "memoize" clear enough.

You use it thus:

  def foo():
      ...

  foo = memoize(foo)

And from now on foo is a lot faster than it was before[*].

> Essentially, you do something like this:
> 
> def foo():
>     pass
> 
> def bar():
>     pass
> 
> lookup = {
>     'foo': {'func': foo, 'cache': {}},
>     'bar': {'func': bar, 'cache': {}},
>     }
> 
> for operation,args in WorkQueue:
>     curr = lookup[operation]
>     try:
>         return curr['cache'][args]
>     except KeyError:
>         return curr['cache'].setdefault(args, curr['func'](*args))

Nononononooooo ! :-)

In any given loop, I know _which_ function I want to call, so the
dictionary of dictionaries is pointless. Let's recap the original
memoizer:

  def memoize(callable):
      cache = {}
      def proxy(*args):
          try: return cache[args]
          except KeyError: return cache.setdefault(args, callable(*args))
      return proxy

I thought that you were suggesting to replace "proxy" with just the
dictionary "cache", in order to save the function call overhead, as
proxy is (almost) just a wrapper around the dictionary lookup. That's
great, but what do I do in the (very rare) cases where I'm presented
with an argument/key I haven't seen yet? Somehow, I need to recognize
that the key is not present, call the original function, and add the
key-value pair to the cache. I can't see how to do that without
re-introducing the function call. I could to it by inlining the try
block, but then I wouldn't be able to use the memoized function inside
map ... and turning a map into a for-loop would lose me more than I'd
gained.



[*] With a whole bunch of exceptions which are beside the point here.