好久沒(méi)有寫(xiě)一些微觀方面的文章了，今天寫(xiě)一篇關(guān)于CPU Cache相關(guān)的文章，這篇文章會(huì)講述一些多核 CPU 的系統(tǒng)架構(gòu)以及其原理，包括對(duì)程序性能上的影響，以及在進(jìn)行并發(fā)編程的時(shí)候需要注意到的一些問(wèn)題。這篇文章我會(huì)盡量地寫(xiě)簡(jiǎn)單和通俗易懂一些，主要是講清楚相關(guān)的原理和問(wèn)題，而對(duì)于一些細(xì)節(jié)和延伸閱讀我會(huì)在文章最好給出相關(guān)的資源。

本文比較長(zhǎng)，主要分成這么幾個(gè)部分：基礎(chǔ)知識(shí)、緩存的命中、緩存的一致性、相關(guān)的代碼示例和延伸閱讀。

因?yàn)闊o(wú)論你寫(xiě)什么樣的代碼都會(huì)交給CPU來(lái)執(zhí)行，所以，如果你想寫(xiě)出性能比較高的代碼，這篇文章中的技術(shù)還是應(yīng)該認(rèn)真學(xué)習(xí)的。

基礎(chǔ)知識(shí)

首先，我們都知道現(xiàn)在的CPU多核技術(shù)，都會(huì)有幾級(jí)緩存，老的CPU會(huì)有兩級(jí)內(nèi)存（L1和L2），新的CPU會(huì)有三級(jí)內(nèi)存（L1，L2，L3 ），如下圖所示：

其中：

L1緩分成兩種，一種是指令緩存，一種是數(shù)據(jù)緩存。L2緩存和L3緩存不分指令和數(shù)據(jù)。

L1和L2緩存在第一個(gè)CPU核中，L3則是所有CPU核心共享的內(nèi)存。

L1、L2、L3的越離CPU近就越小，速度也越快，越離CPU遠(yuǎn)，速度也越慢。

再往后面就是內(nèi)存，內(nèi)存的后面就是硬盤(pán)。我們來(lái)看一些他們的速度：

L1 的存取速度： 4 個(gè)CPU時(shí)鐘周期

L2 的存取速度： 11 個(gè)CPU時(shí)鐘周期

L3 的存取速度： 39 個(gè)CPU時(shí)鐘周期

RAM內(nèi)存的存取速度 ：107 個(gè)CPU時(shí)鐘周期

我們可以看到，L1的速度是RAM的27倍，但是L1/L2的大小基本上也就是KB級(jí)別的，L3會(huì)是MB級(jí)別的。例如： Intel Core i7-8700K ，是一個(gè)6核的CPU，每核上的L1是64KB（數(shù)據(jù)和指令各32KB），L2 是 256K，L3有12MB（我的蘋(píng)果電腦是 Intel Core i9-8950HK ，和Core i7-8700K的Cache大小一樣）。

于是我們的數(shù)據(jù)就從內(nèi)存向上，先到L3，再到L2，再到L1，最后到寄存器進(jìn)行CPU計(jì)算。為什么會(huì)設(shè)計(jì)成三層？這里有下面幾個(gè)方面的考慮：

一個(gè)方面是物理速度，如果你要更在的容量就需要更多的晶體管，除了芯片的體積會(huì)變大，更重要的是大量的晶體管會(huì)導(dǎo)致速度下降，因?yàn)樵L問(wèn)速度和要訪問(wèn)的晶體管的位置成反比，也就是當(dāng)信號(hào)路徑變長(zhǎng)時(shí)，通信速度會(huì)變慢。這部分是物理問(wèn)題。

另外一個(gè)問(wèn)題是，多核技術(shù)中，數(shù)據(jù)的狀態(tài)需要在多個(gè)CPU中進(jìn)行同步，并且，我們可以看到，cache和RAM的速度差距太大，所以，多級(jí)不同尺寸的緩存有利于提高整體的性能。

這個(gè)世界永遠(yuǎn)是平衡的，一面變得有多光鮮，另一面也會(huì)變得有多黑暗。建立這么多級(jí)的緩存，一定就會(huì)引入其它的問(wèn)題，這里有兩個(gè)比較重要的問(wèn)題，

