關於多執行緒同步的一切：偽共享

```c++
const size_t shm_size = 16*1024*1024; //16M
static char shm[shm_size];
std::atomic<size_t> shm_offset{0};


void f() {
   for (;;) {
       auto off = shm_offset.fetch_add(sizeof(long));
       if (off >= shm_size) break;
       *(long*)(shm + off) = off;
   }
}
```

考察上面的程式，shm是一塊16M位元組的記憶體，我測試機器的L3 Cache是32M，所以挑選16M這個值確保shm陣列在Cache裡能存放得下。

f()函式在迴圈裡，把shm視為long型別的陣列，依次給每個元素賦值，shm_offset用於記錄偏移位置，shm_offset.fetch_add(sizeof(long))原子性的增加shm_offset的值（因為x86_64系統上long的長度為8，所以shm_offset每次增加8位元組），並返回增加前的值，對shm上long陣列的每個元素賦值後，結束迴圈從函式返回。

因為shm_offset是atomic型別變數，所以多執行緒呼叫f()依然能正常工作，雖然多個執行緒會競爭shm_offset，但每個執行緒會排他性的對各long元素賦值，多執行緒並行會加快對shm的賦值操作。

我們加上多執行緒呼叫，程式碼如下：

```c++
std::atomic<size_t> step{0};


const int THREAD_NUM = 2;


void work_thread() {
   const int N = 10;
   for (int n = 1; n <= N; ++n) {
       f();
       ++step;
       while (step.load() < n * THREAD_NUM) {}
       shm_offset = 0;
   }
}


int main() {
   std::thread threads[THREAD_NUM];
   for (int i = 0; i < THREAD_NUM; ++i) {
       threads[i] = std::move(std::thread(work_thread));
   }
   for (int i = 0; i < THREAD_NUM; ++i) {
       threads[i].join();
   }
   return 0;
}
```

• main函式裡啟動2個工作執行緒work_thread
• 工作執行緒對shm共計賦值N（10）輪，後面的每一輪會訪問Cache裡的shm資料，step用於work_thread之間每一輪的同步
• 工作執行緒呼叫完f()後會增加step，等2個工作執行緒都呼叫完之後，step的值增加到n * THREAD_NUM後，while()迴圈結束，重置shm_offset，重新開始新一輪對shm的賦值

編譯後執行上面的程式，產生如下的結果：

```
time ./a.out

real 0m3.406s
user 0m6.740s
sys 0m0.040s
```

time命令用於時間測量，在a.out程式執行完成，會列印耗時，real行顯式耗時3.4秒。

改進版f_fast

我們稍微修改一下f函式，改進版f函式取名f_fast：

```c++
void f_fast() {
   for (;;) {
       const long inner_loop = 16;
       auto off = shm_offset.fetch_add(sizeof(long) * inner_loop);
       for (long j = 0; j < inner_loop; ++j) {
           if (off >= shm_size) return;
           *(long*)(shm + off) = j;
           off += sizeof(long);
       }
   }
}
```

for迴圈裡，shm_offset不再是每次增加8位元組（sizeof(long)），而是8*16=128位元組，然後在內層的迴圈裡，依次對16個long連續元素賦值，然後下一輪迴圈又再次增加128位元組，直到完成對整個shm的賦值。

編譯後重新執行程式，結果顯示耗時降低到0.06秒，對比前一種耗時3.4秒，f_fast效能大幅提升。

```
time ./a.out

real 0m0.062s
user 0m0.110s
sys 0m0.012s
```

f和f_fast的行為差異

shm陣列總共有2M個long元素，因為16M / sizeof(long) => 2M，

1. f()函式行為邏輯

執行緒1和執行緒2的work_thread裡會交錯地對shm元素賦值，shm的2M個long元素，會順序的一個接一個的派給2個執行緒去賦值。

例如：

• 可能元素1由執行緒1賦值，元素2由執行緒2賦值，然後元素3和元素4由執行緒1賦值，然後元素5由執行緒2賦值...
• 每次派元素的時候，shm_offset都會atomic的增加8位元組，所以不會出現2個執行緒給1個元素賦值的情況

2. f_fast()函式行為邏輯

• 每次派元素的時候，shm_offset原子性的增加128位元組（16個元素）
• 這16個位元組作為一個整體，派給執行緒1或者執行緒2；雖然執行緒1和執行緒2還是會交錯的操作shm元素，但是以16個元素（128位元組）為單元，這16個連續的元素不會被分派到不同執行緒
• 一次派發的16個元素，會在內部迴圈裡被一個接著一個的賦值，在一個執行緒裡執行

