快速计算表达式树

前言

.NET 3.5 中新增的表达式树（Expression Tree）特性，第一次在.NET 平台中引入了“逻辑即数据”的概念。也就是说，我们可以在代码里使用高级语言的形式编写一段逻辑，但是这段逻辑最终会被保存为数据。正因为如此，我们可以使用各种不同的方法对它进行处理。例如，您可以将其转化为一个 SQL 查询，或者外部服务调用等等，这便是 LINQ to Everything 在技术实现上的重要基石之一。

实事求是地说，.NET 3.5 中的表达式树的能力较为有限，只能用来表示一个“表达式”，而不能表示“语句”。也就是说，我们可以用它来表示一次“方法调用”或“属性访问”，但不能用它来表示一段“逻辑”。不过，微软在.NET 4.0 中增强了这一特性。在.NET 4.0 中，我们可以使用表达式树构建一段带有“变量声明”，“判断”，“循环”的逻辑。当“逻辑”成为“数据”时，我们就拥有了更广阔的空间来发挥创造力。例如，我们可以将一段使用 C#编写的顺序型逻辑，转化为包含异步调用的客户端 JavaScript 代码，以此快速构建带有复杂客户端逻辑的 Web 应用程序。

不过，即便是.NET 3.5 中表达式树的“半吊子”特性，也已经显著加强了.NET 平台的能力，甚至改变了我们对于一些事物的使用方式。

表达式树的优势

由于.NET 3.5 中的语言（如 C# 3.0，VB.NET 9.0）都在语法层面上集成了表达式树的构建，因此 API 设计者可以充分利用表达式树的优势来提供更强大易用的 API。优势主要有三个方面：

1. 强类型
2. 语义清晰
3. 简化 API 开发

强类型

就以.NET 平台中著名的 Mock 框架 NMock 来说，以下代码将会构造一个 ICalculator 接口的 Mock 对象，并指定 Sum 方法的一组输入和输出：

<span>var </span>mocks = <span>new </span><span>Mockery</span>();
<span>var </span>mockCalculator = mock.NewMock<<span>ICalculator</span>>();
 
<span>Expect</span>.Once.On(mockCalculator)
   .Method(<span>"Sum"</span>)
   .With(1, 2)
   .Will(<span>Return</span>.Value(3));

与此形成鲜明对比的是，作为.NET 平台中 Mock 框架的后起之秀 Moq ，充分利用了 C# 3.0 中的 Lambda 表达式特性改进了 API。因此，以上代码在 Moq 中的近似实现便是：

<span>Mock</span><<span>ICalculator</span>> mock = <span>new </span><span>Mock</span><<span>ICalculator</span>>();
mock.Setup(c => c.Sum(1, 2)).Returns(3);

NMock 使用字符串表示“方法”，使用 object 数组来表示参数，用 object 存放返回值的做法，在 Moq 中完全变成了强类型的“方法调用”。这样，开发人员在使用 Moq 使便可以获得更好的工具支持，如编辑器的智能提示（Intellisense），编译器的静态检查等等。

语义清晰

从语法上看，使用 Lambda 表达式构建表达式树，与高级语言中最常见的语句并无二致。由于表达式树在使用时仅仅是“构建”，而不会真正“执行”，因此 API 设计者可以把它作为一种天然的 DSL。例如在 Moq 中，我们便可以灵活指定 ICalculator 对象的行为：

<span>Mock</span><<span>ICalculator</span>> mock = <span>new </span><span>Mock</span><<span>ICalculator</span>>();
mock.Setup(c => c.Divide(<span>It</span>.IsAny<<span>int</span>>(), 0)).Throws(<span>new </span><span>DivideByZeroException</span>());
mock.Setup(c => c.Divide(0, <span>It</span>.Is<<span>int</span>>(i => i != 0))).Returns(0);

简化 API 开发

严格说来，“清晰语义”与 API 设计有关，并非表达式树的专利。例如同为.NET 平台下的 Mock 框架， RhinoMocks 使用如下的语法来定义 Mock 对象的行为：

<span>var </span>mocks = <span>new </span><span>MockRepository</span>();
<span>var </span>mockCalculator = mocks.CreateMock<<span>ICalculator</span>>();
 