一個(gè)是比較簡(jiǎn)單的緩存的命中率的問(wèn)題。

另一個(gè)是比較復(fù)雜的緩存更新的一致性問(wèn)題。

尤其是第二個(gè)問(wèn)題，在多核技術(shù)下，這就很像分布式的系統(tǒng)了，要對(duì)多個(gè)地方進(jìn)行更新。

緩存的命中

在說(shuō)明這兩個(gè)問(wèn)題之前。我們需要要解一個(gè)術(shù)語(yǔ) Cache Line。緩存基本上來(lái)說(shuō)就是把后面的數(shù)據(jù)加載到離自己進(jìn)的地方，對(duì)于CPU來(lái)說(shuō)，它是不會(huì)一個(gè)字節(jié)一個(gè)字節(jié)的加載的，因?yàn)檫@非常沒(méi)有效率，一般來(lái)說(shuō)都是要一塊一塊的加載的，在CPU的緩存技術(shù)中，這個(gè)術(shù)語(yǔ)叫“Cache Line”（有的中文編譯成“緩存線”），一般來(lái)說(shuō)，一個(gè)主流的CPU的Cache Line 是 64 Bytes（也有的CPU用32Bytes和128Bytes），也就是16個(gè)32位的整型。也就是說(shuō)，CPU從內(nèi)存中撈數(shù)據(jù)上來(lái)的最小數(shù)據(jù)單位。

比如：Cache Line是最小單位（64Bytes），所以先把Cache分布多個(gè)Cache Line，比如：L1有32KB，那么，32KB/64B = 500 個(gè) Cache Line。

一方面，緩存需要把內(nèi)存里的數(shù)據(jù)放到放進(jìn)來(lái)，英文叫 CPU Associativity。Cache的數(shù)據(jù)放置的策略決定了內(nèi)存中的數(shù)據(jù)塊會(huì)拷貝到CPU Cache中的哪個(gè)位置，因?yàn)镃ache的大小遠(yuǎn)遠(yuǎn)小于內(nèi)存，所以，需要有一種地址關(guān)聯(lián)的算法，能夠讓內(nèi)存中的數(shù)據(jù)可以被映射到cache中來(lái)。這個(gè)有點(diǎn)像內(nèi)存管理的方法。

基本上來(lái)說(shuō)，我們會(huì)有如下的一些方法。

一種方法是，任何一個(gè)內(nèi)存地址的數(shù)據(jù)可以被緩存在任何一個(gè)Cache Line里，這種方法是最靈活的，但是，如果我們要知道一個(gè)內(nèi)存是否存在于Cache中，我們就需要進(jìn)行O（n）復(fù)雜度的Cache遍歷，這是很沒(méi)有效率的。

另一種方法，為了降低緩存搜索算法，我們需要使用像Hash Table這樣的數(shù)據(jù)結(jié)構(gòu)，最簡(jiǎn)單的hash table就是做“求模運(yùn)算”，比如：我們的L1 Cache有500個(gè)Cache Line，那么，公式：`（內(nèi)存地址 mod 500）x 64` 就可以直接找到所在的Cache地址的偏移了。但是，這樣的方式需要我們的程序?qū)?nèi)存地址的訪問(wèn)要非常地平均，這成了一種非常理想的情況了。

為了避免上述的兩種方案的問(wèn)題，于是就要容忍一定的hash沖突，也就出現(xiàn)了 N-Way 關(guān)聯(lián)。也就是把連續(xù)的N個(gè)Cache Line綁成一組，然后，先把找到相關(guān)的組，然后再在這個(gè)組內(nèi)找到相關(guān)的Cache Line。

那么，Cache的命中率會(huì)成為程序運(yùn)行性能非常關(guān)鍵的事，所以，了解上面的這些東西，會(huì)有利于我們知道在什么情況下有可以導(dǎo)致緩存的失效。

對(duì)于 N-Way 關(guān)聯(lián)我們?nèi)€(gè)例子，并多說(shuō)一些細(xì)節(jié)（因?yàn)楹竺鏁?huì)用到），Intel 大多數(shù)處理器的L1 Cache都是32KB，8-Way 組相聯(lián)，Cache Line 是64 Bytes。于是，

