谈表达式树的缓存（7）：五种缓存方式的总体分析及改进方案
終于到了這個(gè)系列的最后一篇文章了，這個(gè)系列的文章本是許多話題的基礎(chǔ)，卻拖了那么長(zhǎng)時(shí)間還沒有完結(jié)。這篇文章主要討論五種緩存方式各自的優(yōu)劣，以及他們的性能關(guān)鍵在什么地方，如果要進(jìn)行改進(jìn)又有什么可選方案。在這個(gè)問題上，老趙的思考可能會(huì)有遺漏，如果您有任何補(bǔ)充，也請(qǐng)不吝指出。
SimpleKeyCache
SimpleKeyCache是最直接的緩存方案：將表達(dá)式樹進(jìn)行完整編碼，將其轉(zhuǎn)化為一個(gè)獨(dú)一無二的字符串，然后作為Key存放到字典中。
從上一篇文章的實(shí)驗(yàn)來看，無論從耗時(shí)還是對(duì)GC造成的壓力上來說，SimpleKeyCache都是五種緩存方案中最差的。這一點(diǎn)倒很容易理解。因?yàn)樵?NET中拼接字符串是一種相對(duì)來說消耗巨大的操作。而將一個(gè)表達(dá)式樹進(jìn)行完整編碼，勢(shì)必要將它的各種信息都存放到字符串中。此時(shí)您就會(huì)發(fā)現(xiàn)，例如表達(dá)式樹的每個(gè)節(jié)點(diǎn)中的Type或MemberInfo信息會(huì)占用較大的空間，同時(shí)一顆表達(dá)式樹內(nèi)部的節(jié)點(diǎn)數(shù)量也可能比較可觀。兩者相輔相成，使得構(gòu)造一個(gè)字符串的代價(jià)就非常顯著了。
不過，SimpleKeyCache的優(yōu)點(diǎn)是什么呢？它的優(yōu)點(diǎn)就在于，它是五種緩存方案中唯一“能夠任意重現(xiàn)”的方案。也就是說，無論是在哪臺(tái)機(jī)器上，無論是哪一次啟動(dòng)，相同表達(dá)式樹的編碼結(jié)果是不變的。這也是實(shí)現(xiàn)“分布式存儲(chǔ)”的必要條件。之前文章中所提到的各種緩存方案都是在單個(gè)進(jìn)程內(nèi)實(shí)現(xiàn)的，因此只要在程序啟動(dòng)之后某些必要信息不會(huì)改變（例如某個(gè)對(duì)象的GetHashCode調(diào)用結(jié)果）即可。但是在分布是存儲(chǔ)環(huán)境中，會(huì)出現(xiàn)多個(gè)進(jìn)程多臺(tái)機(jī)器，如果它們產(chǎn)生的“鍵”無法保持不變，就無法使用相同表達(dá)式樹進(jìn)行可持續(xù)的通信了。
如果您真的在“分布式存儲(chǔ)”環(huán)境，或是其他需要“穩(wěn)定”特性的場(chǎng)景下（例如把一個(gè)表達(dá)式樹存入數(shù)據(jù)庫(kù)）使用表達(dá)式樹作為標(biāo)識(shí)符，那么您可以選擇的做法可能是優(yōu)化編碼方案了。例如，您可以把最終的字符串進(jìn)行分段，在header中寫入Type對(duì)象的信息并為它指定一個(gè)簡(jiǎn)短的表識(shí)符，這樣在字符串的body里就可以省去對(duì)大量數(shù)據(jù)的重復(fù)了。
不過，復(fù)雜的編碼也可能帶來額外的運(yùn)算開銷，對(duì)于性能不一定會(huì)帶來好處。因此，在得出確定的結(jié)論之前，一定要對(duì)實(shí)現(xiàn)進(jìn)行性能評(píng)測(cè)，不用感覺，而是用數(shù)據(jù)說話。
PrefixTreeCache
PrefixTreeCache使用了前綴樹作為存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。它將表達(dá)式樹轉(zhuǎn)化為一個(gè)單一序列，并使用Hashtable來作為前綴樹的單個(gè)節(jié)點(diǎn)，形成了一個(gè)粗略的表達(dá)式樹。
與SimpleKeyCache相比，PrefixTreeCache省去了大量的字符串拼接操作，節(jié)省了客觀的內(nèi)存占用，因此在GC上與前者相比有了非常明顯的改善。但是從結(jié)果上看，其性能并不如理論上來的高。老趙認(rèn)為這是因?yàn)槲覀兊膶?shí)現(xiàn)過于粗糙導(dǎo)致的。.NET類庫(kù)中的Hashtable性能應(yīng)該很難進(jìn)一步提到（因?yàn)閺拇a上看并沒有發(fā)現(xiàn)明顯需要優(yōu)化的地方——老趙是指只讀環(huán)境中），因此我們只能設(shè)法優(yōu)化自己的實(shí)現(xiàn)。
我們?cè)诒磉_(dá)式樹的每一層進(jìn)行查詢時(shí)會(huì)根據(jù)當(dāng)前節(jié)點(diǎn)的信息構(gòu)造一個(gè)匿名對(duì)象，并作為Key去Hashtable中進(jìn)行查詢。大量的匿名對(duì)象造成了GC壓力在五種緩存中僅僅落后SimpleKeyCache，而遙遙領(lǐng)先于其余三種方案。從編譯器自動(dòng)生成的類型上看，其GetHashCode方法和Equals方法的實(shí)現(xiàn)并沒有明顯的性能方面問題。因此我們優(yōu)化的著眼點(diǎn)，似乎只有在對(duì)Hashtable的查詢次數(shù)上了。
我們的實(shí)現(xiàn)中對(duì)于Hashtable的查詢次數(shù)的確太多。為了編程方便，每一個(gè)節(jié)點(diǎn)至少會(huì)對(duì)有兩次查詢，因此一個(gè)擁有20個(gè)節(jié)點(diǎn)的表達(dá)式（這個(gè)數(shù)量并不多）就會(huì)進(jìn)行40次以上的查詢。對(duì)于PrefixTreeCache，我們需要設(shè)法減少Hashtable的查詢次數(shù)。例如，我們其實(shí)完全可以把每一個(gè)節(jié)點(diǎn)的查詢次數(shù)簡(jiǎn)化到1次。更進(jìn)一步，我們可以設(shè)法把兩個(gè)節(jié)點(diǎn)并作一個(gè)進(jìn)行查詢，就好比傳統(tǒng)前綴樹實(shí)現(xiàn)中的優(yōu)化方式一樣。只是這樣做的話編程就變得非常復(fù)雜了。
PrefixTreeCache的實(shí)現(xiàn)似乎并沒有太大優(yōu)化的余地，而它的性能也不是太好。因此，老趙目前還想不到什么情況下適合使用這種存儲(chǔ)方案。
SortedListCache
SortedListCache使用排序列表進(jìn)行存儲(chǔ)，這樣每次查詢需要O(log(n))次比較，每次比較需要O(m)次操作，因此它也是五種存儲(chǔ)中時(shí)間復(fù)雜度唯一不是理論最優(yōu)值O(log(n) * m)的方案。
我們?yōu)镾ortedListCache實(shí)現(xiàn)了ExpressionComparer，可以比較兩個(gè)表達(dá)式樹的“大小”。ExpressionComparer的實(shí)現(xiàn)非常高效，沒有出現(xiàn)任何裝箱拆箱操作，因此它可以說沒有對(duì)GC造成任何壓力，這也是為什么它沒有造成任何回收操作的原因。雖然它在理論上的時(shí)間復(fù)雜度較高，為O(log(n) * m)，但是由于存儲(chǔ)中的表達(dá)式樹的數(shù)量不會(huì)不太多，其log(n)之后就變得非常小。因此從實(shí)際看來它的性能反而較SimpleKeyCache和PrefixTreeCache為好。性能較好的另一個(gè)原因在于ExpressionComparer不會(huì)形成一個(gè)完整遍歷，一旦它發(fā)現(xiàn)兩個(gè)表達(dá)式樹的任意節(jié)點(diǎn)有所不同，那么就會(huì)立即返回。
在上一篇文章的結(jié)尾，老趙提出了一個(gè)問題：“能否設(shè)計(jì)一種用例，讓SortedListCache的耗時(shí)超過PrefixTreeCache或SimpleKeyCache”。這個(gè)問題其實(shí)可以轉(zhuǎn)化為“能夠設(shè)計(jì)一種用例，讓ExpressionComparer耗時(shí)盡可能長(zhǎng)”，也就是說，我們其實(shí)是要設(shè)計(jì)一種方案，設(shè)法讓ExpressionComparer可以遍歷到盡可能后的位置，例如每次都遍歷到底。當(dāng)然，表達(dá)式樹長(zhǎng)度的增加，也會(huì)導(dǎo)致SimpleKeyCache和PrefixTreeCache的耗時(shí)增加，是否確定能夠滿足要求，事實(shí)上老趙也并不確定。
那么，我們又如何可以讓ExpressionComparer比較次數(shù)盡可能少呢？這就要視情況而定了。例如，ExpressionComparer現(xiàn)在其實(shí)使用深度優(yōu)先的方式進(jìn)行比較，那么如果換成廣度優(yōu)先的方式是否能更快發(fā)現(xiàn)兩個(gè)表達(dá)式樹的差別呢？
HashedListCache
HashedListCache是性能最好的，它的關(guān)鍵便是在于使用了散列值將不同的表達(dá)式首先分布到不同的SortedList對(duì)象中，然后再使用類似SortedListCache的方式，使用O(log(k) * m)的時(shí)間復(fù)雜度進(jìn)行查詢。
散列值的計(jì)算是HashedListCache性能的關(guān)鍵。計(jì)算散列值要求快，而且離散。“快”保證了可以在短時(shí)間內(nèi)計(jì)算出一個(gè)表達(dá)式樹。而“離散”保證了經(jīng)過分布之后，每個(gè)SortedList對(duì)象中的表達(dá)式樹數(shù)量k非常少。我們實(shí)現(xiàn)的ExpressionHasher基本上滿足了這個(gè)條件。首先在計(jì)算散列值時(shí)只消耗了O(m)的時(shí)間復(fù)雜度，并且由于使用了和ExpressionComparer相同的遍歷順序，使得“前綴相同”的兩顆表達(dá)式樹的“散列值”很有可能不同。這樣每個(gè)SortedList中，“前綴相同”的可能性就被降低了。自然ExpressionHasher便可更快地比較出兩顆表達(dá)式樹的區(qū)別來，節(jié)省了實(shí)現(xiàn)。
此外，ExpressionHasher的設(shè)計(jì)也消除了任何裝箱/拆箱，節(jié)省了時(shí)間消耗和GC壓力。如果要進(jìn)行優(yōu)化的話，可能就需要設(shè)計(jì)一個(gè)更好的散列值計(jì)算方式。例如，我們可以對(duì)表達(dá)式樹進(jìn)行“采樣”散列，而不是一個(gè)完整散列。但是“采樣”散列很可能會(huì)降低離散程度，因此任何的改進(jìn)還是要以性能評(píng)測(cè)為依據(jù)。
DictionaryCache
DictionaryCache為標(biāo)準(zhǔn)的字典存儲(chǔ)方式。我們構(gòu)造了一個(gè)CacheKey對(duì)象封裝了表達(dá)式樹，并且實(shí)現(xiàn)了Dictionary所需要的GetHashCode和Equals方法。
由于每次查詢需要構(gòu)造一個(gè)CacheKey對(duì)象，因此對(duì)于GC會(huì)有“些許”影響，但是這個(gè)影響其實(shí)可以忽略不計(jì)。DictionaryCache也是繼續(xù)散列值的存儲(chǔ)方式，它與HashedListCache的區(qū)別在于由散列值獲得某個(gè)“分區(qū)”之后，從分區(qū)中進(jìn)行查找的時(shí)間復(fù)雜度是O(k * m)而不是HashedListCache的O(log(k) * m)。因此，DictionaryCache比HashedListCache更加依賴一個(gè)優(yōu)秀的散列算法。如果一個(gè)散列算法的計(jì)算結(jié)果足夠分布，那么HashedListCache和DictionaryCache的性能可謂不分伯仲。這也是為什么在上一篇文章試驗(yàn)中，DictionaryCache和HashedListCache的性能幾乎相同。
DictionaryCache的優(yōu)勢(shì)并非在于它的實(shí)現(xiàn)有什么精妙之處，反而在于“平實(shí)”。由于DictionaryCache的實(shí)現(xiàn)使用了.NET中標(biāo)準(zhǔn)的鍵/值存儲(chǔ)方式，因此這種方法可以與其他組件輕易集成。例如我們的幾種“緩存方式”其實(shí)都有點(diǎn)“名不副實(shí)”，因?yàn)槿鄙倭恕斑^期”及“自動(dòng)清除”的機(jī)制。如果您要實(shí)現(xiàn)一個(gè)真正的“緩存”機(jī)制，可能就要借助現(xiàn)有的成熟的緩存容器了（實(shí)現(xiàn)一個(gè)成熟的，高效的，線程安全的緩存容器其實(shí)是一件非常困難的事情）。而有了DictionaryCache作為藍(lán)本之后，我們就可以輕松地使用CacheKey對(duì)象封裝表達(dá)式樹，并作為Key放入緩存容器了。
這就是“標(biāo)準(zhǔn)”的優(yōu)勢(shì)之一。
總結(jié)
五種緩存策略評(píng)價(jià)完了，您是否還有種意猶未盡的感覺？您現(xiàn)在是否可以根據(jù)不同場(chǎng)景選擇不同方案了呢？您是否對(duì)老趙的分析還有所補(bǔ)充？
請(qǐng)留下您的看法，老趙在此先謝過了。
?
完整代碼下載：http://code.msdn.microsoft.com/ExpressionCache
相關(guān)文章：
- 談表達(dá)式樹的緩存（1）：引言
- 談表達(dá)式樹的緩存（2）：由表達(dá)式樹生成字符串
- 談表達(dá)式樹的緩存（3）：使用前綴樹
- 談表達(dá)式樹的緩存（4）：使用二叉搜索樹（AVL樹）
- 談表達(dá)式樹的緩存（5）：引入散列值
- 談表達(dá)式樹的緩存（6）：五種緩存方式的性能比較
轉(zhuǎn)載于:https://www.cnblogs.com/JeffreyZhao/archive/2009/05/31/expression-cache-7-optimization.html
總結(jié)
以上是生活随笔為你收集整理的谈表达式树的缓存（7）：五种缓存方式的总体分析及改进方案的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 学习 SQL 语句 - Select(3
- 下一篇： SPQuery查询语法介绍