2020 Google开发者大会重磅开幕 了解详情

快速计算表达式树

2009 年 7 月 27 日

前言

.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对象,其中存放 5,2,3 三个元素。
  • 一个新的表达式:(object)((int)p[0] + (int)p[1]) * (int)p[2]。其中 p 为 List类型的参数对象。

    这样的“标准化”操作主要有两个好处:

    • 只要是结构相同的表达式树,在“标准化”后得到的新表达式树则完全相同,这大大提高了缓存命中率。
    • 无论何种表达式树,标准化后的结果永远只有一个 List参数,由此避免了常数过多而导致的编译失败。

      我们得到了标准化之后的表达式树,便可以将其编译为相同的委托对象。这部分功能由 DelegateGenerator 类进行:

      复制代码
      <span>public class </span><span>DelegateGenerator </span>: <span>ExpressionVisitor<br></br></span>{
      <span>private static readonly </span><span>MethodInfo </span>s_indexerInfo = <span>typeof</span>(<span>List</span><<span>object</span>>).GetMethod(<span>"get_Item"</span>);
      <span>private int </span>m_parameterCount;
      <span>private </span><span>ParameterExpression </span>m_parametersExpression;
      <span>public </span><span>Func</span><<span>List</span><<span>object</span>>, <span>object</span>> Generate(<span>Expression </span>exp)
      {
      <span>this</span>.m_parameterCount = 0;
      <span>this</span>.m_parametersExpression =
      <span>Expression</span>.Parameter(<span>typeof</span>(<span>List</span><<span>object</span>>), <span>"parameters"</span>);
      <span>var </span>body = <span>this</span>.Visit(exp); <span>// normalize<br></br></span><span>if </span>(body.Type != <span>typeof</span>(<span>object</span>))
      {
      body = <span>Expression</span>.Convert(body, <span>typeof</span>(<span>object</span>));
      }
      <span>var </span>lambda = <span>Expression</span>.Lambda<<span>Func</span><<span>List</span><<span>object</span>>, <span>object</span>>>(body, <span>this</span>.m_parametersExpression);
      <span>return </span>lambda.Compile();
      }
      <span>protected override </span><span>Expression </span>VisitConstant(<span>ConstantExpression </span>c)
      {
      <span>Expression </span>exp = <span>Expression</span>.Call(
      <span>this</span>.m_parametersExpression,
      s_indexerInfo,
      <span>Expression</span>.Constant(<span>this</span>.m_parameterCount++));
      <span>return </span>c.Type == <span>typeof</span>(<span>object</span>) ? exp : <span>Expression</span>.Convert(exp, c.Type);
      }
      }

      与 WeakTypeDelegateGenerator 一样,DelegateGenerator 也是拿 ConstantExpression 开刀。只不过后者并不是直接将其替换为新建的 ParameterExpression,而是转化为对 List类型参数的元素下标访问(get_Item)——必要时再配合一次类型转换。Visit 的过程也就是一次标准化的过程,最终得到的表达式树会被编译为一个接受 List作为参数,并返回 object 类型的委托对象。至于提取将表达式树的常量提取为 List类型的参数列表,已经由之前的 ConstantExtractor 实现了,我们直接使用即可。

      将 DelegateGenerator、ConstantExtractor 及 ExpressionCache 三者加以组合,便可得出计算表达式树的新组件 FastEvaluator:

      复制代码
      <span>public class </span><span>FastEvaluator </span>: <span>IEvaluator<br></br></span>{
      <span>private static </span><span>IExpressionCache</span><<span>Func</span><<span>List</span><<span>object</span>>, <span>object</span>>> s_cache =
      <span>new </span><span>HashedListCache</span><<span>Func</span><<span>List</span><<span>object</span>>, <span>object</span>>>();
      <span>private </span><span>DelegateGenerator </span>m_delegateGenerator = <span>new </span><span>DelegateGenerator</span>();
      <span>private </span><span>ConstantExtractor </span>m_constantExtrator = <span>new </span><span>ConstantExtractor</span>();
      <span>private </span><span>IExpressionCache</span><<span>Func</span><<span>List</span><<span>object</span>>, <span>object</span>>> m_cache;
      <span>private </span><span>Func</span><<span>Expression</span>, <span>Func</span><<span>List</span><<span>object</span>>, <span>object</span>>> m_creatorDelegate;
      <span>public </span>FastEvaluator()
      : <span>this</span>(s_cache)
      { }
      <span>public </span>FastEvaluator(<span>IExpressionCache</span><<span>Func</span><<span>List</span><<span>object</span>>, <span>object</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(parameters);
      }
      }

      我们再进行一次简单的实验,将运算符数量为 1-20 的四则运算表达式各 10 个,分别计算 1000 次。三种实现耗时对比如下:

      FastEvaluator 的主要开销在于从 ExpressionCache 中提取数据,它随着表达式的长度线性增加。拥有 n 个运算符的四则运算表达式树,其常量节点的数量为 n + 1,因此总结节点数量为 2n + 1。根据我的个人经验,项目中所计算的表达式树的节点数量一般都在 10 个以内。如图所示,在这个数据范围内,FastEvaluator 的计算耗时仅为传统方法的 1/20,并且随着节点数量的减少,两者差距进一步增大。此外,由于节省了反射调用的开销,即使在 CacheEvaluator 可以正常工作的范围内(1-3 个运算符),FastEvaluator 相对前者也有明显的性能提升。

      总结

      表达式树拥有语义清晰,强类型等诸多优势,可以预见,越来越多的项目会采取这种方式来改进自己的 API。在这种情况下,表达式树的计算对于程序性能的影响也会越来越大。本文提出了一种表达式树计算操作的优化方式,将不同表达式树“标准化”为几种有限的结构,并复用其编译结果。由于减少了编译操作和反射操作的次数,表达式计算所需开销大大降低。

      本文所有代码都公布于 MSDN Code Gallary 中的 FastLambda 项目中,您可以根据需要随意修改使用。此外,FastLambda 项目中还包含了可以将表达式树的多个常量部分进行简化的组件(如将 5 + 2 + 3 * 4 * x 简化为 7 + 12 * x),这对于处理原本就包含 ParameterExpression 的表达式树非常有用(如编写 LINQ Provider 时)。如果您对此感兴趣,可以关注项目中的 PartialEvaluator 和 FastPartialEvaluator 类,它们的区别在于前者利用 Evaluator,而后者利用 FastEvaluator 进行表达式树的局部计算。


      给 InfoQ 中文站投稿或者参与内容翻译工作,请邮件至 editors@cn.infoq.com 。也欢迎大家加入到 InfoQ 中文站用户讨论组中与我们的编辑和其他读者朋友交流。

