3.3.2 Cache的性能測(cè)試

用于測(cè)試程序的數(shù)據(jù)可以模擬一個(gè)任意大小的工作集：包括讀、寫(xiě)訪問(wèn)，隨機(jī)、連續(xù)訪問(wèn)。在圖3.4中我們可以看到，程序?yàn)楣ぷ骷瘎?chuàng)建了一個(gè)與其大小和元素類型相同的數(shù)組：

struct l {struct l *n;long int pad[NPAD]; };

n字段將所有節(jié)點(diǎn)隨機(jī)得或者順序的加入到環(huán)形鏈表中，用指針從當(dāng)前節(jié)點(diǎn)進(jìn)入到下一個(gè)節(jié)點(diǎn)。pad字段用來(lái)存儲(chǔ)數(shù)據(jù)，其可以是任意大小。在一些測(cè)試程序中，pad字段是可以修改的, 在其他程序中，pad字段只可以進(jìn)行讀操作。

在性能測(cè)試中，我們談到工作集大小的問(wèn)題，工作集使用結(jié)構(gòu)體l定義的元素表示的。2^N?字節(jié)的工作集包含

個(gè)元素. 顯然sizeof(struct l) 的值取決于NPAD的大小。在32位系統(tǒng)上，NPAD=7意味著數(shù)組的每個(gè)元素的大小為32字節(jié)，在64位系統(tǒng)上，NPAD=7意味著數(shù)組的每個(gè)元素的大小為64字節(jié)。

單線程順序訪問(wèn)

最簡(jiǎn)單的情況就是遍歷鏈表中順序存儲(chǔ)的節(jié)點(diǎn)。無(wú)論是從前向后處理，還是從后向前，對(duì)于處理器來(lái)說(shuō)沒(méi)有什么區(qū)別。下面的測(cè)試中，我們需要得到處理鏈表中一個(gè)元素所需要的時(shí)間，以CPU時(shí)鐘周期最為計(jì)時(shí)單元。圖3.10顯示了測(cè)試結(jié)構(gòu)。除非有特殊說(shuō)明, 所有的測(cè)試都是在Pentium?4 64-bit 平臺(tái)上進(jìn)行的，因此結(jié)構(gòu)體l中NPAD=0，大小為8字節(jié)。

一開(kāi)始的兩個(gè)測(cè)試數(shù)據(jù)收到了噪音的污染。由于它們的工作負(fù)荷太小，無(wú)法過(guò)濾掉系統(tǒng)內(nèi)其它進(jìn)程對(duì)它們的影響。我們可以認(rèn)為它們都是4個(gè)周期以內(nèi)的。這樣一來(lái)，整個(gè)圖可以劃分為比較明顯的三個(gè)部分:

• 工作集小于2¹⁴字節(jié)的。
• 工作集從2¹⁵字節(jié)到2²⁰字節(jié)的。
• 工作集大于2²¹字節(jié)的。

這樣的結(jié)果很容易解釋——是因?yàn)樘幚砥饔?6KB的L1d和1MB的L2。而在這三個(gè)部分之間，并沒(méi)有非常銳利的邊緣，這是因?yàn)橄到y(tǒng)的其它部分也在使用緩存，我們的測(cè)試程序并不能獨(dú)占緩存的使用。尤其是L2，它是統(tǒng)一式的緩存，處理器的指令也會(huì)使用它(注: Intel使用的是包容式緩存)。

測(cè)試的實(shí)際耗時(shí)可能會(huì)出乎大家的意料。L1d的部分跟我們預(yù)想的差不多，在一臺(tái)P4上耗時(shí)為4個(gè)周期左右。但L2的結(jié)果則出乎意料。大家可能覺(jué)得需要14個(gè)周期以上，但實(shí)際只用了9個(gè)周期。這要?dú)w功于處理器先進(jìn)的處理邏輯，當(dāng)它使用連續(xù)的內(nèi)存區(qū)時(shí)，會(huì)?預(yù)先讀取下一條緩存線的數(shù)據(jù)。這樣一來(lái)，當(dāng)真正使用下一條線的時(shí)候，其實(shí)已經(jīng)早已讀完一半了，于是真正的等待耗時(shí)會(huì)比L2的訪問(wèn)時(shí)間少很多。

