Hello World
Spiga

快速计算表达式树

2009-07-29 09:25 by 老赵, 8853 visits

前言

.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平台的能力,甚至改变了我们对于一些事物的使用方式。

表达式树的优势

详见文章完整内容(链接)。

表达式树的计算

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

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

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

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

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

static object Eval(Expression expr)
{
    LambdaExpression lambda = Expression.Lambda(expr);
    Delegate func = lambda.Compile();
    return func.DynamicInvoke(null);
}

static void Main(string[] args)
{
    Expression<Func<DateTime>> expr = () => DateTime.Now.AddDays(1);
    Console.WriteLine(Eval(expr.Body));
}

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

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

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

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

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

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

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

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

减少Compile开销

详见文章完整内容(链接)。

减少反射开销

详见文章完整内容(链接)。

最后我们进行一个简单试验,将运算符数量为1-20的四则运算表达式各10个,分别计算1000次。三种实现耗时对比如下(请关注Normal和Fast的对比):

perf test

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中文站,欢迎访问《快速计算表达式树》。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

48 条回复

  1. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2009-07-29 09:27:00

    Expression Tree ,刚好赶上在学习...

  2. 斯克迪亚
    *.*.*.*
    链接

    斯克迪亚 2009-07-29 09:32:00

    欢迎访问《快速计算表达式树》。这里链接错误

  3. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2009-07-29 09:37:00

    只能看看了,这个了解不深

  4. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2009-07-29 09:37:00

    老赵,“我的衣橱” 是基于Asp.net MVC框架做的么

  5. 老赵
    admin
    链接

    老赵 2009-07-29 09:40:00

    Leon Weng:老赵,“我的衣橱” 是基于Asp.net MVC框架做的么


    不是。

  6. 老赵
    admin
    链接

    老赵 2009-07-29 09:40:00

    斯克迪亚:欢迎访问《快速计算表达式树》。这里链接错误


    回应真快,其实我发布不久就改掉了,呵呵。

  7. IE6不好吗??[未注册用户]
    *.*.*.*
    链接

    IE6不好吗??[未注册用户] 2009-07-29 09:56:00

    看你的文章不容易啊,为了那几句话我决定改用FF来评论。

    IE6真是就这样受BS吗??

    我们网站统计用IE6访问的用户占70%。

  8. 老赵
    admin
    链接

    老赵 2009-07-29 10:16:00

    @IE6不好吗??
    嗯,在我封杀IE6之前,我的blog访问用户里25%是IE6。
    作为技术人员使用IE6,升个级还要积极歪歪的,我倒真觉得应该受BS。

    不过,对于你换个浏览器来访问得做法,我还是多谢你的支持,以及你对技术推动所做出的贡献。

  9. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-07-29 10:17:00

    老赵 我新学mvc 问点基础的


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

    循环
    Html.ActionLink<ArticleController>(c => c.Detail(article.ArticleID, page), article.Title)

    循环结束


    如果我不想(或者客户审批太麻烦而不能)引入fastlambda 是否可以把expression 提取到循环外 进行编译 , 如果可以该怎么做呢

  10. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-07-29 10:19:00

    是不是这样就可以了

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


    var exp1=(c => c.Detail(article.ArticleID, page));
    循环
    Html.ActionLink<ArticleController>(exp1, article.Title)

    循环结束

  11. 老赵
    admin
    链接

    老赵 2009-07-29 10:32:00

    @韦恩卑鄙
    既然是循环,循环中page是会变的咯,你怎么在外面先“预编译”啊。
    而且,其实表达式树是“数据”,实际使用时往往是用来解析的,不是用来“编译”的。
    比如你举的代码,就算可行,在每个ActionLink里还是会重新解析一遍,省下的只是构造表达式树所带来的一点点开销。

  12. 徐少侠
    *.*.*.*
    链接

    徐少侠 2009-07-29 10:37:00

    顶起

    老赵出手就是不凡啊

    这个东西要持续关注的

    貌似这么一搞以后可以在很多地方就直接用你的FastLambda项目来耍了?

    用了啥开源协议不?呵呵

  13. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-07-29 10:41:00

    我的代码太简单 我的意思是否可以不用缓存 在循环体外编译
    就算编译成delegate 传递进去应该也能节省一点吧

    "而且,其实表达式树是“数据”,实际使用时往往是用来解析的,不是用来“编译”的。" 这点我很认同拉。


  14. andy.wu
    *.*.*.*
    链接

    andy.wu 2009-07-29 10:42:00

    我的感觉,表达式树只是ms搞Linq的副产品,或者说,是因为Linq的需要,才设计了表达式树。

    对于“将逻辑保存下来”,实际上之前就有很多方式可以做到,比如codedom或vsa,或脚本引擎。相比这些技术,目前的表达式树有很多不足,在我看来的优势还是和Linq相关,那就是lambda(方便)和强类型。

    文章中提到,在.net 4中会进一步加强表达式树,可以表达语句了,这么说来,感觉上的方向,是想实现语法树了,最终变成用另一种形式,实现脚本引擎的功能了。

    不管如何,Linq的确是个好东西,Linq相关的也相当的有价值。

  15. 老赵
    admin
    链接

    老赵 2009-07-29 10:48:00

    @徐少侠
    嗯,我已经在很多地方使用到了。不是开源产品,但是也有协议:
    http://code.msdn.microsoft.com/FastLambda/Project/License.aspx
    简单说来,代码使用MS-PL,文字使用CC 3.0。

  16. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-07-29 10:49:00

    我的代码太简单 我的意思是否可以不用缓存 在循环体外编译
    就算编译成delegate 传递进去应该也能节省一点吧

    "而且,其实表达式树是“数据”,实际使用时往往是用来解析的,不是用来“编译”的。" 这点我很认同拉。

    但是如果瓶颈主要是在 lambda expression 那么我们是不是尽量减少lambda expression 在循环中立即解析的次数

    这样是否有意义呢

    我不觉得 在 var exp1=(lambda)
    之后 每个循环体内 都会重新解析(slambda)

  17. 老赵
    admin
    链接

    老赵 2009-07-29 11:00:00

    @韦恩卑鄙
    在这里,表达式树没有编译,也不需要编译成delegate啊,它完全是用来解析的。这里没有编译整棵树,在解析的时候是用if/else + 访问成员之类的。
    ActionLink方法的实现就是解析表达式树,为啥你“不觉得”每次都会解析呢?你可以读一下ActionLink方法的源代码。
    你这么做,节省的最多只是构造表达式树的一点点开销。而且,表达式树是immutable的,因此也没有办法“改变”循环变量。

  18. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-07-29 11:05:00

    恩 大概明白了~~ 3q

  19. 老赵
    admin
    链接

    老赵 2009-07-29 11:05:00

    @韦恩卑鄙
    表达式树只是一个表示方法,它的作用不是用来“执行”的。它可以编译成delegate,但是几乎不太会有拿到一棵树就编译的场景。
    有些所谓“优化”方式,什么预编译成delegate,也是有它的上下文的,不是通用的做法。

    当然,在表达式数解析过程中是会求值得,也就是把一颗树的一小部分拿出来,编译成delegate,求一个值。
    但是,没有办法避免这个编译,因为这是求值的唯一方法了。

  20. 老赵
    admin
    链接

    老赵 2009-07-29 11:13:00

    andy.wu:
    我的感觉,表达式树只是ms搞Linq的副产品,或者说,是因为Linq的需要,才设计了表达式树。

    对于“将逻辑保存下来”,实际上之前就有很多方式可以做到,比如codedom或vsa,或脚本引擎。相比这些技术,目前的表达式树有很多不足,在我看来的优势还是和Linq相关,那就是lambda(方便)和强类型。

    文章中提到,在.net 4中会进一步加强表达式树,可以表达语句了,这么说来,感觉上的方向,是想实现语法树了,最终变成用另一种形式,实现脚本引擎的功能了。

    不管如何,Linq的确是个好东西,Linq相关的也相当的有价值。


    我不认为表达式树是Linq的副产品,确切地说,是我不认为表达式数的优势需要由Linq才能得以发挥。反而我觉得,linq是表达式树的延伸,它利用了表达树的能力。表达式树自己本身已经是一个很强大,很有用的功能了。
    表达式树的关键在于,它可以通过lambda表达式在代码中直接构造,而且强类型等优势一应俱全。这不是codedom等能够比拟的。试想,你用codedom构造一段语句需要多少代码?
    .net 4虽然加强了表达式树,但是lambda表达式的直接构造没有跟上,也就是说你可以使用c => c.MyMethod()来构造一个expression,但是你没有办法用下面的做法构造一个statement。
    c =>
    {
    for (int i = 0; i < c.Count;i ++) Do(i);
    }

    简单的说,就是编译器的能力没有赶上框架的进步,呵呵。不过以后肯定就好了。
    顺便一提,这方面F#实现的很完整,所以非常强大。

  21. heguo
    *.*.*.*
    链接

    heguo 2009-07-29 11:28:00

    都用上c#4.0了?C#4.0能实现WCF和Linq的无缝接合编程吗?
    我希望:在客户端写了Linq to sql查询,自动或手动将此linq序列化(成表达式树)后传输到服务端,并由服务端解释此linq并调用sql语句,读取数据回传到客户端。
    请教能这样实现吗?

  22. 老赵
    admin
    链接

    老赵 2009-07-29 11:43:00

    @heguo
    手动序列化总归是可以的啊,现在就可以。

  23. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-07-29 11:44:00

    表达式树就是一个通用的AST(目前还不足以表达诸如C#的所有方法级抽象文法)。不过用于DLR诸多语言很好

  24. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-07-29 12:51:00

    Html.ActionLink<T>这个方法死活没找到,是不是我的ASP.NET MVC版本不对?

  25. 老赵
    admin
    链接

    老赵 2009-07-29 13:50:00

    @Ivony...
    在MvcFutures里。

  26. AlexLiu
    *.*.*.*
    链接

    AlexLiu 2009-07-29 15:57:00

    我只见过赵老师经常讨论这个问题。

  27. -brian-
    *.*.*.*
    链接

    -brian- 2009-07-29 16:52:00

    @asem
    无语,弄着评论上别的博客乱上,就冲这一点...

  28. 老赵
    admin
    链接

    老赵 2009-07-29 16:53:00

    无关讨论堆太高了,看来看去,还是决定删除了。

  29. -brian-
    *.*.*.*
    链接

    -brian- 2009-07-29 16:53:00

    乱发

  30. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2009-07-29 16:59:00

    还是不太理解表达式树。
    它是干什么用的呢?难道就是为了封装一段逻辑?

  31. 老赵
    admin
    链接

    老赵 2009-07-29 17:03:00

    @麒麟.NET
    把代码当作数据来处理,infoq的文章里写过了。

  32. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2009-07-29 17:16:00

    它通常用于解决哪些方面的问题呢?

  33. 老赵
    admin
    链接

    老赵 2009-07-29 17:17:00

    @麒麟.NET
    infoq的文章里都写了,看文章吧。

  34. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-07-29 19:03:00

    如此高质量的文章。

  35. ie6+ is garbage[未注册用户…
    *.*.*.*
    链接

    ie6+ is garbage[未注册用户] 2009-07-29 23:27:00

    一不小心又点到你的文章
    然后又跳到了那个广告页
    火了:
    简直跟中国电信的行为一样龌龊...
    忍无可忍
    立马写了个过滤
    世界又清净了...
    #exd#*JeffreyZhao*#.*(?:window\.|\s|^)location(?:\s*=|\.assign|\.replace).+JeffreyZhao.+

  36. 老赵
    admin
    链接

    老赵 2009-07-30 09:54:00

    @ie6+ is garbage
    谢谢,欢迎您推广“抵制老赵”行动。

  37. 萧乐
    *.*.*.*
    链接

    萧乐 2009-07-30 10:17:00

    估计老赵你在相当长的一段时间里都要与人在IE6问题杠上了。
    我建议你就在那个拒绝访问页面里写上一段东西免得同一个回答复制那么多次。
    注意DRY!DRY!

  38. 老赵
    admin
    链接

    老赵 2009-07-30 13:04:00

    @asem
    欢迎交流,用短消息或Email吧,不要博客上留言了。

  39. asem[未注册用户]
    *.*.*.*
    链接

    asem[未注册用户] 2009-07-30 13:10:00

    好的,有空我也注册一个,更好地向你请教,话说MS最新推出了所谓“软件事务内存”,好像很不错,请有空多一些相关介绍

  40. 老赵
    admin
    链接

    老赵 2009-07-30 13:13:00

    @asem
    有机会我看看吧,应该还是和我搞得东西蛮接近的。

  41. Jeffrey Fuck[未注册用户]
    *.*.*.*
    链接

    Jeffrey Fuck[未注册用户] 2009-07-30 15:03:00

    楼主就一傻逼

  42. 老赵
    admin
    链接

    老赵 2009-07-30 17:55:00

    @Jeffrey Fuck
    hi,Mr.Fuck.
    我们的first name相同耶。

  43. chenleinet
    *.*.*.*
    链接

    chenleinet 2009-08-01 21:03:00

    Jeffrey Fuck,是妒忌呢,还是天外的高手呢

  44. bulong xu
    116.228.247.*
    链接

    bulong xu 2010-11-02 17:14:21

    其实根本不需要平台引什么“逻辑即数据”的概念。SharpDevelop的源码中早就可以挖掘出这些功能(不同的是MS的命名空间用System打头)。

    其根本是:巴克斯-努尔范式(ABNF)。你就可以使用Yacc(c/c++),或COCO/R(c#,java,vb...),或antli(java)解析任何语言(可以自创)。

    根本不必烦恼.NET3.5还不够完善,需要等待下个版本。

  45. 老赵
    admin
    链接

    老赵 2010-11-02 17:53:07

    @bulong xu

    你说的都对,这些都不是新东西了,每个IDE里也都实现过一遍,但好不好用还是很重要的。

  46. Rocky
    183.12.198.*
    链接

    Rocky 2014-10-30 22:19:37

    请问你的FastLambda我可以用在我的开源ORM中吗?

  47. 老赵
    admin
    链接

    老赵 2014-10-31 00:05:04

    @Rocky

    随意,不需要注明出处,哈哈。

  48. Rocky
    183.54.93.*
    链接

    Rocky 2014-11-01 14:48:49

    呵呵,3颗药~~那我就择时开放咯,不会注明出处,只会写上你的大名^_^

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我