```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字節(jié)的內(nèi)存，我測(cè)試機(jī)器的L3 Cache是32M，所以挑選16M這個(gè)值確保shm數(shù)組在Cache里能存放得下。

f()函數(shù)在循環(huán)里，把shm視為long類(lèi)型的數(shù)組，依次給每個(gè)元素賦值，shm_offset用于記錄偏移位置，shm_offset.fetch_add(sizeof(long))原子性的增加shm_offset的值（因?yàn)閤86_64系統(tǒng)上long的長(zhǎng)度為8，所以shm_offset每次增加8字節(jié)），并返回增加前的值，對(duì)shm上long數(shù)組的每個(gè)元素賦值后，結(jié)束循環(huán)從函數(shù)返回。

因?yàn)閟hm_offset是atomic類(lèi)型變量，所以多線程調(diào)用f()依然能正常工作，雖然多個(gè)線程會(huì)競(jìng)爭(zhēng)shm_offset，但每個(gè)線程會(huì)排他性的對(duì)各long元素賦值，多線程并行會(huì)加快對(duì)shm的賦值操作。

我們加上多線程調(diào)用，代碼如下：

```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函數(shù)里啟動(dòng)2個(gè)工作線程work_thread
• 工作線程對(duì)shm共計(jì)賦值N（10）輪，后面的每一輪會(huì)訪問(wèn)Cache里的shm數(shù)據(jù)，step用于work_thread之間每一輪的同步
• 工作線程調(diào)用完f()后會(huì)增加step，等2個(gè)工作線程都調(diào)用完之后，step的值增加到n * THREAD_NUM后，while()循環(huán)結(jié)束，重置shm_offset，重新開(kāi)始新一輪對(duì)shm的賦值

編譯后執(zhí)行上面的程序，產(chǎn)生如下的結(jié)果：

```
time ./a.out

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

time命令用于時(shí)間測(cè)量，在a.out程序運(yùn)行完成，會(huì)打印耗時(shí)，real行顯式耗時(shí)3.4秒。

改進(jìn)版f_fast

我們稍微修改一下f函數(shù)，改進(jìn)版f函數(shù)取名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循環(huán)里，shm_offset不再是每次增加8字節(jié)（sizeof(long)），而是8*16=128字節(jié)，然后在內(nèi)層的循環(huán)里，依次對(duì)16個(gè)long連續(xù)元素賦值，然后下一輪循環(huán)又再次增加128字節(jié)，直到完成對(duì)整個(gè)shm的賦值。

編譯后重新執(zhí)行程序，結(jié)果顯示耗時(shí)降低到0.06秒，對(duì)比前一種耗時(shí)3.4秒，f_fast性能大幅提升。

```
time ./a.out

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

f和f_fast的行為差異

shm數(shù)組總共有2M個(gè)long元素，因?yàn)?6M / sizeof(long) => 2M，

1. f()函數(shù)行為邏輯

線程1和線程2的work_thread里會(huì)交錯(cuò)地對(duì)shm元素賦值，shm的2M個(gè)long元素，會(huì)順序的一個(gè)接一個(gè)的派給2個(gè)線程去賦值。

例如：

• 可能元素1由線程1賦值，元素2由線程2賦值，然后元素3和元素4由線程1賦值，然后元素5由線程2賦值...
• 每次派元素的時(shí)候，shm_offset都會(huì)atomic的增加8字節(jié)，所以不會(huì)出現(xiàn)2個(gè)線程給1個(gè)元素賦值的情況

2. f_fast()函數(shù)行為邏輯

• 每次派元素的時(shí)候，shm_offset原子性的增加128字節(jié)（16個(gè)元素）
• 這16個(gè)字節(jié)作為一個(gè)整體，派給線程1或者線程2；雖然線程1和線程2還是會(huì)交錯(cuò)的操作shm元素，但是以16個(gè)元素（128字節(jié)）為單元，這16個(gè)連續(xù)的元素不會(huì)被分派到不同線程
• 一次派發(fā)的16個(gè)元素，會(huì)在內(nèi)部循環(huán)里被一個(gè)接著一個(gè)的賦值，在一個(gè)線程里執(zhí)行