32KB的可以分成，32KB / 64 = 512 條 Cache Line。

因?yàn)橛? Way，于是會(huì)每一Way 有 512 / 8 = 64 條 Cache Line。

于是每一路就有 64 x 64 = 4096 Byts 的內(nèi)存。

為了方便索引內(nèi)存地址，

Tag ：每條 Cache Line 前都會(huì)有一個(gè)獨(dú)立分配的 24 bits來(lái)存的 tag，其就是內(nèi)存地址的前24bits

Index ：內(nèi)存地址后續(xù)的6個(gè)bits則是在這一Way的是Cache Line 索引，2^6 = 64 剛好可以索引64條Cache Line

Offset ：再往后的6bits用于表示在Cache Line 里的偏移量

如下圖所示：（更多的細(xì)節(jié)可以讀一下《 Cache： a place for concealment and safekeeping 》）

（圖片來(lái)自《 Cache： a place for concealment and safekeeping 》）

這意味著：

L1 Cache 可映射 36bits 的內(nèi)存地址，一共 2^36 = 64GB的內(nèi)存

因?yàn)橹灰^24bits相同就會(huì)被映射到同一個(gè)Way中，所以，每4096個(gè)地址會(huì)放在一Way中。

當(dāng)CPU要訪問(wèn)一個(gè)內(nèi)存的時(shí)候，通過(guò)這個(gè)內(nèi)存的前24bits 和中間的6bits可以直接定位相應(yīng)的Cache Line。

此外，當(dāng)有數(shù)據(jù)沒(méi)有命中緩存的時(shí)候，CPU就會(huì)以最小為Cache Line的單元向內(nèi)存更新數(shù)據(jù)。當(dāng)然，CPU并不一定只是更新64Bytes，因?yàn)樵L問(wèn)主存是在是太慢了，所以，一般都會(huì)多更新一些。好的CPU會(huì)有一些預(yù)測(cè)的技術(shù)，如果找到一種pattern的話，就會(huì)預(yù)先加載更多的內(nèi)存，包括指令也可以預(yù)加載。這叫 Prefetching 技術(shù) （參看，Wikipedia 的 Cache Prefetching 和 紐約州立大學(xué)的 Memory Prefetching ）。比如，你在for-loop訪問(wèn)一個(gè)連續(xù)的數(shù)組，你的步長(zhǎng)是一個(gè)固定的數(shù)，內(nèi)存就可以做到prefetching。（注：指令也是以預(yù)加載的方式執(zhí)行，參看本站的《 代碼執(zhí)行的效率 》中的第三個(gè)示例）

緩存的一致性

對(duì)于主流的CPU來(lái)說(shuō)，緩存的寫(xiě)操作基本上是兩種策略（參看本站《 緩存更新的套路 》），

一種是Write Back，寫(xiě)操作只要在cache上，然后再flush到內(nèi)存上。

一種是Write Through，寫(xiě)操作同時(shí)寫(xiě)到cache和內(nèi)存上。

為了提高寫(xiě)的性能，一般來(lái)說(shuō)，主流的CPU（如：Intel Core i7/i9）采用的是Write Back的策略，因?yàn)橹苯訉?xiě)內(nèi)存實(shí)在是太慢了。

好了，現(xiàn)在問(wèn)題來(lái)了，如果有一個(gè)數(shù)據(jù) x 在 CPU 第0核的緩存上被更新了，那么其它CPU核上對(duì)于這個(gè)數(shù)據(jù) x 的值也要被更新，這就是緩存一致性的問(wèn)題。（當(dāng)然，對(duì)于我們上層的程序我們不用關(guān)心CPU多個(gè)核的緩存是怎么同步的，這對(duì)上層都是透明的）

一般來(lái)說(shuō)，在CPU硬件上，會(huì)有兩種方法來(lái)解決這個(gè)問(wèn)題。

