缓存编译的表达式树

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)使用同一委托）。