並行刺客（False Sharing）——並行程式的隱藏殺手
並行刺客（False Sharing）——並行程式的隱藏殺手
前言
前段時間在各種社交平臺「雪糕刺客」這個詞比較火，簡單的來說就是雪糕的價格非常高！其實在並行程式當中也有一個刺客，如果在寫並行程式的時候不注意不小心，這個刺客很可能會拖累我們的並行程式，讓我們並行程式執行的效率變低，讓並行程式付出很大的代價，這和「雪糕刺客」當中的「刺客」的含義是一致的。這個並行程式當中的刺客就是——假共用（False Sharing）。
假共用（False Sharing）
快取行
當CPU從更慢級別的快取讀取資料的時候（三級Cache會從記憶體當中讀取資料，二級快取會從三級快取當中讀取資料，一級快取會從二級快取當中讀取資料，快取級別越低執行速度越快），CPU並不是一個位元組一個位元組的讀取的，而是一次會讀取一塊資料，然後將這個資料快取到CPU當中，而這一塊資料就叫做快取行。有一種快取行的大小就是64位元組，那麼我們為什麼會做這種優化呢？這是因為區域性性原理，所謂區域性性原理簡單說來就是，當時使用一個資料的時候，它附近的資料在未來的一段時間你也很可能用到，比如說我們遍歷陣列，我們通常從前往後進行遍歷，比如我們陣列當中的資料大小是8個位元組，如果我們的快取行是64個位元組的話，那麼一個快取行就可以快取8個資料，那麼我們在遍歷第一個資料的時候將這8個資料載入進入快取行，那麼我們在遍歷未來7個資料的時候都不需要再從記憶體當中拿資料，直接從快取當中拿就行，這就可以節約程式執行的時間。
假共用
當兩個執行緒在CPU上兩個不同的核心上執行程式碼的時候，如果這兩個執行緒使用了同一個快取行C，而且對這個快取行當中兩個不同的變數進行寫操作，比如執行緒A對變數a進行寫操作，執行緒B對變數b進行寫操作。而由於快取一致性（Cache coherence）協定的存在，如果其中A執行緒對快取行C中變數a進行了寫操作的話，為了保證各個CPU核心的資料一致（也就是說兩個CPU核心看到了a的值是一樣的，因為a的值已經發生變化了，需要讓另外的CPU核心知道，不然另外的CPU核心使用的就是舊的值，那麼程式結果就不對了），其他核心的這個快取行就會失效，如果他還想使用這個快取行的話就需要重新三級Cache載入，如果資料不存在三級Cache當中的話，就會從記憶體當中載入，而這個重新載入的過程就會很拖累程式的執行效率，而事實上執行緒A寫的是變數a，執行緒B寫的是變數b，他們並沒有真正的有共用的資料，只是他們需要的資料在同一個快取行當中，因此稱這種現象叫做假共用（False Sharing）。
上面我們談到了，當快取行失效的時候會從三級Cache或者記憶體當中載入，而多個不同的CPU核心是共用三級Cache的（上圖當中已經顯示出來了），其中一個CPU核心更新了資料，會把資料重新整理到三級Cache或者記憶體當中，因此這個時候其他的CPU核心去載入資料的時候就是新值了。
上面談到的關於CPU的快取一致性（Cache coherence）的內容還是比較少的，如果你想深入瞭解快取一致性（Cache coherence）和快取一致性協定可以仔細去看這篇文章。
我們再來舉一個更加具體的例子：
假設在記憶體當中，變數a和變數b都佔四個位元組，而且他們的記憶體地址是連續且相鄰的，現在有兩個執行緒A和B，執行緒A要不斷的對變數a進行+1操作，執行緒B需要不斷的對變數進行+1操作，現在這個兩個資料所在的快取行已經被快取到三級快取了。
- 執行緒A從三級快取當中將資料載入到二級快取和一級快取然後在CPU- Core0當中執行程式碼，執行緒B從三級快取將資料載入到二級快取和一級快取然後在CPU- Core1當中執行程式碼。
- 執行緒A不斷的執行a += 1，因為執行緒B快取的快取行當中包含資料a，執行緒A在修改a的值之後，就會在匯流排上傳送訊息，讓其他處理器當中含有變數a的快取行失效，在處理器將快取行失效之後，就會在匯流排上傳送訊息，表示快取行已經失效，執行緒A所在的CPU- Core0收到訊息之後將更新後的資料重新整理到三級Cache。
- 這個時候執行緒B所在的CPU-Core1當中含有a的快取行已經失效，因為變數b和變數a在同一個快取行，現線上程B想對變數b進行加一操作，但是在一級和二級快取當中已經沒有了，它需要三級快取當中載入這個快取行，如果三級快取當中沒有就需要去記憶體當中載入。
- 仔細分析上面的過程你就會發現執行緒B並沒有對變數a有什麼操作，但是它需要的快取行就失效了，雖然和執行緒B共用需要同一個內容的快取行，但是他們之間並沒有真正共用資料，所以這種現象叫做假共用。
Java程式碼復現假共用
復現假共用
下面是兩個執行緒不斷對兩個變數執行++操作的程式碼：
class Data {
public volatile long a;
public volatile long b;
}
public class FalseSharing {
public static void main(String[] args) throws InterruptedException {
Data data = new Data();
long start = System.currentTimeMillis();
Thread A = new Thread(() -> {
for (int i = 0; i < 500_000_000; i++) {
data.a += 1;
}
}, "A");
Thread B = new Thread(() -> {
for (int i = 0; i < 500_000_000; i++) {
data.b += 1;
}
}, "B");
A.start();
B.start();
A.join();
B.join();
long end = System.currentTimeMillis();
System.out.println("花費時間為：" + (end - start));
System.out.println(data.a);
System.out.println(data.b);
}
}
上面的程式碼比較簡單，這裡就不進行說明了，上面的程式碼在我的筆電上的執行時間大約是17秒。
上面的程式碼變數a和變數b在記憶體當中的位置是相鄰的，他們在被CPU載入之後會在同一個快取行當中，因此會存在假共用的問題，程式的執行時間會變長。
下面的程式碼是優化過後的程式碼，在變數a前面和後面分別加入56個位元組的資料，再加上a的8個位元組（long型別是8個位元組），這樣a前後加上a的資料有64個位元組，而現在主流的快取行是64個位元組，夠一個快取行的大小，因為資料a和資料b就不會在同一個快取行當中，因此就不會存在假共用的問題了。而下面的程式碼在我筆電當中執行的時間大約為5秒。這就足以看出假共用會對程式的執行帶來多大影響了。
class Data {
public volatile long a1, a2, a3, a4, a5, a6, a7;
public volatile long a;
public volatile long b1, b2, b3, b4, b5, b6, b7;
public volatile long b;
}
public class FalseSharing {
public static void main(String[] args) throws InterruptedException {
Data data = new Data();
long start = System.currentTimeMillis();
Thread A = new Thread(() -> {
for (int i = 0; i < 500_000_000; i++) {
data.a += 1;
}
}, "A");
Thread B = new Thread(() -> {
for (int i = 0; i < 500_000_000; i++) {
data.b += 1;
}
}, "B");
A.start();
B.start();
A.join();
B.join();
long end = System.currentTimeMillis();
System.out.println("花費時間為：" + (end - start));
System.out.println(data.a);
System.out.println(data.b);
}
}
JDK解決假共用
為了解決假共用的問題，JDK為我們提供了一個註解@Contened解決假共用的問題。
import sun.misc.Contended;
class Data {
// public volatile long a1, a2, a3, a4, a5, a6, a7;
@Contended
public volatile long a;
// public volatile long b1, b2, b3, b4, b5, b6, b7;
@Contended
public volatile long b;
}
public class FalseSharing {
public static void main(String[] args) throws InterruptedException {
Data data = new Data();
long start = System.currentTimeMillis();
Thread A = new Thread(() -> {
for (long i = 0; i < 500_000_000; i++) {
data.a += 1;
}
}, "A");
Thread B = new Thread(() -> {
for (long i = 0; i < 500_000_000; i++) {
data.b += 1;
}
}, "B");
A.start();
B.start();
A.join();
B.join();
long end = System.currentTimeMillis();
System.out.println("花費時間為：" + (end - start));
System.out.println(data.a);
System.out.println(data.b);
}
}
上面程式碼的執行時間也是5秒左右，和之前我們自己在變數的左右兩邊插入變數的效果是一樣的，但是JDK提供的這個介面和我們自己實現的還是有所區別的。（注意：上面的程式碼是在JDK1.8下執行的，如果要想@Contended註解生效，你還需要在JVM引數上加入-XX:-RestrictContended，這樣上面的程式碼才能生效否則是不能夠生效的）
-
在我們自己解決假共用的程式碼當中，是在變數
a的左右兩邊加入56個位元組的其他變數，讓他和變數b不在同一個快取行當中。 -
在JDK給我們提供的註解
@Contended，是在被加註解的欄位的右邊加入一定數量的空位元組，預設加入128空位元組，那麼變數a和變數b之間的記憶體地址大一點，最終不在同一個快取行當中。這個位元組數量可以使用JVM引數-XX:ContendedPaddingWidth=64，進行控制，比如這個是64個位元組。 -
除此之外
@Contended註解還能夠將變數進行分組：
class Data {
@Contended("a")
public volatile long a;
@Contended("bc")
public volatile long b;
@Contended("bc")
public volatile long c;
}
在解析註解的時候會讓同一組的變數在記憶體當中的位置相鄰，不同的組之間會有一定數量的空位元組，設定方式還是跟上面一樣，預設每組之間空位元組的數量為128。
比如上面的變數在記憶體當中的邏輯佈局詳細布局如下：
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) 20 0a 06 00 (00100000 00001010 00000110 00000000) (395808)
12 132 (alignment/padding gap)
144 8 long Data.a 0
152 128 (alignment/padding gap)
280 8 long Data.b 0
288 8 long Data.c 0
296 128 (loss due to the next object alignment)
Instance size: 424 bytes
Space losses: 260 bytes internal + 128 bytes external = 388 bytes total
上面的內容是通過下面程式碼列印的，你只要在pom檔案當中引入包jol即可：
import org.openjdk.jol.info.ClassLayout;
import sun.misc.Contended;
class Data {
@Contended("a")
public volatile long a;
@Contended("bc")
public volatile long b;
@Contended("bc")
public volatile long c;
}
public class FalseSharing {
public static void main(String[] args) throws InterruptedException {
Data data = new Data();
System.out.println(ClassLayout.parseInstance(data).toPrintable());
}
}
從更低層次C語言看假共用
前面我們是使用Java語言去驗證假共用，在本小節當中我們通過一個C語言的多執行緒程式（使用pthread）去驗證假共用。（下面的程式碼在類Unix系統都可以執行）
#include <stdio.h>
#include <pthread.h>
#include <time.h>
#define CHOOSE // 這裡定義了 CHOOSE 如果不想定義CHOOSE 則將這一行註釋掉即可
// 定義一個全域性變數
int data[1000];
void* add(void* flag) {
// 這個函數的作用就是不斷的往 data 當中的某個資料進行加一操作
int idx = *((int *)flag);
for (long i = 0; i < 10000000000; ++i) {
data[idx]++;
}
}
int main() {
pthread_t a, b;
#ifdef CHOOSE // 如果定義了 CHOOSE 則執行下面的程式碼 讓兩個執行緒操作的變數隔得遠一點 讓他們不在同一個快取行當中
int flag_a = 0;
int flag_b = 100;
printf("遠離\n");
#else // 如果沒有定義 讓他們隔得近一點 也就是說讓他們在同一個快取行當中
int flag_a = 0;
int flag_b = 1;
printf("臨近\n");
#endif
pthread_create(&a, NULL, add, &flag_a); // 建立執行緒a 執行函數 add 傳遞引數 flag_a 並且啟動
pthread_create(&b, NULL, add, &flag_b); // 建立執行緒b 執行函數 add 傳遞引數 flag_b 並且啟動
long start = time(NULL);
pthread_join(a, NULL); // 主執行緒等待執行緒a執行完成
pthread_join(b, NULL); // 主執行緒等待執行緒b執行完成
long end = time(NULL);
printf("data[0] = %d\t data[1] = %d\n", data[0], data[1]);
printf("cost time = %ld\n", (end - start));
return 0;
}
上面程式碼的輸出結果如下圖所示：
我們首先來解釋一下上面time命令的輸出：
readl：這個表示真實世界當中的牆鍾時間，就是表示這個程式執行所花費的時間，這個秒單位和我們平常說的秒是一樣的。user：這個表示程式在使用者態執行的CPU時間，CPU時間和真實時間是不一樣的，這裡需要注意區分，這裡的秒和我們平常的秒是不一樣的。sys：這個表示程式在核心態執行所花費的CPU時間。
從上面程式的輸出結果我們可以很明顯的看出來當操作的兩個整型變數相隔距離遠的時候，也就是不在同一個快取行的時候，程式執行的速度是比資料隔得近在同一個快取行的時候快得多，這也從側面顯示了假共用很大程度的降低了程式執行的效率。
總結
在本篇文章當中主要討論了以下內容：
- 當多個執行緒操作同一個快取行當中的多個不同的變數時，雖然他們事實上沒有對資料進行共用，但是他們對同一個快取行當中的資料進行修改，而由於快取一致性協定的存在會導致程式執行的效率降低，這種現象叫做假共用。
- 在Java程式當中我們如果想讓多個變數不在同一個快取行當中的話，我們可以在變數的旁邊通過增加其他變數的方式讓多個不同的變數不在同一個快取行。
- JDK也為我們提供了
Contended註解可以在欄位的後面通過增加空位元組的方式讓多個資料不在同一個快取行，而且你需要在JVM引數當中加入-XX:-RestrictContended，同時你可以通過JVM引數-XX:ContendedPaddingWidth=64調整空位元組的數目。JDK8之後註解Contended在JDK當中的位置有所變化，大家可以查詢一下。 - 我們也是用了C語言的API去測試了假共用，事實上在Java虛擬機器器當中底層的執行緒也是通過呼叫
pthread_create進行建立的。
更多精彩內容合集可存取專案：https://github.com/Chang-LeHung/CSCore
關注公眾號：一無是處的研究僧，瞭解更多計算機（Java、Python、計算機系統基礎、演演算法與資料結構）知識。