谈表达式树的缓存(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查询语法介绍