文末含分享內(nèi)容視頻鏈接

CPU Cache 基礎(chǔ)

最近看了一些 CPU 緩存相關(guān)的東西商乎，在這里做一下記錄啰脚。

Wiki 詞條：CPU cache - Wikipedia

一些基本概念

CPU 緩存出現(xiàn)的原因

1. 主存一般是 DRAM，CPU 速度比主存快很多倍鸳玩，沒(méi)有緩存存在時(shí) CPU 性能很大程度取決于讀取存儲(chǔ)數(shù)據(jù)的能力
2. 比 DRAM 快的存儲(chǔ)介質(zhì)是存在的，比如作為 CPU 高速緩存的 SRAM，只是很貴统倒，做很大的 SRAM 不經(jīng)濟(jì)
3. CPU 訪問(wèn)數(shù)據(jù)存在時(shí)間局部性和空間局部性，所以可以將 CPU 需要頻繁訪問(wèn)的少量熱數(shù)據(jù)放在速度快但很貴的 SRAM 中熏迹，既能大幅度改善 CPU 性能也不會(huì)讓成本提升太多

Cache Line

CPU 每次訪問(wèn)數(shù)據(jù)時(shí)先在緩存中查找一次檐薯，找不到則去主存找，訪問(wèn)完數(shù)據(jù)后會(huì)將數(shù)據(jù)存入緩存注暗，以備后用坛缕。這就產(chǎn)生了一個(gè)問(wèn)題，CPU 在訪問(wèn)某個(gè)地址的時(shí)候如何知道目標(biāo)數(shù)據(jù)是在緩存中存在捆昏？如何知道緩存的數(shù)據(jù)是否還有效沒(méi)被修改赚楚？不能為每個(gè)存入緩存的字節(jié)都打標(biāo)記，所以 CPU 緩存會(huì)劃分為固定大小的 Block 稱(chēng)為 Cache Line骗卜，作為存取數(shù)據(jù)的最小單位宠页。大小都為 2 的整數(shù)冪，比如 16 字節(jié)寇仓，256 字節(jié)等举户。這樣一個(gè) cache line 這一整塊內(nèi)存能通過(guò)一個(gè)標(biāo)記來(lái)記錄是否在內(nèi)存中，是否還有效遍烦，是否被修改等俭嘁。一次存取一塊數(shù)據(jù)也能充分利用總線帶寬以及 CPU 訪問(wèn)的空間局部性。

Cache Write Policy

Cache 不光是在讀取數(shù)據(jù)時(shí)有用服猪，目前大部分 CPU 在寫(xiě)入數(shù)據(jù)時(shí)也會(huì)先寫(xiě) Cache供填。一方面是因?yàn)樾麓鏀?shù)據(jù)很可能會(huì)被再次使用，新寫(xiě)數(shù)據(jù)先寫(xiě) Cache 能提高緩存命中率罢猪；另一方面 CPU 寫(xiě) Cache 速度更快近她，從而寫(xiě)完之后 CPU 可以去干別的事情，能提高性能膳帕。

CPU 寫(xiě)數(shù)據(jù)如果 Cache 命中了粘捎，則為了保持 Cache 和主存一致有兩種策略。如果 CPU 寫(xiě) Cache 每次都要更新主存，則稱(chēng)為 Write-Through 晌端，因?yàn)槊看螌?xiě) Cache 都伴隨主存更新所以性能差捅暴，實(shí)際使用的也少；寫(xiě) Cache 之后并不立即寫(xiě)主存而是等待一段時(shí)間能積累一些改動(dòng)后再更新主存的策略稱(chēng)為 Write-Back 咧纠，性能更好但為了保證寫(xiě)入的數(shù)據(jù)不丟使機(jī)制更加復(fù)雜蓬痒。采用 Write Back 方式被修改的內(nèi)存在從 Cache 移出(比如 Cache 不夠需要騰點(diǎn)空間)時(shí)，如果被修改的 Cache Line 還未寫(xiě)入主存需要在被移出 Cache 時(shí)更新主存漆羔，為了能分辨出哪些 Cache 是被修改過(guò)哪些沒(méi)有梧奢，又需要增加一個(gè)新的標(biāo)志位在 Cache Line 中去標(biāo)識(shí)。

CPU 寫(xiě)數(shù)據(jù)如果 Cache 未命中演痒，則只能直接去更新主存亲轨。但更新完主存后又有兩個(gè)選擇，將剛修改的數(shù)據(jù)存入 Cache 還是不存鸟顺。每次直接修改完主存都將主存被修改數(shù)據(jù)所在 Cache Line 存入 Cache 叫做 Write-Allocate 惦蚊。需要注意的是 Cache 存取的最小單位是 Cache Line。即使 CPU 只寫(xiě)一個(gè)字節(jié)讯嫂，也需要將被修改字節(jié)所在附近 Cache Line 大小的一塊內(nèi)存完整的讀入 Cache蹦锋。如果 CPU 寫(xiě)主存的數(shù)據(jù)超過(guò)一個(gè) Cache Line 大小，則不用再讀主存原來(lái)內(nèi)容欧芽，直接將新修改數(shù)據(jù)寫(xiě)入 Cache莉掂。相當(dāng)于完全覆蓋主存之前的數(shù)據(jù)。

