關于多線程同步的一切：偽共享
```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，所以性能不會那么糟。
