c# - 缓存编译表达式树

Question

如何有效地缓存从表达式树编译的方法？

public void SomeToStringCalls()
{
    ToString(i => (i + 1).ToString(), 1);
    ToString(i => (i + 1).ToString(), 2);
    ToString(i => (i + 2).ToString(), 3);
    ToString(i => (i + 2).ToString(), 4);
}

private string ToString<T>(Expression<Func<T, string>> expression, T input)
{
    var method = expression.Compile();
    return method.Invoke(input);
}

上面，每个调用都会重新编译每个表达式，即使有些是相同的。我无法Dictionary<Expression<Func<T, string>>, Func<T, string>>()从表达式中缓存已编译的方法，因为equals遗嘱失败了。

Answer 1

在集中式缓存中缓存表达式树的问题是：

1. 您将需要全面的等式比较和散列算法。
2. 您将需要自己实现这些算法，因为标准表达式类型不提供开箱即用的它们。

全面的等式比较执行起来会很昂贵，但是使用廉价的散列函数可以在一定程度上减轻成本。此外，由于表达式树是不可变的，您可以在第一次计算哈希码后对其进行缓存。这可能会节省一些查找时间，但是每次您使用新创建的表达式作为键检查缓存时（我想大多数情况下都是这样），您至少需要对新表达式进行哈希处理。

选项 1：本地/静态缓存

一个理想的解决方案将避免所有这些开销。如果可行（即，如果这些表达式不是动态组合的），最好的办法是简单地将表达式树缓存在其声明站点附近。您应该能够将其中的大部分（如果不是全部）存储在静态字段中：

private static readonly Expression<Func<int, string>> _addOne =
    i => (i + 1).ToString();
private static readonly Expression<Func<int, string>> _addTwo =
    i => (i + 2).ToString();

public void SomeToStringCalls()
{
    ToString(_addOne, 1);
    ToString(_addOne, 2);
    ToString(_addTwo, 3);
    ToString(_addTwo, 4);
}

缺点是您最终可能会在各种类型中使用重复的表达式，但如果您没有生成大量表达式，这可能不是问题。

选项 2：集中缓存

如果这不是您的选择，您将必须实现一个集中式缓存以及执行此操作所需的散列和相等算法。散列算法将帮助您缩小候选集的范围，因此它工作得相当好是很重要的，即在实践中产生很少的冲突。但是，鉴于表达式树的复杂性，您希望降低成本。因此，我建议您不要以完美的散列函数为目标，而应以相当便宜但有效的散列函数为目标。也许是这样的：

internal static class ExpressionHasher
{
    private const int NullHashCode = 0x61E04917;

    [ThreadStatic]
    private static HashVisitor _visitor;

    private static HashVisitor Visitor
    {
        get
        {
            if (_visitor == null)
                _visitor = new HashVisitor();
            return _visitor;
        }
    }

    public static int GetHashCode(Expression e)
    {
        if (e == null)
            return NullHashCode;

        var visitor = Visitor;

        visitor.Reset();
        visitor.Visit(e);

        return visitor.Hash;
    }

    private sealed class HashVisitor : ExpressionVisitor
    {
        private int _hash;

        internal int Hash
        {
            get { return _hash; }
        }

        internal void Reset()
        {
            _hash = 0;
        }

        private void UpdateHash(int value)
        {
            _hash = (_hash * 397) ^ value;
        }

        private void UpdateHash(object component)
        {
            int componentHash;

            if (component == null)
            {
                componentHash = NullHashCode;
            }
            else
            {
                var member = component as MemberInfo;
                if (member != null)
                {
                    componentHash = member.Name.GetHashCode();

                    var declaringType = member.DeclaringType;
                    if (declaringType != null && declaringType.AssemblyQualifiedName != null)
                        componentHash = (componentHash * 397) ^ declaringType.AssemblyQualifiedName.GetHashCode();
                }
                else
                {
                    componentHash = component.GetHashCode();
                }
            }

            _hash = (_hash * 397) ^ componentHash;
        }

        public override Expression Visit(Expression node)
        {
            UpdateHash((int)node.NodeType);
            return base.Visit(node);
        }

        protected override Expression VisitConstant(ConstantExpression node)
        {
            UpdateHash(node.Value);
            return base.VisitConstant(node);
        }

        protected override Expression VisitMember(MemberExpression node)
        {
            UpdateHash(node.Member);
            return base.VisitMember(node);
        }

        protected override MemberAssignment VisitMemberAssignment(MemberAssignment node)
        {
            UpdateHash(node.Member);
            return base.VisitMemberAssignment(node);
        }

