.NET 3.5中新增的表達式樹（Expression Tree）特性，第一次在.NET平臺中引入了“邏輯即數據”的概念，它是LINQ to Everything在技術實現上的重要基石之一。對表達式樹進行計算，是處理表達式樹時中最常見的工作了。根據我的本地測試結果，在一臺P4 2.0 GHz的服務器上，單線程連續計算一萬個簡單的四則運算表達式便要花費超過1秒鐘時間。這并非是一個可以忽略的性能開銷，引入一種性能更好的表達式樹計算方法勢在必行。

前言

.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的對比）：

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中文站，歡迎訪問《快速計算表達式樹》。