I presume that you know what the memoization is. And if not then you can read about it on wikipedia. I’d like to write about problems that I ran into while implementing memoization in Python.

I will not explain how I implemented the cache subsystem because it is a separete problem. Lets say that the cache is a simple unlimited dictionary with key:value pairs where the key is a calculated fingerprint based on a function and its parameters and the value is a return value of that function.

Trivial implementation with decorator

g_cache = {}

def memoize(func):
    def cached_substitute(*args, **kwargs):
        global g_cache

        fingerprint = hex(id(func)) + repr((args, kwargs))

        try:
            value = g_cache[fingerprint]
        except KeyError:
            value = func(*args, **kwargs)
            g_cache[fingerprint] = value

        return value

    return cached_substitute

usage example:

@memoize
def expensive_computation(x, y):
    print "computing"
    return x + y

print expensive_computation(2, 4)
print expensive_computation(2, 4)
# output:
# computing
# 6
# 6

Without @memoize there will be the message “computing” twice in the output. But the second call didn’t invoke execution of the expensive_computation because the function was already called with the same parameters.

Troubles

So far so good. But as usual almost nothing in the real world is as easy as it looks. I found a few problems which must be taken care of and others which are a matter of choice.

Function identification

I you want to have a generic memoization decorator then you have to distinguish nonidentical functions. I choose the simplest way and that is a function id(…) which returns the function’s address. Possible decorated functions are:

1. function on a module level (global scope)
2. function in a function
3. class method

There is no problem with the first one. The second scenario (FiF) is not solvable in a generic way. It is necessary to use some custom fingerprint generator (see below). Finally class methods have their implementing functions that you must refer to. Simple implementation:

def callable_id(callable):
    if isinstance(callable, types.FunctionType):
        return hex(id(callable))
    elif isinstance(callable, MethodType):
        return hex(id(callable.im_func))
    raise TypeError("%s is not supported callable" % repr(callable))

Parameters fingerprint

How to distinguish whether the function expensive_computation was called with parameters (2, 4) or (10, 20)? You have two basic (and generic) choices:

• repr((args, kwargs))
• pickle.dumps((args, kwargs)

The first one is a bit faster but it has troubles with objects – it doesn’t see “into” the object. It depends how those objects have implemented their __repr__ method. Pickle is more generic but it can be slow and sometimes can fail with “unpickleable” objects.

Parameters significance

Other problem is that sometimes it is not important to represent a determinant from all of the function’s parameters. One example is a class method. Every method has a mandatory parameter self. Imagine a method that you would like to memoize but its result is not influenced by the instance data. Then you would like to “combine” cached results from multiple instances thus you would like to exclude the self from the parameters fingerprint. So you can implement the parameters fingerprint like repr((args[1:], kwargs)) but then you will loose the genericity.

Different example is that you would like to include some environmental data to those function’s parameters like repr((args, kwargs, environment)). Solution is a custom fingerprint generator.

Custom fingerprint generators

This should be the best medicine for the most problems around memoization. You can create your own fingerprint generator for functions and even parameters. Check out following code:

import types
import pickle

g_cache = {}

def callable_id(callable):
    if isinstance(callable, types.FunctionType):
        return hex(id(callable))
    elif isinstance(callable, MethodType):
        return hex(id(callable.im_func))
    raise TypeError("%s is not supported callable" % repr(callable))

def basic_fingerprint_generator(callable, args, kwargs):
    return callable_id(callable) + repr((args, kwargs))    

def pickle_fingerprint_generator(callable, args, kwargs):
    return callable_id(callable) + pickle.dumps((args, kwargs))    

def memoize(fingerprint_generator=basic_fingerprint_generator):
    def memoize_decorator(func):
        def cached_substitute(*args, **kwargs):
            global g_cache

            fingerprint = fingerprint_generator(func, args, kwargs)

            try:
                value = g_cache[fingerprint]
            except KeyError:
                value = func(*args, **kwargs)
                g_cache[fingerprint] = value

            return value

        return cached_substitute

    return memoize_decorator

There you can see that the memoize() function has one more nested function. Now the memoize() is not the decorator itself but it returns a “custom” generator. So the usage is different. Instead of

@memoize
def expensive_computation(x, y):
    pass

we will use

@memoize()
def expensive_computation(x, y):
    pass

# or e.g.

@memoize(pickle_fingerprint_generator)
def expensive_computation(x, y):
    pass

That’s all folks!