為什麼f_fast更快？

第一眼感覺是f_fast()裡shm_offset.fetch_add()呼叫頻次降低到了原來的1/16，我們有理由懷疑是原子變數的競爭減少導致程式執行速度加快。

為了驗證，讓我們在內層的迴圈里加一個原子變數test的fetch_add，test原子變數的競爭會像f()函式裡shm_offset.fetch_add()一樣被激烈競爭，修改後的f_fast程式碼變成下面這樣：

```c++
void f_fast() {
   for (;;) {
       const long inner_loop = 16;
       auto off = shm_offset.fetch_add(sizeof(long) * inner_loop);
       for (long j = 0; j < inner_loop; ++j) {
           test.fetch_add(1);
           if (off >= shm_size) return;
           *(long*)(shm + off) = j;
           off += sizeof(long);
       }
   }
}
```

為了避免test.fetch_add(1)的呼叫被編譯器優化掉，我們在main函式的最後把test的值打印出來。

編譯後測試一下，結果顯示：執行時間只是稍微增加到`real 0m0.326s`。所以，很顯然，並不是atomic的呼叫頻次減少導致效能飆升。

我們重新審視f()迴圈裡的邏輯：f()迴圈裡的操作很簡單：原子增加、判斷、賦值。

會不會是賦值太慢？

我們把f()的裡賦值註釋掉，再測試一下，發現它的速度得到了很大提升，看來是`*(long*)(shm + off) = off;`這一行程式碼執行慢，但這明明只是一行賦值。

我們把它反彙編來看，它只是一個mov指令，源運算元是暫存器，目標運算元是記憶體地址，從暫存器拷貝資料到一個記憶體地址，而這個記憶體資料應該被cache住了，為什麼會這麼慢呢？

答案

現在揭曉原因，導致f()效能底下的元凶是偽共享（false sharing），那什麼是偽共享？

要說清這個問題，還得聯絡CPU的架構，以及CPU怎麼訪問資料，我們回顧一下關於多核Cache結構：

背景知識

我們知道現代CPU可以有多個核，每個核有自己的L1-L2快取，L1又區分資料快取（L1-DCache）和指令快取（L1-ICache），L2不區分資料和指令Cache，而L3跨核共享，L3通過記憶體匯流排連線到記憶體，記憶體被所有CPU所有Core共享。

CPU訪問L1 Cache的速度大約是訪問記憶體的100倍，Cache作為CPU與記憶體之間的快取，減少CPU對記憶體的訪問頻率。

從記憶體載入資料到Cache的時候，是以Cache Line為長度單位的，Cache Line的長度通常是64位元組。

所以，那怕只讀一個位元組，但是包含該位元組的整個Cache Line都會被載入到快取，同樣，如果修改一個位元組，那麼最終也會導致整個Cache Line被沖刷到記憶體。

如果一塊記憶體資料被多個執行緒訪問，假設多個執行緒在多個Core上並行執行，那麼它便會被載入到多個Core的的Local Cache中；這些執行緒在哪個Core上執行，就會被載入到哪個Core的Local Cache中，所以，記憶體中的一個數據，在不同Core的Cache裡會同時存在多份拷貝。

如果我們修改了Core1快取裡的某個資料，則該資料所在的Cache Line的狀態需要同步給其他Core的快取，Core之間可以通過核間訊息同步狀態，比如通過傳送Invalidate訊息給其他核，接收到該訊息的核會把對應Cache Line置為無效，然後重新從記憶體里加載最新資料。

被載入到多個Core快取中的同一Cache Line，會被標記為共享（Shared）狀態，對共享狀態的快取行進行修改，需要先獲取快取行的修改權（獨佔），MESI協議用來保證多核快取的一致性，更多的細節可以參考MESI資料。

示例分析

現在來看看我們的程式。

假設執行緒1執行在Core1，執行緒2執行在Core2。

因為shm被執行緒1和執行緒2這兩個執行緒併發訪問，所以shm的記憶體資料會以Cache Line粒度，被同時載入到2個Core的Cache，因為被多核共享，所以該Cache Line被標註為Shared狀態。

假設執行緒1在offset為64的位置寫入了一個8位元組的資料（sizeof(long)），要修改一個狀態為Shared的Cache Line，Core1會發送核間通訊訊息到Core2，去拿到該Cache Line的獨佔權，在這之後，Core1才能修改Local Cache。