在工作集超過(guò)L2的大小之后，預(yù)取的效果更明顯了。前面我們說(shuō)過(guò)，主存的訪問(wèn)需要耗時(shí)200個(gè)周期以上。但在預(yù)取的幫助下，實(shí)際耗時(shí)保持在9個(gè)周期左右。200 vs 9，效果非常不錯(cuò)。

我們可以觀察到預(yù)取的行為，至少可以間接地觀察到。圖3.11中有4條線，它們表示處理不同大小結(jié)構(gòu)時(shí)的耗時(shí)情況。隨著結(jié)構(gòu)的變大，元素間的距離變大了。圖中4條線對(duì)應(yīng)的元素距離分別是0、56、120和248字節(jié)。

圖中最下面的這一條線來(lái)自前一個(gè)圖，但在這里更像是一條直線。其它三條線的耗時(shí)情況比較差。圖中這些線也有比較明顯的三個(gè)階段，同時(shí)，在小工作集的情況下也有比較大的錯(cuò)誤(請(qǐng)?jiān)俅魏雎赃@些錯(cuò)誤)。在只使用L1d的階段，這些線條基本重合。因?yàn)檫@時(shí)候還不需要預(yù)取，只需要訪問(wèn)L1d就行。

在L2階段，三條新加的線基本重合，而且耗時(shí)比老的那條線高很多，大約在28個(gè)周期左右，差不多就是L2的訪問(wèn)時(shí)間。這表明，從L2到L1d的預(yù)取并沒(méi)有生效。這是因?yàn)?#xff0c;對(duì)于最下面的線(NPAD=0)，由于結(jié)構(gòu)小，8次循環(huán)后才需要訪問(wèn)一條新緩存線，而上面三條線對(duì)應(yīng)的結(jié)構(gòu)比較大，拿相對(duì)最小的NPAD=7來(lái)說(shuō)，光是一次循環(huán)就需要訪問(wèn)一條新線，更不用說(shuō)更大的NPAD=15和31了。而預(yù)取邏輯是無(wú)法在每個(gè)周期裝載新線的，因此每次循環(huán)都需要從L2讀取，我們看到的就是從L2讀取的時(shí)延。

更有趣的是工作集超過(guò)L2容量后的階段。快看，4條線遠(yuǎn)遠(yuǎn)地拉開(kāi)了。元素的大小變成了主角，左右了性能。處理器應(yīng)能識(shí)別每一步(stride)的大小，不去為NPAD=15和31獲取那些實(shí)際并不需要的緩存線(參見(jiàn)6.3.1)。元素大小對(duì)預(yù)取的約束是根源于硬件預(yù)取的限制——它無(wú)法跨越頁(yè)邊界。如果允許預(yù)取器跨越頁(yè)邊界，而下一頁(yè)不存在或無(wú)效，那么OS還得去尋找它。這意味著，程序需要遭遇一次并非由它自己產(chǎn)生的頁(yè)錯(cuò)誤，這是完全不能接受的。在NPAD=7或者更大的時(shí)候，由于每個(gè)元素都至少需要一條緩存線，預(yù)取器已經(jīng)幫不上忙了，它沒(méi)有足夠的時(shí)間去從內(nèi)存裝載數(shù)據(jù)。 另一個(gè)導(dǎo)致慢下來(lái)的原因是TLB緩存的未命中。TLB是存儲(chǔ)虛實(shí)地址映射的緩存，參見(jiàn)第4節(jié)。為了保持快速，TLB只有很小的容量。如果有大量頁(yè)被反復(fù)訪問(wèn)，超出了TLB緩存容量，就會(huì)導(dǎo)致反復(fù)地進(jìn)行地址翻譯，這會(huì)耗費(fèi)大量時(shí)間。TLB查找的代價(jià)分?jǐn)偟剿性厣?#xff0c;如果元素越大，那么元素的數(shù)量越少，每個(gè)元素承擔(dān)的那一份就越多。