為什么f_fast更快？

第一眼感覺(jué)是f_fast()里shm_offset.fetch_add()調(diào)用頻次降低到了原來(lái)的1/16，我們有理由懷疑是原子變量的競(jìng)爭(zhēng)減少導(dǎo)致程序執(zhí)行速度加快。

為了驗(yàn)證，讓我們?cè)趦?nèi)層的循環(huán)里加一個(gè)原子變量test的fetch_add，test原子變量的競(jìng)爭(zhēng)會(huì)像f()函數(shù)里shm_offset.fetch_add()一樣被激烈競(jìng)爭(zhēng)，修改后的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)的調(diào)用被編譯器優(yōu)化掉，我們?cè)趍ain函數(shù)的最后把test的值打印出來(lái)。

編譯后測(cè)試一下，結(jié)果顯示：執(zhí)行時(shí)間只是稍微增加到`real 0m0.326s`。所以，很顯然，并不是atomic的調(diào)用頻次減少導(dǎo)致性能飆升。

我們重新審視f()循環(huán)里的邏輯：f()循環(huán)里的操作很簡(jiǎn)單：原子增加、判斷、賦值。

會(huì)不會(huì)是賦值太慢？

我們把f()的里賦值注釋掉，再測(cè)試一下，發(fā)現(xiàn)它的速度得到了很大提升，看來(lái)是`*(long*)(shm + off) = off;`這一行代碼執(zhí)行慢，但這明明只是一行賦值。

我們把它反匯編來(lái)看，它只是一個(gè)mov指令，源操作數(shù)是寄存器，目標(biāo)操作數(shù)是內(nèi)存地址，從寄存器拷貝數(shù)據(jù)到一個(gè)內(nèi)存地址，而這個(gè)內(nèi)存數(shù)據(jù)應(yīng)該被cache住了，為什么會(huì)這么慢呢？

答案

現(xiàn)在揭曉原因，導(dǎo)致f()性能底下的元兇是偽共享（false sharing），那什么是偽共享？

要說(shuō)清這個(gè)問(wèn)題，還得聯(lián)系CPU的架構(gòu)，以及CPU怎么訪問(wèn)數(shù)據(jù)，我們回顧一下關(guān)于多核Cache結(jié)構(gòu)：

背景知識(shí)

我們知道現(xiàn)代CPU可以有多個(gè)核，每個(gè)核有自己的L1-L2緩存，L1又區(qū)分?jǐn)?shù)據(jù)緩存（L1-DCache）和指令緩存（L1-ICache），L2不區(qū)分?jǐn)?shù)據(jù)和指令Cache，而L3跨核共享，L3通過(guò)內(nèi)存總線連接到內(nèi)存，內(nèi)存被所有CPU所有Core共享。

CPU訪問(wèn)L1 Cache的速度大約是訪問(wèn)內(nèi)存的100倍，Cache作為CPU與內(nèi)存之間的緩存，減少CPU對(duì)內(nèi)存的訪問(wèn)頻率。

從內(nèi)存加載數(shù)據(jù)到Cache的時(shí)候，是以Cache Line為長(zhǎng)度單位的，Cache Line的長(zhǎng)度通常是64字節(jié)。

所以，那怕只讀一個(gè)字節(jié)，但是包含該字節(jié)的整個(gè)Cache Line都會(huì)被加載到緩存，同樣，如果修改一個(gè)字節(jié)，那么最終也會(huì)導(dǎo)致整個(gè)Cache Line被沖刷到內(nèi)存。

