What kinds of functions are candidates for memoization?

Question

I've decided on PostSharp (indistinguishable from magic) to read attributes and memoize functions. The hash of the function call will be the key and the cached (in Velocity) result will be returned instead of calling the function again. Easy peasy, mac-and-cheesy.

I've already given up on being able to detect side effects in decorated functions, which turned out to be a "hard problem", even for the experts, which I am certainly not. Next, I've got to figure out what other functions are candidates for memoization.

• What about methods that take complex reference types as parameters?
• What about methods that depend on data inside of the instances they're called from?

ActiveRecord-esque data objects come to mind on that last one.

Am I going to have to refactor week-old code to support memoization?

Answer 1

You can only memoize a function if all of its inputs are value types or immutable reference types, if it returns either a value type or a new instance of a reference type, and if it has no side effects. Period.

Memoization depends on a deterministic mapping between inputs and outputs. Every call to F(a, b, c) in which a, b, and c contain the same values must return the same result in order for memoization to be possible.

If a parameter's a reference type, then even though its value doesn't change, multiple calls to the function using it may produce a different result. A trivial example:

public int MyFunction(MyType t)
{
   return t.Value;
}

Console.WriteLine(MyFunction(t));
t.Value++;
Console.WriteLine(MyFunction(t));

Similarly, if a function depends on a value external to it, then multiple calls to that function with the same parameters can return different results:

int Value = 0;

public int MyFunction(int input)
{
   return Value;
}

Console.WriteLine(MyFunction(1));
Value++;
Console.WriteLine(MyFunction(1));

And heaven help you if your memoized function does something other than return a value or a new reference type:

int Value = 0;

public int MyFunction(int input)
{
   Value++;
   return input;
}

If you call that function 10 times, Value will be 10. If you refactor it to use memoization and then call it 10 times, Value will be 1.

You can start going down the path of figuring out how to memoize state, so that you can phony up a function that memoizes a reference type. But what you're really memoizing is the set of values that the function works on. You can similarly hack a memoized function that has side effects so that its side effects occur before the memoization. But this is all begging for trouble.

If you want to implement memoization into a function that takes a reference type, the proper approach is to refactor out the part of the function that only works on value types, and memoize that function, e.g.:

public int MyFunction(MyType t)
{
   return t.Value + 1;
}

to this:

public int MyFunction(MyType t)
{
   return MyMemoizableFunction(t.Value);
}

private int MyMemoizableFunction(int value)
{
   return value + 1;
}

Any other approach to implementing memoization that you take either a) does the same thing, through more obscure means, or b) won't work.