執行緒1執行完`shm_offset.fetch_add(sizeof(long))`後，shm_offset會增加到72。

這時候Core2上執行的執行緒2也會執行`shm_offset.fetch_add(sizeof(long))`，它返回72並將shm_offset增加到80。

執行緒2接下來要修改shm[72]的記憶體位置，因為shm[64]和shm[72]在一個Cache Line，而這個Cache Line又被置為Invalidate，所以，它需要從記憶體裡重新載入這一個Cache Line，而在這之前，Core1上的執行緒1需要把Cache Line沖刷到記憶體，這樣執行緒2才能載入最新的資料。

這種交替執行模式，相當於Core1和Core2之間需要頻繁的傳送核間訊息，收到訊息的Core的對應Cache Line被置為無效，並重新從記憶體里加載資料到Cache，每次修改後都需要把Cache中的資料刷入記憶體。

這其實相當於廢棄掉了Cache，因為每次讀寫都直接跟記憶體打交道，Cache的作用不復存在，效能下降。

多核多執行緒程式，因為併發讀寫同一個Cache Line的資料（臨近位置的記憶體資料），導致Cache Line的頻繁失效，記憶體的頻繁Load/Store，從而導致效能急劇下降的現象叫偽共享，偽共享是效能殺手。

另一個偽共享的例子

假設執行緒x和y，分別修改Data的a和b變數，如果被頻繁呼叫，根據前面的分析，也會出現效能低下的情況，怎麼規避呢？

```c++
struct Data {
   int a;
   int b;
};

Data data; // global

void thread1() {
   data.a = 1;
}

void thread2() {
   data.b = 2;
}
```

**空間換時間**

避免Cache偽共享導致效能下降的思路是用空間換時間，通過在a和b成員之間增加填充，讓a、b兩個變數分佈到不同的Cache Line，這樣對a和b的修改就會作用於不同Cache Line，就能避免Cache line失效的問題。

```c++
struct Data {
   int a;
   int padding[60];
   int b;
};
```

在Linux kernel中存在__cacheline_aligned_in_smp巨集定義用於解決false sharing問題。

```c
#ifdef CONFIG_SMP
#define __cacheline_aligned_in_smp __cacheline_aligned
#else
#define __cacheline_aligned_in_smp
#endif

struct Data {
   int a;
   int b __cacheline_aligned_in_smp;
};
```

從上面的巨集定義，我們可以看到：

• 在多核（MP）系統裡，該巨集定義是 __cacheline_aligned，也就是Cache Line的大小
• 在單核系統裡，該巨集定義是空的

偽共享的疑問

既然多CPU多核併發讀寫一個Cache Line裡的記憶體資料，會出現偽共享，那麼，我們對`atomic<size_t> shm_offset`的fetch_add()操作也滿足這個條件，多個執行緒同時對同一個shm_offset變數併發讀寫，那為什麼效能不會很差呢？

我們反彙編發現`atomic.fetch_add`會被翻譯成`lock; xadd %rax (%rdx)`，lock是一個指令字首，配合其他指令使用。

bus lock做的事情就是鎖住匯流排，然後執行後面的xadd，在此期間，別的執行緒都不能訪問任何記憶體資料。

實際上，鎖匯流排的操作比較重，相當於全域性的記憶體匯流排鎖，lock字首之後的指令操作就直接作用於記憶體，bypass掉快取，lock也相當於記憶體屏障。

但翻看Intel手冊發現，執行lock指令，CPU會根據情況自行決定到底是鎖快取，還是assert #LOCK signal（鎖匯流排）。

如果訪問的記憶體區域已經快取在處理器的快取行中，Intel的現代處理器則不會assert #LOCK訊號，它會對CPU的快取中的快取行進行鎖定，在鎖定期間，其它CPU不能同時快取此資料，在修改之後，通過快取一致性協議來保證修改的原子性，這個操作被稱為“快取鎖”。

false sharing對應的是多執行緒同時讀寫一個Cache Line的多個數據，Core-A修改資料x後，會置Cache Line為Invalid，Core-B讀該快取行的另一個數據y，需要Core-A把Cache Line Store到記憶體，Core-B再從記憶體裡Load對應Cache Line，資料要過記憶體。

而atomic，多個執行緒修改的是同一個變數。lock指令字首，應該會用到快取鎖（鎖Cache Line），atomic在Cache Line裡的最新值通過核間訊息傳送給其他核就可以了，不需要頻繁的Store/Load，所以效能不會那麼糟。