<span>Expect</span>.Call(mockCalculator.Sum(1, 2)).Return(3);

这样的语法可谓不输于 Lambda 表达式所体现出来的语义。可是，使用 Lambda 表达式与否大大影响了实现此类 API 的难度。在 RhinoMocks 中，语句执行之时会切切实实地调用 Sum 方法，于是我们就必须使用动态类型等.NET 高级技术来实现这样的语法。而在 Moq 框架中，c => c.Sum(1, 2) 这样的代码会被构建为一颗表达式树，成为“数据”，并不会对 Sum 方法产生任何调用。而 API 设计者所要做的，仅仅是对这些数据进行分析，以获取 API 使用者所希望表现出的含义而已。

对表达式树进行计算，是处理表达式树时中最常见的工作了。几乎可以这么说，任何处理表达式树的工作都无法回避这个问题。在这里，“表达式树的计算”是指将一个复杂的表达式树转化为一个常量。例如，下图中左侧的表达式树，便可以转化为右侧的常量。

请注意，右侧的结果是一个常量，而不是一个 ConstantExpression 对象。当然，我们在必要的时候，也可以重新构造一个 ConstantExpression 对象，以便组成新的表达式树供后续分析。这个例子非常简单，而在实际的使用过程中遇到的表达式往往会复杂的多，他们可能包含“对象构造”、“下标访问”、“方法调用”、“属性读取”以及“?:”三目运算符等各种成员。它们的共同点，便是继承于 Expression 这一基类，并且最终都可以被计算为一个常量。

传统的表达式树的计算方式，是将其进行 Compile 为一个强类型的委托对象并加以执行，如下：

<span>Expression</span><<span>Func</span><<span>DateTime</span>>> expr = () => <span>DateTime</span>.Now.AddDays(1);
 
<span>Func</span><<span>DateTime</span>> tomorrow = expr.Compile();
<span>Console</span>.WriteLine(tomorrow());

如果是要计算一个类型不明确的表达式树，那么我们便需要要写一个通用的 Eval 方法，如下：

<span>static object </span>Eval(<span>Expression </span>expr)
{
   <span>LambdaExpression </span>lambda = <span>Expression</span>.Lambda(expr);
   <span>Delegate </span>func = lambda.Compile();
   <span>return </span>func.DynamicInvoke(<span>null</span>);
}
 
 
<span>static void </span>Main(<span>string</span>[] args)
{
   <span>Expression</span><<span>Func</span><<span>DateTime</span>>> expr = () => <span>DateTime</span>.Now.AddDays(1);
   <span>Console</span>.WriteLine(Eval(expr.Body));
}

简单说来，计算表达式树的通用方法会分三步走：

1. 将表达式树封装在一个 LambdaExpression 对象
2. 调用 LambdaExpression 的 Compile 方法动态生成一个委托对象
3. 使用 DynamicInvoke 方法调用该委托对象，获取其返回值

Compile 方法在内部使用了 Emit，而 DynamicInvoke 方法其本质与反射调用差不多，因此这种通用的表达式计算方法会带来相对较为可观的开销。尤其是在某些场景中，很容易出现大量表达式树的计算操作。例如，在开发 ASP.NET MVC 应用程序的视图时，“最佳实践”之一便是使用支持表达式树的辅助方法来构造链接，例如：

<span><</span><span>h2</span><span>></span>Article List<span></</span><span>h2</span><span>></span><span><%</span> <span>foreach </span>(<span>var </span>article <span>in </span>Model.Articles) { <span>%></span><span><</span><span>div</span><span>><br></br></span><span><%</span><span>= </span>Html.ActionLink<<span>ArticleController</span>>(c => c.Detail(article.ArticleID, 1), article.Title) <span>%><br></br></span>   
   <span><%</span> <span>for </span>(<span>var </span>page = 2; page <= article.MaxPage; page++) { <span>%></span>    <span><</span><span>small</span><span>><br></br></span><span><%</span><span>= </span>Html.ActionLink<<span>ArticleController</span>>(c => c.Detail(article.ArticleID, page), page.ToString()) <span>%><br></br></span>    <span></</span><span>small</span><span>></span><span><%</span> } <span>%></span>       
<span></</span><span>div</span><span>><br></br></span><span><%</span> } <span>%><br></br></span>