寫(xiě)數(shù)據(jù)時(shí)除了需要考慮上述寫(xiě) Cache 策略外千扔，還需要保持各 CPU Cache 之間的一致性憎妙。比如一個(gè) CPU 要向某個(gè)內(nèi)存地址寫(xiě)數(shù)據(jù)，它需要通知其它所有 CPU 自己要寫(xiě)這個(gè)地址曲楚，如果其它 CPU 的 Cache Line 內(nèi)有緩存這個(gè)地址的話厘唾，需要將這個(gè) Cache Line 設(shè)置為 Invalidate。這樣寫(xiě)數(shù)據(jù)的那個(gè) CPU 就能安全的寫(xiě)數(shù)據(jù)了龙誊。下一次其它 CPU 要讀這個(gè)內(nèi)存地址時(shí)阅嘶，發(fā)現(xiàn)這個(gè) Cache Line 是 Invalidate 狀態(tài)，所以需要重新從內(nèi)存做加載载迄，即發(fā)生一次 Communication Miss。這種 Miss 不是 Cache 不夠大抡蛙，也不是 Cache 沖突护昧，而是因?yàn)槠渌?CPU 寫(xiě)同一個(gè) Cache Line 里數(shù)據(jù)導(dǎo)致了 Cache Miss。緩存一致性維護(hù)需要專(zhuān)門(mén)文章來(lái)寫(xiě)粗截。

SMP 和 NUMA

SMP 詞條：Symmetric multiprocessing - Wikipedia
NUMA 詞條：Non-uniform memory access - Wikipedia

簡(jiǎn)單說(shuō) SMP 就是一組 CPU 會(huì)通過(guò)一條總線共享機(jī)器內(nèi)的內(nèi)存惋耙、IO 等資源。因?yàn)樗袞|西都是共享的，所以擴(kuò)展性受限绽榛。

NUMA 則是將機(jī)器內(nèi) CPU 分為若干組湿酸，每個(gè)組內(nèi)都有獨(dú)立的內(nèi)存，IO資源灭美，組與組之間不相互共享內(nèi)存和 IO 等資源推溃，組之間通過(guò)專(zhuān)門(mén)的互聯(lián)模塊連接〗旄總體上擴(kuò)展性更強(qiáng)铁坎。

本文主要以 SMP 系統(tǒng)為例。CPU 以及 Cache硬萍，Memory 的關(guān)系如下：

image

CPU 緩存結(jié)構(gòu)

Direct Mapped Cache

最簡(jiǎn)單的緩存結(jié)構(gòu)就是 Direct Mapped 結(jié)構(gòu)围详。如下圖所示，每個(gè) Cache Line 由基本的 Valid 標(biāo)志位助赞，Tag 以及 Data 組成。當(dāng)訪問(wèn)一個(gè)內(nèi)存地址時(shí)哩都，根據(jù)內(nèi)存地址用 Hash 函數(shù)處理得到目標(biāo)地址所在 Cache Line 的 Index。根據(jù) Index 在 Cache 中找到對(duì)應(yīng) Cache Line 的 Data 數(shù)據(jù)婉徘，再?gòu)?Data 中根據(jù)內(nèi)存地址的偏移量讀取所需數(shù)據(jù)漠嵌。因?yàn)?Hash 函數(shù)是固定的儒鹿，所以每一個(gè)內(nèi)存地址在緩存上對(duì)應(yīng)固定的一塊 Cache Line约炎。所以是 Direct Mapped蟹瘾。

實(shí)際中為了性能 hash 函數(shù)都非常簡(jiǎn)單憾朴，就是從內(nèi)存地址讀取固定的幾個(gè) bit 數(shù)據(jù)作為 Cache Line 的 Index。拿下圖為例灸拍，Cache Line 大小為 4 字節(jié)鸡岗，一共 32 bit 是圖中的 Data 字段轩性。4 字節(jié)一共需要 2 bit 用于尋址，所以看到 32 bit 的地址中捌刮，0 1 兩個(gè) bit 作為 Offset。2 ~ 11 bit 作為 Cache Line 的 Index 一共 1024 個(gè)绅作，12 ~ 31 bit 作為 tag 用于區(qū)分映射到相同 Cache Line 的不同內(nèi)存 block蛾派。比如現(xiàn)在要讀取的地址是 0x1124200F洪乍，先從地址中取 2 ~ 11 bit 得到 0x03 表示目標(biāo) Cache Line 的 Index 是 3壳澳，之后從地址中讀 12 ~ 31 bit 作為 tag 是 0x11242巷波。拿這個(gè) Tag 跟 Index 為 3 的 Cache Line 的 Tag 做比較看是否一致抹镊，一致則表示當(dāng)前 Cache Line 中包含目標(biāo)地址垮耳，不一致則表示當(dāng)前 Cache Line 中沒(méi)有目標(biāo)地址终佛。因?yàn)?Cache 比內(nèi)存小很多，所以可能出現(xiàn)多個(gè)不在同一 Cache Line 的內(nèi)存地址被映射到同一個(gè) Cache Line 的情況乌询，所以需要用 Tag 做區(qū)分妹田。最后鬼佣，如果目標(biāo)地址確實(shí)在 Cache Line晶衷，且 Cache Line 的 Valid 為 true晌纫，則讀取 0x1124200F 地址的 0 ~ 1 bit锹漱，即找目標(biāo)數(shù)據(jù)在 Cache Line 內(nèi)的 Offset哥牍，得到 0x03 表示讀取當(dāng)前 Cache Line 中最后一個(gè)字節(jié)的數(shù)據(jù)喝检。

image

