快速計算表達式樹

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。優勢主要有三個方面：

強類型

語義清晰

簡化API開發

強類型

就以.NET平台中著名的Mock架構NMock來說，以下代碼将會構造一個ICalculator接口的Mock對象，并指定Sum方法的一組輸入和輸出：

var mocks = new Mockery();

var mockCalculator = mock.NewMock<ICalculator>();

Expect.Once.On(mockCalculator)

    .Method("Sum")

    .With(1, 2)

    .Will(Return.Value(3));與此形成鮮明對比的是，作為.NET平台中Mock架構的後起之秀Moq，充分利用了C# 3.0中的Lambda表達式特性改進了API。是以，以上代碼在Moq中的近似實作便是：

Mock<ICalculator> mock = new Mock<ICalculator>();

mock.Setup(c => c.Sum(1, 2)).Returns(3);

NMock使用字元串表示“方法”，使用object數組來表示參數，用object存放傳回值的做法，在Moq中完全變成了強類型的“方法調用”。這樣，開發人員在使用Moq使便可以獲得更好的工具支援，如編輯器的智能提示（Intellisense），編譯器的靜态檢查等等。

語義清晰

從文法上看，使用Lambda表達式建構表達式樹，與進階語言中最常見的語句并無二緻。由于表達式樹在使用時僅僅是“建構”，而不會真正“執行”，是以API設計者可以把它作為一種天然的DSL。例如在Moq中，我們便可以靈活指定ICalculator對象的行為：

Mock<ICalculator> mock = new Mock<ICalculator>();

mock.Setup(c => c.Divide(It.IsAny<int>(), 0)).Throws(new DivideByZeroException());

mock.Setup(c => c.Divide(0, It.Is<int>(i => i != 0))).Returns(0);

簡化API開發

嚴格說來，“清晰語義”與API設計有關，并非表達式樹的專利。例如同為.NET平台下的Mock架構，RhinoMocks使用如下的文法來定義Mock對象的行為：

var mocks = new MockRepository();

var mockCalculator = mocks.CreateMock<ICalculator>();

Expect.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為一個強類型的委托對象并加以執行，如下：

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));

}

簡單說來，計算表達式樹的通用方法會分三步走：

将表達式樹封裝在一個LambdaExpression對象

調用LambdaExpression的Compile方法動态生成一個委托對象

使用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開銷

如果您仔細比較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）對象，那麼系統中所有的表達式樹都可以變為有限的幾種結構。它們之間的差別，隻是在替換的過程中提取到的“常量序列”不同。如果我們把包含參數的表達式樹編譯為委托對象，再把它緩存起來，不就可以多次複用了嗎？是以，我們在計算表達式樹時設法減少編譯次數的解決方案可以分三步走：

提取表達式樹中所有常量

從緩存中提取，或重新構造一個委托對象

把常量作為參數執行委托對象

第3步自不必多說，下面我們來分析前兩步的做法。操作表達式樹的傳統手段還是使用ExpressionVisitor。首先，我們為第1步工作實作一個ConstantExtrator，如下：

public class ConstantExtractor : ExpressionVisitor{

    private List<object> m_constants;

    public List<object> Extract(Expression exp)

    {

        this.m_constants = new List<object>();

        this.Visit(exp);

        return this.m_constants;

    }

    protected override Expression VisitConstant(ConstantExpression c)

    {

        this.m_constants.Add(c.Value);

        return c;

    }

}      

由于我們的目标僅僅是常量，是以隻需要重寫VisitConstant方法，并收集其Value即可。接着，我們便要将一個Expression編譯為一個Delegate對象，為此我們實作一個WeakTypeDelegateGenerator，它自然也是一個ExpressionVisitor的子類：

public class WeakTypeDelegateGenerator : ExpressionVisitor{

    private List<ParameterExpression> m_parameters;

    public Delegate Generate(Expression exp)

    {

        this.m_parameters = new List<ParameterExpression>();

        var body = this.Visit(exp);

        var lambda = Expression.Lambda(body, this.m_parameters.ToArray());

        return lambda.Compile();

    }

    protected override Expression VisitConstant(ConstantExpression c)

    {

        var p = Expression.Parameter(c.Type, "p" + this.m_parameters.Count);

        this.m_parameters.Add(p);

        return p;

    }

}WeakTypeDelegateGenerator會将所有的ConstantExpression轉變成同類型的ParameterExpression，并進行收集。在通路了整個表達式樹之後，将會把含有ParameterExpression的表達式使用LambdaExpression包裝起來，再調用Compile方法進行編譯，并将結果傳回。

public class CacheEvaluator: IEvaluator{

    private static IExpressionCache<Delegate> s_cache = new HashedListCache<Delegate>();

    private WeakTypeDelegateGenerator m_delegateGenerator = new WeakTypeDelegateGenerator();

    private ConstantExtractor m_constantExtrator = new ConstantExtractor();

    private IExpressionCache<Delegate> m_cache;

    private Func<Expression, Delegate> m_creatorDelegate;

    public CacheEvaluator()

        : this(s_cache)

    { }

    public CacheEvaluator(IExpressionCache<Delegate> cache)

    {

        this.m_cache = cache;

        this.m_creatorDelegate = (key) => this.m_delegateGenerator.Generate(key);

    }

    public object Eval(Expression exp)

    {

        if (exp.NodeType == ExpressionType.Constant)

        {

            return ((ConstantExpression)exp).Value;

        }

