老趙點滴 - 追求編程之美先做人，再做技術人員，最后做程序員。打造國內(nèi)最好的.NET技術博客。

談表達式樹的緩存（7）：五種緩存方式的總體分析及改進方案

2009-05-31 22:47 Jeffrey Zhao 閱讀(23182) 評論(12) 收藏舉報

終于到了這個系列的最后一篇文章了，這個系列的文章本是許多話題的基礎，卻拖了那么長時間還沒有完結。這篇文章主要討論五種緩存方式各自的優(yōu)劣，以及他們的性能關鍵在什么地方，如果要進行改進又有什么可選方案。在這個問題上，老趙的思考可能會有遺漏，如果您有任何補充，也請不吝指出。

SimpleKeyCache

SimpleKeyCache是最直接的緩存方案：將表達式樹進行完整編碼，將其轉化為一個獨一無二的字符串，然后作為Key存放到字典中。

從上一篇文章的實驗來看，無論從耗時還是對GC造成的壓力上來說，SimpleKeyCache都是五種緩存方案中最差的。這一點倒很容易理解。因為在.NET中拼接字符串是一種相對來說消耗巨大的操作。而將一個表達式樹進行完整編碼，勢必要將它的各種信息都存放到字符串中。此時您就會發(fā)現(xiàn)，例如表達式樹的每個節(jié)點中的Type或MemberInfo信息會占用較大的空間，同時一顆表達式樹內(nèi)部的節(jié)點數(shù)量也可能比較可觀。兩者相輔相成，使得構造一個字符串的代價就非常顯著了。

不過，SimpleKeyCache的優(yōu)點是什么呢？它的優(yōu)點就在于，它是五種緩存方案中唯一“能夠任意重現(xiàn)”的方案。也就是說，無論是在哪臺機器上，無論是哪一次啟動，相同表達式樹的編碼結果是不變的。這也是實現(xiàn)“分布式存儲”的必要條件。之前文章中所提到的各種緩存方案都是在單個進程內(nèi)實現(xiàn)的，因此只要在程序啟動之后某些必要信息不會改變（例如某個對象的GetHashCode調(diào)用結果）即可。但是在分布是存儲環(huán)境中，會出現(xiàn)多個進程多臺機器，如果它們產(chǎn)生的“鍵”無法保持不變，就無法使用相同表達式樹進行可持續(xù)的通信了。

如果您真的在“分布式存儲”環(huán)境，或是其他需要“穩(wěn)定”特性的場景下（例如把一個表達式樹存入數(shù)據(jù)庫）使用表達式樹作為標識符，那么您可以選擇的做法可能是優(yōu)化編碼方案了。例如，您可以把最終的字符串進行分段，在header中寫入Type對象的信息并為它指定一個簡短的表識符，這樣在字符串的body里就可以省去對大量數(shù)據(jù)的重復了。

不過，復雜的編碼也可能帶來額外的運算開銷，對于性能不一定會帶來好處。因此，在得出確定的結論之前，一定要對實現(xiàn)進行性能評測，不用感覺，而是用數(shù)據(jù)說話。

PrefixTreeCache

PrefixTreeCache使用了前綴樹作為存儲數(shù)據(jù)結構。它將表達式樹轉化為一個單一序列，并使用Hashtable來作為前綴樹的單個節(jié)點，形成了一個粗略的表達式樹。

與SimpleKeyCache相比，PrefixTreeCache省去了大量的字符串拼接操作，節(jié)省了客觀的內(nèi)存占用，因此在GC上與前者相比有了非常明顯的改善。但是從結果上看，其性能并不如理論上來的高。老趙認為這是因為我們的實現(xiàn)過于粗糙導致的。.NET類庫中的Hashtable性能應該很難進一步提到（因為從代碼上看并沒有發(fā)現(xiàn)明顯需要優(yōu)化的地方——老趙是指只讀環(huán)境中），因此我們只能設法優(yōu)化自己的實現(xiàn)。

我們在表達式樹的每一層進行查詢時會根據(jù)當前節(jié)點的信息構造一個匿名對象，并作為Key去Hashtable中進行查詢。大量的匿名對象造成了GC壓力在五種緩存中僅僅落后SimpleKeyCache，而遙遙領先于其余三種方案。從編譯器自動生成的類型上看，其GetHashCode方法和Equals方法的實現(xiàn)并沒有明顯的性能方面問題。因此我們優(yōu)化的著眼點，似乎只有在對Hashtable的查詢次數(shù)上了。

我們的實現(xiàn)中對于Hashtable的查詢次數(shù)的確太多。為了編程方便，每一個節(jié)點至少會對有兩次查詢，因此一個擁有20個節(jié)點的表達式（這個數(shù)量并不多）就會進行40次以上的查詢。對于PrefixTreeCache，我們需要設法減少Hashtable的查詢次數(shù)。例如，我們其實完全可以把每一個節(jié)點的查詢次數(shù)簡化到1次。更進一步，我們可以設法把兩個節(jié)點并作一個進行查詢，就好比傳統(tǒng)前綴樹實現(xiàn)中的優(yōu)化方式一樣。只是這樣做的話編程就變得非常復雜了。

PrefixTreeCache的實現(xiàn)似乎并沒有太大優(yōu)化的余地，而它的性能也不是太好。因此，老趙目前還想不到什么情況下適合使用這種存儲方案。