上圖的 Cache 是 1024 X 4 字節(jié) 一共 4 KB澡谭。但由于 Tag 和 Valid 的存在损俭，緩存實(shí)際占用的空間還會(huì)更大撩炊。

替換策略

因?yàn)?Direct Mapped 方式下拧咳，每個(gè)內(nèi)存在 Cache 中有固定的映射位置骆膝，所以新訪問(wèn)的數(shù)據(jù)要被存入 Cache 時(shí)阅签，根據(jù)數(shù)據(jù)所在內(nèi)存地址計(jì)算出 Index 發(fā)現(xiàn)該 Index 下已經(jīng)存在有效的 Cache Line政钟，需要將這個(gè)已存在的有效 Cache Line 從 Cache 中移出。如果采用 Write-Back 策略瓢宦，移出時(shí)需要判斷這個(gè)數(shù)據(jù)是否有被修改驮履，被修改了需要更新主存玫镐。

Write-Back 策略在前面有介紹恐似，即寫(xiě)數(shù)據(jù)時(shí)只寫(xiě)緩存就立即返回蹂喻，但標(biāo)記緩存為 Dirty捂寿，之后在某個(gè)時(shí)間再將 Dirty 的緩存寫(xiě)入主存秦陋。

Two-way Set Associative Cache

我們希望緩存越大越好驳概，越大的緩存經(jīng)常意味著更快的執(zhí)行速度顺又。對(duì)于 Direct Mapped Cache 結(jié)構(gòu)稚照，增大緩存就是增加 Index 數(shù)量果录，相當(dāng)于是對(duì)上面表進(jìn)行縱向擴(kuò)展弱恒。但除了縱向擴(kuò)展之外返弹，還可以橫向擴(kuò)展來(lái)增加 Cache 大小，這就是 Two-way Set Associative Cache悦施。

基本就是如下圖所示，圖上省略了 Tag 和 Valid 等標(biāo)識(shí)每個(gè) cell 就是一個(gè) Cache Line土陪，與 Direct Mapped Cache 不同點(diǎn)在于鬼雀，Two-way Set Associative Cache 里每個(gè) Index 對(duì)應(yīng)了兩個(gè) Cache Line源哩，每個(gè) Cache Line 有自己的 Tag励烦。同一個(gè) index 下的兩個(gè) cache line 組成 Set坛掠。在訪問(wèn)內(nèi)存時(shí)屉栓，先根據(jù)內(nèi)存地址找到目標(biāo)地址所在 Set 的 index友多，之后并發(fā)的去驗(yàn)證 Set 下的兩個(gè) Cache Line 的 Tag域滥，驗(yàn)證目標(biāo)地址是否在 Cache Line 內(nèi)骗绕，在的話就讀取數(shù)據(jù)酬土，不在則去讀主存撤缴。

這里并發(fā)的驗(yàn)證兩個(gè) Cache Line 的 Tag 是由硬件來(lái)保證屈呕，硬件電路結(jié)構(gòu)會(huì)更加復(fù)雜但查詢效率與 Direct Mapped Cache 一致虎眨。

image

Set 內(nèi)的兩個(gè) Cache Line 是具有相同 Index 的兩個(gè)不同 Cache Line岳守。上圖來(lái)自 Is Parallel Programming Hard, And, If So, What Can You Do About It?湿痢，圖 C.2譬重。以這個(gè)圖為例臀规，假設(shè) Cache Line 大小是 256 字節(jié)以现，所以圖上所有地址最右側(cè)都是 00邑遏，即有 8 bit 的 Offset记盒，從 0 到 7纪吮。因?yàn)?Cache Line 只有 16 個(gè)碾盟，所以 index 是 4 bit冰肴，從 8 ~ 11熙尉。圖中看到 0x12345E00 和 0x43210E00 在 8 ~ 11 bit 位置上是相同的检痰，都是 0xE 所以這兩個(gè)內(nèi)存地址被映射到 Cache 中同一個(gè) Index 下铅歼。這兩個(gè) Cache Line 就會(huì)放在同一個(gè) Set 內(nèi)椎椰，在訪問(wèn)時(shí)能同時(shí)被比較 Tag。

替換策略

新數(shù)據(jù)要存入 Cache 時(shí)套媚，根據(jù)數(shù)據(jù)所在內(nèi)存地址計(jì)算出 Index 后發(fā)現(xiàn)該 Index 下兩個(gè) Way 的 Cache Line 都已被占用且處在有效狀態(tài)堤瘤。需要有辦法從這兩個(gè) Cache Line 里選一個(gè)出來(lái)移除本辐。Direct Mapped 因?yàn)橐粋€(gè) Index 下只有一個(gè) Cache Line 就沒(méi)這個(gè)問(wèn)題慎皱。

如果是這里說(shuō)的 Two-way Set Associative Cache 還比較好弄茫多，給每個(gè) Way 增加一個(gè)最近訪問(wèn)過(guò)的標(biāo)識(shí)。每次一個(gè) Way 被訪問(wèn)就將最近訪問(wèn)位置位今膊，并清理另一個(gè) Way 的最近訪問(wèn)位斑唬。從而在執(zhí)行替換時(shí)赖钞，將不是最近訪問(wèn)過(guò)的那個(gè) Way 移除雪营。不過(guò)下面會(huì)看到 N-way Set Associative Cache 當(dāng)有 N 個(gè) Way 的時(shí)候替換策略更加復(fù)雜献起，一般是盡可能使用最少的狀態(tài)信息實(shí)現(xiàn)近似的 LRU谴餐。

