Probably the fastest memoization decorator in the world (Python recipe) by Oren Tirosh

ActiveState Code (http://code.activestate.com/recipes/578231/)

This can made [a lot] more useful by generalizing it to handle functions taking one or more arguments without taking a big performance hit.

I've also made the decorator function's name something clearer as well as less implementation revealing.

def memoize(f):
    """ Memoization decorator for functions taking one or more arguments. """
    class memodict(dict):
        def __init__(self, f):
            self.f = f
        def __call__(self, *args):
            return self[args]
        def __missing__(self, key):
            ret = self[key] = self.f(*key)
            return ret
    return memodict(f)

@memoize
def foo(a, b):
    return a * b

print foo(4, 2)
print foo
print foo('xo', 3)
print foo

Core concept courtesy of the PythonDecoratorLibrary.

The whole point of my recipe is to avoid the overhead of an additional python function call (the __call__ wrapper). Time it. Your version is probably not much faster than the "classic" memo decorator

The trick to writing high performance python code is to do the critical part with no python function calls in the inner loop. They are expensive. This memozation decorator can help optimize such inner loops - a cache hit is as fast as a simple dictionary lookup. If you really need a multiple argument function call it with a tuple.

@Oren Tirosh: Yes, I'm aware there's the extra overhead of a function call, and so would assume that overall it must slower for the special case of single argument functions your can decorator handle. Whether that expensive is acceptable would have to be considered relative to computational cost of calling the function being decorated or not not decorating it all.

I suppose another alternative would be to use your decorator and explicitly pass the function a single tuple of arguments on each invocation -- which is basically all the __call__() method is doing in my version.

Here's a slightly shorter version of a multi-argument function memoizing decorator:

def memoize(f):
    """ Memoization decorator for a function taking one or more arguments. """
    class memodict(dict):
        def __getitem__(self, *key):
            return dict.__getitem__(self, key)

        def __missing__(self, key):
            ret = self[key] = f(*key)
            return ret

    return memodict().__getitem__

It still incurs the overhead of an additional function call and, for a single argument function, is slower than the original recipe. To quantify the cost of this additional overhead I compared applying each decorator to the following highly recursive Fibonacci number function:

def fib(n):
    return n if n < 2 else fib0(n-1) + fib0(n-2)

The results for a very large number of repetitions were that the original decorator made calling the function almost 136,000 times faster verses only 93,000 times faster for my modified version, meaning the latter was about 1.5 times slower. In some other test cases I ran with a smaller number of repetitions, it was about 2.3 times slower.

I couldn't do a comparison for decorating a function with more than one argument because the original decorator doesn't support it. Also, the results for a single-argument function would likely be different had it been done using a test function that was compute-bound rather than function-call bound.

In CPython 2/3, this decorator is approximately 6x faster than the next best implementation (using closures).

In PyPy it's about 3.5x faster.

Nice one. It's worth mentioning this does not work for decorating methods, both zero-arg and one-arg ones.

Very clever. Of course, help() on a memoized function will be useless, as the original function's docstring and signature are lost, but the performance improvement may make it worthwhile in some applications.

These type of micro-optimizations are silly. But since you're making claims ... your decorator does two unnecessary dict lookups on cache misses, costs of which vary by python version..

def memoize(f):
  class memodict(dict):
      __slots__ = ()
      def __missing__(self, key):
          self[key] = ret = f(key)
          return ret
  return memodict().__getitem__

On my machine (MBP, OS X), with the best of 1000 repetitions of 10^4 calls, all cache misses:

                      cPython 2.7  cPython 3.3  PyPy 2.2.1
No-op function        0.147us      0.139us     N.A. 0.003us (pypy optimized out my test function.)    
  no-op decorator     0.297us      0.293us     N.A. 0.003us
  original decorator  0.496us      0.445us     0.457us    
  fixed assign order  0.484us      0.447us     0.370us
  added __slots__     0.484us      0.447us     0.336us

Silly? Fun!

I was mostly concerned about the performance of cache hits, under the assumption that cache miss performance is dominated by the underlying function.

Love it!

Oren/Martin,

Could you guys help me out here..

http://stackoverflow.com/questions/39010366/python-funtools-wrapper-attributeerror-attribute-doc-of-type-objects