Memoization: A functional approach to making slow code fast

Hackered
Sunday, September 21, 2014
by Sean McAlinden

I recently worked on a project where expression trees were regularly created for property mapping, whilst the gains from using expression trees in code were clear, the performance hit from the continual need to generate a new expression tree was dreadful.

Memoization to the rescue...

I decided to create a memoize function (see functional programming) to make the code nice and fast, without a doubt it did just that

In this post I am going to show you a representative scenario and memoize function in c#.

The slow method

private static PropertyInfo GetPropertyInfo(Expression expression)
{
    // Some slow code
    // then
    if (expression as MemberExpression != null)
    {
        return ((MemberExpression)expression).Member as PropertyInfo;
    }

    throw new NotSupportedException("Not supported in this blog code :)");
}

The Memoize method

public static class ExpressionToPropertyInfoMemoizer
{
    static readonly ConcurrentDictionary<Expression , PropertyInfo> ExpressionPropertyInfoMaps = new ConcurrentDictionary<Expression , PropertyInfo>();
 
    public static Func<Expression, PropertyInfo> Memoize(this Func<Expression , PropertyInfo> function)
    {
        return param =>;
        {
            PropertyInfo value;
            if (ExpressionPropertyInfoMaps.TryGetValue(param, out value))
            {
                return value;
            }
 
            value = function(param);
            ExpressionPropertyInfoMaps.TryAdd(param, value);
            return value;
        };
    }
}

The calling code

Expression<Func<MyClass, string>> myProperty = x => x.MyProperty;
Func<Expression, PropertyInfo> getPropertyInfo = GetPropertyInfo;
var memoizedGetPropertyInfo = getPropertyInfo.Memoize();
 
var propertyInfo = memoizedGetPropertyInfo(myProperty.Body);
var propertyInfoAgainButFaster = memoizedGetPropertyInfo(myProperty.Body);
 
public class MyClass
{
    public string MyProperty { get; set; }
}

What is going on?

The ExpressionToPropertyInfoMemoizer function has the same signature as the GetPropertyInfo method which is extends.

The first time the ExpressionToPropertyInfoMemoizer is called, the value does not exist so GetPropertyInfo is called.

All subsequent calls with the same lambda expression are immediately pulled out of the ConcurrentDictionary.

If the ExpressionToPropertyInfoMemoizer is called with a different lambda expression (eg. another property) then the first time the GetPropertyInfo is called and as before all subsequent calls will be retrieved from the ConcurrentDictionary.