|
本文較長，請耐心讀完，你一定會有收獲！ 本文以C語言為例，但是文中涉及到的原理和方法，適合所有編程語言！ 先看第一個，多線程的例子。 兩個幾乎一模一樣的程序
 程序很簡單，聲明了一個結構體，并定義一個全局變量data，然后創(chuàng)建兩個線程，thread_1給data.a字段賦值，thread_2給data.b字段賦值，每個線程各循環(huán)10億次。
 和test1.c唯一的區(qū)別是交換了結構體中字段b和字段data的位置。 不可思議的性能差異現(xiàn)在分別編譯運行test1.c和test2.c，并用time命令測量一下這兩個程序的運行時間：  test1的消耗的時間居然是test2的兩倍！ 兩個幾乎一模一樣的程序，就只是簡單的交換了一下結構體中的兩個字段，卻有著不可思議的性能差異！為什么？ 建議先不要繼續(xù)往下讀，請先花一分鐘時間，仔細思考一下，可能是什么原因呢？ 如果你能不假思索地給出答案，并且和后文中的解釋是不謀而合的，說明你對計算機系統(tǒng)底層原理已經(jīng)有了相當程度的了解！如果思考之后，暫時還不能給出答案，也不必著急，后文會詳細講解！ 重要說明由于涉及到計算機系統(tǒng)比較底層的知識，為了盡可能的講解清楚，有必要先補充一些關于現(xiàn)代計算機存儲系統(tǒng)相關的背景知識，這也是理解這個問題的關鍵所在。不管你是否已經(jīng)對此非常熟悉，建議都仔細看下。 為方便大家理解，我會盡量以白話的形式進行講解，盡可能避免枯燥無味的純理論描述。 存儲金字塔相信不少人都聽過“存儲金字塔”這個詞，或者至少見過類似下面這張圖：  這張圖很直觀的描述了現(xiàn)代計算機系統(tǒng)的分級存儲模型。 可以認為CPU就位于金字塔的頂點上，越靠近塔頂，離CPU越近，訪問速度越快，但生產(chǎn)成本越高，相應的容量也就越小。在所有存儲器中，寄存器直接內(nèi)嵌在CPU中，訪問速度最快，容量也最小，一般CPU上也就最多幾十個通用寄存器供應用程序使用。 反之，越往下靠近塔底，訪問速度越慢，生產(chǎn)成本越低，相應的容量也就越大。比如圖中最底部的網(wǎng)絡存儲設備，相對其他存儲設備而言是訪問速度最慢的，但其容量卻幾乎可以認為是無限制的。 那么，這種金字塔式結構中，不同層級的存儲設備之間究竟是如何協(xié)調(diào)工作的呢？ 用一句話概括：高一級的存儲設備，往往是作為低一級存儲設備的緩存來使用的。 簡單來說，系統(tǒng)運行時，為了提升數(shù)據(jù)訪問效率，把程序中最近最經(jīng)常訪問的數(shù)據(jù)，盡可能放到訪問速度更快的高一級存儲器中。這樣一來，每次訪問數(shù)據(jù)時，從金字塔的頂端開始，都先嘗試在高一級存儲器中查找，如果被訪問的數(shù)據(jù)存在且有效，則直接訪問，否則，就逐級到更低級的存儲器中去查找。 這種金字塔式的分級存儲模型之所以能夠以近乎完美的方式運行，實際上都是建立在現(xiàn)代計算機科學中的一個非常重要的理論基礎之上：程序的局部性原理。 局部性原理一個程序的局部性，包含兩個維度：時間局部性和空間局部性。
