CODEWITHSUNDEEP
c#.netexpressionexpression-treesmemoization
Alex Zhukovskiy
Alex Zhukovskiy

Reputation: 10015

Fastest way to memoize expression

I have a function, that transform input Expression to output BlockExpression. So I write this code:

    private static readonly Dictionary<Expression, BlockExpression> MemberMemoizeDictionary = new Dictionary<Expression, BlockExpression>(); 
    private static BlockExpression CreateBody<TProperty>(CustomComparer<T> comparer, Expression<Func<T, TProperty>> member, bool createLabel)
        where TProperty : IComparable<TProperty>, IComparable
    {
        BlockExpression expression;
        if (MemberMemoizeDictionary.TryGetValue(member, out expression))
        {
            return expression;
        }

        MemberExpression memberExpression = (MemberExpression) (member.Body is MemberExpression ? member.Body : ((UnaryExpression)member.Body).Operand);
        BlockExpression result = comparer.CreateCompareTo<TProperty>(memberExpression, createLabel);
        MemberMemoizeDictionary[member] = result;
        return result;
    }

but it's not working.

I was thinking that Expressions are immutable, so I can use them as dictionary keys, but I see it's not true.

What is easiest and fastest way to solve this problem? It's always a single member-expression, with a possible convert due to boxing of value-type properties.

Upvotes: 3

Views: 310

Answers (2)

MBoros
MBoros

Reputation: 1140

As xantos stated, the expression trees are reference equal, so you cannot use them as dicrionary key. Use the MemberInfo as your key, that will work. 

private static readonly Dictionary<MemberInfo, BlockExpression> MemberMemoizeDictionary = new Dictionary<MemberInfo, BlockExpression>(); 
private static BlockExpression CreateBody<TProperty>(CustomComparer<T> comparer, Expression<Func<T, TProperty>> member, bool createLabel)
    where TProperty : IComparable<TProperty>, IComparable
{
    BlockExpression expression;
    MemberExpression memberExpression = (MemberExpression) (member.Body is MemberExpression ? member.Body : ((UnaryExpression)member.Body).Operand);
    if (MemberMemoizeDictionary.TryGetValue(memberExpression.Member, out expression))
    {
        return expression;
    }

    BlockExpression result = comparer.CreateCompareTo<TProperty>(memberExpression, createLabel);
    MemberMemoizeDictionary[member] = result;
    return result;
}

Disclaimer: I didnt check if this code compiles, but i think you get the point :)

Upvotes: 1

xanatos
xanatos

Reputation: 111870

I was thinking that Expressions are immutable

True

But note that expressions are regenerated every time!

public static Expression Exp = null;

public static void Foo(Expression<Func<bool>> exp)
{
    if (Exp == null)
    {
        Exp = exp;
    }
    else
    {
        Console.WriteLine(object.ReferenceEquals(Exp, exp));
    }

}

and

for (int i = 0; i < 2; i++)
{
    Foo(() => true);
}

writes

False

Sadly "literal" Expressions aren't "interned" by the C# compiler. It is even written somewhere in the MSDN.

Upvotes: 2

Related Questions