2009 年 7 月 27 日 01:54 8611
用户头像

发布了 157 篇内容, 共 43.0 次阅读, 收获喜欢 2 次。

关注

评论

发布
暂无评论
发现更多内容

能走出来的,都不叫困境

zkback

区块链系列教程之:比特币的钱包与交易

程序那些事

比特币 区块链 智能合约 钱包 交易

ArrayList哪种循环效率更好你真的清楚吗

java金融

Java 后端 ArrayList 循环效率 方式

运营系统架构文档

师哥

ARTS - Week Five

shepherd

JavaScript algorithm

[安利] 可能会让你爱上书写的工具组合!

猴哥一一 cium

Typora markdown markdown编辑器 玩转写作平台

由一次管理后台定时推送功能引发的对 RabbitMQ 延迟队列的思考 (二)

LSJ

Java RabbitMQ 延迟队列 优先级队列

【Golang runtime学习笔记-启动过程分析】

卓丁

golang 初始化 runtime 汇编 go汇编

从拼多多突破阿里和京东两大巨头绞杀,市值破千亿美金来看职业价值链

非著名程序员

程序员 程序人生 职业规划 程序员成长 职业成长

架构师训练营-week01 学习总结

GunShotPanda

游戏夜读 | 最常见的两种类型

game1night

移动终端智能卡与安全计算环境研究

石君

安全芯片 移动终端 终端安全

Week3 命题作业

星河寒水

极客大学架构师训练营

如何做好职场印象管理?

石云升

职场 印象管理 职场形象

在项目中随手把haseMap改成了currenHaseMap差点被公司给开除了

java金融

Java 后端 BigDecimal金额 Arrays.asList

antdesign table 设置默认选中行且不可编辑

张张张小烦

架构师训练营 Week 03 关于反应式Web框架Flower

Wancho

2020年6月19日 服务器性能剖析

瑞克与莫迪

Java世界的“烂”包管理

阿喜伯

maven Git Submodule

区块链的未来,公链回归

CECBC区块链专委会

区块链技术 联盟链 公链 底层技术

依赖倒置-好莱坞原则

yupi

优化工程师逻辑视角下的微信“拍一拍”功能

Earth_Polarbear

人工智能 微信 系统工程 优化逻辑

如何让企业的IT数据运维更有“烟火气”?

BonreeAPM

数据挖掘 机器学习 数据中台 运维 大屏可视化

系统设计(4)-请设计一个线程安全的HashMap

王传义

系统设计

行业观察丨区块链如何与工业互联网深度融合

CECBC区块链专委会

区块链技术 工业互联网 分布式存储

三流程序员大晚上不睡觉,竟然在做这件事

Janenesome

写作平台 碎碎念

把主机放在家里

centos Homework

终于有人把 java代理 讲清楚了,万字详解!

java金融

Java jdk 后端 动态代理 cglib

低代码平台,我看好宜搭

飞哥

低代码

“技术是用的,不是喊的”区块链标准为电商引入“诚信管家”

CECBC区块链专委会

区块链技术 溯源 电商 防篡改 诚信管家

Kafka面试题:基础27问,必须都会的呀!

Java小咖秀

大数据 kafka 分布式 队列 延时消息

微服务治理平台化探索

微服务治理平台化探索

快速计算表达式树-InfoQ