面試官：什麼是偽共用，如何避免？
theme: jzman
本文已收錄到 GitHub · AndroidFamily，有 Android 進階知識體系，歡迎 Star。技術和職場問題，請關注公眾號 [彭旭銳] 私信我提問。
前言
大家好，我是小彭。
在前面的文章裡，我們聊到了 CPU 的快取記憶體機制。由於 CPU 和記憶體的速度差距太大，現代計算機會在兩者之間插入一塊快取記憶體。
然而，CPU 快取總能提高程式效能嗎，有沒有什麼情況 CPU 快取反而會成為程式的效能瓶頸？這就是我們今天要討論的偽共用（False Sharing）。
學習路線圖：
1. 回顧 MESI 快取一致性協定
由於 CPU 和記憶體的速度差距太大，為了拉平兩者的速度差，現代計算機會在兩者之間插入一塊速度比記憶體更快的快取記憶體，CPU 快取是分級的，有 L1 / L2 / L3 三級快取。
由於單核 CPU 的效能遇到瓶頸（主頻與功耗的矛盾），晶片廠商開始在 CPU 晶片裡整合多個 CPU 核心，每個核心有各自的 L1 / L2 快取。其中 L1 / L2 快取是核心獨佔的，而 L3 快取是多核心共用的。為了保證同一份資料在記憶體和多個快取副本中的一致性，現代 CPU 會使用 MESI 等快取一致性協定保證系統的資料一致性。
快取一致性問題
MESI 協定
現在，我們的問題是：CPU 快取總能夠提高程式效能嗎？
2. 什麼是偽共用？
基於區域性性原理的應用，CPU Cache 在讀取記憶體資料時，每次不會唯讀一個字或一個位元組，而是一塊塊地讀取，每一小塊資料也叫 CPU 快取行（CPU Cache Line）。
在並行場景中，當多個處理器核心修改同一個快取行變數時，有 2 種情況：
- 情況 1 - 修改同一個變數： 兩個處理器並行修改同一個變數的情況，CPU 會通過 MESI 機制維持兩個核心的快取中的資料一致性（Conherence）。簡單來說，一個核心在修改資料時，需要先向所有核心廣播 RFO 請求，將其它核心的 Cache Line 置為 「已失效」。其它核心在讀取或寫入 「已失效」 資料時，需要先將其它核心 「已修改」 的資料寫回記憶體，再從記憶體讀取；
事實上，多個核心修改同一個變數時，使用 MESI 機制維護資料一致性是必要且合理的。但是多個核心分別存取不同變數時，MESI 機制卻會出現不符合預期的效能問題。
- 情況 2 - 修改不同變數： 兩個處理器並行修改不同變數的情況，從程式設計師的邏輯上看，兩個核心沒有資料依賴關係，因此每次寫入操作並不需要把其他核心的 Cache Line 置為 「已失效」。但從 CPU 的快取一致性機制上看，由於 CPU 快取的顆粒度是一個個快取行，而不是其中的一個個變數。當修改其中的一個變數後，快取控制機制也必須把其它核心的整個 Cache Line 置為 「已失效」。
在高並行的場景下，核心的寫入操作就會交替地把其它核心的 Cache Line 置為失效，強制對方重新整理快取資料，導致快取行失去作用，甚至效能比序列計算還要低。
這個問題我們就稱為偽共用問題。
出現偽共用問題時，有可能出現程式並行執行的耗時比序列執行的耗時還要長。耗時排序： 並行執行有偽共用 > 序列執行 > 並行執行無偽共用。
偽共用效能測試
—— 資料參照自 Github · falseSharing —— MJjainam 著
3. 快取行填充
那麼，怎麼解決偽共用問題呢？其實方法很簡單 —— 快取行填充：
- 1、分組： 首先需要考慮哪些變數是獨立變化的，哪些變數是協同變化的。協同變化的變數放在一組，而無關的變數分到不同組；
- 2、填充： 在變數前後填充額外的佔位變數，避免變數和其他分組的被填充到同一個快取行中，從而規避偽共用問題。
下面，我們以 Java 為例介紹如何做快取行填充，在不同 Java 版本上填充的實現方式不同：
- Java 8 之前
通過填充 long 變數填充 Padding。 網上有的資料會將前置填充和後置填充放在同一個類中， 這是不對的。例如：
錯誤範例
public class Data {
long a1,a2,a3,a4,a5,a6,a7; // 前置填充
volatile int value;
long b1,b2,b3,b4,b5,b6,b7; // 後置填充
}
在 《物件的記憶體分為哪幾個部分？》 這篇文章中，我們分析 Java 物件的記憶體佈局：其中我們提到：「其中，父類別宣告的範例欄位會放在子類範例欄位之前，而欄位間的並不是按照原始碼中的宣告順序排列的，而是相同寬度的欄位會分配在一起：參照型別 > long/double > int/float > short/char > byte/boolean。」
Java 物件記憶體佈局
因此，上面的程式碼中，所有填充變數都變成前置填充了，並沒有起到填充的效果：
實驗驗證
# 使用 JOL 工具輸出物件記憶體佈局：
OFFSET SIZE TYPE DESCRIPTION VALUE
0 4 (object header) 01 00 00 00 (00000001 00000000 00000000 00000000) (1)
4 4 (object header) 00 00 00 00 (00000000 00000000 00000000 00000000) (0)
8 4 (object header) 43 c1 00 f8 (01000011 11000001 00000000 11111000) (-134168253)
# 填充無效
12 4 int Data.value 0
16 8 long Data.a1 0
24 8 long Data.a2 0
32 8 long Data.a3 0
40 8 long Data.a4 0
48 8 long Data.a5 0
56 8 long Data.a6 0
64 8 long Data.a7 0
72 8 long Data.b1 0
80 8 long Data.b2 0
88 8 long Data.b3 0
96 8 long Data.b4 0
104 8 long Data.b5 0
112 8 long Data.b6 0
120 8 long Data.b7 0
Instance size: 128 bytes
正確的做法是利用父子類繼承來做快取行填充：
正確範例
public abstract class SuperPadding {
long a1,a2,a3,a4,a5,a6,a7; // 前置填充
}
public abstract class DataField extends SuperPadding {
volatile int value;
}
public class Data extends DataField {
long b1,b2,b3,b4,b5,b6,b7; // 後置填充
}
實驗驗證
# 使用 JOL 工具輸出物件記憶體佈局：
OFFSET SIZE TYPE DESCRIPTION VALUE
0 4 (object header) 01 00 00 00 (00000001 00000000 00000000 00000000) (1)
4 4 (object header) 00 00 00 00 (00000000 00000000 00000000 00000000) (0)
8 4 (object header) bf c1 00 f8 (10111111 11000001 00000000 11111000) (-134168129)
12 4 (alignment/padding gap)
16 8 long SuperPadding.a1 0
24 8 long SuperPadding.a2 0
32 8 long SuperPadding.a3 0
40 8 long SuperPadding.a4 0
48 8 long SuperPadding.a5 0
56 8 long SuperPadding.a6 0
64 8 long SuperPadding.a7 0
72 4 int DataField.value 0
76 4 (alignment/padding gap)
80 8 long Data.b1 0
88 8 long Data.b2 0
96 8 long Data.b3 0
104 8 long Data.b4 0
112 8 long Data.b5 0
120 8 long Data.b6 0
128 8 long Data.b7 0
Instance size: 136 bytes
快取行填充
例如，Java 並行框架 Disruptor 就是使用繼承的方式實現：
abstract class RingBufferPad {
protected long p1, p2, p3, p4, p5, p6, p7;
}
abstract class RingBufferFields<E> extends RingBufferPad {
// 前置填充：父類別的 7 個 long 變數
...
private final long indexMask;
private final Object[] entries;
protected final int bufferSize;
protected final Sequencer sequencer;
...
// 後置填充：子類的 7 個 long 變數
}
public final class RingBuffer<E> extends RingBufferFields<E> implements Cursored, EventSequencer<E>, EventSink<E> {
protected long p1, p2, p3, p4, p5, p6, p7;
...
}
- Java 8 開始
@sun.misc.Contended 註解是 JDK 1.8 新增的註解。如果 JVM 開啟位元組填充功能 -XX:-RestrictContended ，在執行時就會在變數或類前後填充 Padding。
Java 8 Thread.java
/** The current seed for a ThreadLocalRandom */
@sun.misc.Contended("tlr")
long threadLocalRandomSeed;
/** Probe hash value; nonzero if threadLocalRandomSeed initialized */
@sun.misc.Contended("tlr")
int threadLocalRandomProbe;
/** Secondary seed isolated from public ThreadLocalRandom sequence */
@sun.misc.Contended("tlr")
int threadLocalRandomSecondarySeed;
Java 8 ConcurrentHashMap.java
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
4. 總結
-
1、在並行場景中，當多個處理器核心修改同一個快取行變數時，即使兩個變數沒有邏輯上的資料依賴性，CPU 快取一致性機制也會使得兩個核心中的快取交替地失效，拉低程式的效能。這種現象叫偽共用問題；
-
2、解決偽共用問題的方法是緩衝行填充：在變數前後填充額外的佔位變數，避免變數和其他分組的被填充到同一個快取行中，從而規避偽共用問題。
本文為稀土掘金技術社群首發簽約文章，14天內禁止轉載，14天后未獲授權禁止轉載，侵權必究！
參考資料
- 深入淺出計算機組成原理（第 37 講） —— 徐文浩 著，極客時間 出品
- 位元組面：什麼是偽共用？ —— 小林 Coding 著
- Be careful when trying to eliminate false sharing in Java —— nitsanw 著
- False Sharing && Java 7 —— Martin Thompson 著
- False sharing —— Wikepedia
