丨理解cpucache上4毫秒究竟值多少錢(qián)

在這段Java程序中，我們首先構(gòu)造了一個(gè)64×1024×1024大小的整型數(shù)組。在循環(huán)1里，我們遍歷整個(gè)數(shù)組，將數(shù)組中每一項(xiàng)的值變成了原來(lái)的3倍；在循環(huán)2里，我們每隔16個(gè)索引一個(gè)數(shù)組元素，將這一項(xiàng)的值變成了原來(lái)的3倍。按道理來(lái)說(shuō)，循環(huán)2只循環(huán)1中1/16的數(shù)組元素，只進(jìn)行了循環(huán)1中1/16的乘法計(jì)算，那循環(huán)2花費(fèi)的時(shí)間應(yīng)該是循環(huán)1的1/16左右。但是實(shí)際上，循環(huán)1在我的電腦上運(yùn)行需要50毫秒，循環(huán)2只需要46毫秒。這兩個(gè)循環(huán)花費(fèi)時(shí)間之差在15%之內(nèi)。為什么會(huì)有這15%的差異呢？這和我們今天要講的CPUCache有關(guān)。之前我們看到了內(nèi)存和硬盤(pán)之間存在的巨大性能差異。在CPU眼里，內(nèi)存也慢得不行。于是，聰明的工程師們就在CPU里面嵌入了CPUCache（高速緩存），來(lái)解決這一問(wèn)題。按照摩爾定律，CPU的速度每18個(gè)月便會(huì)翻一番，相當(dāng)于每年增長(zhǎng)60%。內(nèi)存的訪問(wèn)速度雖然也在不斷增長(zhǎng)，卻遠(yuǎn)沒(méi)有這么快，每年只增長(zhǎng)7%左右。而這兩個(gè)增長(zhǎng)速度的差異，使得CPU性能和內(nèi)存性能的差距不斷拉大。到今天來(lái)看，一次內(nèi)存的，大約需要120個(gè)CPUCycle，這也意味著，在今天，CPU和內(nèi)存的速度已經(jīng)有了120如果拿我們現(xiàn)實(shí)生活來(lái)打個(gè)比方的話，CPU的速度好比風(fēng)馳電掣的高鐵，每小時(shí)350公里，然而，它卻只能等著旁邊腿腳不太靈便的老太太，也就是內(nèi)存，以每小時(shí)3公里的速度緩慢步行。因?yàn)镃PU需要執(zhí)行的指令、需要的數(shù)據(jù)，都在這個(gè)速度不到自己1%的隨著時(shí)間變遷，CPU和內(nèi)存之間的性能差距越來(lái)為了彌補(bǔ)兩者之間的性能差異，我們能把CPU的性能提升用起來(lái)，而不是讓它在那兒空轉(zhuǎn)，我們?cè)诂F(xiàn)代CPU中引入了高速緩存。從CPUCache被加入到現(xiàn)有的CPU里開(kāi)始，內(nèi)存中的指令、數(shù)據(jù)，會(huì)被加載到L1-L3Cache中，而不是直接由CPU內(nèi)存去拿。在95%的情況下，CPU都只需要L1-L3Cache，從里面指令和數(shù)據(jù)，而無(wú)需內(nèi)存。要注意的是，這里我們說(shuō)的CPUCache或者L1/L3Cache，不是一個(gè)單純的、概念上的緩存（比如之前我們說(shuō)的拿內(nèi)存作為硬盤(pán)的緩存），而是指特定的由SRAM組成的物理。這里是一張 CPU的放大。這里面大片的長(zhǎng)方形，就是這個(gè)CPU使用20MBL3Cache現(xiàn)代CPU大量的空間已經(jīng)被SRAM圖中用紅色框出的部分就是CPUCache在這一講一開(kāi)始的程序里，運(yùn)行程序的時(shí)間主要花在了將對(duì)應(yīng)的數(shù)據(jù)從內(nèi)存中出來(lái)，加載到CPUCache里。CPU從內(nèi)存中數(shù)據(jù)到CPUCache的過(guò)程中，是一小塊一小塊來(lái)數(shù)據(jù)的，而不是按照單個(gè)數(shù)組元素來(lái)數(shù)據(jù)的。這樣一小塊一小塊的數(shù)據(jù)，在CPUCache里面，我們把它叫作CaeLie（緩存塊）。在我們?nèi)粘Ｊ褂玫腎n 服務(wù)器或者PC里，CacheLine的大小通常是64字節(jié)。而在上面的循環(huán)2里面，我們每隔16個(gè)整型數(shù)計(jì)算一次，16個(gè)整型數(shù)正好是64個(gè)字節(jié)。于是，循環(huán)1和循環(huán)2，需要把同樣數(shù)量的CacheLine數(shù)據(jù)從內(nèi)存中到CPUCache中，最知道了為什么需要CPUCache，接下來(lái)，我們就來(lái)看一看，CPU究竟是如何CPUCache的，以及CPUCache是如何組織數(shù)據(jù)，使得CPU可以找到自己想要的數(shù)據(jù)的。因?yàn)镃ache作為“緩存”的意思，在很多別的設(shè)備里面都會(huì)用到。為了避免你混淆，在表示抽象的“緩存“概念時(shí)，用中文的“緩存”；如果是CPUCache，我會(huì)用“高現(xiàn)代CPU進(jìn)行數(shù)據(jù)的時(shí)候，無(wú)論數(shù)據(jù)是否已經(jīng)在Cache中，CPU始終會(huì)首先訪問(wèn)Cache。只有當(dāng)CPU在Cache中找不到數(shù)據(jù)的時(shí)候，才會(huì)去內(nèi)存，并將到的數(shù)據(jù)寫(xiě)入Cache之中。當(dāng)時(shí)間局部性原理起作用后，這個(gè)最近剛剛被的數(shù)據(jù)，會(huì)很快再次被。而Cache的速度遠(yuǎn)遠(yuǎn)快于內(nèi)存，這樣，CPU花在等待內(nèi)存上的時(shí)間這樣的機(jī)制，和我們自己在開(kāi)發(fā)應(yīng)用系統(tǒng)的時(shí)候，“使用內(nèi)存作為硬盤(pán)的緩存”的邏輯是一樣的。在各類(lèi)基準(zhǔn)測(cè)試（Benark）和實(shí)際應(yīng)用場(chǎng)景中，CPUCache中率通常能達(dá)到95%以上。問(wèn)題來(lái)了，CPU如何知道要的內(nèi)存數(shù)據(jù)，在Cache的哪個(gè)位置呢？接下來(lái)，我從最基本的直接映射Cache（DirectMappedCache）說(shuō)起，帶你來(lái)看整個(gè)Cache的據(jù)結(jié)構(gòu)和邏輯在開(kāi)頭的3行小程序里我，CPU內(nèi)存數(shù)據(jù)，是一小塊一小塊數(shù)據(jù)來(lái)的。對(duì)于Cache采用的策略，就是確保任何一個(gè)內(nèi)存塊的地址，始終映射到一個(gè)固定的CPUCache地址（CacheLine）。而這個(gè)映射關(guān)系，通常用mod運(yùn)算（求余運(yùn)算）來(lái)實(shí)現(xiàn)。下面我舉比如說(shuō)，我們的主內(nèi)存被分成0～31號(hào)這樣32個(gè)塊。我們一共有8個(gè)緩存塊。用戶想要第21號(hào)內(nèi)存塊。如果21號(hào)內(nèi)存塊內(nèi)容在緩存塊中的話，它一定在5號(hào)緩存塊（21mod8=5）中。Cache采用mod的方式，把內(nèi)存塊映射到對(duì)應(yīng)的CPUCache實(shí)際計(jì)算中，有一個(gè)小小的技巧，通常我們會(huì)把緩存塊的數(shù)量設(shè)置成2的N方。這樣在計(jì)算取模的時(shí)候，可以直接取地址的低N位，也就是二進(jìn)制里面的后幾位。比如這里的8個(gè)緩存塊，就是2的3次方。那么，在對(duì)21取模的時(shí)候，可以對(duì)21的2進(jìn)制表示10101取地址的低三位，也就是101，對(duì)應(yīng)的5，就是對(duì)應(yīng)的緩存塊地址取Block地址的低位，就能得到對(duì)應(yīng)的CacheLine地址，除了21號(hào)內(nèi)存塊外，13號(hào)、5號(hào)等很多內(nèi)存塊的數(shù)據(jù)，都對(duì)應(yīng)著5號(hào)緩存塊中。既然如此，假如現(xiàn)在CPU想要21號(hào)內(nèi)存塊，在到5號(hào)緩存塊的時(shí)候，我們?cè)趺粗览锩娴臄?shù)據(jù)，究竟是不是21號(hào)對(duì)應(yīng)的數(shù)據(jù)呢？同樣，建議你借助現(xiàn)有知識(shí)，先自己思考一下，然后再看我下面的分析，這樣會(huì)印象比較深刻。這個(gè)時(shí)候，在對(duì)應(yīng)的緩存塊中，我們會(huì)一個(gè)組標(biāo)記（Tag）。這個(gè)組標(biāo)記會(huì)記錄，當(dāng)前緩存塊內(nèi)的數(shù)據(jù)對(duì)應(yīng)的內(nèi)存塊，而緩存塊本身的地址表示地址的低N位。就像上面的例子，21的低3位101，緩存塊本身的地址已經(jīng)涵蓋了對(duì)應(yīng)的信息、對(duì)應(yīng)的組標(biāo)記，我們只需要記錄21剩余的高2位的信息，也就是10就可以了。數(shù)據(jù)，另一個(gè)是有效位（validbit）。啥是有效位呢？它其實(shí)就是用來(lái)標(biāo)記，對(duì)應(yīng)的緩存塊中的數(shù)據(jù)是否是有效的，確保不是機(jī)器剛剛啟動(dòng)時(shí)候的空數(shù)據(jù)。如果有效位是0，無(wú)論其中的組標(biāo)記和CacheLine里的數(shù)據(jù)內(nèi)容是什么，CPU都不會(huì)管這些數(shù)據(jù)，而要直接內(nèi)CPU在數(shù)據(jù)的時(shí)候，并不是要一整個(gè)Block，而是一個(gè)他需要的整數(shù)。這樣的數(shù)據(jù)，我們叫作CPU里的一個(gè)字（Word）。具體是哪個(gè)字，就用這個(gè)字在整個(gè)Block里面的位置來(lái)決定。這個(gè)位置，我們叫作偏移量（Offset）總結(jié)一下，一個(gè)內(nèi)存的地址，最終包位代表的組標(biāo)記、低位代表的索引，以及在對(duì)應(yīng)的DataBlock中定位對(duì)應(yīng)字的位置偏移量。內(nèi)存地址到CacheLine的關(guān)而內(nèi)存地址對(duì)應(yīng)到Cache里的數(shù)據(jù)結(jié)構(gòu)，則多了一個(gè)有效位和對(duì)應(yīng)的數(shù)據(jù)，由“索引+有效位+組標(biāo)記+數(shù)據(jù)”組成。如果內(nèi)存中的數(shù)據(jù)已經(jīng)在CPUCache里了，那一個(gè)內(nèi)存地址的，就會(huì)經(jīng)歷這樣4個(gè)步驟：根據(jù)內(nèi)存地址的低位，計(jì)算在Cache中的索引判斷有效位，確認(rèn)Cache中的數(shù)據(jù)是有效的對(duì)比內(nèi)存地址的，和Cache中的組標(biāo)記，確認(rèn)Cache中的數(shù)據(jù)就是我們要訪問(wèn)的內(nèi)存數(shù)據(jù)，從CacheLine中到對(duì)應(yīng)的數(shù)據(jù)塊（DataBlock）；根據(jù)內(nèi)存地址的Offset位，從DataBlock中，希望到的字如果在2、3這兩個(gè)步驟中，CPU發(fā)現(xiàn)，Cache中的數(shù)據(jù)并不是要的內(nèi)存地址的數(shù)據(jù)，那CPU就會(huì)內(nèi)存，并把對(duì)應(yīng)的BlockData更新到CacheLine中，同時(shí)更新對(duì)好了，講到這里，相信你明白現(xiàn)代CPU，是如何通過(guò)直接映射Cae，來(lái)定位一個(gè)內(nèi)存訪問(wèn)地址在Cache中的位置了。其實(shí)，除了直接映射Cache之外，我們常見(jiàn)的緩存放置策略還有全相連Cache（FlyAssoaieCache）、組相連Cache（etAssoaieCache）。這幾種策略的數(shù)據(jù)結(jié)構(gòu)都是相似的，理解了最簡(jiǎn)單的直接映射Cache，其他的策略你很容易就能理解了。減少4毫秒，公司掙了剛才我花了很多篇幅，講了CPU和內(nèi)存之間的性能差異，以及我們?nèi)绾瓮ㄟ^(guò)CPUCache竟，一次內(nèi)存的，只不過(guò)需要100納秒而已。1秒鐘時(shí)間內(nèi)，足有1000萬(wàn)個(gè)100納2008年，一家叫作SpreadNetworks的通信公司花費(fèi)3億，做了一個(gè)光纜建設(shè)項(xiàng)目。目標(biāo)是建設(shè)一條從芝加哥到新澤西，總長(zhǎng)1331公里的光纜線路。建設(shè)這條線路的目的，其實(shí)是為了將兩地之間原有的網(wǎng)絡(luò)延時(shí)，從17毫秒降低到13毫秒。你可能會(huì)說(shuō)，僅僅縮短了4毫秒時(shí)間啊，卻花費(fèi)3個(gè)億，真的值嗎？為這4毫秒時(shí)間的，其實(shí)是一批高頻公司。它們以5年1400萬(wàn)的價(jià)格，使用這條線路。利用這短短的4毫秒的時(shí)間優(yōu)勢(shì)，這些公司通過(guò)高性能的計(jì)算機(jī)程序，在芝加哥和新澤西兩地的所進(jìn)行高頻，以獲得每年以10億計(jì)的利潤(rùn)。現(xiàn)在你還覺(jué)得這個(gè)不值得嗎？其實(shí)，只要350微秒的差異，就足夠高頻公司用來(lái)進(jìn)行無(wú)風(fēng)險(xiǎn)了。而350微秒，如果用來(lái)進(jìn)行100納秒一次的內(nèi)存，大約只夠進(jìn)行3500次。而引入CPUCache之很多時(shí)候，程序的性能瓶頸，來(lái)自使用DRAM芯片的內(nèi)存速度根據(jù)摩爾定律，自上世紀(jì)80年代以來(lái)，CPU和內(nèi)存的性能鴻溝越拉越大。于是，現(xiàn)代CPU的設(shè)計(jì)者們，直接在CPU中嵌入了使用更高性能的SRAM的Cache，來(lái)彌補(bǔ)這一性能差異。通過(guò)巧妙地將內(nèi)存地址，拆分成“索引+組標(biāo)記+偏移量”的方式，使得我們可以將很大的內(nèi)存地址，映射到很小的CPUCache地址里。而CPUCache帶來(lái)的毫秒乃至微秒級(jí)別的性能差異，又能帶來(lái)巨大的商業(yè)利益，十多年前的高頻行業(yè)就是最好的在搞清楚從內(nèi)存加載數(shù)據(jù)到Cache，以及從Cache里到想要的數(shù)據(jù)之后，我們又要面臨一個(gè)新的了。CPU不僅要讀數(shù)據(jù)，還需要寫(xiě)數(shù)據(jù)，我們不能只把數(shù)據(jù)寫(xiě)入到Cache里面就結(jié)束了。下一講，我們就來(lái)仔細(xì)講講，CPU要寫(xiě)入數(shù)據(jù)的時(shí)候，怎么既不犧牲性能，又能保證數(shù)據(jù)的一致性如果你學(xué)有余力，這里有兩篇文章推薦給如果想深入了解CPU和內(nèi)存之間的性能，你可以閱讀WhatEveryProgrammerShouldKnowAboutMemory?，F(xiàn)代CPU已經(jīng)很少使用直接映射Cache了，通常用的是組相連Cache（setassociativecache），想要了解組相連Cache，你可以閱讀《計(jì)算機(jī)