如果一塊內(nèi)存數(shù)據(jù)被多個(gè)線程訪問(wèn)，假設(shè)多個(gè)線程在多個(gè)Core上并行執(zhí)行，那么它便會(huì)被加載到多個(gè)Core的的Local Cache中；這些線程在哪個(gè)Core上運(yùn)行，就會(huì)被加載到哪個(gè)Core的Local Cache中，所以，內(nèi)存中的一個(gè)數(shù)據(jù)，在不同Core的Cache里會(huì)同時(shí)存在多份拷貝。

如果我們修改了Core1緩存里的某個(gè)數(shù)據(jù)，則該數(shù)據(jù)所在的Cache Line的狀態(tài)需要同步給其他Core的緩存，Core之間可以通過(guò)核間消息同步狀態(tài)，比如通過(guò)發(fā)送Invalidate消息給其他核，接收到該消息的核會(huì)把對(duì)應(yīng)Cache Line置為無(wú)效，然后重新從內(nèi)存里加載最新數(shù)據(jù)。

被加載到多個(gè)Core緩存中的同一Cache Line，會(huì)被標(biāo)記為共享（Shared）狀態(tài)，對(duì)共享狀態(tài)的緩存行進(jìn)行修改，需要先獲取緩存行的修改權(quán)（獨(dú)占），MESI協(xié)議用來(lái)保證多核緩存的一致性，更多的細(xì)節(jié)可以參考MESI資料。

示例分析

現(xiàn)在來(lái)看看我們的程序。

假設(shè)線程1運(yùn)行在Core1，線程2運(yùn)行在Core2。

因?yàn)閟hm被線程1和線程2這兩個(gè)線程并發(fā)訪問(wèn)，所以shm的內(nèi)存數(shù)據(jù)會(huì)以Cache Line粒度，被同時(shí)加載到2個(gè)Core的Cache，因?yàn)楸欢嗪斯蚕?，所以該Cache Line被標(biāo)注為Shared狀態(tài)。

假設(shè)線程1在offset為64的位置寫(xiě)入了一個(gè)8字節(jié)的數(shù)據(jù)（sizeof(long)），要修改一個(gè)狀態(tài)為Shared的Cache Line，Core1會(huì)發(fā)送核間通信消息到Core2，去拿到該Cache Line的獨(dú)占權(quán)，在這之后，Core1才能修改Local Cache。

線程1執(zhí)行完`shm_offset.fetch_add(sizeof(long))`后，shm_offset會(huì)增加到72。

這時(shí)候Core2上運(yùn)行的線程2也會(huì)執(zhí)行`shm_offset.fetch_add(sizeof(long))`，它返回72并將shm_offset增加到80。

線程2接下來(lái)要修改shm[72]的內(nèi)存位置，因?yàn)閟hm[64]和shm[72]在一個(gè)Cache Line，而這個(gè)Cache Line又被置為Invalidate，所以，它需要從內(nèi)存里重新加載這一個(gè)Cache Line，而在這之前，Core1上的線程1需要把Cache Line沖刷到內(nèi)存，這樣線程2才能加載最新的數(shù)據(jù)。

這種交替執(zhí)行模式，相當(dāng)于Core1和Core2之間需要頻繁的發(fā)送核間消息，收到消息的Core的對(duì)應(yīng)Cache Line被置為無(wú)效，并重新從內(nèi)存里加載數(shù)據(jù)到Cache，每次修改后都需要把Cache中的數(shù)據(jù)刷入內(nèi)存。

這其實(shí)相當(dāng)于廢棄掉了Cache，因?yàn)槊看巫x寫(xiě)都直接跟內(nèi)存打交道，Cache的作用不復(fù)存在，性能下降。

多核多線程程序，因?yàn)椴l(fā)讀寫(xiě)同一個(gè)Cache Line的數(shù)據(jù)（臨近位置的內(nèi)存數(shù)據(jù)），導(dǎo)致Cache Line的頻繁失效，內(nèi)存的頻繁Load/Store，從而導(dǎo)致性能急劇下降的現(xiàn)象叫偽共享，偽共享是性能殺手。

