Memoization in Groovy with a Decorator

February 27, 2008

Memoization is a well known optimization technique to avoid repeated calculations. With dynamic programming languages like Groovy it is possible to extend the behaviour of an already exisiting class at runtime.

In Groovy this is accomplished with the Meta Object Protocoll and its ExpandoMetaClass. In Groovy every class has a meta class that can be changed and extended at runtime. One method of this meta class is the invokeMethod() that has the following signature.

Object invokeMethod(Object object, String methodName, Object arguments)

This method controls the calls of methods in the class. By overwriting this method one can implement memoization easily.

class MemoizationDecorator {
	static void memoizeMethods(Class clazz, Set<string> methods) {
		Map cache = [:]
		clazz.metaClass.invokeMethod = { String name, args -&gt;
			def key
			def result
			if (methods.contains(name)) {
				// initialise the cache

				if (!cache[name]) cache[name] = [:]
				if (!cache[name][delegate]) cache[name][delegate] = [:]
				// is there already a memoized result?

				key = args.collect { it.hashCode().toString() }.join('-')
				result = cache[name][delegate][key]
			if (null == result) {
				// if there is no result, call the method

				def method = delegate.metaClass.getMetaMethod(name, args)
				if (method) result = method.invoke(delegate, args)
			if (methods.contains(name)) {
				// store the result

				cache[name][delegate][key] = result
			return result

The cache cache contains the results of the previous calls. The set methods contains the name of the methods that should get memoized.

Lets write a test for this class.

class TestClass {
    int fCalls = 0
    int gCalls = 0
    int f() { fCalls++ }
    int g() { gCalls++ }

def m0 = new TestClass()
MemoizationDecorator.memoizeMethods(TestClass, ['f'] as Set)
def m1 = new TestClass()

m0.f() + m0.f() + m0.f() + m0.g() + m0.g() + m0.g()
assert m0.fCalls == 3
assert m0.gCalls == 3

m1.f() + m1.f() + m1.f() + m1.g() + m1.g() + m1.g()
assert m1.fCalls == 1
assert m1.gCalls == 3

The object m0 is created before the memoization decorator was called. Therefore all the three calls to the method f were executed. For object m1 the method f was called only once. Well the observant reader will have noticed, that the results of the computations are different for m0 and m1. This is a reminder that the correctness is preserved only for purely functional methods, e. g. methods without internal state. This is not the case in our example.

Remark: This post was adapted to the new blog format in November 2016.