高速緩存 - Cache根據(jù)常識，我們知道，程序要想被CPU正常執(zhí)行，必須要先被加載到內(nèi)存中。（當然也有例外，有童鞋知道哪些程序不是在內(nèi)存中運行的嗎？歡迎留言討論?。?/p> 但是，內(nèi)存的訪問速度與CPU運行速度相比，要慢好幾個數(shù)量級，可以想象一下，如果CPU每次都直接從內(nèi)存中存取數(shù)據(jù)，會造成大量的計算資源浪費，程序性能嚴重受損，假如真是這樣的話，你還能像現(xiàn)在這樣愉快的吃雞嗎？ 為了解決CPU和內(nèi)存之間速度嚴重不匹配的問題，在CPU和內(nèi)存之間設計了高速緩存，即Cache。  目前，主流CPU一般都有三級（或更多級）的Cache，依次是L1 Cache、L2 Cache、L3 Cache。其中L1 Cache速度最快，幾乎可以和內(nèi)嵌在CPU中的寄存器媲美，容量也最小，而L3 Cache速度最慢（但仍然比內(nèi)存快很多），但容量最大。 CPU讀取數(shù)據(jù)時，會在L1、L2、L3Cache中逐級查找，如果找到，就從Cache直接讀取，找不到再從內(nèi)存讀取，并且把數(shù)據(jù)存放到Cache中，以便提高下次訪問的效率。 在這個過程中，如果在Cache中找到所需數(shù)據(jù)，稱為Cache命中(Cache Hit), 找不到稱為Cache未命中(Cache Miss)。 不難看出，L1 Cache命中的時候，讀取數(shù)據(jù)最快，性能最好，而當L1、L2、L3 Cache全部未命中時，就必須要直接從內(nèi)存中讀取數(shù)據(jù)，性能最差！ Cache LineCache Line 是 Cache和內(nèi)存之間進行數(shù)據(jù)傳輸?shù)淖钚挝弧?/span> 根據(jù)上文講解的程序的局部性原理，如果一個數(shù)據(jù)被CPU訪問了，那么這個數(shù)據(jù)相鄰的其他數(shù)據(jù)也很快會被訪問到。因此，為了提高內(nèi)存數(shù)據(jù)的讀取效率，并且最大化利用CPU資源，數(shù)據(jù)在Cache和內(nèi)存之間傳輸時，不是一個字節(jié)一個字節(jié)進行傳輸?shù)?，而是以緩存?Cache Line)為單位進行傳輸?shù)摹?/strong> 不同CPU的Cache line大小可能不同，典型的CPU Cache line大小是64個字節(jié)。 我們通過下面一個簡單的例子，加深一下理解。 Cache Line 實例講解在一個Cache Line大小為64字節(jié)的機器上，定義個數(shù)組： int a[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};我們假設數(shù)組a的起始地址是Cache Line對齊的，可以簡單理解為a的地址能被64整除。假設，數(shù)組a還從來沒有被訪問過，如果此時需要訪問a中的一個元素a[5]，如： 由于在此之前數(shù)組a沒有被訪問過，所以理論上講，數(shù)組a應該只存在于內(nèi)存中，并未被加載到Cache中。因此，此時CPU在Cache中找不到a[5]，觸發(fā)Cache Miss，然后需要從內(nèi)存中讀取數(shù)據(jù)，并更加載到Cache中。 前面提到，Cache和內(nèi)存之間是以Cache Line為單位進行數(shù)據(jù)傳輸?shù)?，因此，這里會把一個Cache line大?。?4字節(jié)）的數(shù)據(jù)從內(nèi)存讀取出來加載到Cache中。由于a的起始地址恰巧是Cache line對齊的，所以CPU會把整個數(shù)組（64個字節(jié)，剛好一個Cache Line）都加載到Cache中。 緊接著，如果再訪問數(shù)組a的元素，如： int y = a[10];此時，整個數(shù)組都在Cache中，所以CPU在訪問時，觸發(fā)Cache Hit，直接從Cache讀取數(shù)據(jù)即可，不需要再從內(nèi)存中讀取。 下面，用一個簡單的例子，直觀感受下Cache對程序性能究竟能有多大！ Cache 對程序性能影響有多大定義一個同樣大小的二維數(shù)組，然后循環(huán)遍歷，對數(shù)組元素賦值。
 編譯運行，并用time命令統(tǒng)計一下運行時間：  array1用時0.528秒，array2用時10.310秒。array2耗時居然是array1的將近20倍！ 有沒有被這個結果震驚到！ 為什么會有如此之大的性能差異呢？ 先不要往下看，花一分鐘時間，結合上面講到的知識，先自己仔細思考一下，看能否想明白呢？ 按行訪問和按列訪問的差異 - CacheC語言的數(shù)組，所有元素是存放在地址連續(xù)的內(nèi)存中的，此外，C語言的多維數(shù)組，是按行進行存儲的。 array1.c按行對數(shù)組進行訪問，也就是從數(shù)組起始地址開始，一直連續(xù)訪問到數(shù)組的最后一個元素的地址處。第一次訪問一個Cache Line的首個元素時，觸發(fā)Cache Miss，與該元素臨近的幾個元素會組成一個Cache Line，被一起加載到Cache中。如此，在訪問下一個元素的時候，就會Cache Hit，直接從Cache讀取數(shù)據(jù)即可。 而array2.c按列對數(shù)組進行訪問，因此并不是按照連續(xù)地址進行訪問的，而是每次間隔10240 * 4個字節(jié)進行訪問。第一次訪問一個Cache Line的首個元素時，假設地址為x，盡管該元素臨近的一個Cache Line大小的元素也會被一起加載進Cache中，但是程序接下來訪問的并不是臨近的元素，而是地址為x + 10240 * 4處的元素，因此會再次觸發(fā)Cache Miss。而當程序回過頭來訪問x + 4地址處的元素時，這個Cache Line可能已經(jīng)被其他數(shù)據(jù)沖刷掉了。因為，盡管Cache會盡量緩存最近訪問過的數(shù)據(jù)，但畢竟大小有限，當Cache被占滿時，一些舊的數(shù)據(jù)就會被沖刷替換掉。 可以看出，無論是時間局部性還是空間局部性，array1.c都要比array2.c好很多！相比array1.c，array2.c會觸發(fā)大量的Cache Miss，這也是為什么array2的性能會如此之差！ 前面討論的都是單CPU系統(tǒng)，在多CPU系統(tǒng)上，情況會更加復雜。 多CPU系統(tǒng)上的Cache在SMP(對稱多處理器)系統(tǒng)中，每個CPU core都有自己的本地Cache。如下圖所示：  在上圖中，每個CPU Core都有自己的獨立的L1 Cache，Core 0和Core 1共享L2 Cache，Core 2和Core 3共享L2 Cache，而L3 Cache則是在所有的CPU core之間共享。 Cache一致性因此，在多CPU系統(tǒng)上，同一個地址的數(shù)據(jù)，比如同一個變量，有可能在多個CPU的本地Cache中存在多分拷貝。既然同一數(shù)據(jù)存在多分拷貝，那么就必然存在數(shù)據(jù)一致性問題。 簡單來說，就是必須要保證，在任意時間點，所有CPU看到的同一個地址的數(shù)據(jù)，必須是一樣的。換言之，就是必須要保證每個CPU的本地Cache中的數(shù)據(jù)，能夠如實反映內(nèi)存中數(shù)據(jù)的真實的值。 假設內(nèi)存中一個變量A = 1, 在CPU 0 和CPU 1的本地Cache中都有一份拷貝A0 = 1 和 A1 = 1。 如果此時CPU 0需要修改變量的值，至少需要這些操作：