為了觀察TLB的性能，我們可以進(jìn)行另兩項(xiàng)測(cè)試。第一項(xiàng)：我們還是順序存儲(chǔ)列表中的元素，使NPAD=7，讓每個(gè)元素占滿整個(gè)cache line，第二項(xiàng)：我們將列表的每個(gè)元素存儲(chǔ)在一個(gè)單獨(dú)的頁(yè)上，忽略每個(gè)頁(yè)沒(méi)有使用的部分以用來(lái)計(jì)算工作集的大小。（這樣做可能不太一致，因?yàn)樵谇懊娴臏y(cè)試中，我計(jì)算了結(jié)構(gòu)體中每個(gè)元素沒(méi)有使用的部分，從而用來(lái)定義NPAD的大小，因此每個(gè)元素占滿了整個(gè)頁(yè)，這樣以來(lái)工作集的大小將會(huì)有所不同。但是這不是這項(xiàng)測(cè)試的重點(diǎn)，預(yù)取的低效率多少使其有點(diǎn)不同）。結(jié)果表明，第一項(xiàng)測(cè)試中，每次列表的迭代都需要一個(gè)新的cache line，而且每64個(gè)元素就需要一個(gè)新的頁(yè)。第二項(xiàng)測(cè)試中，每次迭代都會(huì)在一個(gè)新的頁(yè)中加載一個(gè)新的cache line。

結(jié)果見(jiàn)圖3.12。該測(cè)試與圖3.11是在同一臺(tái)機(jī)器上進(jìn)行的。基于可用RAM空間的有限性，測(cè)試設(shè)置容量空間大小為2的24次方字節(jié)，這就需要1GB的容量將對(duì)象放置在分頁(yè)上。圖3.12中下方的紅色曲線正好對(duì)應(yīng)了圖3.11中NPAD等于7的曲線。我們看到不同的步長(zhǎng)顯示了高速緩存L1d和L2的大小。第二條曲線看上去完全不同，其最重要的特點(diǎn)是當(dāng)工作容量到達(dá)2的13次方字節(jié)時(shí)開(kāi)始大幅度增長(zhǎng)。這就是TLB緩存溢出的時(shí)候。我們能計(jì)算出一個(gè)64字節(jié)大小的元素的TLB緩存有64個(gè)輸入。成本不會(huì)受頁(yè)面錯(cuò)誤影響，因?yàn)槌绦蜴i定了存儲(chǔ)器以防止內(nèi)存被換出。

可以看出，計(jì)算物理地址并把它存儲(chǔ)在TLB中所花費(fèi)的周期數(shù)量級(jí)是非常高的。圖3.12的表格顯示了一個(gè)極端的例子，但從中可以清楚的得到：TLB緩存效率降低的一個(gè)重要因素是大型NPAD值的減緩。由于物理地址必須在緩存行能被L2或主存讀取之前計(jì)算出來(lái)，地址轉(zhuǎn)換這個(gè)不利因素就增加了內(nèi)存訪問(wèn)時(shí)間。這一點(diǎn)部分解釋了為什么NPAD等于31時(shí)每個(gè)列表元素的總花費(fèi)比理論上的RAM訪問(wèn)時(shí)間要高。

通過(guò)查看鏈表元素被修改時(shí)測(cè)試數(shù)據(jù)的運(yùn)行情況，我們可以窺見(jiàn)一些更詳細(xì)的預(yù)取實(shí)現(xiàn)細(xì)節(jié)。圖3.13顯示了三條曲線。所有情況下元素寬度都為16個(gè)字節(jié)。第一條曲線“Follow”是熟悉的鏈表走線在這里作為基線。第二條曲線，標(biāo)記為“Inc”，僅僅在當(dāng)前元素進(jìn)入下一個(gè)前給其增加thepad[0]成員。第三條曲線，標(biāo)記為”Addnext0″， 取出下一個(gè)元素的thepad[0]鏈表元素并把它添加為當(dāng)前鏈表元素的thepad[0]成員。

