This article will present a technique for caching pure functions in C# using
Memoize technique.
This is a programmatic caching of pure method or function where we have a method that always returns the same result or equivalent result given an input.
This adds scalability, maybe the method takes long time to process and we want to avoid using resources and provide a quicker answer.
If your method has side effects or does not yield the same or equivalent result (cosmetic changes ignored) given a set of parameter(s), it should not be memoized.
But if it does, here is how you can do this.
Note that memoize is a general technique used in functional programming and is used in many languages such as Javascript, for example in the Underscore.Js lib.
First off, let's define some POCOs to test the memoize function out. We will use a small sample set of movies and their actors and additional information from the fabulous year 1997.
MovieStore.cs
public class MovieStore {
public string GetActorsByMovieTitle(string movieTitle)
{
Console.WriteLine($"Retrieving actors for movie with title {movieTitle} at: {DateTime.Now}");
List<Movie> movies1997 = System.Text.Json.JsonSerializer.Deserialize<List<Movie>>(movies1997json);
string actors = string.Join(",", movies1997
.FirstOrDefault(m => m.name?.ToLower() == movieTitle?.ToLower())?.actors.ToArray());
return actors;
}
string movies1997json = """
[
{
"name": "The Lost World: Jurassic Park",
"year": 1997,
"runtime": 129,
"categories": [
"adventure",
"action",
"sci-fi"
],
"releasedate": "1997-05-23",
"director": "Steven Spielberg",
"writer": [
"Michael Crichton",
"David Koepp"
],
"actors": [
"Jeff Goldblum",
"Julianne Moore",
"Pete Postlethwaite"
],
"storyline": "Four years after the failure of Jurassic Park on Isla Nublar, John Hammond reveals to Ian Malcolm that there was another island (\"Site B\") on which dinosaurs were bred before being transported to Isla Nublar. Left alone since the disaster, the dinosaurs have flourished, and Hammond is anxious that the world see them in their \"natural\" environment before they are exploited."
},
{
"name": "The Fifth Element",
"year": 1997,
"runtime": 127,
"categories": [
"action",
"adventure",
"sci-fi"
],
"releasedate": "1997-05-09",
"director": "Luc Besson",
"writer": [
"Luc Besson",
"Robert Mark Kamen"
],
"actors": [
"Bruce Willis",
"Milla Jovovich",
"Gary Oldman",
"Chris Tucker",
"Ian Holm",
"Luke Perry",
"Brion James",
"Tommy Lister",
"Lee Evans",
"Charlie Creed-Miles",
"John Neville",
"John Bluthal",
"Mathieu Kassovitz",
"Christpher Fairbank"
],
"storyline": "In the colorful future, a cab driver unwittingly becomes the central figure in the search for a legendary cosmic weapon to keep Evil and Mr. Zorg at bay."
} ,
{
"name": "Starship Troopers",
"year": 1997,
"runtime": 129,
"categories": [
"action",
"adventure",
"sci-fi",
"thriller"
],
"releasedate": "1997-11-07",
"director": "Paul Verhoeven",
"writer": [
"Edward Neumeier",
"Robert A. Heinlein"
],
"actors": [
"Casper Van Dien",
"Dina Meyer",
"Denise Richards",
"Jake Busey",
"Neil Patrick Harris",
"Clancy Brown",
"Seth Gilliam",
"Patrick Muldoon",
"Michael Ironside"
],
"storyline": "In the distant future, the Earth is at war with a race of giant alien insects. Little is known about the Bugs except that they are intent on the eradication of all human life. But there was a time before the war... A Mobile Infantry travels to distant alien planets to take the war to the Bugs. They are a ruthless enemy with only one mission: Survival of their species no matter what the cost..."
}
]
""";
}
Movie.cs
public class Movie
{
public string name { get; set; }
public int year { get; set; }
public int runtime { get; set; }
public List<string> categories { get; set; }
public string releasedate { get; set; }
public string director { get; set; }
public List<string> writer { get; set; }
public List<string> actors { get; set; }
public string storyline { get; set; }
}
Let's suppose the method
GetActorsByMovieTitle is called many times or takes a lot of time to calculate. We want to cache it, to memoize it. It will be cached in a simple manner using
memoize. This will short term cache the results, if we would like to persist the memoized results for long duration, we would use some other caching service such as database or Redis cache.
The caching will function in sequential calls inside the same scope, it could be scoped as a singleton and long term cached inside memory for example.
So here is how we can do the memoization shown below.
FunctionalExtensions.cs
public static Func<T1, TOut> Memoize<T1, TOut>(this Func<T1, TOut> @this, Func<T1, string> keyGenerator)
{
var dict = new Dictionary<string, TOut>();
return x =>
{
string key = keyGenerator(x);
if (!dict.ContainsKey(key))
{
dict.Add(key, @this(x));
}
return dict[key];
};
}
public static Func<T1, T2, TOut> Memoize<T1, T2, TOut>(this Func<T1, T2, TOut> @this, Func<T1, T2, string> keyGenerator)
{
var dict = new Dictionary<string, TOut>();
return (x,y) =>
{
string key = keyGenerator(x,y);
if (!dict.ContainsKey(key))
{
dict.Add(key, @this(x,y));
}
return dict[key];
};
}
public static Func<T1, T2, T3, TOut> Memoize<T1, T2, T3, TOut>(this Func<T1, T2, T3, TOut> @this, Func<T1, T2, T3, string> keyGenerator)
{
var dict = new Dictionary<string, TOut>();
return (x, y, z) =>
{
string key = keyGenerator(x, y,z);
if (!dict.ContainsKey(key))
{
dict.Add(key, @this(x, y, z));
}
return dict[key];
};
}
public static Func<T1, T2, T3, T4, TOut> Memoize<T1, T2, T3, T4, TOut>(this Func<T1, T2, T3, T4, TOut> @this, Func<T1, T2, T3, T4, string> keyGenerator)
{
var dict = new Dictionary<string, TOut>();
return (x, y, z, w) =>
{
string key = keyGenerator(x, y, z, w);
if (!dict.ContainsKey(key))
{
dict.Add(key, @this(x, y, z, w));
}
return dict[key];
};
}
As we see above, we use a dictionary inside the memoize overloads and the way generics works, a dictionary will live inside each overloaded method accepting a different count of generic type parameters.
We also provide a keyGenerator method that must be supplied to specify how we build up a unique key that we decide how we shall key each results from the given set of parameter(s).
Note that we return here a function result, that is a func, that returns TOut and accepts the specified parameters in each overload. T1 or T1,T2 or T1,T2,T3 or T1,T2,T3,T4 and so on.
Expanding the methods above to for example 16 parameters would be fairly easy, the code above shows how we can add support for more and more parameters. I believe you should avoid methods with more than 7 parameters,
but the code above should be clear. We return a func and we also accept also a func which returns TOut and same amount of parameters of same types T1,.. in each overload.
Okay, next up an example how we can use this memoize function in the main method.
Program.cs
void Main()
{
var movieStore = new MovieStore();
//string actors = movieStore.GetActorsByMovieTitle("Starship troopers");
//actors.Dump("Starship Troopers - Actors");
//
//Demo of memoized function
var GetActorsByMovieTitle = ((string movieTitle) => movieStore.GetActorsByMovieTitle(movieTitle));
var GetActorsByMovieTitleM = GetActorsByMovieTitle.Memoize(x => x);
var starShipTroopersActors1 = GetActorsByMovieTitleM("Starship troopers");
starShipTroopersActors1.Dump("Starship troopers - Call to method #1 time");
var starShipTroopersActors2 = GetActorsByMovieTitleM("Starship troopers");
starShipTroopersActors2.Dump("Starship troopers - Call to method #2 time");
var starShipTroopersActors3 = GetActorsByMovieTitleM("Starship troopers");
starShipTroopersActors3.Dump("Starship troopers - Call to method #3 time");
}
Note that in the test case above we send in one parameter T1 of type string, which is a movie title and we declare a func variable first using a lambda. We have to do the memoization in two declarations here and we use the convention that we suffix the memoized function with 'M' for 'Memoize'
Program.cs
void Main()
{
var movieStore = new MovieStore();
var GetActorsByMovieTitle = ((string movieTitle) => movieStore.GetActorsByMovieTitle(movieTitle));
var GetActorsByMovieTitleM = GetActorsByMovieTitle.Memoize(x => x);
The code has added a
Console.WriteLine in the method which is memoized to check how many times the method is actually called or the cached result is returned instead.
A run in Linqpad 7 is shown in screenshot below, showing that the output is cached correct.
Note that if we wanted a thread implementation, we could instead use ConcurrentDictionary for example. The following methods show how we can do this. We exchanged Dictionary with ConcurrentDictionary and exchanged Add with TryAdd method of ConcurrentDictionary.
Program.cs
public static Func<T1, TOut> MemoizeV2<T1, TOut>(this Func<T1, TOut> @this, Func<T1, string> keyGenerator)
{
var dict = new ConcurrentDictionary<string, TOut>();
return x =>
{
string key = keyGenerator(x);
if (!dict.ContainsKey(key))
{
dict.TryAdd(key, @this(x));
}
return dict[key];
};
}
public static Func<T1, T2, TOut> MemoizeV2<T1, T2, TOut>(this Func<T1, T2, TOut> @this, Func<T1, T2, string> keyGenerator)
{
var dict = new ConcurrentDictionary<string, TOut>();
return (x, y) =>
{
string key = keyGenerator(x, y);
if (!dict.ContainsKey(key))
{
dict.TryAdd(key, @this(x, y));
}
return dict[key];
};
}
public static Func<T1, T2, T3, TOut> MemoizeV2<T1, T2, T3, TOut>(this Func<T1, T2, T3, TOut> @this, Func<T1, T2, T3, string> keyGenerator)
{
var dict = new ConcurrentDictionary<string, TOut>();
return (x, y, z) =>
{
string key = keyGenerator(x, y, z);
if (!dict.ContainsKey(key))
{
dict.TryAdd(key, @this(x, y, z));
}
return dict[key];
};
}
public static Func<T1, T2, T3, T4, TOut> MemoizeV2<T1, T2, T3, T4, TOut>(this Func<T1, T2, T3, T4, TOut> @this, Func<T1, T2, T3, T4, string> keyGenerator)
{
var dict = new ConcurrentDictionary<string, TOut>();
return (x, y, z, w) =>
{
string key = keyGenerator(x, y, z, w);
if (!dict.ContainsKey(key))
{
dict.TryAdd(key, @this(x, y, z, w));
}
return dict[key];
};
}
Hopefully,
memoize or the process of
memoization should be clearer now. It is a call based caching technique used preferably for pure functions / methods that has the same or equivalent result given a set of input parameter(s) and we memoize the function / method and cache the results. When used inside e.g. a singleton, we can cache longer time in memory and achieve performance boosts. You could do the same of course using a static variable, but the memoize technique is more generic purpose and is a pattern that is used in many programming languages. F# usually got way better support for functional programming than C#, but actually lacks a built in memoization functionality. Other languages do support memoization built in, such as in Python and LISP.
The following screen shot shows a run of memoization above, I used ConcurrentDictionary when I tested.