CPU為了保證Cache的一致性，實現(xiàn)了非常復雜的Cache一致性協(xié)議，感興趣的童鞋可以去了解下MESI協(xié)議，這里不再贅述。（文末推薦了一本書，強烈推薦看下?。?/strong> 有了這些背景知識，現(xiàn)在不妨花一分鐘時間，自己思考下，看文章開頭的那個問題能否想明白呢：為什么交換了結構體的兩個字段，性能就會相差這么大呢？ 交換結構體的兩個字段，為什么性能差異這么大？再看一下兩個程序代碼：
 這兩個程序幾乎一模一樣：有兩個線程，分別訪問一個struct全局變量的兩個不同字段。唯一的區(qū)別是： test1.c中，兩個線程訪問的兩個字段是相鄰的： test2.c中，這兩個字段是分開的 看起來，test1.c中兩個字段a和b緊挨著的，按道理說，空間局部性應該更好，對吧？那為什么它的性能會比test2.c差那么多呢？ 其實，這是由于CPU為了保證Cache的一致性，而引起的Cache偽共享問題！ Cache偽共享(Cache False Sharing)問題所謂Cache Line 偽共享，是由于運行在不同CPU上的不同線程，同時修改同一個Cache Line上的數(shù)據(jù)，導致Cache Line失效，從而引起頻繁的Cache Miss。 數(shù)據(jù)在Cache和內(nèi)存直接傳輸時以Cache Line為單位的，所以，即便每個CPU各自修改的是不同的變量，但只要這些變量是在同一個Cache Line上的，那么一個CPU修改了這個Cashe Line之后，為了Cache一致性，必然會導致另外一個CPU的本地Cache中的同一個Cache Line無效，進而引發(fā)Cache Miss。 運行于不同CPU的多個線程，如果頻繁修改位于同一個Cache Line上的數(shù)據(jù)（即便不是同一個地址的數(shù)據(jù)），必然會導致大量Cache Miss，嚴重降低程序性能。 分析性能差異的真正原因test1.c中，字段a和b在同一個Cache Line上，運行于不同CPU的兩個線程同時修改這兩個字段時，會相互導致對方CPU的本地Cache Line頻繁失效，觸發(fā)大量Cache Miss，從而性能非常差！ test2.c中，字段a和b中間隔了一個64字節(jié)的數(shù)組，從而確保了data.a和data.b分別處在不同的Cache Line上。如此一來，即便是兩個線程同時修改這兩個字段，但是他們是不同的Cache Line，也不會相互干擾，大大提高Cache命中率，甚至幾乎不會出現(xiàn)Cache Miss，這就是為什么會有如此巨大的性能提升！ 如何檢測Cache偽共享在Linux上，可以使用perf c2c工具來檢測和分析Cache偽共享的問題，篇幅所限，不在展開介紹，感興趣的童鞋可以查看相關手冊，或留言討論！ 思考題
|
|
|
來自： 鹵煮炒肝大腰子 > 《好想好想小雞小雞》