上述代码的作用，是在文章列表页上生成一系列指向文章详细页的链接。那么在上面的代码中，将会出现多少次表达式树的计算呢？

 
Html.ActionLink<<span>ArticleController</span>>(c => c.Detail(<span>article.ArticleID</span>, 1), article.Title)
 
Html.ActionLink<<span>ArticleController</span>>(c => c.Detail(<span>article.ArticleID</span>, <span>page</span>), article.Title)

可以看出，每篇文章将进行 (2 * MaxPage – 1) 次计算，对于一个拥有数十篇文章的列表页，计算次数很可能逾百次。此外，再加上页面上的各种其它元素，如分类列表，Tag Cloud 等等，每生成一张略为复杂的页面便会造成数百次的表达式树计算。从 Simone Chiaretta 的性能测试上来看，使用表达式树生成链接所花时间，大约为直接使用字符串的 30 倍。而根据我的本地测试结果，在一台 P4 2.0 GHz 的服务器上，单线程连续计算一万个简单的四则运算表达式便要花费超过 1 秒钟时间。这并非是一个可以忽略的性能开销，引入一种性能更好的表达式树计算方法势在必行。

减少 Compile 开销

如果您仔细比较 Compile 方法和 DynamicInvoke 方法的开销，您会发现前者占据了总耗时的 90-95%。这意味着传统计算方式的性能瓶颈在于其编译过程，这也是我们首要进行优化的目标。

减少编译次数，就意味着复用编译的结果，便是缓存。如果使用键 / 值对的缓存方式，其“值”自然是编译的结果，即是委托对象。那么“键”呢？我们很容易得知“键”肯定是一个表达式树。不过，有个问题必须思考，什么样的表达式树适合作为“键”？例如，“(5 + 2) * 3”这样的表达式是否可以直接作为“键”来使用？

很显然，当我们再次遇上“(5 + 2) * 3”这样的表达式，我们便可直接获得之前编译所得的委托对象。如果两个表达式树“全等”自然不在话下——在这里“全等”的定义是“两个表达式树的结构完全相同，其中各个常量的值也对应相等”。但是，这一点在实际使用过程中的价值并不大，因为它至少存在以下几点问题：

• 复用性不高。例如之前举出的例子，循环内部每次使用的 Article 对象或 page 参数的值都各不相同，每次计算表达式树时还是需要重新编译。
• 常量对应相等，并不是复用编译结果的必要条件。例如还是那个例子，其实只要 Article 对象的 ArticleID 属性相等即可复用，而我们表达式中的常量是一个完整的 article 对象。
• 由于需要判断两个对象是否相等，这要求每个需要参与计算的常量都必须正确实现 GetHashCode 和 Equals 方法。这是个代价很高的副作用。

既然是要缓存，则必须要考虑到缓存的命中率。“全等”的最大问题还是缓存的命中率过于低下，甚至会导致“还不如不缓存”的情况发生。不过，当我们仔细分析各种情况后会发现，其实我们可以有更好的方式来复用编译结果。

在一个项目中，只要不是动态构建表达式树，那么其中可能会出现的表达式树的“结构”肯定是有限的。还是拿之前的例子来说，我们虽然有许多次循环，但是需要计算的表达式只有两种不同的结构：article.ArticleID 和 page——而不同的计算，只是使用不同的“值”去填充常量的位置而已。同样道理，表达式“(5 + 2) * 3”与“(4 + 6) * 7”的结构完全相同。因此，我们可以在对一棵表达式树进行计算时，可以先将其“结构化”，如下图：

如果我们把表达式树的所有常量替换成同类型的参数（ParameterExpression）对象，那么系统中所有的表达式树都可以变为有限的几种结构。它们之间的区别，只是在替换的过程中提取到的“常量序列”不同。如果我们把包含参数的表达式树编译为委托对象，再把它缓存起来，不就可以多次复用了吗？因此，我们在计算表达式树时设法减少编译次数的解决方案可以分三步走：

1. 提取表达式树中所有常量
2. 从缓存中提取，或重新构造一个委托对象
3. 把常量作为参数执行委托对象

第 3 步自不必多说，下面我们来分析前两步的做法。操作表达式树的传统手段还是使用 ExpressionVisitor 。首先，我们为第 1 步工作实现一个 ConstantExtrator，如下：

