Welcome, guest | Sign In | My Account | Store | Cart

With apologies to a certain European brand of beer, this is probably the fastest memoization decorator in the world. Implemented using the __missing__ method in a dict subclass.

Python, 7 lines
1
2
3
4
5
6
7
def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret 
    return memodict().__getitem__

Memoization is the canonical example for Python decorators. For a single argument function this is probably the fastest possible implementation - a cache hit case does not introduce any extra python function call overhead on top of the dictionary lookup.

If you need access to the underlying dictionary for any reason use f.__self__

11 comments

Martin Miller 9 years, 5 months ago  # | flag

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.

Oren Tirosh (author) 9 years, 5 months ago  # | flag

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.

Martin Miller 9 years, 5 months ago  # | flag

@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.

Martin Miller 9 years, 5 months ago  # | flag

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.

Oren Tirosh (author) 9 years, 5 months ago  # | flag

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.

George Sakkis 8 years, 6 months ago  # | flag

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

Jerry Kindall 8 years, 3 months ago  # | flag

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.

Isaac Levy 8 years ago  # | flag

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
Oren Tirosh (author) 8 years ago  # | flag

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.

kurt rose 7 years, 1 month ago  # | flag

Love it!

Created by Oren Tirosh on Thu, 2 Aug 2012 (MIT)
Python recipes (4591)
Oren Tirosh's recipes (16)

Required Modules

  • (none specified)

Other Information and Tasks