```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，所以性能不會那么糟。