        protected override MemberBinding VisitMemberBinding(MemberBinding node)
        {
            UpdateHash((int)node.BindingType);
            UpdateHash(node.Member);
            return base.VisitMemberBinding(node);
        }

        protected override MemberListBinding VisitMemberListBinding(MemberListBinding node)
        {
            UpdateHash((int)node.BindingType);
            UpdateHash(node.Member);
            return base.VisitMemberListBinding(node);
        }

        protected override MemberMemberBinding VisitMemberMemberBinding(MemberMemberBinding node)
        {
            UpdateHash((int)node.BindingType);
            UpdateHash(node.Member);
            return base.VisitMemberMemberBinding(node);
        }

        protected override Expression VisitMethodCall(MethodCallExpression node)
        {
            UpdateHash(node.Method);
            return base.VisitMethodCall(node);
        }

        protected override Expression VisitNew(NewExpression node)
        {
            UpdateHash(node.Constructor);
            return base.VisitNew(node);
        }

        protected override Expression VisitNewArray(NewArrayExpression node)
        {
            UpdateHash(node.Type);
            return base.VisitNewArray(node);
        }

        protected override Expression VisitParameter(ParameterExpression node)
        {
            UpdateHash(node.Type);
            return base.VisitParameter(node);
        }

        protected override Expression VisitTypeBinary(TypeBinaryExpression node)
        {
            UpdateHash(node.Type);
            return base.VisitTypeBinary(node);
        }
    }
}

它并不完美，但它应该会给你带来很好的结果：

1. 它向下钻取并包括树中的每个表达式。
2. 至少，NodeType每个子表达式的 都包含在哈希中。一项明显（但可能代价高昂）的改进是还包括Type; 如果您发现碰撞次数过多，请尝试一下。
3. 包括表达式中引用的成员和类型。
4. 包括出现在树中的常数值。
5. 它不需要堆分配来运行，但代价是不可重入（因为您只分析顶级表达式，这很好）。您可以在多个线程上同时运行它。

由于您实际上并未覆盖GetHashCode()任何表达式类型，因此散列函数的缺陷不会泄漏并影响外部代码。这为我们提供了弯曲散列函数规则的自由度。

您的平等比较需要更全面。虽然散列函数实际上是用于最小化候选集的“估计”，但相等比较执行实际匹配，它需要完美。您当然可以使用我提出的散列解决方案作为解决问题的模板，但请记住，您必须对表达式的所有属性进行详尽的比较。要记住的一件事是，您可能不想比较ParameterExpression树中节点的名称，但您需要维护要比较的两棵树中的参数/变量的映射，以确保它们在其父表达式树的上下文中表示“相同”的值。

除了忽略参数/变量名称外，不要费心尝试解决“语义等价”，即产生相同结果和副作用但结构不同的表达式。它不能有效地完成，也不值得尝试。

最后，您可以通过实现两级查找来加快速度：首先，根据参数类型选择正确的缓存，然后在该缓存中查找匹配项。如果保证每个 lambda 表达式都只有一个参数，这种方法将是最有效的。随着争论的增多，好处会降低。

Answer 2

很久以前我发现了这篇文章，它揭示了表达式缓存的优点和缺点（使用常量提取......它允许您编译.Where(t=>t.prop==3)并.Where(t=>t.prop==5)使用相同的委托）。

Answer 3

您不能使用的原因Dictionary<Expression<Func<T, string>>, Func<T, string>>是它Expression<T> GetHashCode不够聪明，无法检测“相等”的表达式。我不确定，但很可能Expression<T>.GetHashCode返回表达式的内存地址。

为了解决这个问题，您可以引入更“智能”的哈希计算。让我们考虑具有相等主体的相等表达式。这是一条很滑的路，但如果你愿意承担责任，确保：

1. 没有两个不同的表达式具有相同的哈希码
2. 具有相同主体的两个表达式具有相同的哈希码

你可以实现你想要的。

这是我在 pastebin 为您组装的简单概念验证代码。这不是工业实力（评论中有一些改进它的提示），但它清楚地证明了方法的可行性。

在进一步阐述之前需要考虑几件事：不正确的哈希函数可能会导致非常棘手的错误。所以，三思而后行，编写大量的单元测试和猎物 :)

Answer 4

您描述的问题是严重的，因为评估两个表达式的语义相等性至少与编译表达式一样昂贵。为了说明这一点，这里有一个表达式相等实现的链接。这个实现并不完美，例如：