        var parameters = this.m_constantExtrator.Extract(exp);

        var func = this.m_cache.Get(exp, this.m_creatorDelegate);

        return 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方法還有一個重載允許我們指定一個新的委托類型，它要求比對源表達式的參數個數，參數類型以及其傳回值類型。如果沒有指定特定的委托類型，架構便會選用以下委托對象中的一種作為編譯目标：

namespace System

{

    public delegate TResult Func<TResult>();

    public delegate TResult Func<T, TResult>(T a);

    public delegate TResult Func<T1, T2, TResult>(T1 a1, T2 a2);

    public delegate TResult Func<T1, T2, T3, TResult>(T1 a1, T2 a2, T3 a3);

    public delegate TResult Func<T1, T2, T3, T4, TResult>(T1 a1, T2 a2, T3 a3, T4 a4);

}當參數數量超過4個的時候，Compile方法便會抛出異常（在.NET 4.0中則增加到16個）。如果要徹底解決這個問題，似乎唯一的方法便是根據需求，動态生成各種參數長度的委托類型。但是這麼做大大增加了解決方案的複雜程度，對于性能優化也沒有任何幫助。那麼有沒有什麼辦法，可以“統一”地處理任意簽名的表達式呢？答案是肯定的，因為.NET架構中的“反射”特性給了我們一個很好的參考：

public class MethodInfo{

    public object Invoke(object instance, object[] parameters);

}

System.MethodInfo類中的Invoke方法便支援任意的方法簽名，因為它把一個簽名轉化成為“執行個體”，“參數清單”和“傳回值”三個部分，而每個部分又都使用了object類型，是以可以存放任意類型的對象。由此，我們不妨也嘗試着将不同表達式樹歸納成同樣的形式——即将其“标準化”。例如，表達式“(5 + 2) * 3”便可以轉化為：

一個List<object>對象，其中存放5，2，3三個元素。

一個新的表達式：(object)((int)p[0] + (int)p[1]) * (int)p[2]。其中p為List<object>類型的參數對象。

這樣的“标準化”操作主要有兩個好處：

隻要是結構相同的表達式樹，在“标準化”後得到的新表達式樹則完全相同，這大大提高了緩存命中率。

無論何種表達式樹，标準化後的結果永遠隻有一個List<object>參數，由此避免了常數過多而導緻的編譯失敗。

我們得到了标準化之後的表達式樹，便可以将其編譯為相同的委托對象。這部分功能由DelegateGenerator類進行：

public class DelegateGenerator : ExpressionVisitor{

    private static readonly MethodInfo s_indexerInfo = typeof(List<object>).GetMethod("get_Item");

    private int m_parameterCount;

    private ParameterExpression m_parametersExpression;

    public Func<List<object>, object> Generate(Expression exp)

    {

        this.m_parameterCount = 0;

        this.m_parametersExpression =

            Expression.Parameter(typeof(List<object>), "parameters");

        var body = this.Visit(exp); // normalize        if (body.Type != typeof(object))

        {

            body = Expression.Convert(body, typeof(object));

        }

        var lambda = Expression.Lambda<Func<List<object>, object>>(body, this.m_parametersExpression);

        return lambda.Compile();

    }

    protected override Expression VisitConstant(ConstantExpression c)

    {

        Expression exp = Expression.Call(

            this.m_parametersExpression,

            s_indexerInfo,

            Expression.Constant(this.m_parameterCount++));

        return c.Type == typeof(object) ? exp : Expression.Convert(exp, c.Type);

    }

}與WeakTypeDelegateGenerator一樣，DelegateGenerator也是拿ConstantExpression開刀。隻不過後者并不是直接将其替換為建立的ParameterExpression，而是轉化為對List<object>類型參數的元素下标通路（get_Item）——必要時再配合一次類型轉換。Visit的過程也就是一次标準化的過程，最終得到的表達式樹會被編譯為一個接受List<object>作為參數，并傳回object類型的委托對象。至于提取将表達式樹的常量提取為List<object>類型的參數清單，已經由之前的ConstantExtractor實作了，我們直接使用即可。

将DelegateGenerator、ConstantExtractor及ExpressionCache三者加以組合，便可得出計算表達式樹的新元件FastEvaluator：

public class FastEvaluator : IEvaluator{

    private static IExpressionCache<Func<List<object>, object>> s_cache =

        new HashedListCache<Func<List<object>, object>>();

    private DelegateGenerator m_delegateGenerator = new DelegateGenerator();

    private ConstantExtractor m_constantExtrator = new ConstantExtractor();

    private IExpressionCache<Func<List<object>, object>> m_cache;

    private Func<Expression, Func<List<object>, object>> m_creatorDelegate;

    public FastEvaluator()

        : this(s_cache)

    { }

    public FastEvaluator(IExpressionCache<Func<List<object>, object>> cache)

    {

        this.m_cache = cache;

        this.m_creatorDelegate = (key) => this.m_delegateGenerator.Generate(key);

    }

    public object Eval(Expression exp)

    {

        if (exp.NodeType == ExpressionType.Constant)

        {

            return ((ConstantExpression)exp).Value;

        }

        var parameters = this.m_constantExtrator.Extract(exp);

        var func = this.m_cache.Get(exp, this.m_creatorDelegate);

        return 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進行表達式樹的局部計算

轉載于:https://www.cnblogs.com/ph00/archive/2010/05/14/1735454.html