SortedListCache

SortedListCache使用排序列表進行存儲，這樣每次查詢需要O(log(n))次比較，每次比較需要O(m)次操作，因此它也是五種存儲中時間復雜度唯一不是理論最優(yōu)值O(log(n) * m)的方案。

我們?yōu)镾ortedListCache實現(xiàn)了ExpressionComparer，可以比較兩個表達式樹的“大小”。ExpressionComparer的實現(xiàn)非常高效，沒有出現(xiàn)任何裝箱拆箱操作，因此它可以說沒有對GC造成任何壓力，這也是為什么它沒有造成任何回收操作的原因。雖然它在理論上的時間復雜度較高，為O(log(n) * m)，但是由于存儲中的表達式樹的數(shù)量不會不太多，其log(n)之后就變得非常小。因此從實際看來它的性能反而較SimpleKeyCache和PrefixTreeCache為好。性能較好的另一個原因在于ExpressionComparer不會形成一個完整遍歷，一旦它發(fā)現(xiàn)兩個表達式樹的任意節(jié)點有所不同，那么就會立即返回。

在上一篇文章的結尾，老趙提出了一個問題：“能否設計一種用例，讓SortedListCache的耗時超過PrefixTreeCache或SimpleKeyCache”。這個問題其實可以轉化為“能夠設計一種用例，讓ExpressionComparer耗時盡可能長”，也就是說，我們其實是要設計一種方案，設法讓ExpressionComparer可以遍歷到盡可能后的位置，例如每次都遍歷到底。當然，表達式樹長度的增加，也會導致SimpleKeyCache和PrefixTreeCache的耗時增加，是否確定能夠滿足要求，事實上老趙也并不確定。

那么，我們又如何可以讓ExpressionComparer比較次數(shù)盡可能少呢？這就要視情況而定了。例如，ExpressionComparer現(xiàn)在其實使用深度優(yōu)先的方式進行比較，那么如果換成廣度優(yōu)先的方式是否能更快發(fā)現(xiàn)兩個表達式樹的差別呢？

HashedListCache

HashedListCache是性能最好的，它的關鍵便是在于使用了散列值將不同的表達式首先分布到不同的SortedList對象中，然后再使用類似SortedListCache的方式，使用O(log(k) * m)的時間復雜度進行查詢。

散列值的計算是HashedListCache性能的關鍵。計算散列值要求快，而且離散。“快”保證了可以在短時間內(nèi)計算出一個表達式樹。而“離散”保證了經(jīng)過分布之后，每個SortedList對象中的表達式樹數(shù)量k非常少。我們實現(xiàn)的ExpressionHasher基本上滿足了這個條件。首先在計算散列值時只消耗了O(m)的時間復雜度，并且由于使用了和ExpressionComparer相同的遍歷順序，使得“前綴相同”的兩顆表達式樹的“散列值”很有可能不同。這樣每個SortedList中，“前綴相同”的可能性就被降低了。自然ExpressionHasher便可更快地比較出兩顆表達式樹的區(qū)別來，節(jié)省了實現(xiàn)。

此外，ExpressionHasher的設計也消除了任何裝箱/拆箱，節(jié)省了時間消耗和GC壓力。如果要進行優(yōu)化的話，可能就需要設計一個更好的散列值計算方式。例如，我們可以對表達式樹進行“采樣”散列，而不是一個完整散列。但是“采樣”散列很可能會降低離散程度，因此任何的改進還是要以性能評測為依據(jù)。

DictionaryCache

DictionaryCache為標準的字典存儲方式。我們構造了一個CacheKey對象封裝了表達式樹，并且實現(xiàn)了Dictionary所需要的GetHashCode和Equals方法。

由于每次查詢需要構造一個CacheKey對象，因此對于GC會有“些許”影響，但是這個影響其實可以忽略不計。DictionaryCache也是繼續(xù)散列值的存儲方式，它與HashedListCache的區(qū)別在于由散列值獲得某個“分區(qū)”之后，從分區(qū)中進行查找的時間復雜度是O(k * m)而不是HashedListCache的O(log(k) * m)。因此，DictionaryCache比HashedListCache更加依賴一個優(yōu)秀的散列算法。如果一個散列算法的計算結果足夠分布，那么HashedListCache和DictionaryCache的性能可謂不分伯仲。這也是為什么在上一篇文章試驗中，DictionaryCache和HashedListCache的性能幾乎相同。

DictionaryCache的優(yōu)勢并非在于它的實現(xiàn)有什么精妙之處，反而在于“平實”。由于DictionaryCache的實現(xiàn)使用了.NET中標準的鍵/值存儲方式，因此這種方法可以與其他組件輕易集成。例如我們的幾種“緩存方式”其實都有點“名不副實”，因為缺少了“過期”及“自動清除”的機制。如果您要實現(xiàn)一個真正的“緩存”機制，可能就要借助現(xiàn)有的成熟的緩存容器了（實現(xiàn)一個成熟的，高效的，線程安全的緩存容器其實是一件非常困難的事情）。而有了DictionaryCache作為藍本之后，我們就可以輕松地使用CacheKey對象封裝表達式樹，并作為Key放入緩存容器了。

這就是“標準”的優(yōu)勢之一。