N-way Set Associative Cache

顧名思義汁展，就是在 Two-way Set Associative Cache 基礎(chǔ)上繼續(xù)橫向擴(kuò)展食绿，在一個(gè) Set 內(nèi)加入更多更多的 Way 也即 Cache Line器紧。這些 Cache Line 能被并發(fā)的同時(shí)驗(yàn)證 Tag铲汪。如果 Cache 內(nèi)所有的 Cache Line 都在同一個(gè) Set 內(nèi)掌腰，即所有 Cache Line 都能同時(shí)被驗(yàn)證 Tag辅斟，則這種 Cache 叫做 Fully Associative Cache 〗湍唬可以看出 Fully Associative Cache 性能是最強(qiáng)的芳撒，能省去從地址中讀取 Index 查找 Set 的過(guò)程笔刹。但橫向擴(kuò)展的 Way 越多萌壳，結(jié)構(gòu)越復(fù)雜袱瓮，成本越高尺借，越難實(shí)現(xiàn)大的 Cache燎斩。所以 Fully Associative Cache 雖然存在，但都很小，一般用在 TLB 上坛吁。

Cache 結(jié)構(gòu)為什么發(fā)展出橫向擴(kuò)展拨脉？

這個(gè)是我自己提出來(lái)的問(wèn)題。對(duì) Direct Mapped Cache 擴(kuò)展 Cache 時(shí)就是增加更多的 index帖旨，讓 cache 表變得更長(zhǎng)解阅。但為什么會(huì)發(fā)展出 Two-way Set Associative Cache 呢货抄？比如如果一共 16 個(gè) Cache Line积暖，是 16 行 Cache Line 還是 8 行 Set 每個(gè) Set 兩個(gè) Cache Line 在容量和命中率上似乎并沒(méi)有差別夺刑。

后來(lái)看到了 這個(gè)問(wèn)題 ，明白了其中的原因错览。主要是需要區(qū)分出來(lái) Conflict Miss 和 Capacity Miss (還有一個(gè) Communication Miss倾哺，前面說(shuō)過(guò))羞海。當(dāng) Cache 容量足夠，但由于兩塊不同的內(nèi)存映射到了同一個(gè) Cache Line腊徙，導(dǎo)致必須將老的內(nèi)存塊剔除產(chǎn)生的 Miss 叫做 Conflict Miss撬腾，即使整個(gè) Cache 都是空的，只有這一個(gè) Cache Line 有效時(shí)也會(huì)出現(xiàn) Miss漓踢。而由于容量不足導(dǎo)致的 Miss 就是 Capacity Miss彭雾。比如 cache 只有 32k，訪問(wèn)的數(shù)據(jù)有 200k锁保，那訪問(wèn)時(shí)候一定會(huì)出現(xiàn)后訪問(wèn)的數(shù)據(jù)不斷的把先訪問(wèn)數(shù)據(jù)從 Cache 中頂出去薯酝，導(dǎo)致 Cache 一直處在 Miss 狀態(tài)的問(wèn)題半沽。

在 Capacity Miss 方面橫向擴(kuò)展和縱向擴(kuò)展沒(méi)有什么區(qū)別，主要區(qū)別就是 Conflict Miss吴菠。假若輪番訪問(wèn) A B 兩個(gè)內(nèi)存，這兩個(gè)內(nèi)存映射到同一個(gè) Cache Line 上做葵，那對(duì)于 Direct Mapped Cache占哟，因?yàn)槊繅K內(nèi)存只有固定的一個(gè) Cache Line 能存放，則會(huì)出現(xiàn)持續(xù)的 Conflict Miss酿矢，稱(chēng)為 cache thrashing榨乎。而 Two-way Set Associative Cache 就能將 A B 兩塊內(nèi)存放入同一個(gè) Set 下，就都能 Cache 住瘫筐，不會(huì)出現(xiàn) Conflict Miss蜜暑。這就是橫向擴(kuò)展的好處，也是為什么橫向擴(kuò)展即使困難策肝，各個(gè) CPU 都在向這個(gè)方向發(fā)展肛捍。并且橫向擴(kuò)展和縱向擴(kuò)展并不沖突，Two-way Set Associative Cache 也能加多 Set 來(lái)進(jìn)行擴(kuò)展之众。

Cache Prefetching

詞條：Cache prefetching - Wikipedia

Cache 運(yùn)作時(shí)并不一定每次只加載一條 Cache Line拙毫，而是可能根據(jù)程序運(yùn)行狀況，發(fā)現(xiàn)有一些固定模式比如 for loop 的時(shí)候在加載 Cache Line 時(shí)會(huì)多加載一點(diǎn)棺禾，類(lèi)似于通過(guò) Batch 來(lái)做優(yōu)化一樣缀蹄。

為什么緩存存取速度比主存快

Why is SRAM better than DRAM? - Quora

False Sharing

Wiki 詞條：False sharing - Wikipedia

比如像下面圖這個(gè)樣子：

image

