丨理解cpucache上4毫秒究竟值多少錢

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