C# Memoization

You want to optimize a method in your C# program that has few arguments and is called with the same arguments many times during execution. With the memoization optimization technique, you can store the results of a method as it is called, then use the lookup table to return them when needed again.

Memoize example

Let's get started by looking at an example of a non-memoized function (Lowercase1) and a memoized function (Lowercase2). The first function is much simpler: it simply calls ToLower on the string argument each time and returns it. The second is more complex: it first checks the static Dictionary if the key is found. If it finds a match, it doesn't recalculate the lowercase string. If no match is found, it calls ToLower and stores the result in the Dictionary, then returns the result.

This C# example program uses memoization to optimize repeat calls.

Program that achieves memoization [C#]

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	string result1 = Lowercase1("Test");
	string result2 = Lowercase2("Test"); // Call Lowercase2.
	string result3 = Lowercase2("Test"); // Call Lowercase2 again.
	Console.WriteLine("{0} {1} {2}", result1, result2, result3);
    }

    static string Lowercase1(string value)
    {
	return value.ToLower();
    }

    static Dictionary<string, string> _lowercase = new Dictionary<string, string>();
    static string Lowercase2(string value)
    {
	string lookup;
	if (_lowercase.TryGetValue(value, out lookup))
	    return lookup;

	lookup = value.ToLower();

	_lowercase[value] = lookup;
	return lookup;
    }
}

Output

test test test

Memoization optimization. In the Main entry point, the Lowercase2 method is called twice, but that method only lowercases the string once! This is because the two call sites use the same string argument. We avoid recalculating the result for the second method invocation.

Benchmark

To demonstrate the performance advantage, I used a benchmark harness and timed the cost of lowercasing the string "Test" one million times and took the average. The Lowercase2 method (memoization) results in a greater than 2x performance boost here. The results are not typical because only one argument is passed to the Lowercase methods.

Memoization benchmark result

Lowercase1: 99.62 ns
Lowercase2: 42.08 ns

Arrays

You do not need to use a Dictionary to achieve memoization in a method. For a method that only receives positive integers, you might be able to use an int[] (integer array) lookup table. This would improve performance over a Dictionary but might lead to edge cases and errors.

Multiple arguments

You can also memoize multiple argument methods. This can be really advantageous if there are only very few variations on most of the arguments. To memoize multiple arguments, you can concatenate a string key and then do a Dictionary lookup. This would only optimize methods that are much slower than string concatenations.

Theory

Memoization is an old and well-known optimization in computer science. As stated in the Structure and Interpretation of Computer Programs, it can "transform processes that require an exponential number of steps into processes whose space and time requirements grow linearly with the input" (p. 41). This is because previously computed results are not recomputed.

Notes

I have found memoization to be one of the more useful optimization techniques in programs. Frequently, methods are called repeatedly with the same arguments. Sometimes, memoization can be achieved on a parameterless method with a static field.

Summary

We described memoization as an optimization technique in the C# language. This optimization can greatly reduce the space and time requirements of certain methods that are called repeatedly with the same arguments. It is most effective on programs that call a method with a small number of arguments, repeatedly, and where external factors such as time are not considerations.