A B 兩個(gè)對(duì)象在內(nèi)存上被連續(xù)的創(chuàng)建在一起，假若這兩個(gè)對(duì)象都很小膘婶，小于一個(gè) Cache Line 大小袍患，那他們可能會(huì)共用同一個(gè) Cache Line。如果再有兩個(gè)線程 Thread 1 和 Thread 2 會(huì)去操作這兩個(gè)對(duì)象竣付，我們從代碼角度保證 Thread 1 只會(huì)操作 A，而 Thread2 只會(huì)操作 B滞欠。那按道理這兩個(gè) Thread 訪問(wèn) A B 不該有相互影響古胆，都能并行操作。但現(xiàn)在因?yàn)樗鼈z剛好在同一個(gè) Cache Line 內(nèi)筛璧，就會(huì)出現(xiàn) A B 對(duì)象所在 Cache Line 在兩個(gè) CPU 上來(lái)回搬遷的問(wèn)題逸绎。

比如 Thread 1 要修改對(duì)象 A，那 Thread 1 所在 CPU 1 會(huì)先獲取 A 所在 Cache Line 的 Exclusive 權(quán)限夭谤，會(huì)發(fā)送 Invalidate 給其它 CPU 讓其它 CPU 設(shè)置該 Cache Line 為無(wú)效棺牧。之后 Thread 2 要修改對(duì)象 B，Thread 2 所在 CPU 2 又會(huì)嘗試獲取 B 所在 Cache Line 的 Exclusive 權(quán)限朗儒，會(huì)發(fā) Invalidate 給其它 CPU颊乘，包括 CPU 1参淹。CPU 1 要是已經(jīng)寫(xiě)完了 A，那就要把數(shù)據(jù)刷寫(xiě)內(nèi)存乏悄，之后設(shè)置 Cache Line 無(wú)效并響應(yīng) Invalidate浙值。沒(méi)寫(xiě)完就得等待 CPU 1 寫(xiě)完 A 后再處理 Cache Line 的 Invalidate 問(wèn)題。之后 CPU 2 再去操作 Cache Line 更新 B 對(duì)象檩小。再后來(lái) Thread 1 要去更新 A 對(duì)象的話又要去把 A B 所在 Cache Line 在 CPU 2 上設(shè)置無(wú)效开呐。也就是說(shuō)這塊 Cache Line 失去了 Cache 功能，會(huì)在兩個(gè) CPU 上來(lái)回搬遷规求，會(huì)經(jīng)常性的執(zhí)行刷寫(xiě)內(nèi)存筐付，讀取內(nèi)存操作，導(dǎo)致兩個(gè)本來(lái)看上去沒(méi)有關(guān)系的操作實(shí)際上有相互干擾阻肿。

想觀測(cè)到這個(gè)現(xiàn)象最簡(jiǎn)單的是讓 A B 是同一個(gè)類(lèi)的不同 Field瓦戚，而不是兩個(gè)獨(dú)立對(duì)象，比如：

class SomeClass{
    volatile long valueA;
    volatile long valueB;
}

這個(gè)對(duì)象在內(nèi)存上布局如下：

image

看到這個(gè) Object 只有 32 字節(jié)冕茅，在我機(jī)器上一個(gè) Cache Line 是 64 字節(jié) (mac 上執(zhí)行 sysctl machdep.cpu.cache.linesize伤极，Linux 上執(zhí)行 getconf LEVEL1_DCACHE_LINESIZE 來(lái)查看)，所以 A B 都能放在同一個(gè) Cache Line 上姨伤，之后可以創(chuàng)建出來(lái)兩個(gè) Thread 去分別操作同一個(gè) SomeClass 對(duì)象的 valueA 和 valueB Field哨坪，記錄一下時(shí)間，再跟下面解決方案里說(shuō)的方式做對(duì)比乍楚，看看 False Sharing 的現(xiàn)象当编。

解決辦法

解決這個(gè)問(wèn)題的辦法也很容易，如果是上面例子的話徒溪，就是讓被操作的 valueA 和 valueB 隔得遠(yuǎn)一點(diǎn)忿偷。比如可以這么聲明：

class SomeClassPadding {
    volatile long valueA;
    public long p01, p02, p03, p04, p05, p06, p07, p08;
    volatile long valueB;
}

對(duì)象內(nèi)存布局就變成了：

image

因?yàn)槲掖_認(rèn)我機(jī)器的 Cache Line 是 64 字節(jié)，所以加了 8 個(gè) long臊泌。如果 Padding 少一些鲤桥，比如 6 個(gè)，那 valueA 在 Offset 16渠概，第六個(gè) Padding 在 Offset 64茶凳，valueB 恰好是 Offset 64，似乎已經(jīng)足夠?qū)?valueB 放到下一個(gè) Cache Line 了但實(shí)際還是有問(wèn)題播揪。因?yàn)閷?duì)象不一定剛好分配在 Cache Line 開(kāi)頭贮喧，比如 Cache Line 恰好從 valueA 所在 Offset 16 開(kāi)始，到 Offset 80 結(jié)束猪狈，如果只有 6 個(gè) long 做 Padding箱沦，那 valueA 和 valueB 還是在同一個(gè) Cache Line 上。所以 Padding 至少需要和 Cache Line 一樣長(zhǎng)雇庙。

還有要注意看到 Padding 得聲明為 public谓形，不然 JVM 發(fā)現(xiàn)這一堆 Padding 不可能被訪問(wèn)到可能就直接優(yōu)化掉了灶伊。