<span>public class </span><span>ConstantExtractor </span>: <span>ExpressionVisitor<br></br></span>{
   <span>private </span><span>List</span><<span>object</span>> m_constants;
 
   <span>public </span><span>List</span><<span>object</span>> Extract(<span>Expression </span>exp)
   {
       <span>this</span>.m_constants = <span>new </span><span>List</span><<span>object</span>>();
       <span>this</span>.Visit(exp);
       <span>return this</span>.m_constants;
   }
 
   <span>protected override </span><span>Expression </span>VisitConstant(<span>ConstantExpression </span>c)
   {
       <span>this</span>.m_constants.Add(c.Value);
       <span>return </span>c;
   }
}       

由于我们的目标仅仅是常量，因此只需要重写 VisitConstant 方法，并收集其 Value 即可。接着，我们便要将一个 Expression 编译为一个 Delegate 对象，为此我们实现一个 WeakTypeDelegateGenerator，它自然也是一个 ExpressionVisitor 的子类：

<span>public class </span><span>WeakTypeDelegateGenerator </span>: <span>ExpressionVisitor<br></br></span>{
   <span>private </span><span>List</span><<span>ParameterExpression</span>> m_parameters;
 
   <span>public </span><span>Delegate </span>Generate(<span>Expression </span>exp)
   {
       <span>this</span>.m_parameters = <span>new </span><span>List</span><<span>ParameterExpression</span>>();
 
       <span>var </span>body = <span>this</span>.Visit(exp);
       <span>var </span>lambda = <span>Expression</span>.Lambda(body, <span>this</span>.m_parameters.ToArray());
       <span>return </span>lambda.Compile();
   }
 
   <span>protected override </span><span>Expression </span>VisitConstant(<span>ConstantExpression </span>c)
   {
       <span>var </span>p = <span>Expression</span>.Parameter(c.Type, <span>"p" </span>+ <span>this</span>.m_parameters.Count);
       <span>this</span>.m_parameters.Add(p);
       <span>return </span>p;
   }
}

WeakTypeDelegateGenerator 会将所有的 ConstantExpression 转变成同类型的 ParameterExpression，并进行收集。在访问了整个表达式树之后，将会把含有 ParameterExpression 的表达式使用 LambdaExpression 包装起来，再调用 Compile 方法进行编译，并将结果返回。

<span>public class </span><span>CacheEvaluator</span>: <span>IEvaluator<br></br></span>{
   <span>private static </span><span>IExpressionCache</span><<span>Delegate</span>> s_cache = <span>new </span><span>HashedListCache</span><<span>Delegate</span>>();
 
   <span>private </span><span>WeakTypeDelegateGenerator </span>m_delegateGenerator = <span>new </span><span>WeakTypeDelegateGenerator</span>();
   <span>private </span><span>ConstantExtractor </span>m_constantExtrator = <span>new </span><span>ConstantExtractor</span>();
 
   <span>private </span><span>IExpressionCache</span><<span>Delegate</span>> m_cache;
   <span>private </span><span>Func</span><<span>Expression</span>, <span>Delegate</span>> m_creatorDelegate;
 
   <span>public </span>CacheEvaluator()
       : <span>this</span>(s_cache)
   { }
 
   <span>public </span>CacheEvaluator(<span>IExpressionCache</span><<span>Delegate</span>> cache)
   {
       <span>this</span>.m_cache = cache;
       <span>this</span>.m_creatorDelegate = (key) => <span>this</span>.m_delegateGenerator.Generate(key);
   }
 
   <span>public object </span>Eval(<span>Expression </span>exp)
   {
       <span>if </span>(exp.NodeType == <span>ExpressionType</span>.Constant)
       {
           <span>return </span>((<span>ConstantExpression</span>)exp).Value;
       }
 
       <span>var </span>parameters = <span>this</span>.m_constantExtrator.Extract(exp);
       <span>var </span>func = <span>this</span>.m_cache.Get(exp, <span>this</span>.m_creatorDelegate);
       <span>return </span>func.DynamicInvoke(parameters.ToArray());
   }
}