Directory 協(xié)議 。這種方法的典型實(shí)現(xiàn)是要設(shè)計(jì)一個(gè)集中式控制器，它是主存儲(chǔ)器控制器的一部分。其中有一個(gè)目錄存儲(chǔ)在主存儲(chǔ)器中，其中包含有關(guān)各種本地緩存內(nèi)容的全局狀態(tài)信息。當(dāng)單個(gè)CPU Cache 發(fā)出讀寫(xiě)請(qǐng)求時(shí)，這個(gè)集中式控制器會(huì)檢查并發(fā)出必要的命令，以在主存和CPU Cache之間或在CPU Cache自身之間進(jìn)行數(shù)據(jù)同步和傳輸。

Snoopy 協(xié)議 。這種協(xié)議更像是一種數(shù)據(jù)通知的總線型的技術(shù)。CPU Cache通過(guò)這個(gè)協(xié)議可以識(shí)別其它Cache上的數(shù)據(jù)狀態(tài)。如果有數(shù)據(jù)共享的話，可以通過(guò)廣播機(jī)制將共享數(shù)據(jù)的狀態(tài)通知給其它CPU Cache。這個(gè)協(xié)議要求每個(gè)CPU Cache 都可以 “窺探” 數(shù)據(jù)事件的通知并做出相應(yīng)的反應(yīng)。

因?yàn)镈irectory協(xié)議是一個(gè)中心式的，會(huì)有性能瓶頸，而且會(huì)增加整體設(shè)計(jì)的復(fù)雜度。而Snoopy協(xié)議更像是微服務(wù)+消息通訊，所以，現(xiàn)在基本都是使用Snoopy的總線的設(shè)計(jì)。

這里，我想多寫(xiě)一些細(xì)節(jié)，因?yàn)檫@種微觀的東西，不自然就就會(huì)更分布式系統(tǒng)相關(guān)聯(lián)，在分布式系統(tǒng)中我們一般用Paxos/Raft這樣的分布式一致性的算法。而在CPU的微觀世界里，則不必使用這樣的算法，原因是因?yàn)镃PU的多個(gè)核的硬件不必考慮網(wǎng)絡(luò)會(huì)斷會(huì)延遲的問(wèn)題。所以，CPU的多核心緩存間的同步的核心就是要管理好數(shù)據(jù)的狀態(tài)就好了。

這里介紹幾個(gè)狀態(tài)協(xié)議，先從最簡(jiǎn)單的開(kāi)始，MESI協(xié)議，這個(gè)協(xié)議跟那個(gè)著名的足球運(yùn)動(dòng)員梅西沒(méi)什么關(guān)系，其主要表示緩存數(shù)據(jù)有四個(gè)狀態(tài)：Modified（已修改）， Exclusive（獨(dú)占的），Shared（共享的），Invalid（無(wú)效的）。

這些狀態(tài)的狀態(tài)機(jī)如下所示：

下面是個(gè)示例（如果你想看一下動(dòng)畫(huà)演示的話，這里有一個(gè)網(wǎng)頁(yè)（ MESI Interactive Animations ），你可以進(jìn)行交互操作，這個(gè)動(dòng)畫(huà)演示中使用的Write Through算法）：

當(dāng)前操作CPU0CPU1Memory說(shuō)明1） CPU0 read（x）x=1 （E）x=1只有一個(gè)CPU有 x 變量，

所以，狀態(tài)是 Exclusive2） CPU1 read（x）x=1 （S）x=1（S）x=1有兩個(gè)CPU都讀取 x 變量，

所以狀態(tài)變成 Shared3） CPU0 write（x，9）x= 9 （M）x=1（I）x=1變量改變，在CPU0中狀態(tài)

變成 Modified，在CPU1中

狀態(tài)變成 Invalid4） 變量 x 寫(xiě)回內(nèi)存x=9 （M）X=1（I）x=9目前的狀態(tài)不變5） CPU1 read（x）x=9 （S）x=9（S）x=9變量同步到所有的Cache中，

狀態(tài)回到Shared