在我機(jī)器上測(cè)試，Padding 之后性能提升了大概 4 5 倍的樣子套耕。如果上面 SomeClasPadding 去掉 volatile 聲明谁帕，則提升大概 1.5 倍的樣子，之所以有這個(gè)差距是因?yàn)闆](méi)有 volatile 的話線程操作 valueA 和 valueB 如果 Cache Line 不在當(dāng)前 CPU Cache 中冯袍，它并不要求等待 Cache Line 加載進(jìn)來(lái)后再做寫(xiě)入匈挖，而是可以把寫(xiě)入操作放在一個(gè)叫 Store Buffer 的地方以提高性能，具體可以關(guān)注我們的下一篇分享內(nèi)容康愤。等 Cache Line 加載后再對(duì)它做修改儡循，相當(dāng)于是將一段時(shí)間的寫(xiě)入操作積累了一下一口氣寫(xiě)入。而有了 volatile 后則要求每次寫(xiě)入真的得等 Cache Line 加載后再寫(xiě)征冷，從而放大了等待 Cache Line 加載的時(shí)間择膝，更容易觀察到 False Sharing 問(wèn)題。

另外检激，Padding 當(dāng)然是有代價(jià)的肴捉。一個(gè)是讓對(duì)象變得更大，占用內(nèi)存叔收，再有是 Padding 了一堆無(wú)用數(shù)據(jù)還得加載到 Cache 里齿穗，白白占用了 Cache 空間。

需要注意的是自己手工 Padding 方法可能被虛擬機(jī)做重排饺律，即 Padding 本來(lái)想加到 valueA 和 valueB 之間窃页，但可能被重排到 valueB 之后，導(dǎo)致實(shí)際沒(méi)有什么用复濒。比如：

class SomeClassPadding {
    volatile long valueA;
    public int p01, p02, p03, p04, p05, p06, p07, p08;
    volatile long valueB;
}

實(shí)際的內(nèi)存布局是下圖這樣脖卖，即 Padding 都跑到 valueB 后面去了。另外按說(shuō) Cache Line 是 64 字節(jié)的話用 int 做 Padding 至少要 16 個(gè)巧颈，我這里只是為了說(shuō)明手工 Padding 的問(wèn)題畦木，所以少寫(xiě)了一些。

image

內(nèi)存布局實(shí)際會(huì)依賴(lài)虛擬機(jī)而不同砸泛，所以上面這種 Padding 方式是不可靠的十籍。即使變量真聲明為 long 也不能保證所有虛擬機(jī)都按照相同方式做排列。最靠譜的手工 Padding 方式是用 Class 的層級(jí)結(jié)構(gòu)做 Padding晾嘶，因?yàn)?JVM 要求父類(lèi)的成員一定要排在子類(lèi)成員之前，所以級(jí)聯(lián)的 Class 結(jié)構(gòu)能保證 Padding 的可靠性娶吞。比如：

class SomeClassValueA {
    volatile long valueA;
}
class SomeClassPaddings extends SomeClassValueA{
    public int p01, p02, p03, p04, p05, p06, p07, p08, p09, p10, p11;
}
class SomeClassValueB extends SomeClassPaddings{
    volatile long valueB;
}
class SomeClass extends SomeClassValueB{   
}

內(nèi)存結(jié)構(gòu)就變成:

image

這里為了演示用 int 做 Padding垒迂，又不想讓圖片太長(zhǎng)，所以只寫(xiě)了 11 個(gè) int妒蛇，但實(shí)際至少需要 16 個(gè) int 即湊夠 64 字節(jié)才行机断。一般 Padding 都用 long 做楷拳，不會(huì)用 int，可以少寫(xiě)很多變量吏奸。

這個(gè)順序是 JVM 規(guī)范保證的欢揖，所以所有虛擬機(jī)都會(huì)按照這個(gè)方式排列，所以是可靠的奋蔚。

另一個(gè)方法是用 @Contentded 注解她混，java 8 后開(kāi)始支持，java 11 后 Contended 從 sun.misc 搬到了 jdk.internal.misc泊碑。它作用就是自動(dòng)幫你做 Padding坤按，它保證在任意 JVM 上都能有 Padding 效果，就不用我們?cè)偃?gòu)造 Class 級(jí)聯(lián)結(jié)構(gòu)了馒过。比如上面例子中用 @Contended 就是：

class SomeClassContended {
    volatile long valueA;
    @Contended
    volatile long valueB;
}

它的內(nèi)存結(jié)構(gòu)在 HotSpot 64 下是:

image

它是按 128 做 padding 的臭脓，它并沒(méi)管我機(jī)器的 Cache Line 是多少，另外它是在 valueB 前后都做 Padding腹忽。這也是更推薦的方式来累。一般來(lái)說(shuō)都盡力用 @Contended 注解了，除非為了兼容 Java 8 以下 JVM 或者為了性能窘奏，為了 Object 大小等原因嘹锁，才可能會(huì)去手工做 Padding。

上面內(nèi)存結(jié)構(gòu)是通過(guò) JOL 插件 來(lái)查看的蔼夜，它里面用的OpenJDK: jol 工具兼耀。

False Sharing 測(cè)試的話可以參考 JMH 的例子 寫(xiě)自己的測(cè)試。

實(shí)際 Padding 例子求冷，可以看看 Netty 4.1.48 下的 InternalThreadLocalMap瘤运。

JVM 上這個(gè)問(wèn)題常見(jiàn)嗎