IEvaluator 接口中定义了 Eval 方法，目的是把一个 Expression 对象“计算”为一个常量。CacheEvaluator 在实现 Eval 方法时利用了 ConstantExtrator 和 WeakTypeDelegateGenerator，分别用于提取常量及构造委托对象。在得到委托对象之后，我们会使用 DynamicInvoke 方法，将常量作为参数进行调用。值得注意的是，这样做的必要条件之一，便是传入的常量与委托的参数顺序必须一致。由于 ContstantExtrator 和 WeakTypeDelegateGenerator 都是基于相同的 ExpressionVisitor 实现，因此它们对于同一表达式树的节点遍历顺序也完全相同，我们对此可以完全放心。

这里自然还离不开最重要的组件：缓存容器。把表达式树作为缓存容器的“键”并不像普通对象那么容易，为此我在博客上连载了7 篇文章专门讨论了这个问题。这几篇文章提出了多种解决方案，并进行了对比和分析。最终，我们在这里选择了时间及空间上表现都比较优秀的HashedListCache。如果您有更好（或者在您的场景中表现更佳）的实现，您也可以在此替换默认的缓存容器。

下面我们来进行一个简单的试验，试验数据为运算符数量为1-3 的四则运算表达式各10 个，每个表达式分别计算1000 次的结果。

从上图中看来，传统方法对于每种长度的表达式计算耗时普遍超过了1.2 秒，而启用了缓存的计算方式则将时间控制在了100 毫秒左右。这无疑是一个显著的性能提升。

减少反射开销

在传统的调用方式中，编译操作占了95% 的开销。而现在经过对编译操作的优化，总开销变成了原来的10%，这意味着目前编译和执行的差不多各占50% 的时间。如果我们可以优化反射调用的过程，那么性能便可以得到进一步的提高。而且，目前的优化方式还有一个重要的问题，使我们不得不对其进行修改。您知道为什么在上面的示例中，只测试了最多3 个运算符的四则运算表达式吗？这是因为目前的做法无法支持更多的运算符——其实是参数的数量。

在一个四则运算表达式中，常数的个数总是比操作符要多一个。也就是说，3 个运算符的四则运算表达式，其中有4 个常数。在目前的解决方案中，所有的常数都会被替换为参数。这就是现在的问题：LambdaExpression.Compile(ParameterExpression[]) 方法只支持最多4 个参数。Compile 方法还有一个重载允许我们指定一个新的委托类型，它要求匹配源表达式的参数个数，参数类型以及其返回值类型。如果没有指定特定的委托类型，框架便会选用以下委托对象中的一种作为编译目标：

 <span>namespace </span>System
{
   <span>public delegate </span>TResult <span>Func</span><TResult>();
   <span>public delegate </span>TResult <span>Func</span><T, TResult>(T a);
   <span>public delegate </span>TResult <span>Func</span><T1, T2, TResult>(T1 a1, T2 a2);
   <span>public delegate </span>TResult <span>Func</span><T1, T2, T3, TResult>(T1 a1, T2 a2, T3 a3);
   <span>public delegate </span>TResult <span>Func</span><T1, T2, T3, T4, TResult>(T1 a1, T2 a2, T3 a3, T4 a4);
}

当参数数量超过 4 个的时候，Compile 方法便会抛出异常（在.NET 4.0 中则增加到 16 个）。如果要彻底解决这个问题，似乎唯一的方法便是根据需求，动态生成各种参数长度的委托类型。但是这么做大大增加了解决方案的复杂程度，对于性能优化也没有任何帮助。那么有没有什么办法，可以“统一”地处理任意签名的表达式呢？答案是肯定的，因为.NET 框架中的“反射”特性给了我们一个很好的参考：

<span>public class </span><span>MethodInfo<br></br></span>{
   <span>public object </span>Invoke(<span>object </span>instance, <span>object</span>[] parameters);
}

System.MethodInfo 类中的 Invoke 方法便支持任意的方法签名，因为它把一个签名转化成为“实例”，“参数列表”和“返回值”三个部分，而每个部分又都使用了 object 类型，因此可以存放任意类型的对象。由此，我们不妨也尝试着将不同表达式树归纳成同样的形式——即将其“标准化”。例如，表达式“(5 + 2) * 3”便可以转化为：

• 一个 List