MESI 這種協(xié)議在數(shù)據(jù)更新后，會(huì)標(biāo)記其它共享的CPU緩存的數(shù)據(jù)拷貝為Invalid狀態(tài)，然后當(dāng)其它CPU再次read的時(shí)候，就會(huì)出現(xiàn) cache misses 的問(wèn)題，此時(shí)再?gòu)膬?nèi)存中更新數(shù)據(jù)?？梢?jiàn)，從內(nèi)存中更新數(shù)據(jù)意味著20倍速度的降低。我們能不直接從我隔壁的CPU緩存中更新？是的，這就可以增加很多速度了，但是狀態(tài)控制也就變麻煩了。還需要多來(lái)一個(gè)狀態(tài)：Owner（宿主），用于標(biāo)記，我是更新數(shù)據(jù)的源。于是，現(xiàn)了 MOESI 協(xié)議

MOESI協(xié)議的狀態(tài)機(jī)和演示我就不貼了，我們只需要理解MOESI協(xié)議允許 CPU Cache 間同步數(shù)據(jù)，于是也降低了對(duì)內(nèi)存的操作，性能是非常大的提升，但是控制邏輯也非常復(fù)雜。

順便說(shuō)一下，與 MOESI 協(xié)議類(lèi)似的一個(gè)協(xié)議是 MESIF ，其中的 F 是 Forward，同樣是把更新過(guò)的數(shù)據(jù)轉(zhuǎn)發(fā)給別的 CPU Cache 但是，MOESI 中的 Owner 狀態(tài) 和MESIF 中的 Forward 狀態(tài)有一個(gè)非常大的不一樣—— Owner狀態(tài)下的數(shù)據(jù)是dirty的，還沒(méi)有寫(xiě)回內(nèi)存，F(xiàn)orward狀態(tài)下的數(shù)據(jù)是clean的，可以丟棄而不用另行通知。

需要說(shuō)明的是，AMD用MOESI，Intel用MESIF。所以，F(xiàn) 狀態(tài)主要是針對(duì) CPU L3 Cache 設(shè)計(jì)的（前面我們說(shuō)過(guò)，L3是所有CPU核心共享的）。（相關(guān)的比較可以參看 StackOverlow上這個(gè)問(wèn)題的答案 ）

程序性能

了解了我們上面的這些東西后，我們來(lái)看一下對(duì)于程序的影響。

示例一

首先，假設(shè)我們有一個(gè)64M長(zhǎng)的數(shù)組，設(shè)想一下下面的兩個(gè)循環(huán)：

const int LEN = 64*1024*1024;int *arr = new int［LEN］;for （int i = 0; i 《 LEN; i += 2） arr［i］ *= i;for （int i = 0; i 《 LEN; i += 8） arr［i］ *= i;

按我們的想法來(lái)看，第二個(gè)循環(huán)要比第一個(gè)循環(huán)少4倍的計(jì)算量，其應(yīng)該也是要快4倍的。但實(shí)際跑下來(lái)并不是， 在我的機(jī)器上，第一個(gè)循環(huán)需要127毫秒，第二個(gè)循環(huán)則需要121毫秒，相差無(wú)幾 。這里最主要的原因就是 Cache Line，因?yàn)镃PU會(huì)以一個(gè)Cache Line 64Bytes最小時(shí)單位加載，也就是16個(gè)32bits的整型，所以，無(wú)論你步長(zhǎng)是2還是8，都差不多。而后面的乘法其實(shí)是不耗CPU時(shí)間的。

示例二

我們?cè)賮?lái)看一個(gè)與緩存命中率有關(guān)的代碼，我們以一定的步長(zhǎng) increment 來(lái)訪問(wèn)一個(gè)連續(xù)的數(shù)組。

for （int i = 0; i 《 10000000; i++） { for （int j = 0; j 《 size; j += increment） { memory［j］ += j; }}

我們測(cè)試一下，在下表中， 表頭是步長(zhǎng)，也就是每次跳多少個(gè)整數(shù)，而縱向是這個(gè)數(shù)組可以跳幾次（你可以理解為要幾條Cache Line），于是表中的任何一項(xiàng)代表了這個(gè)數(shù)組有多少，而且步長(zhǎng)是多少。比如：橫軸是 512，縱軸是4，意思是，這個(gè)數(shù)組有 4*512 = 2048 個(gè)長(zhǎng)度，訪問(wèn)時(shí)按512步長(zhǎng)訪問(wèn)，也就是訪問(wèn)其中的這幾項(xiàng)： ［0， 512， 1024， 1536］ 這四項(xiàng)。

