Fastest way to memoize expression

Question

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.

"its not working" care to expand on that? What is it or isn't it doing? — Ron Beyer, May 01 '15 at 19:13
Dictionary keys need to not be mutated while they're in the dictionary, but that alone isn't enough. They also need to have `Equals` and `GetHashCode` implementations that have the desired semantics. — Servy, May 01 '15 at 19:16
Why do you want to memoize this? This doesn't look like an expensive method. — svick, May 02 '15 at 18:48
@svick because entire complexity is hidden in `CreateCompareTo` method — Alex Zhukovskiy, May 03 '15 at 04:04

score 2 · Answer 1 · answered May 01 '15 at 19:14

2

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.

answered May 01 '15 at 19:14

xanatos

109,618
12
197
280

2

Of course, the problem isn't even just that equal expressions aren't always reference equal, but rather that the `Equals` and `GetHashCode` implementations of `Expression` also use reference semantics, not value semantics, and writing a valute-based comparer would be...hard. – Servy May 01 '15 at 19:17
1

@Servy Your sentence implies that there are `Expression.Equals` and `Expression.GetHashCode` overloads that are "badly done"... But there aren't! :-) It is more similar to collection types that don't have comparers :-) – xanatos May 01 '15 at 19:19
I *stated* that they have reference semantics. I made no value judgement at all about whether or not that was a good decision, but rather that the OP seems to be under the impression that they behave differently than they actually do. – Servy May 01 '15 at 19:21
@Servy *Equals and GetHashCode implementations of Expression* There is a (light) implication that there is a specific (non-default-`object`) `Equals` implementation/overload in the `Expression` class. Clearly your sentence could be interpreted as "the class `Expression` subclasses the `object` class and takes as its own all the `object` methods", but it was open to interpretation. I was quipping on that. And I **do** feel that a `Expression.Intern` would be a good idea. – xanatos May 01 '15 at 19:27
Whether there is a custom implementation or merely the use of the inherited implementation is *irrelevant*. What matters is how the implementation behaves, not who wrote it. The behavior of those methods is that the identity of the object is the object's reference. How that came to be is purely trivia. – Servy May 01 '15 at 19:29
While this clearly explains the problem, it doesn't actually offer any solution. – svick May 02 '15 at 18:46
1

@svick You can look at http://stackoverflow.com/q/673205/613130 There are some solutions there... – xanatos May 02 '15 at 18:59

score 1 · Accepted Answer · answered May 06 '15 at 06:27

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 :)

Fastest way to memoize expression

2 Answers2