在沒(méi)運(yùn)行時(shí)，大家可能會(huì)以為”Addnext0″更慢，因?yàn)樗龅氖虑楦唷跊](méi)進(jìn)到下個(gè)元素之前就需要裝載它的值。但實(shí)際的運(yùn)行結(jié)果令人驚訝——在某些小工作集下，”Addnext0″比”Inc”更快。這是為什么呢？原因在于，系統(tǒng)一般會(huì)對(duì)下一個(gè)元素進(jìn)行強(qiáng)制性預(yù)取。當(dāng)程序前進(jìn)到下個(gè)元素時(shí)，這個(gè)元素其實(shí)早已被預(yù)取在L1d里。因此，只要工作集比L2小，”Addnext0″的性能基本就能與”Follow”測(cè)試媲美。

但是，”Addnext0″比”Inc”更快離開(kāi)L2，這是因?yàn)樗枰獜闹鞔嫜b載更多的數(shù)據(jù)。而在工作集達(dá)到2?²¹字節(jié)時(shí)，”Addnext0″的耗時(shí)達(dá)到了28個(gè)周期，是同期”Follow”14周期的兩倍。這個(gè)兩倍也很好解釋。”Addnext0″和”Inc”涉及對(duì)內(nèi)存的修改，因此L2的逐出操作不能簡(jiǎn)單地把數(shù)據(jù)一扔了事，而必須將它們寫(xiě)入內(nèi)存。因此FSB的可用帶寬變成了一半，傳輸?shù)攘繑?shù)據(jù)的耗時(shí)也就變成了原來(lái)的兩倍。

決定順序式緩存處理性能的另一個(gè)重要因素是緩存容量。雖然這一點(diǎn)比較明顯，但還是值得一說(shuō)。圖3.14展示了128字節(jié)長(zhǎng)元素的測(cè)試結(jié)果(64位機(jī)，NPAD=15)。這次我們比較三臺(tái)不同計(jì)算機(jī)的曲線，兩臺(tái)P4，一臺(tái)Core 2。兩臺(tái)P4的區(qū)別是緩存容量不同，一臺(tái)是32k的L1d和1M的L2，一臺(tái)是16K的L1d、512k的L2和2M的L3。Core 2那臺(tái)則是32k的L1d和4M的L2。

圖中最有趣的地方，并不是Core 2如何大勝兩臺(tái)P4，而是工作集開(kāi)始增長(zhǎng)到連末級(jí)緩存也放不下、需要主存熱情參與之后的部分。

與我們預(yù)計(jì)的相似，最末級(jí)緩存越大，曲線停留在L2訪問(wèn)耗時(shí)區(qū)的時(shí)間越長(zhǎng)。在220字節(jié)的工作集時(shí)，第二臺(tái)P4(更老一些)比第一臺(tái)P4要快上一倍，這要完全歸功于更大的末級(jí)緩存。而Core 2拜它巨大的4M L2所賜，表現(xiàn)更為卓越。

對(duì)于隨機(jī)的工作負(fù)荷而言，可能沒(méi)有這么驚人的效果，但是，如果我們能將工作負(fù)荷進(jìn)行一些裁剪，讓它匹配末級(jí)緩存的容量，就完全可以得到非常大的性能提升。也是由于這個(gè)原因，有時(shí)候我們需要多花一些錢，買一個(gè)擁有更大緩存的處理器。

單線程隨機(jī)訪問(wèn)模式的測(cè)量

前面我們已經(jīng)看到，處理器能夠利用L1d到L2之間的預(yù)取消除訪問(wèn)主存、甚至是訪問(wèn)L2的時(shí)延。

但是，如果換成隨機(jī)訪問(wèn)或者不可預(yù)測(cè)的訪問(wèn)，情況就大不相同了。圖3.15比較了順序讀取與隨機(jī)讀取的耗時(shí)情況。

換成隨機(jī)之后，處理器無(wú)法再有效地預(yù)取數(shù)據(jù)，只有少數(shù)情況下靠運(yùn)氣剛好碰到先后訪問(wèn)的兩個(gè)元素挨在一起的情形。

