How to perform thread-safe function memoization in c#?
Like Gman mentioned ConcurrentDictionary
is the preferred way to do this, however if that is not available to a simple lock
statement would suffice.
static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
var d = new Dictionary<A, R>();
return a=>
{
R r;
lock(d)
{
if (!d.TryGetValue(a, out r))
{
r = f(a);
d.Add(a, r);
}
}
return r;
};
}
One potential issue using locks instead of ConcurrentDictionary
is this method could introduce deadlocks in to your program.
- You have two memoized functions
_memo1 = Func1.Memoize()
and_memo2 = Func2.Memoize()
, where_memo1
and_memo2
are instance variables. - Thread1 calls
_memo1
,Func1
starts processing. - Thread2 calls
_memo2
, insideFunc2
there is a call to_memo1
and Thread2 blocks. - Thread1's processing of
Func1
gets to a call of_memo2
late in the function, Thread1 blocks. - DEADLOCK!
So if at all possible, use ConcurrentDictionary
, but if you can't and you use locks instead do not call other Memoized functions that are scoped outside of the function you are running in when inside Memoized functions or you open yourself up to the risk of deadlocks (if _memo1
and _memo2
been local variables instead of instance variables the deadlock would not have happened).
(Note, performance may be slightly improved by using ReaderWriterLock
but you still will have the same deadlock issue.)
Expanding on GMan's answer, I wanted to memoize a function with more than one argument. Here's how I did it, using a C# Tuple
(requires C# 7) as they key for the ConcurrentDictionary
.
This technique could easily be extended to allow yet more arguments:
public static class FunctionExtensions
{
// Function with 1 argument
public static Func<TArgument, TResult> Memoize<TArgument, TResult>
(
this Func<TArgument, TResult> func
)
{
var cache = new ConcurrentDictionary<TArgument, TResult>();
return argument => cache.GetOrAdd(argument, func);
}
// Function with 2 arguments
public static Func<TArgument1, TArgument2, TResult> Memoize<TArgument1, TArgument2, TResult>
(
this Func<TArgument1, TArgument2, TResult> func
)
{
var cache = new ConcurrentDictionary<(TArgument1, TArgument2), TResult>();
return (argument1, argument2) =>
cache.GetOrAdd((argument1, argument2), tuple => func(tuple.Item1, tuple.Item2));
}
}
For example:
Func<int, string> example1Func = i => i.ToString();
var example1Memoized = example1Func.Memoize();
var example1Result = example1Memoized(66);
Func<int, int, int> example2Func = (a, b) => a + b;
var example2Memoized = example2Func.Memoize();
var example2Result = example2Memoized(3, 4);
(Of course, to get the benefit of memoization you'd normally want to keep example1Memoized
/ example2Memoized
in a class variable or somewhere where they're not short-lived).
You can use ConcurrentDictionary.GetOrAdd
which does everything you need:
static Func<A, R> ThreadsafeMemoize<A, R>(this Func<A, R> f)
{
var cache = new ConcurrentDictionary<A, R>();
return argument => cache.GetOrAdd(argument, f);
}
The function f
should be thread-safe itself, because it can be called from multiple threads simultaneously.
This code also doesn't guarantee that function f
is called only once per unique argument value. It can be called many times, in fact, in the busy environment. If you need this kind of contract, you should take a look at the answers in this related question, but be warned that they're not as compact and require using locks.