MethodA() { MethodB(); }
MethodB() { ... }

在上面的示例中，MethodA并且MethodB在它们做同样的事情的意义上是等效的，并且您很可能希望将它们视为等效的。例如，在启用编译器优化的 C# 中构建它会将调用替换为MethodB调用MethodA。比较代码时存在无数问题，这是一个正在进行的研究课题。

如果您发现编译表达式是您的应用程序的瓶颈，您应该考虑这样一种设计，其中表达式由某种标识它的键引用。当您确定相等时，您可能已经编译了它。

为了评论 J0HN 的答案，它比较了主体的哈希码和参数，这绝不是一个可靠的解决方案，因为它没有对表达式树进行深度评估。

另外，看看评论中发布的这个问题。

Answer 5

如果您的目标是从表达式中编译 + 调用“提取值”，那么您可能会寻找另一种方式。

我试图从表达式树中提取值而不通过反射进行编译。

我的解决方案并不完全支持所有表达式，起初它是为没有 lambda 和算术的缓存方法调用而编写的，但通过一些改进它可以提供帮助。

这里是：

private static object ExtractValue(Expression expression, object[] input, ReadOnlyCollection<ParameterExpression> parameters)
{
    if (expression == null)
    {
        return null;
    }

    var ce = expression as ConstantExpression;
    if (ce != null)
    {
        return ce.Value;
    }

    var pe = expression as ParameterExpression;
    if (pe != null)
    {
        return input[parameters.IndexOf(pe)];
    }

    var ma = expression as MemberExpression;
    if (ma != null)
    {
        var se = ma.Expression;
        object val = null;
        if (se != null)
        {
            val = ExtractValue(se, input, parameters);
        }

        var fi = ma.Member as FieldInfo;
        if (fi != null)
        {
            return fi.GetValue(val);
        }
        else
        {
            var pi = ma.Member as PropertyInfo;
            if (pi != null)
            {
                return pi.GetValue(val);
            }
        }
    }

    var mce = expression as MethodCallExpression;
    if (mce != null)
    {
        return mce.Method.Invoke(ExtractValue(mce.Object, input, parameters), mce.Arguments.Select(a => ExtractValue(a, input, parameters)).ToArray());
    }

    var sbe = expression as BinaryExpression;
    if (sbe != null)
    {
        var left = ExtractValue(sbe.Left, input, parameters);
        var right = ExtractValue(sbe.Right, input, parameters);

        // TODO: check for other types and operands

        if (sbe.NodeType == ExpressionType.Add)
        {
            if (left is int && right is int)
            {
                return (int) left + (int) right;
            }
        }

        throw new NotImplementedException();
    }

    var le = expression as LambdaExpression;
    if (le != null)
    {
        return ExtractValue(le.Body, input, le.Parameters);
    }

    // TODO: Check for other expression types

    var dynamicInvoke = Expression.Lambda(expression).Compile().DynamicInvoke();
    return dynamicInvoke;
}

随着用法：

private static string ToString<T>(Expression<Func<T, string>> expression, T input)
{
    var sw = Stopwatch.StartNew();
    var method = expression.Compile();
    var invoke = method.Invoke(input);
    sw.Stop();
    Console.WriteLine("Compile + Invoke: {0}, {1} ms", invoke, sw.Elapsed.TotalMilliseconds);
    sw.Restart();
    var r2 = ExtractValue(expression, new object[] {input}, null);
    sw.Stop();
    Console.WriteLine("ExtractValue: {0}, {1} ms", r2, sw.Elapsed.TotalMilliseconds);
    return invoke;
}

我认为，通过一些改进和额外的表达式类型，这个解决方案可能是 Compile().DynamicInvoke() 的更快替代方案

Answer 6

另请参阅System.Web.Mvc.ExpressionUtil.CachedExpressionCompiler哪些可用于缓存表达式编译。如果使用 Mvc 5 通过反射调用它，否则可以带一份源代码。

Answer 7

称我为简单，但在我测试的一个简单场景中，这似乎快了大约 4 倍：

    public static Dictionary<string, object> cache
        = new Dictionary<string, object>();
    public static string ToString<T>(
            Expression<Func<T, string>> expression,
            T input)
    {
        string key = typeof(T).FullName + ":" + expression.ToString();
        object o;  cache.TryGetValue(key, out o);
        Func<T, string> method = (Func<T, string>)o;
        if (method == null)
        {
            method = expression.Compile();
            cache[key] = method;
        }
        return method.Invoke(input);
    }