上面 False Sharing 的例子是我們故意構(gòu)造而得到的，所以很容易復(fù)現(xiàn)匠题，很容易觀察到拯坟。但實(shí)際開(kāi)發(fā)中讓同一個(gè)對(duì)象里不同 Field 被多個(gè)線程同時(shí)訪問(wèn)的情況并不多。倒是有這種例子比如 ConcurrentHashMap 里用于計(jì)算元素總量的 CounterCell 類(lèi)韭山。不過(guò)這種場(chǎng)景并不是很多郁季，而一般情況下，拿上面的 SomeClass 來(lái)舉例钱磅，它更可能被聲明為：

class SomeClass{
    volatile long value;
}

SomeClass a = new SomeClass();
SomeClass b = new SomeClass();

之后 Thread 1 和 Thread 2 分別去操作 a梦裂，b 兩個(gè)對(duì)象。這種場(chǎng)景下盖淡，按說(shuō)確實(shí)有 False Sharing 問(wèn)題年柠，但因?yàn)?a, b 對(duì)象都分配在 JVM 堆上，它倆得剛巧在堆上被連續(xù)創(chuàng)建出來(lái)褪迟，且在后續(xù)一系列 GC 中都一直能恰好挨在一起冗恨，才能持續(xù)的存在 False Sharing 問(wèn)題答憔。這么看來(lái) False Sharing 似乎很難出現(xiàn)。比如我們測(cè)試時(shí)掀抹，讓每個(gè) Thread 都像上面這樣 new SomeClass() 之后都操作自己 new 出來(lái)的 SomeClass 對(duì)象虐拓，我們會(huì)發(fā)現(xiàn)無(wú)論怎么測(cè)試，性能都和沒(méi)有 False Sharing 時(shí)的性能一致傲武，也即沒(méi)有 False Sharing 問(wèn)題蓉驹。下面會(huì)說(shuō)為什么這里沒(méi)有 False Sharing。

更進(jìn)一步谱轨，即使是同一個(gè) Class 內(nèi)的不同 Field戒幔，如果不是普通變量而是引用募判，比如這樣：

class SomeClass {
    ObjectA valueA;
    ObjectB valueB;
}

兩個(gè) Thread 分別操作這兩個(gè)引用浩习，F(xiàn)alse Sharing 問(wèn)題要求這兩個(gè)引用恰好指向 JVM 堆上兩個(gè)相鄰對(duì)象，且兩個(gè)對(duì)象得足夠小蜗帜，保證兩個(gè)對(duì)象內(nèi)被操作的值離得足夠近献汗，能放在同一個(gè) Cache Line 上敢订。想想每個(gè)對(duì)象都有 Object Header 也即天生就有至少 16 字節(jié)的 Padding 在，這也讓被操作的值更不容易恰好在同一個(gè) Cache Line 上罢吃。

所以 False Sharing 問(wèn)題在 JVM 上并不會(huì)特別常見(jiàn)楚午。

TLAB，PLAB 可能會(huì)加重 False Sharing 問(wèn)題

按說(shuō) False Sharing 問(wèn)題不會(huì)很常見(jiàn)尿招，不過(guò) TLAB 和 PLAB 機(jī)制可能會(huì)增大它出現(xiàn)的幾率矾柜。TLAB 全稱(chēng) Thread Local Allocation Buffers，我并沒(méi)有找到一個(gè)特別好的介紹就谜，這個(gè) Blog 馬馬虎虎能看看： Introduction to Thread Local Allocation Buffers (TLAB) - DZone Java怪蔑。

以下圖為例，Java 分配內(nèi)存通常一開(kāi)始在 Eden 區(qū)分配丧荐，一個(gè)指針用來(lái)區(qū)分分配過(guò)的區(qū)域和還未分配的區(qū)域缆瓣。每次分配內(nèi)存都需要去移動(dòng)這個(gè)指針來(lái)分配。如果所有線程分配內(nèi)存時(shí)候都去操作這個(gè)指針虹统，勢(shì)必會(huì)產(chǎn)生很多競(jìng)爭(zhēng)弓坞，各個(gè)線程都想去移動(dòng)這個(gè)指針，而 TLAB 的存在即是說(shuō)每次線程分配內(nèi)存的時(shí)候不是申請(qǐng)多少就分配多少车荔，而是每次分配稍大的區(qū)域渡冻，如下圖虛線，之后內(nèi)存分配盡力在線程自己的這塊內(nèi)存區(qū)域上進(jìn)行忧便，從而減少對(duì) ptr 指針的競(jìng)爭(zhēng)族吻。如果線程的 TLAB 用完了，或者分配的對(duì)象太大，才會(huì)去爭(zhēng)搶 ptr呼奢。

image

與 TLAB 類(lèi)似的還一個(gè)叫做 PLAB 的，Promotion Local Allocation Buffers切平，用在一組 GC 線程并發(fā)的將新生代對(duì)象晉升到老代時(shí)使用握础。也是每個(gè) GC 線程會(huì)提前分配一塊區(qū)域，每次晉升對(duì)象的時(shí)候?qū)?duì)象拷貝至線程自己的這塊分配好的區(qū)域上悴品，從而減小競(jìng)爭(zhēng)禀综。

如果是標(biāo)記-整理算法，按說(shuō)對(duì)象并發(fā)的 Sweep 到新位置時(shí)也會(huì)是用上面這種方法進(jìn)行苔严。不過(guò)這個(gè)我沒(méi)有找到說(shuō)明的地方定枷。