另一個(gè)偽共享的例子

假設(shè)線程x和y，分別修改Data的a和b變量，如果被頻繁調(diào)用，根據(jù)前面的分析，也會(huì)出現(xiàn)性能低下的情況，怎么規(guī)避呢？

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

Data data; // global

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

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

**空間換時(shí)間**

避免Cache偽共享導(dǎo)致性能下降的思路是用空間換時(shí)間，通過(guò)在a和b成員之間增加填充，讓a、b兩個(gè)變量分布到不同的Cache Line，這樣對(duì)a和b的修改就會(huì)作用于不同Cache Line，就能避免Cache line失效的問(wèn)題。

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

在Linux kernel中存在__cacheline_aligned_in_smp宏定義用于解決false sharing問(wèn)題。

```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）系統(tǒng)里，該宏定義是 __cacheline_aligned，也就是Cache Line的大小
• 在單核系統(tǒng)里，該宏定義是空的

偽共享的疑問(wèn)

既然多CPU多核并發(fā)讀寫(xiě)一個(gè)Cache Line里的內(nèi)存數(shù)據(jù)，會(huì)出現(xiàn)偽共享，那么，我們對(duì)`atomic<size_t> shm_offset`的fetch_add()操作也滿足這個(gè)條件，多個(gè)線程同時(shí)對(duì)同一個(gè)shm_offset變量并發(fā)讀寫(xiě)，那為什么性能不會(huì)很差呢？

我們反匯編發(fā)現(xiàn)`atomic.fetch_add`會(huì)被翻譯成`lock; xadd %rax (%rdx)`，lock是一個(gè)指令前綴，配合其他指令使用。

bus lock做的事情就是鎖住總線，然后執(zhí)行后面的xadd，在此期間，別的線程都不能訪問(wèn)任何內(nèi)存數(shù)據(jù)。

實(shí)際上，鎖總線的操作比較重，相當(dāng)于全局的內(nèi)存總線鎖，lock前綴之后的指令操作就直接作用于內(nèi)存，bypass掉緩存，lock也相當(dāng)于內(nèi)存屏障。

但翻看Intel手冊(cè)發(fā)現(xiàn)，執(zhí)行l(wèi)ock指令，CPU會(huì)根據(jù)情況自行決定到底是鎖緩存，還是assert #LOCK signal（鎖總線）。

如果訪問(wèn)的內(nèi)存區(qū)域已經(jīng)緩存在處理器的緩存行中，Intel的現(xiàn)代處理器則不會(huì)assert #LOCK信號(hào)，它會(huì)對(duì)CPU的緩存中的緩存行進(jìn)行鎖定，在鎖定期間，其它CPU不能同時(shí)緩存此數(shù)據(jù)，在修改之后，通過(guò)緩存一致性協(xié)議來(lái)保證修改的原子性，這個(gè)操作被稱(chēng)為“緩存鎖”。

false sharing對(duì)應(yīng)的是多線程同時(shí)讀寫(xiě)一個(gè)Cache Line的多個(gè)數(shù)據(jù)，Core-A修改數(shù)據(jù)x后，會(huì)置Cache Line為Invalid，Core-B讀該緩存行的另一個(gè)數(shù)據(jù)y，需要Core-A把Cache Line Store到內(nèi)存，Core-B再?gòu)膬?nèi)存里L(fēng)oad對(duì)應(yīng)Cache Line，數(shù)據(jù)要過(guò)內(nèi)存。

而atomic，多個(gè)線程修改的是同一個(gè)變量。lock指令前綴，應(yīng)該會(huì)用到緩存鎖（鎖Cache Line），atomic在Cache Line里的最新值通過(guò)核間消息發(fā)送給其他核就可以了，不需要頻繁的Store/Load，所以性能不會(huì)那么糟。