圖3.15中有兩個(gè)需要關(guān)注的地方。首先，在大的工作集下需要非常多的周期。這臺(tái)機(jī)器訪問(wèn)主存的時(shí)間大約為200-300個(gè)周期，但圖中的耗時(shí)甚至超過(guò)了450個(gè)周期。我們前面已經(jīng)觀察到過(guò)類似現(xiàn)象(對(duì)比圖3.11)。這說(shuō)明，處理器的自動(dòng)預(yù)取在這里起到了反效果。

其次，代表隨機(jī)訪問(wèn)的曲線在各個(gè)階段不像順序訪問(wèn)那樣保持平坦，而是不斷攀升。為了解釋這個(gè)問(wèn)題，我們測(cè)量了程序在不同工作集下對(duì)L2的訪問(wèn)情況。結(jié)果如圖3.16和表3.2。

從圖中可以看出，當(dāng)工作集大小超過(guò)L2時(shí)，未命中率(L2未命中次數(shù)/L2訪問(wèn)次數(shù))開(kāi)始上升。整條曲線的走向與圖3.15有些相似: 先急速爬升，隨后緩緩下滑，最后再度爬升。它與耗時(shí)圖有緊密的關(guān)聯(lián)。L2未命中率會(huì)一直爬升到100%為止。只要工作集足夠大(并且內(nèi)存也足夠大)，就可以將緩存線位于L2內(nèi)或處于裝載過(guò)程中的可能性降到非常低。

緩存未命中率的攀升已經(jīng)可以解釋一部分的開(kāi)銷。除此以外，還有一個(gè)因素。觀察表3.2的L2/#Iter列，可以看到每個(gè)循環(huán)對(duì)L2的使用次數(shù)在增長(zhǎng)。由于工作集每次為上一次的兩倍，如果沒(méi)有緩存的話，內(nèi)存的訪問(wèn)次數(shù)也將是上一次的兩倍。在按順序訪問(wèn)時(shí)，由于緩存的幫助及完美的預(yù)見(jiàn)性，對(duì)L2使用的增長(zhǎng)比較平緩，完全取決于工作集的增長(zhǎng)速度。

而換成隨機(jī)訪問(wèn)后，單位耗時(shí)的增長(zhǎng)超過(guò)了工作集的增長(zhǎng)，根源是TLB未命中率的上升。圖3.17描繪的是NPAD=7時(shí)隨機(jī)訪問(wèn)的耗時(shí)情況。這一次，我們修改了隨機(jī)訪問(wèn)的方式。正常情況下是把整個(gè)列表作為一個(gè)塊進(jìn)行隨機(jī)(以∞表示)，而其它11條線則是在小一些的塊里進(jìn)行隨機(jī)。例如，標(biāo)簽為’60′的線表示以60頁(yè)(245760字節(jié))為單位進(jìn)行隨機(jī)。先遍歷完這個(gè)塊里的所有元素，再訪問(wèn)另一個(gè)塊。這樣一來(lái)，可以保證任意時(shí)刻使用的TLB條目數(shù)都是有限的。 NPAD=7對(duì)應(yīng)于64字節(jié)，正好等于緩存線的長(zhǎng)度。由于元素順序隨機(jī)，硬件預(yù)取不可能有任何效果，特別是在元素較多的情況下。這意味著，分塊隨機(jī)時(shí)的L2未命中率與整個(gè)列表隨機(jī)時(shí)的未命中率沒(méi)有本質(zhì)的差別。隨著塊的增大，曲線逐漸逼近整個(gè)列表隨機(jī)對(duì)應(yīng)的曲線。這說(shuō)明，在這個(gè)測(cè)試?yán)?#xff0c;性能受到TLB命中率的影響很大，如果我們能提高TLB命中率，就能大幅度地提升性能(在后面的一個(gè)例子里，性能提升了38%之多)。

總結(jié)

以上是生活随笔為你收集整理的产生线程安全的原因（2）（操作系统）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。