這么一來(lái)之前說(shuō)兩個(gè)線程分別 new SomeClass()，每個(gè)線程只操作自己 new 出來(lái)的 SomeClass 對(duì)象不會(huì)引起 False Sharing 的原因就清楚了届氢，因?yàn)槊總€(gè)線程會(huì)把 SomeClass 分配在自己的 TLAB 上欠窒，一般 TLAB 大于 Cache Line 所以不會(huì)引起 False Sharing 問(wèn)題。JVM 上容易引起 False Sharing 問(wèn)題的點(diǎn)也清楚了退子，即一個(gè)線程連續(xù)分配了兩個(gè)對(duì)象岖妄，這兩個(gè)對(duì)象后來(lái)被分配給不同的線程，并且被它們頻繁更新寂祥，這兩個(gè)對(duì)象在兩個(gè)不同線程上就容易出現(xiàn) False Sharing 問(wèn)題荐虐，即使經(jīng)歷數(shù)輪 GC，它倆可能在內(nèi)存上還是可能在一起丸凭，所以說(shuō) TLAB 和 PLAB 會(huì)增大 False Sharing 出現(xiàn)的概率福扬。

怎么證實(shí)這一點(diǎn)呢？不太容易惜犀，但指導(dǎo)思想就是讓同一個(gè)線程連續(xù) new 對(duì)象铛碑，再讓其它線程來(lái)訪問(wèn)這些對(duì)象。只要對(duì)象不會(huì)很大向拆，因?yàn)?TLAB 的關(guān)系亚茬，這些對(duì)象中有兩個(gè)在同一個(gè) Cache Line 上的幾率會(huì)很大。比如我在 JMH 測(cè)試時(shí)這么寫(xiě)：

public static class SomeClassValue {
    volatile int value;
}
@State(Scope.Group)
public static class SomeClass {
    SomeClassValue[] val = new SomeClassValue[2];
    public SomeClass() {
        this.val[0] = new SomeClassValue();
        this.val[1] = new SomeClassValue();
    }
}
@Benchmark
@Group("share")
public void testA(SomeClass someClass) {
    someClass.c[0].value++;
}

@Benchmark
@Group("share")
public void testB(SomeClass someClass) {
    someClass.c[1].value++;
}

看到線程會(huì)共享 SomeClass 對(duì)象浓恳，但會(huì)分別訪問(wèn) SomeClass 中不同的 SomeClassValue刹缝。這兩個(gè) value 可能會(huì)被放在同一個(gè) Cache Line 上而被觀測(cè)到執(zhí)行性能下降。

JVM 上 False Sharing 嚴(yán)重嗎

正常來(lái)說(shuō) False Sharing 并不常見(jiàn)颈将，想測(cè)出它也不容易梢夯，可能根據(jù)機(jī)器型號(hào)不同，JVM 版本不同晴圾，運(yùn)行狀況甚至運(yùn)行時(shí)機(jī)不同而不一定什么時(shí)候出現(xiàn)颂砸，但是一旦出現(xiàn)在系統(tǒng)的 Hot Spot 上，數(shù)倍的性能損失是很?chē)?yán)重的。False Sharing 可能產(chǎn)生嚴(yán)重問(wèn)題的場(chǎng)景是：

• 某個(gè) Class 的對(duì)象被連續(xù)的創(chuàng)建人乓；
• 創(chuàng)建的對(duì)象被分發(fā)給多個(gè)不同的線程去讀取勤篮、寫(xiě)入，每個(gè)線程本來(lái)可以獨(dú)享一個(gè)對(duì)象色罚；
• 對(duì)象內(nèi)被線程操作的 Field 被聲明為 volatile碰缔；

比如可以拿 Netty 4.1.48 下的 InternalThreadLocalMap 作為例子感受一下。這個(gè) Thread Local Map 本來(lái)是每個(gè) EventLoop 一個(gè)的戳护，各個(gè) EventLoop 不相互干擾金抡。但是訪問(wèn) Thread Local 對(duì)象本身是 Hot Spot，訪問(wèn)的很多腌且，如果一旦出現(xiàn) False Sharing 就會(huì)導(dǎo)致性能大幅度下降梗肝。EventLoop 是 Netty 啟動(dòng)時(shí)在一個(gè) for loop 中一口氣被創(chuàng)建出來(lái)的，所以一組 InternalThreadLocalMap 中有幾個(gè)剛巧緊挨著被創(chuàng)建出來(lái)是完全可能的铺董。所以 InternalThreadLocalMap 用 Padding 做了一下保護(hù)巫击。當(dāng)然我理解即使 EventLoop 不是連續(xù)被創(chuàng)建出來(lái)也該去保護(hù)一下 InternalThreadLocalMap 以防恰好多個(gè) Map 對(duì)象被放到同一個(gè) Cache Line 上去。

參考

• 本文是我在準(zhǔn)備 LeanCloud 內(nèi)部的一個(gè)分享時(shí)寫(xiě)的精续，感興趣的讀者可以查看分享視頻：CPU Cache（CPU 緩存）基礎(chǔ)解析喘鸟。其他分享：IO 多路復(fù)用（上）、IO 多路復(fù)用（下）驻右。
• PerfBook
• 淺談memory cache ? Opass’s Blog
• Computer Architecture - Class notes
• 《現(xiàn)代體系結(jié)構(gòu)上的UNIX系統(tǒng)》
• 與程序員相關(guān)的CPU緩存知識(shí) | | 酷 殼 - CoolShell
• https://people.freebsd.org/~lstewart/articles/cpumemory.pdf
• Writing cache-friendly code - Stardog
• http://java-performance.com/