Wikipedia defines memoization as:
In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually-recursive descent parsing[1] in a general top-down parsing algorithm[2][3] that accommodates ambiguity and left recursion in polynomial time and space. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement. In the context of some Logic Programming languages, memoization is also known as tabling.[4] – [more]
I’ve been meaning to write something in .NET to be able to do this. After doing some Googling and seeing what other people have come up with, it appeared to me that I didn’t need Lambda expressions or something fancy to do this, but I had to be able to make sure that I could use the functionality on any class. So, I ran onto an answer on StackOverflow: C# – Refactor and Remove Duplication From this Memoization Code. The implementation relies on Func<T> and its variants, which appeared in .NET 3.5, to make the “magic” happen.
What I have done is take the code in the StackOverflow question and modify it to create the cache key based on not only the class, but also the method. Also when the Reset method is called, we don’t necessarily want to completely blow away the entire cache. We really only want to remove any of the cache keys related specifically to the memoization.
Enough talk, code!
using System;
using System.Web.Caching;
namespace MemoizationTester
{
public static class Memoize
{
// .NET 3.5 only supports up to 4 params to a Func<T>
// .NET 4.0 supports up to 16 params to a Func<T>
// 5 Params
public delegate TResult Func<T1, T2, T3, T4, T5, TResult>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5);
// 6 Params
public delegate TResult Func<T1, T2, T3, T4, T5, T6, TResult>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6);
// 7 Params
public delegate TResult Func<T1, T2, T3, T4, T5, T6, T7, TResult>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7);
// 8 Params
public delegate TResult Func<T1, T2, T3, T4, T5, T6, T7, T8, TResult>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8);
public static Cache LocalCache = System.Web.HttpRuntime.Cache ?? System.Web.HttpContext.Current.Cache;
/// <summary>
/// Helps to provide a consistent string that can be searched for in Cache collection.
/// </summary>
private const string MemoizeCacheKey = "memoize_";
/// <summary>
/// Memoize a Method call that takes no Parameters.
/// </summary>
/// <typeparam name="TResult">The <see cref="System.Type"/> of the method result.</typeparam>
/// <param name="func">The class method you want to memoize.</param>
/// <param name="durationInSeconds">The duration in seconds that you want to cache the method call result.</param>
/// <returns>The memoized method's result data.</returns>
public static TResult ResultOf<TResult>(
Func<TResult> func,
long durationInSeconds)
{
var key = HashArguments(
func.Method.DeclaringType.GUID,
func.Method.Name
);
return Complete(key, durationInSeconds, func);
}
/// <summary>
/// Memoize a Method call that takes 1 Parameter.
/// </summary>
/// <typeparam name="TArg1">The <see cref="System.Type"/> of the class method's first parameter.</typeparam>
/// <typeparam name="TResult">The <see cref="System.Type"/> of the method result.</typeparam>
/// <param name="func">The class method you want to memoize.</param>
/// <param name="arg1">The value of the class method's first parameter.</param>
/// <param name="durationInSeconds">The duration in seconds that you want to cache the method call result.</param>
/// <returns>The memoized method's result data.</returns>
public static TResult ResultOf<TArg1, TResult>(
Func<TArg1, TResult> func,
TArg1 arg1,
long durationInSeconds)
{
var key = HashArguments(
func.Method.DeclaringType.GUID,
func.Method.Name,
typeof(TArg1).GUID,
(object)arg1);
return Complete(key, durationInSeconds, () => func(arg1));
}
/// <summary>
/// Memoize a Method call that takes 2 Parameters.
/// </summary>
/// <typeparam name="TArg1">The <see cref="System.Type"/> of the class method's first parameter.</typeparam>
/// <typeparam name="TArg2">The <see cref="System.Type"/> of the class method's second parameter.</typeparam>
/// <typeparam name="TResult">The <see cref="System.Type"/> of the method result.</typeparam>
/// <param name="func">The class method you want to memoize.</param>
/// <param name="arg1">The value of the class method's first parameter.</param>
/// <param name="arg2">The value of the class method's second parameter.</param>
/// <param name="durationInSeconds">The duration in seconds that you want to cache the method call result.</param>
/// <returns>The memoized method's result data.</returns>
public static TResult ResultOf<TArg1, TArg2, TResult>(
Func<TArg1, TArg2, TResult> func,
TArg1 arg1,
TArg2 arg2,
long durationInSeconds)
{
var key = HashArguments(
func.Method.DeclaringType.GUID,
func.Method.Name,
typeof(TArg1).GUID,
(object)arg1,
typeof(TArg2).GUID,
(object)arg2);
return Complete(key, durationInSeconds, () => func(arg1, arg2));
}
/// <summary>
/// Memoize a Method call that takes 3 Parameters.
/// </summary>
/// <typeparam name="TArg1">The <see cref="System.Type"/> of the class method's first parameter.</typeparam>
/// <typeparam name="TArg2">The <see cref="System.Type"/> of the class method's second parameter.</typeparam>
/// <typeparam name="TArg3">The <see cref="System.Type"/> of the class method's third parameter.</typeparam>
/// <typeparam name="TResult">The <see cref="System.Type"/> of the method result.</typeparam>
/// <param name="func">The class method you want to memoize.</param>
/// <param name="arg1">The value of the class method's first parameter.</param>
/// <param name="arg2">The value of the class method's second parameter.</param>
/// <param name="arg3">The value of the class method's third parameter.</param>
/// <param name="durationInSeconds">The duration in seconds that you want to cache the method call result.</param>
/// <returns>The memoized method's result data.</returns>
public static TResult ResultOf<TArg1, TArg2, TArg3, TResult>(
Func<TArg1, TArg2, TArg3, TResult> func,
TArg1 arg1,
TArg2 arg2,
TArg3 arg3,
long durationInSeconds)
{
var key = HashArguments(
func.Method.DeclaringType.GUID,
func.Method.Name,
typeof(TArg1).GUID,
(object)arg1,
typeof(TArg2).GUID,
(object)arg2,
typeof(TArg3).GUID,
(object)arg3);
return Complete(key, durationInSeconds, () => func(arg1, arg2, arg3));
}
/// <summary>
/// Memoize a call that takes 4 Parameters.
/// </summary>
/// <typeparam name="TArg1">The <see cref="System.Type"/> of the class method's first parameter.</typeparam>
/// <typeparam name="TArg2">The <see cref="System.Type"/> of the class method's second parameter.</typeparam>
/// <typeparam name="TArg3">The <see cref="System.Type"/> of the class method's third parameter.</typeparam>
/// <typeparam name="TArg4">The <see cref="System.Type"/> of the class method's fourth parameter.</typeparam>
/// <typeparam name="TResult">The <see cref="System.Type"/> of the method result.</typeparam>
/// <param name="func">The class method you want to memoize.</param>
/// <param name="arg1">The value of the class method's first parameter.</param>
/// <param name="arg2">The value of the class method's second parameter.</param>
/// <param name="arg3">The value of the class method's third parameter.</param>
/// <param name="arg4">The value of the class method's fourth parameter.</param>
/// <param name="durationInSeconds">The duration in seconds that you want to cache the method call result.</param>
/// <returns>The memoized method's result data.</returns>
public static TResult ResultOf<TArg1, TArg2, TArg3, TArg4, TResult>(
Func<TArg1, TArg2, TArg3, TArg4, TResult> func,
TArg1 arg1,
TArg2 arg2,
TArg3 arg3,
TArg4 arg4,
long durationInSeconds)
{
var key = HashArguments(
func.Method.DeclaringType.GUID,
func.Method.Name,
typeof(TArg1).GUID,
(object)arg1,
typeof(TArg2).GUID,
(object)arg2,
typeof(TArg3).GUID,
(object)arg3,
typeof(TArg4).GUID,
(object)arg4);
return Complete(key, durationInSeconds, () => func(arg1, arg2, arg3, arg4));
}
/// <summary>
/// Memoize a call that takes 5 Parameters.
/// </summary>
/// <typeparam name="TArg1">The <see cref="System.Type"/> of the class method's first parameter.</typeparam>
/// <typeparam name="TArg2">The <see cref="System.Type"/> of the class method's second parameter.</typeparam>
/// <typeparam name="TArg3">The <see cref="System.Type"/> of the class method's third parameter.</typeparam>
/// <typeparam name="TArg4">The <see cref="System.Type"/> of the class method's fourth parameter.</typeparam>
/// <typeparam name="TArg5">The <see cref="System.Type"/> of the class method's fifth parameter.</typeparam>
/// <typeparam name="TResult">The <see cref="System.Type"/> of the method result.</typeparam>
/// <param name="func">The class method you want to memoize.</param>
/// <param name="arg1">The value of the class method's first parameter.</param>
/// <param name="arg2">The value of the class method's second parameter.</param>
/// <param name="arg3">The value of the class method's third parameter.</param>
/// <param name="arg4">The value of the class method's fourth parameter.</param>
/// <param name="arg5">The value of the class method's fifth parameter.</param>
/// <param name="durationInSeconds">The duration in seconds that you want to cache the method call result.</param>
/// <returns>The memoized method's result data.</returns>
public static TResult ResultOf<TArg1, TArg2, TArg3, TArg4, TArg5, TResult>(
Func<TArg1, TArg2, TArg3, TArg4, TArg5, TResult> func,
TArg1 arg1,
TArg2 arg2,
TArg3 arg3,
TArg4 arg4,
TArg5 arg5,
long durationInSeconds)
{
var key = HashArguments(
func.Method.DeclaringType.GUID,
func.Method.Name,
typeof(TArg1).GUID,
(object)arg1,
typeof(TArg2).GUID,
(object)arg2,
typeof(TArg3).GUID,
(object)arg3,
typeof(TArg4).GUID,
(object)arg4,
typeof(TArg5).GUID,
(object)arg5);
return Complete(key, durationInSeconds, () => func(arg1, arg2, arg3, arg4, arg5));
}
/// <summary>
/// Memoize a call that takes 6 Parameters.
/// </summary>
/// <typeparam name="TArg1">The <see cref="System.Type"/> of the class method's first parameter.</typeparam>
/// <typeparam name="TArg2">The <see cref="System.Type"/> of the class method's second parameter.</typeparam>
/// <typeparam name="TArg3">The <see cref="System.Type"/> of the class method's third parameter.</typeparam>
/// <typeparam name="TArg4">The <see cref="System.Type"/> of the class method's fourth parameter.</typeparam>
/// <typeparam name="TArg5">The <see cref="System.Type"/> of the class method's fifth parameter.</typeparam>
/// <typeparam name="TArg6">The <see cref="System.Type"/> of the class method's sixth parameter.</typeparam>
/// <typeparam name="TResult">The <see cref="System.Type"/> of the method result.</typeparam>
/// <param name="func">The class method you want to memoize.</param>
/// <param name="arg1">The value of the class method's first parameter.</param>
/// <param name="arg2">The value of the class method's second parameter.</param>
/// <param name="arg3">The value of the class method's third parameter.</param>
/// <param name="arg4">The value of the class method's fourth parameter.</param>
/// <param name="arg5">The value of the class method's fifth parameter.</param>
/// <param name="arg6">The value of the class method's sixth parameter.</param>
/// <param name="durationInSeconds">The duration in seconds that you want to cache the method call result.</param>
/// <returns>The memoized method's result data.</returns>
public static TResult ResultOf<TArg1, TArg2, TArg3, TArg4, TArg5, TArg6, TResult>(
Func<TArg1, TArg2, TArg3, TArg4, TArg5, TArg6, TResult> func,
TArg1 arg1,
TArg2 arg2,
TArg3 arg3,
TArg4 arg4,
TArg5 arg5,
TArg6 arg6,
long durationInSeconds)
{
var key = HashArguments(
func.Method.DeclaringType.GUID,
func.Method.Name,
typeof(TArg1).GUID,
(object)arg1,
typeof(TArg2).GUID,
(object)arg2,
typeof(TArg3).GUID,
(object)arg3,
typeof(TArg4).GUID,
(object)arg4,
typeof(TArg5).GUID,
(object)arg5,
typeof(TArg6).GUID,
(object)arg6);
return Complete(key, durationInSeconds, () => func(arg1, arg2, arg3, arg4, arg5, arg6));
}
/// <summary>
/// Memoize a call that takes 7 Parameters.
/// </summary>
/// <typeparam name="TArg1">The <see cref="System.Type"/> of the class method's first parameter.</typeparam>
/// <typeparam name="TArg2">The <see cref="System.Type"/> of the class method's second parameter.</typeparam>
/// <typeparam name="TArg3">The <see cref="System.Type"/> of the class method's third parameter.</typeparam>
/// <typeparam name="TArg4">The <see cref="System.Type"/> of the class method's fourth parameter.</typeparam>
/// <typeparam name="TArg5">The <see cref="System.Type"/> of the class method's fifth parameter.</typeparam>
/// <typeparam name="TArg6">The <see cref="System.Type"/> of the class method's sixth parameter.</typeparam>
/// <typeparam name="TArg7">The <see cref="System.Type"/> of the class method's seventh parameter.</typeparam>
/// <typeparam name="TResult">The <see cref="System.Type"/> of the method result.</typeparam>
/// <param name="func">The class method you want to memoize.</param>
/// <param name="arg1">The value of the class method's first parameter.</param>
/// <param name="arg2">The value of the class method's second parameter.</param>
/// <param name="arg3">The value of the class method's third parameter.</param>
/// <param name="arg4">The value of the class method's fourth parameter.</param>
/// <param name="arg5">The value of the class method's fifth parameter.</param>
/// <param name="arg6">The value of the class method's sixth parameter.</param>
/// <param name="arg7">The value of the class method's seventh parameter.</param>
/// <param name="durationInSeconds">The duration in seconds that you want to cache the method call result.</param>
/// <returns>The memoized method's result data.</returns>
public static TResult ResultOf<TArg1, TArg2, TArg3, TArg4, TArg5, TArg6, TArg7, TResult>(
Func<TArg1, TArg2, TArg3, TArg4, TArg5, TArg6, TArg7, TResult> func,
TArg1 arg1,
TArg2 arg2,
TArg3 arg3,
TArg4 arg4,
TArg5 arg5,
TArg6 arg6,
TArg7 arg7,
long durationInSeconds)
{
var key = HashArguments(
func.Method.DeclaringType.GUID,
func.Method.Name,
typeof(TArg1).GUID,
(object)arg1,
typeof(TArg2).GUID,
(object)arg2,
typeof(TArg3).GUID,
(object)arg3,
typeof(TArg4).GUID,
(object)arg4,
typeof(TArg5).GUID,
(object)arg5,
typeof(TArg6).GUID,
(object)arg6,
typeof(TArg7).GUID,
(object)arg7);
return Complete(key, durationInSeconds, () => func(arg1, arg2, arg3, arg4, arg5, arg6, arg7));
}
/// <summary>
/// Memoize a call that takes 8 Parameters.
/// </summary>
/// <typeparam name="TArg1">The <see cref="System.Type"/> of the class method's first parameter.</typeparam>
/// <typeparam name="TArg2">The <see cref="System.Type"/> of the class method's second parameter.</typeparam>
/// <typeparam name="TArg3">The <see cref="System.Type"/> of the class method's third parameter.</typeparam>
/// <typeparam name="TArg4">The <see cref="System.Type"/> of the class method's fourth parameter.</typeparam>
/// <typeparam name="TArg5">The <see cref="System.Type"/> of the class method's fifth parameter.</typeparam>
/// <typeparam name="TArg6">The <see cref="System.Type"/> of the class method's sixth parameter.</typeparam>
/// <typeparam name="TArg7">The <see cref="System.Type"/> of the class method's seventh parameter.</typeparam>
/// <typeparam name="TArg8">The <see cref="System.Type"/> of the class method's eighth parameter.</typeparam>
/// <typeparam name="TResult">The <see cref="System.Type"/> of the method result.</typeparam>
/// <param name="func">The class method you want to memoize.</param>
/// <param name="arg1">The value of the class method's first parameter.</param>
/// <param name="arg2">The value of the class method's second parameter.</param>
/// <param name="arg3">The value of the class method's third parameter.</param>
/// <param name="arg4">The value of the class method's fourth parameter.</param>
/// <param name="arg5">The value of the class method's fifth parameter.</param>
/// <param name="arg6">The value of the class method's sixth parameter.</param>
/// <param name="arg7">The value of the class method's seventh parameter.</param>
/// <param name="arg8">The value of the class method's eighth parameter.</param>
/// <param name="durationInSeconds">The duration in seconds that you want to cache the method call result.</param>
/// <returns>The memoized method's result data.</returns>
public static TResult ResultOf<TArg1, TArg2, TArg3, TArg4, TArg5, TArg6, TArg7, TArg8, TResult>(
Func<TArg1, TArg2, TArg3, TArg4, TArg5, TArg6, TArg7, TArg8, TResult> func,
TArg1 arg1,
TArg2 arg2,
TArg3 arg3,
TArg4 arg4,
TArg5 arg5,
TArg6 arg6,
TArg7 arg7,
TArg8 arg8,
long durationInSeconds)
{
var key = HashArguments(
func.Method.DeclaringType.GUID,
func.Method.Name,
typeof(TArg1).GUID,
(object)arg1,
typeof(TArg2).GUID,
(object)arg2,
typeof(TArg3).GUID,
(object)arg3,
typeof(TArg4).GUID,
(object)arg4,
typeof(TArg5).GUID,
(object)arg5,
typeof(TArg6).GUID,
(object)arg6,
typeof(TArg7).GUID,
(object)arg7,
typeof(TArg8).GUID,
(object)arg8);
return Complete(key, durationInSeconds, () => func(arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8));
}
/// <summary>
/// Flushes the LocalCache of all Memoized method calls
/// </summary>
public static void Reset()
{
var enumerator = LocalCache.GetEnumerator();
while (enumerator.MoveNext())
{
// We only want memoized items, don't flush the entire cache!
if (enumerator.Key.ToString().Contains(MemoizeCacheKey))
{
LocalCache.Remove(enumerator.Key.ToString());
}
}
}
private static T CacheResult<T>(string key, long durationInSeconds, T value)
{
LocalCache.Insert(
key,
value,
null,
DateTime.Now.AddSeconds(durationInSeconds),
new TimeSpan());
return value;
}
static T Complete<T>(string key, long durationInSeconds, Func<T> valueFunc)
{
return LocalCache.Get(key) != null
? (T)LocalCache.Get(key)
: CacheResult(key, durationInSeconds, valueFunc());
}
/// <summary>
/// A not completely foolproof way to generate a unique code to be used as a hash key in the LocalCache.
/// </summary>
/// <param name="args">All of the parameters you want a hash created against.</param>
/// <returns>Hash key string.</returns>
static string HashArguments(params object[] args)
{
if (args == null)
return "null args";
int result = 23;
for (int i = 0; i < args.Length; i++)
{
var arg = args[i];
if (arg == null)
{
result = 31 * result + (i + 1);
continue;
}
result = 31 * result + arg.GetHashCode();
}
return MemoizeCacheKey + result.ToString();
}
}
}
Let’s create some class with a long running method
public class SomeMath
{
public int Add(int a, int b)
{
// simulate a long running method
System.Threading.Thread.Sleep(1000);
return a + b;
}
}
You should now be able to see the difference running a test call
SomeMath math = new SomeMath();
int answer = 0;
// run method 1st time & prime cache
answer = Memoize.ResultOf<int, int, int>(math.Add, 1, 2, 100000);
// run method 2nd time, should be much faster
answer = Memoize.ResultOf<int, int, int>(math.Add, 1, 2, 100000);