表中同的項(xiàng)是，是循環(huán)1000萬(wàn)次的時(shí)間，單位是“微秒”（除以1000后是毫秒）

| count | 1 | 16 | 512 | 1024 |------------------------------------------| 1 | 17539 | 16726 | 15143 | 14477 || 2 | 15420 | 14648 | 13552 | 13343 || 3 | 14716 | 14463 | 15086 | 17509 || 4 | 18976 | 18829 | 18961 | 21645 || 5 | 23693 | 23436 | 74349 | 29796 || 6 | 23264 | 23707 | 27005 | 44103 || 7 | 28574 | 28979 | 33169 | 58759 || 8 | 33155 | 34405 | 39339 | 65182 || 9 | 37088 | 37788 | 49863 |156745 || 10 | 41543 | 42103 | 58533 |215278 || 11 | 47638 | 50329 | 66620 |335603 || 12 | 49759 | 51228 | 75087 |305075 || 13 | 53938 | 53924 | 77790 |366879 || 14 | 58422 | 59565 | 90501 |466368 || 15 | 62161 | 64129 | 90814 |525780 || 16 | 67061 | 66663 | 98734 |440558 || 17 | 71132 | 69753 |171203 |506631 || 18 | 74102 | 73130 |293947 |550920 |

我們可以看到，從［9，1024］ 以后，時(shí)間顯注上升。包括［17，512］ 和 ［18，512］ 也顯注上升。這是因?yàn)?，我機(jī)器的 L1 Cache 是 32KB， 8 Way 的，前面說(shuō)過(guò)，8 Way的一個(gè)組有64個(gè)Cache Line，也就是4096個(gè)字節(jié)，而1024個(gè)整型正好是 4096 Bytes，所以，一旦過(guò)了這個(gè)界，每個(gè)步長(zhǎng)都無(wú)法命中 L1 Cache，每次都是 Cache Miss，所以，導(dǎo)致訪問(wèn)時(shí)間一下子就上升了。而 ［16， 512］也是一樣的，其中的幾步開(kāi)始導(dǎo)致L1 Cache開(kāi)始失效。

示例三

接下來(lái)，我們?cè)賮?lái)看個(gè)示例。下面是一個(gè)二維數(shù)組的兩種遍歷方式，一個(gè)逐行遍歷，一個(gè)是逐列遍歷，這兩種方式在理論上來(lái)說(shuō)，尋址和計(jì)算量都是一樣的，執(zhí)行時(shí)間應(yīng)該也是一樣的。

const int row = 1024;const int col = 512int matrix［row］［col］;//逐行遍歷int sum_row=0;for（int r=0; r《row; r++） { for（int c=0; c《col; c++）{ sum_row += matrix［r］; }}//逐列遍歷int sum_col=0;for（int c=0; c《col; c++） { for（int r=0; r《row; r++）{ sum_col += matrix［r］; }}

然而，并不是，在我的機(jī)器上，得到下面的結(jié)果。

逐行遍歷：0.081ms

逐列遍歷：1.069ms

執(zhí)行時(shí)間有十幾倍的差距。其中的原因，就是逐列遍歷對(duì)于CPU Cache 的運(yùn)作方式并不友好，所以，付出巨大的代價(jià)。

示例四

接下來(lái)，我們來(lái)看一下多核下的性能問(wèn)題，參看如下的代碼。兩個(gè)線程在操作一個(gè)數(shù)組的兩個(gè)不同的元素（無(wú)需加鎖），線程循環(huán)1000萬(wàn)次，做加法操作。在下面的代碼中，我高亮了一行，就是 p2 指針，要么是 p［1］ ，或是 p［18］ ，理論上來(lái)說(shuō)，無(wú)論訪問(wèn)哪兩個(gè)數(shù)組元素，都應(yīng)該是一樣的執(zhí)行時(shí)間。

void fn （int* data） { for（int i = 0; i 《 10*1024*1024; ++i） *data += rand（）;}int p［32］;int *p1 = &p［0］;int *p2 = &p［1］; // int *p2 = &p［30］;thread t1（fn， p1）;thread t2（fn， p2）;

然而，并不是，在我的機(jī)器上執(zhí)行下來(lái)的結(jié)果是：

