Speed: bytecode vz C API calls

[Bengt Richter]

On Tue, 9 Dec 2003 23:50:06 -0500, "Francis Avila" <francisgavila at yahoo.com> wrote:

>Stuart Bishop wrote in message ...
>>About the only thing that could be done then is:
>>
>>def memoize(callable):
>>    cache = {}
>>    def proxy(*args, _cache=cache):
>
>Not legal.  *args must always come after default args. There's no way to do
Never say never ;-)
A function has the __get__ method, which is what getattr magic uses to make a bound method.
You can use this put cache in the "self" position of a bound method, like

 >>> def sq(x): return x*x
 ...
 >>> def memoize(func): # callable is a builtin ;-)
 ...     def proxy(cache, *args):
 ...         try: return cache[args]
 ...         except KeyError: return cache.setdefault(args, func(*args))
 ...     return proxy.__get__({}, proxy.__class__)
 ...

 >>> msq = memoize(sq)
 >>> msq
 <bound method function.proxy of {}>
 >>> msq(3)
 9
 >>> msq
 <bound method function.proxy of {(3,): 9}>
 >>> msq(3)
 9
 >>> msq(2)
 4
 >>> msq
 <bound method function.proxy of {(3,): 9, (2,): 4}>

Looking at the code, it might be worth timing, if you have 90%+ cache hits.
I'd be curious to see what you get

 >>> import dis
 >>> dis.dis(msq)
   3           0 SETUP_EXCEPT            12 (to 15)
               3 LOAD_FAST                0 (cache)
               6 LOAD_FAST                1 (args)
               9 BINARY_SUBSCR
              10 RETURN_VALUE
              11 POP_BLOCK
              12 JUMP_FORWARD            41 (to 56)

   4     >>   15 DUP_TOP
              16 LOAD_GLOBAL              2 (KeyError)
              19 COMPARE_OP              10 (exception match)
              22 JUMP_IF_FALSE           29 (to 54)
              25 POP_TOP
              26 POP_TOP
              27 POP_TOP
              28 POP_TOP
              29 LOAD_FAST                0 (cache)
              32 LOAD_ATTR                3 (setdefault)
              35 LOAD_FAST                1 (args)
              38 LOAD_DEREF               0 (func)
              41 LOAD_FAST                1 (args)
              44 CALL_FUNCTION_VAR        0
              47 CALL_FUNCTION            2
              50 RETURN_VALUE
              51 JUMP_FORWARD             2 (to 56)
         >>   54 POP_TOP
              55 END_FINALLY
         >>   56 LOAD_CONST               0 (None)
              59 RETURN_VALUE


>this without changing the calling characteristics of the function, which the
>OP has stated is vital.
Should be ok, but I wonder about non-hashable args. Never expect them?

>
>It is probably possible to custom-build a code object which makes _cache a
>local reference to the outer cache, and play with the bytecode to make the
>LOAD_DEREF into a LOAD_FAST, but it's not worth the effort.  I don't know
>how fast/slow a LOAD_DEREF is compared to a LOAD_FAST, though. In any case,
>it won't help more than a few percent.
The above seems to do it for the cache-hit case ;-)
>
>Jacek, I think this is as fast as pure Python will get you with this
>approach.  If the speed is simply not acceptable, there are some things you
>need to consider, Is this the *real* bottleneck?

Regards,
Bengt Richter