對(duì)于 p［0］ 和 p［1］ ：560ms

對(duì)于 p［0］ 和 p［30］ ：104ms

這是因?yàn)?p［0］ 和 p［1］ 在同一條 Cache Line 上，而 p［0］ 和 p［30］ 則不可能在同一條Cache Line 上 ，CPU的緩沖最小的更新單位是Cache Line，所以， 這導(dǎo)致雖然兩個(gè)線程在寫(xiě)不同的數(shù)據(jù)，但是因?yàn)檫@兩個(gè)數(shù)據(jù)在同一條Cache Line上，就會(huì)導(dǎo)致緩存需要不斷進(jìn)在兩個(gè)CPU的L1/L2中進(jìn)行同步，從而導(dǎo)致了5倍的時(shí)間差異 。

示例五

接下來(lái)，我們?cè)賮?lái)看一下另外一段代碼：我們想統(tǒng)計(jì)一下一個(gè)數(shù)組中的奇數(shù)個(gè)數(shù)，但是這個(gè)數(shù)組太大了，我們希望可以用多線程來(lái)完成，這個(gè)統(tǒng)計(jì)。下面的代碼中，我們?yōu)槊恳粋€(gè)線程傳入一個(gè) id ，然后通過(guò)這個(gè) id 來(lái)完成對(duì)應(yīng)數(shù)組段的統(tǒng)計(jì)任務(wù)。這樣可以加快整個(gè)處理速度。

int total_size = 16 * 1024 * 1024; //數(shù)組長(zhǎng)度int* test_data = new test_data［total_size］; //數(shù)組int nthread = 6; //線程數(shù)（因?yàn)槲业臋C(jī)器是6核的）int result［nthread］; //收集結(jié)果的數(shù)組void thread_func （int id） { result［id］ = 0; int chunk_size = total_size / nthread + 1; int start = id * chunk_size; int end = min（start + chunk_size， total_size）; for （ int i = start; i 《 end; ++i ） { if （test_data［i］ % 2 ！= 0 ） ++result［id］; }}

然而，在執(zhí)行過(guò)程中，你會(huì)發(fā)現(xiàn)，6個(gè)線程居然跑不過(guò)1個(gè)線程。因?yàn)楦鶕?jù)上面的例子你知道 result［］ 這個(gè)數(shù)組中的數(shù)據(jù)在一個(gè)Cache Line中，所以，所有的線程都會(huì)對(duì)這個(gè) Cache Line 進(jìn)行寫(xiě)操作，導(dǎo)致所有的線程都在不斷地重新同步 result［］ 所在的 Cache Line，所以，導(dǎo)致 6 個(gè)線程還跑不過(guò)一個(gè)線程的結(jié)果。這叫 False Sharing。

優(yōu)化也很簡(jiǎn)單，使用一個(gè)線程內(nèi)的變量。

void thread_func （int id） { result［id］ = 0; int chunk_size = total_size / nthread + 1; int start = id * chunk_size; int end = min（start + chunk_size， total_size）; int c = 0; //使用臨時(shí)變量，沒(méi)有cache line的同步了 for （ int i = start; i 《 end; ++i ） { if （test_data［i］ % 2 ！= 0 ） ++c; } result［id］ = c;}

我們把兩個(gè)程序分別在 1 到 32 個(gè)線程上跑一下，得出的結(jié)果畫(huà)一張圖如下所示：

上圖中，我們可以看到，灰色的曲線就是第一種方法，橙色的就是第二種（用局部變量的）方法。當(dāng)只有一個(gè)線程的時(shí)候，兩個(gè)方法相當(dāng)，而且第二種方法還略差一點(diǎn)，但是在線程數(shù)增加的時(shí)候的時(shí)候，你會(huì)發(fā)現(xiàn)，第二種方法的性能提高的非?？?。直到到達(dá)6個(gè)線程的時(shí)候，開(kāi)始變得穩(wěn)定（前面說(shuō)過(guò)，我的CPU是6核的）。而第一種方法無(wú)論加多少線程也沒(méi)有辦法超過(guò)第二種方法。因?yàn)榈谝环N方法不是CPU Cache 友好的。