導(dǎo)讀： 對于工程經(jīng)驗比較豐富的同學(xué)，并發(fā)應(yīng)該也并不是陌生的概念了，但是每個人所理解的并發(fā)問題，卻又往往并不統(tǒng)一，本文系統(tǒng)梳理了百度C++工程師在進行并發(fā)優(yōu)化時所作的工作。

一、背景

簡單回顧一下，一個程序的性能構(gòu)成要件大概有三個，即算法復(fù)雜度、IO開銷和并發(fā)能力。由于現(xiàn)代計算機體系結(jié)構(gòu)復(fù)雜化，造成很多時候，工程師的性能優(yōu)化會更集中在算法復(fù)雜度之外的另外兩個方向上，即IO和并發(fā)，在之前的《百度C++工程師的那些極限優(yōu)化（內(nèi)存篇）》中，我們介紹了百度C++工程師工程師為了優(yōu)化性能，從內(nèi)存IO角度出發(fā)所做的一些優(yōu)化案例。

這次我們就再來聊一聊另外一個性能優(yōu)化的方向，也就是所謂的并發(fā)優(yōu)化。和IO方向類似，對于工程經(jīng)驗比較豐富的同學(xué)，并發(fā)應(yīng)該也并不是陌生的概念了，但是每個人所理解的并發(fā)問題，卻又往往并不統(tǒng)一。所以下面我們先回到一個更根本的問題，重新梳理一下所謂的并發(fā)優(yōu)化。

二、為什么我們需要并發(fā)？

是的，這個問題可能有些跳躍，但是在自然地進展到如何處理各種并發(fā)問題之前，我們確實需要先停下來，回想一下為什么我們需要并發(fā)？

這時第一個會冒出來的概念可能會是大規(guī)模，例如我們要設(shè)計大規(guī)?；ヂ?lián)網(wǎng)應(yīng)用，大規(guī)模機器學(xué)習(xí)系統(tǒng)。可是我們仔細思考一下，無論使用了那種程度的并發(fā)設(shè)計，這樣的規(guī)?；到y(tǒng)背后，都需要成百上千的實例來支撐。也就是，如果一個設(shè)計（尤其是無狀態(tài)計算服務(wù)設(shè)計）已經(jīng)可以支持某種小規(guī)模業(yè)務(wù)。那么當(dāng)規(guī)模擴大時，很可能手段并不是提升某個業(yè)務(wù)單元的處理能力，而是增加更多業(yè)務(wù)單元，并解決可能遇到的分布式問題。

其實真正讓并發(fā)編程變得有價值的背景，更多是業(yè)務(wù)單元本身的處理能力無法滿足需求，例如一次請求處理時間過久，業(yè)務(wù)精細化導(dǎo)致復(fù)雜度積累提升等等問題。那么又是什么導(dǎo)致了近些年來，業(yè)務(wù)單元處理能力問題不足的問題呈現(xiàn)更加突出的趨勢？

可能下面這個統(tǒng)計會很說明問題：

統(tǒng)計了CPU的核心指標(biāo)參數(shù)趨勢。從其中的晶體管數(shù)目趨勢可以看出，雖然可能逐漸艱難，但是摩爾定律依然尚能維持。然而近十多年，出于控制功耗等因素的考慮，CPU的主頻增長基本已經(jīng)停滯，持續(xù)增加的晶體管轉(zhuǎn)而用來構(gòu)建了更多的核心。

從CPU廠商角度來看，單片處理器所能提供的性能還是保持了持續(xù)提升的，但是單線程的性能增長已經(jīng)顯著放緩。從工程師角度來看，最大的變化是硬件紅利不再能透明地轉(zhuǎn)化成程序的性能提升了。隨時代進步，更精準(zhǔn)的算法，更復(fù)雜的計算需求，都在對的計算性能提出持續(xù)提升的要求。早些年，這些算力的增長需求大部分還可以通過處理器更新?lián)Q代來自然解決，可是隨著主頻增長停滯，如果無法利用多核心來加速，程序的處理性能就會隨主頻一同面臨增長停滯的問題。因此近些年來，是否能夠充分利用多核心計算，也越來越成為高性能程序的一個標(biāo)簽，也只有具備了充分的多核心利用能力，才能隨新型硬件演進，繼續(xù)表現(xiàn)出指數(shù)級的性能提升。而伴隨多核心多線程程序設(shè)計的普及，如何處理好程序的并發(fā)也逐漸成了工程師的一項必要技能。

上圖描述了并發(fā)加速的基本原理，首先是對原始算法的單一執(zhí)行塊拆分成多個能夠同時運行的子任務(wù)，并設(shè)計好子任務(wù)間的協(xié)同。之后利用底層的并行執(zhí)行部件能力，將多個子任務(wù)在時間上真正重疊起來，達到真正提升處理速度的目的。

需要注意的是還有一條從下而上的反向剪頭，主要表達了，為了正確高效地利用并行執(zhí)行部件，往往會反向指導(dǎo)上層的并發(fā)設(shè)計，例如正確地數(shù)據(jù)對齊，合理的臨界區(qū)實現(xiàn)等。雖然加速看似完全是由底層并行執(zhí)行部件的能力所帶來的，程序設(shè)計上只需要做到子任務(wù)拆分即可。但是現(xiàn)階段，執(zhí)行部件對上層還無法達到透明的程度，導(dǎo)致這條反向依賴對于最終的正確性和性能依然至關(guān)重要。既了解算法，又理解底層設(shè)計，并結(jié)合起來實現(xiàn)合理的并發(fā)改造，也就成為了工程師的一項重要技能。

三、單線程中的并行執(zhí)行

提到并行執(zhí)行部件，大家的第一個印象往往時多核心多線程技術(shù)。不過在進入到多線程之前，我們先來看看，即使是單線程的程序設(shè)計中，依然需要關(guān)注的那些并行執(zhí)行能力?；剡^頭再仔細看前文的處理器趨勢圖其實可以發(fā)現(xiàn)，雖然近年主頻不再增長，甚至穩(wěn)中有降，但是單線程處理性能其實還是有細微的提升的。這其實意味著，在單位時鐘周期上，單核心的計算能力依然在提升，而這種提升，很大程度上就得益于單核心單線程內(nèi)的細粒度并行執(zhí)行能力。

3.1 SIMD

其中一個重要的細粒度并行能力就是SIMD（Single Instruction Multiple Data），也就是多個執(zhí)行單元，同時對多個數(shù)據(jù)應(yīng)用相同指令進行計算的模式。在經(jīng)典分類上，一般單核心CPU被歸入SISD（Single Instruction Single Data），而多核心CPU被歸入MIMD（Mingle Instruction Multiple D ata），而GPU才被歸入SIMD的范疇。但是現(xiàn)代CPU上，除了多核心的MIMD基礎(chǔ)模型，也同時附帶了細粒度SIMD計算能力。

上圖是Intel關(guān)于SIMD指令的一個示意圖，通過增加更大位寬的寄存器實現(xiàn)在一個寄存器中，“壓縮”保存多個較小位寬數(shù)據(jù)的能力。再通過增加特殊的運算指令，對寄存器中的每個小位寬的數(shù)據(jù)元素，批量完成某種相同的計算操作，例如圖示中最典型的對位相加運算。以這個對位相加操作為例，CPU只需要增大寄存器，內(nèi)存?zhèn)鬏敽陀嬎悴考粚?，針對這個特殊的應(yīng)用場景，就提升到了8倍的計算性能。相比將核心數(shù)通用地提升到8倍大小，這種方式付出的成本是非常少的，指令流水線系統(tǒng)，緩存系統(tǒng)都做到了復(fù)用。

從CPU發(fā)展的視角來看，為了能夠在單位周期內(nèi)處理更多數(shù)據(jù)，增加核心數(shù)的MIMD強化是最直觀的實現(xiàn)路徑。但是增加一套核心，就意味增加一套 完整的指令部件、流水線部件和緩存部件，而且實際應(yīng)用時，還要考慮額外的核心間數(shù)據(jù)分散和聚合的傳輸和同步開銷。一方面高昂的部件需求， 導(dǎo)致完整的核心擴展成本過高，另一方面，多核心間傳輸和同步的開銷針對小數(shù)據(jù)集場景額外消耗過大，還會進一步限制應(yīng)用范圍。為了最大限度利用好有限的晶體管，現(xiàn)代CPU在塑造更多核心的同時，也在另一個維度上擴展單核心的處理和計算位寬，從而實現(xiàn)提升理論計算性能（核心數(shù) * 數(shù)據(jù)寬度）的目的。

不過提起CPU上的SIMD指令支持，有一個繞不開的話題就是和GPU的對比。CPU上早期SIMD指令集（MMX）的誕生背景，和GPU的功能定位就十分類似，專注于加速圖像相關(guān)算法，近些年又隨著神經(jīng)網(wǎng)絡(luò)計算的興起，轉(zhuǎn)向通用矩陣類計算加速。但是由于GPU在設(shè)計基礎(chǔ)上就以面向密集可重復(fù)計算負(fù)載設(shè)計，指令部件、流水線部件和緩存部件等可以遠比CPU簡潔，也因此更容易在量級上進行擴展。這就導(dǎo)致，當(dāng)計算密度足夠大，數(shù)據(jù)的傳輸和同步開銷被足夠沖淡的情況下（這也是典型神經(jīng)網(wǎng)絡(luò)計算的的特性），CPU僅作為控制流進行指揮，而數(shù)據(jù)批量傳輸?shù)紾PU協(xié)同執(zhí)行反而 會更簡單高效。

由于Intel自身對SIMD指令集的宣傳，也集中圍繞神經(jīng)網(wǎng)絡(luò)類計算來展開，而在當(dāng)前工程實踐經(jīng)驗上，主流的密集計算又以GPU實現(xiàn)為主。這就導(dǎo)致了不少CPU上SIMD指令集無用論應(yīng)運而生，尤其是近兩年Intel在AVX512初代型號上的降頻事件，進一步強化了『CPU就應(yīng)該做好CPU該做的事情』這一論調(diào)。但是單單從這一的視角來認(rèn)識CPU上的SIMD指令又未免有些片面，容易忽視掉一些真正有意義的CPU上SIMD應(yīng)用場景。

對于一段程序來講，如果將每讀取單位數(shù)據(jù)，對應(yīng)的純計算復(fù)雜度大小定義為計算密度，而將算法在不同數(shù)據(jù)單元上執(zhí)行的計算流的相同程度定義為模式重復(fù)度，那么可以以此將程序劃分為4個象限。在大密度可重復(fù)的計算負(fù)載（典型的重型神經(jīng)網(wǎng)絡(luò)計算），和顯著小密度和非重復(fù)計算負(fù)載（例如HTML樹狀解析）場景下，業(yè)界在CPU和GPU的選取上其實是有相對明確“最優(yōu)解”的。不過對于過渡地帶，計算的重復(fù)特征沒有那么強， 或者運算密度沒有那么大的場景下，雙方的弱點都會被進一步放大。即便是規(guī)整可重復(fù)的計算負(fù)載，隨著計算本身強度減小，傳輸和啟動成本逐漸顯著。另一方面，即便是不太規(guī)整可重復(fù)的計算負(fù)載，隨著計算負(fù)荷加大，核心數(shù)不足也會逐漸成為瓶頸。這時候，引入SIMD的CPU和引入SIMT 的GPU間如何選擇和使用，就形成了沒有那么明確，見仁見智的權(quán)衡空間。

即使排除了重型神經(jīng)網(wǎng)絡(luò)，從程序的一般特性而言，具有一定規(guī)模的重復(fù)特性也是一種普遍現(xiàn)象。例如從概念上講，程序中的循環(huán)段落，都或多或少意味著批量/重復(fù)的計算負(fù)載。盡管因為摻雜著分支控制，導(dǎo)致重復(fù)得沒有那么純粹，但這種一定規(guī)模的細粒度重復(fù)，正是CPU上SIMD發(fā)揮獨特價值的地方。例如最常見的SIMD優(yōu)化其實就是memcpy，現(xiàn)代的memcpy實現(xiàn)會探測CPU所能支持的SIMD指令位寬，并盡力使用來加速內(nèi)存?zhèn)鬏?。另一方面現(xiàn)代編譯器也會利用SIMD指令來是優(yōu)化對象拷貝，進行簡單循環(huán)向量化等方式來進行加速。類似這樣的一類優(yōu)化方法偏『自動透明』，也是默默支撐著主頻不變情況下，性能稍有上升的重要推手。

可惜這類簡單的自動優(yōu)化能做到的事情還相當(dāng)有限，為了能夠充分利用CPU上的SIMD加速，現(xiàn)階段還非常依賴程序?qū)舆M行主動算法適應(yīng)性改造，有 目的地使用，換言之，就是主動實施這種單線程內(nèi)的并發(fā)改造。一個無法自動優(yōu)化的例子就是《內(nèi)存篇》中提到的字符串切分的優(yōu)化，現(xiàn)階段通過編譯器分析還很難從循環(huán) + 判斷分支提取出數(shù)據(jù)并行pattern并轉(zhuǎn)換成SIMD化的match&mask動作。而更為顯著的是近年來一批針對SIMD指令重新設(shè)計的算法，例如Swiss Table哈希表，simdjson解析庫，base64編解碼庫等，在各自的領(lǐng)域都帶來了倍數(shù)級的提升，而這一類算法適應(yīng)性改造，就已經(jīng)完全脫離了自動透明所能觸及的范圍?？梢灶A(yù)知近些年，尤其隨著先進工藝下AVX512降頻問題的逐漸解決，還會/也需要涌現(xiàn)出更多的傳統(tǒng)基礎(chǔ)算法的SIMD改造。而熟練運用SIMD指令優(yōu)化技術(shù)，也將成為C++工程師的一項必要技能。

3.2 OoOE

另一個重要的單線程內(nèi)并行能力就是亂序執(zhí)行OoOE（Out of Order Execution）。經(jīng)典教科書上的CPU流水線機制一般描述如下（經(jīng)典5級RISC流水線）。

指令簡化表達為取指/譯碼/計算/訪存/寫回環(huán)節(jié)，當(dāng)執(zhí)行環(huán)節(jié)遇到數(shù)據(jù)依賴，以及緩存未命中等場景，就會導(dǎo)致整體停頓的產(chǎn)生。其中MEM環(huán)節(jié)的影響尤其顯著，主要也是因為緩存層次的深化和多核心的共享現(xiàn)象，帶來單次訪存所需周期數(shù)參差不齊的現(xiàn)象越來越嚴(yán)重。上圖中的流水線在多層緩存下的表現(xiàn)，可能更像下圖所示：

為了減輕停頓的影響，現(xiàn)代面向性能優(yōu)化的CPU一般引入了亂序執(zhí)行結(jié)合超標(biāo)量的技術(shù)。也就是一方面，對于重點執(zhí)行部件，比如計算部件，訪存部件等，增加多份來支持并行。另一方面，在執(zhí)行部件前引入緩沖池/隊列機制，通用更長的預(yù)測執(zhí)行來盡可能打滿每個部件。最終從流水線模式，轉(zhuǎn)向了更類似『多線程』的設(shè)計模式：

亂序執(zhí)行系統(tǒng)中，一般會將通過預(yù)測維護一個較長的指令序列，并構(gòu)建一個指令池，通過解析指令池內(nèi)的依賴關(guān)系，形成一張DAG（有向無環(huán)圖） 組織的網(wǎng)狀結(jié)構(gòu)。通過對DAG關(guān)系的計算，其中依賴就緒的指令，就可以進入執(zhí)行態(tài)，被提交到實際的執(zhí)行部件中處理。執(zhí)行部件類似多線程模型中的工作線程，根據(jù)特性細分為計算和訪存兩類。計算類一般有相對固定可預(yù)期的執(zhí)行周期，而訪存類由于指令周期差異較大，采用了異步回調(diào)的模型，通過Load/Store Buffer支持同時發(fā)起數(shù)十個訪存操作。

亂序執(zhí)行系統(tǒng)和傳統(tǒng)流水線模式的區(qū)別主要體現(xiàn)在，當(dāng)一條訪存指令因為Cache Miss而無法立即完成時，其后無依賴關(guān)系的指令可以插隊執(zhí)行（類似于多線程模型中某個線程阻塞后，OS將其掛起并調(diào)度其他線程）。插隊的計算類指令可以填補空窗充分利用計算能力，而插隊的訪存指令通過更早啟動傳輸，讓訪存停頓期盡量重疊來減小整體的停頓。因此亂序執(zhí)行系統(tǒng)的效率，很大程度上會受到窗口內(nèi)指令DAG的『扁平』程度的影響，依賴深度較淺的DAG可以提供更高的指令級并發(fā)能力，進而提供更高的執(zhí)行部件利用率，以及更少的停頓周期。另一方面，由于Load/Store Buffer也有最大的容量限制，處理較大區(qū)域的內(nèi)存訪問負(fù)載時，將可能帶來更深層穿透的訪存指令盡量靠近排布，來提高訪存停頓的重疊，也能夠有效減少整體的停頓。

雖然理論比較清晰，可是在實踐中，僅僅從外部指標(biāo)觀測到的性能表現(xiàn)，往往難以定位亂序執(zhí)行系統(tǒng)內(nèi)部的熱點。最直白的CPU利用率其實只能表達線程未受阻塞，真實在使用CPU的時間周期，但是其實并不能體現(xiàn)CPU內(nèi)部部件真正的利用效率如何。稍微進階一些的IPC（Instruction Per Cyc le），可以相對深入地反應(yīng)一些利用效能，但是影響IPC的因素又多種多樣。是指令并行度不足？還是長周期ALU計算負(fù)載大？又或者是訪存停頓過久？甚至可能是分支預(yù)測失敗率過高？真實程序中，這幾項問題往往是并存的，而且單一地統(tǒng)計往往又難以統(tǒng)一比較，例如10次訪存停頓/20次ALU 未打滿/30個周期的頁表遍歷，到底意味著瓶頸在哪里？這個問題單一的指標(biāo)往往就難以回答了。

3.3 TMAM

TMAM（Top-down Microarchitecture Analysis Method）是一種利用CPU內(nèi)部PMU（Performance Monitoring Unit）計數(shù)器來從上至下分解定位部件瓶頸的手段。例如在最頂層，首先以標(biāo)定最大指令完成速率為標(biāo)準(zhǔn)（例如Skylake上為單周期4條微指令），如果無法達到標(biāo)定，則認(rèn)為瓶頸在于未能充分利用部件。進一步細分以指令池為分界線，如果指令池未滿，但是取指部件又無法滿負(fù)荷輸出微指令，就表明『前端』存在瓶頸。另一種無法達到最大指令速率的因素，是『前端』雖然在發(fā)射指令到指令池，但是因為錯誤的預(yù)測，最終沒有產(chǎn)出有效結(jié)果，這類損耗則被歸入『錯誤預(yù)測』。除此以外的問題就是因為指令池調(diào)度執(zhí)行能力不足產(chǎn)生的反壓停頓，這一類被歸為『后端』瓶頸。進一步例如『后端』瓶頸還可以根 據(jù)，停頓發(fā)生時，是否伴隨了ALU利用不充分，是否伴隨了Load/Store Buffer滿負(fù)荷等因素，繼續(xù)進行分解細化，形成了一套整體的分析方法。例如針對Intel，這一過程可以通過pmu-tools來被自動完成，對于指導(dǎo)精細化的程序瓶頸分析和優(yōu)化往往有很大幫助。

int array［1024］;

for （size_t i = 0; i 《 1024; i += 2） {

int a = array［i］;

int b = array［i + 1］;

for （size_t j = 0; j 《 1024; ++j） {

a = a + b;

b = a + b;}

array［i］ = a;

array［i + 1］ = b;

}

例如這是里演示一個多輪計算斐波那契數(shù)列的過程，因為計算特征中深層循環(huán)有強指令依賴，且內(nèi)層循環(huán)長度遠大于常規(guī)亂序執(zhí)行的指令池深度， 存在較大的計算依賴瓶頸，從工具分析也可以印證這一點。

程序的IPC只有1，內(nèi)部瓶頸也顯示集中在『后端』內(nèi)部的部件利用效率（大多時間只利用了一個port），此時亂序執(zhí)行并沒有發(fā)揮作用。

int array［1024］;``for （size_t i = 0; i 《 1024; i += 4） { int a = array［i］; int b = array［i + 1］; int c = array［i + 2］; int d = array［i + 3］; for （size_t j = 0; j 《 1024; ++j） { a = a + b; b = a + b; c = c + d; d = c + d; } array［i］ = a; array［i + 1］ = b; array［i + 2］ = c; array［i + 3］ = d;``}

這里演示了典型的的循環(huán)展開方法，通過在指令窗口內(nèi)同時進行兩路無依賴計算，提高了指令并行度，通過工具分析也可以確認(rèn)到效果。

不過實踐中，能夠在寄存器上反復(fù)迭代的運算并不常見，大多情況下比較輕的計算負(fù)載，搭配比較多的訪存動作會更經(jīng)常遇到，像下面的這個例子：

struct Line {

char data［64］;

};

Line* lines［1024］; // 其中亂序存放多個緩存行for （size_t i = 0; i 《 1024; ++i） {

Line* line = lines［i］;

for （size_t j = 0; j 《 64; ++j） {

line-》data［j］ += j;

}

}

這是一個非連續(xù)內(nèi)存上進行累加計算的例子，隨外層迭代會跳躍式緩存行訪問，內(nèi)層循環(huán)在連續(xù)緩存行上進行無依賴的計算和訪存操作。

可以看到，這一次的瓶頸到了穿透緩存后的內(nèi)存訪存延遲上，但同時內(nèi)存訪問的帶寬并沒有被充分利用。這是因為指令窗口內(nèi)雖然并發(fā)度不低，不過因為緩存層次系統(tǒng)的特性，內(nèi)層循環(huán)中的多個訪存指令，其實最終都是等待同一行被從內(nèi)存加載到緩存。導(dǎo)致真正觸發(fā)的底層訪存壓力并不足以打滿傳輸帶寬，但是程序卻表現(xiàn)出了較大的停頓。

for （size_t i = 0; i 《 1024; i += 2） {

Line* line1 = lines［i］;

Line* line2 = lines［i + 1］;

。..

for （size_t j = 0; j 《 64; ++j） {

line1-》data［j］ += j;

line2-》data［j］ += j;

。..

}

}

通過調(diào)整循環(huán)結(jié)構(gòu)，在每一輪內(nèi)層循環(huán)中一次性計算多行數(shù)據(jù)，可以在盡量在停頓到來的指令窗口內(nèi)，讓更多行出于同時從內(nèi)存系統(tǒng)進行傳輸。從統(tǒng)計指標(biāo)上也可以看出，瓶頸重心開始從穿透訪存的延遲，逐步轉(zhuǎn)化向訪存帶寬，而實際的緩存?zhèn)鬏敳考﨔ill Buffer也開始出現(xiàn)了滿負(fù)荷運作的情況。

3.4 總結(jié)一下單線程并發(fā)

現(xiàn)代CPU在遇到主頻瓶頸后，除了改為增加核心數(shù)，也在單核心內(nèi)逐步強化并行能力。如果說多進程多線程技術(shù)的普及，讓多核心的利用技術(shù)多少不那么罕見和困難，那么單核心內(nèi)的并行加速技術(shù)，因為更加黑盒（多級緩存加亂序執(zhí)行），規(guī)范性不足（SIMD），相對普及度和利用率都會更差一些。雖然硬件更多的細節(jié)向應(yīng)用層暴露讓程序的實現(xiàn)更加困難，不過困難和機會往往也是伴隨出現(xiàn)的，既然客觀發(fā)展上這種復(fù)雜性增加已經(jīng)無可避免，那么是否能善加利用也成了工程師進行性能優(yōu)化時的一項利器。隨著體系結(jié)構(gòu)的進一步復(fù)雜化，可見的未來一段時間里，能否利用一些體系結(jié)構(gòu)的原理和工具來進行優(yōu)化，也會不可避免地成為服務(wù)端工程師的一項重要技能。

四、多線程并發(fā)中的臨界區(qū)保護

相比單線程中的并發(fā)設(shè)計，多線程并發(fā)應(yīng)該是更為工程師所熟悉的概念。如今，將計算劃分到多線程執(zhí)行的應(yīng)用技術(shù)本身已經(jīng)相對成熟了，相信各個服務(wù)端工程師都有各自熟悉的隊列+線程池的小工具箱。在不做其他額外考慮的情況下，單純的大任務(wù)分段拆分，提交線程池并回收結(jié)果可能也僅僅是幾行代碼就可以解決的事情了。真正的難點，其實往往不在于『拆』，而在于『合』的部分，也就是任務(wù)拆分中無法避免掉的共享數(shù)據(jù)操作環(huán)節(jié)。如果說更高的分布式層面，還可以盡可能地利用Share Nothing思想，在計算發(fā)生之前，就先盡量通過任務(wù)劃分來做到盡可能充分地隔離資源。但是深入到具體的計算節(jié)點內(nèi)部，如果再進行一些細粒度的拆分加速時，共享往往就難以徹底避免了。如何正確高效地處理這些無法避免的共享問題，就涉及到并發(fā)編程中的一項重要技術(shù)，臨界區(qū)保護。

4.1 什么是臨界區(qū)

算法并發(fā)改造中，一般會產(chǎn)生兩類段落，一類是多個線程間無需交互就可以獨立執(zhí)行的部分，這一部分隨著核心增多，可以順利地水平擴展。而另一類是需要通過操作共享的數(shù)據(jù)來完成執(zhí)行，這部分操作為了能夠正確執(zhí)行，無法被多個核心同時執(zhí)行，只能每個線程排隊通過。因此臨界區(qū)內(nèi)的代碼，也就無法隨著核心增多來擴展，往往會成為多線程程序的瓶頸點。也是因為這個特性，臨界區(qū)的效率就變得至關(guān)重要，而如何保證各個線程安全地通過臨界區(qū)的方法，就是臨界區(qū)保護技術(shù)。

4.1.1 Mutual Exclusion

最基本的臨界區(qū)保護方法，就是互斥技術(shù)。這是一種典型的悲觀鎖算法，也就是假設(shè)臨界區(qū)高概率存在競爭，因此需要先利用底層提供的機制進行仲裁，成功獲得所有權(quán)之后，才進入臨界區(qū)運行。這種互斥算法，有一個典型的全局阻塞問題，也就是上圖中，當(dāng)臨界區(qū)內(nèi)的線程發(fā)生阻塞，或被操作系統(tǒng)換出時，會出現(xiàn)一個全局執(zhí)行空窗。這個執(zhí)行空窗內(nèi)，不僅自身無法繼續(xù)操作，未獲得鎖的線程也只能一同等待，造成了阻塞放大的現(xiàn)象。但是對于并行區(qū)，單一線程的阻塞只會影響自身，同樣位于在上圖中的第二次阻塞就是如此。

由于真實發(fā)生在臨界區(qū)內(nèi)的阻塞往往又是不可預(yù)期的，例如發(fā)生了缺頁中斷，或者為了申請一塊內(nèi)存而要先進行一次比較復(fù)雜的內(nèi)存整理。這就會讓阻塞擴散的問題更加嚴(yán)重，很可能改為讓另一個線程先進入臨界區(qū)，反而可以更快順利完成，但是現(xiàn)在必須所有并發(fā)參與者，都一起等待臨界區(qū)持有者來完成一些并沒有那么『關(guān)鍵』的操作。因為存在全局阻塞的可能性，采用互斥技術(shù)進行臨界區(qū)保護的算法有著最低的阻塞容忍能力，一般在『非阻塞算法』領(lǐng)域作為典型的反面教材存在。

**4.1.2 **Lock Free

針對互斥技術(shù)中的阻塞問題，一個改良型的臨界區(qū)保護算法是無鎖技術(shù)。雖然叫做無鎖，不過主要是取自非阻塞算法等級中的一種分類術(shù)語，本質(zhì)上是一種樂觀鎖算法。也就是首先假設(shè)臨界區(qū)不存在競爭，因此直接開始臨界區(qū)的執(zhí)行，但是通過良好的設(shè)計，讓這段預(yù)先的執(zhí)行是無沖突可回滾的。但是最終設(shè)計一個需要同步的提交操作，一般基于原子變量CAS（Compare And Swap），或者版本校驗等機制完成。在提交階段如果發(fā)生沖突，那么被仲裁為失敗的各方需要對臨界區(qū)預(yù)執(zhí)行進行回滾，并重新發(fā)起一輪嘗試。

無鎖技術(shù)和互斥技術(shù)最大的區(qū)別是，臨界區(qū)核心的執(zhí)行段落是可以類似并行段落一樣獨立進行，不過又不同于真正的并行段落，同時執(zhí)行的臨界區(qū)中，只有一個是真正有效的，其余最終將被仲裁為無效并回滾。但是引入了冗余的執(zhí)行操作后，當(dāng)臨界區(qū)內(nèi)再次發(fā)生阻塞時，不會像互斥算法那樣在參與線程之間進行傳播，轉(zhuǎn)而讓一個次優(yōu)的線程成功提交。雖然從每個并發(fā)算法參與線程的角度，存在沒有執(zhí)行『實質(zhì)有效』計算的段落，但是這種浪費計算的段落，一定對應(yīng)著另一個參與線程執(zhí)行了『有效』的計算。所以從整個算法層面，能夠保證不會全局停頓，總是有一些有效的計算在運行。

**4.1.3 **Wait-Free

無鎖技術(shù)主要解決了臨界區(qū)內(nèi)的阻塞傳播問題，但是本質(zhì)上，多個線程依然是排隊順序經(jīng)過臨界區(qū)。形象來說，有些類似交通中的三叉路口匯合， 無論是互斥還是無鎖，最終都是把兩條車道匯聚成了一條單車道，區(qū)別只是指揮是否高明能保證沒有斷流出現(xiàn)?？墒菬o論如何，臨界區(qū)內(nèi)全局吞吐降低成串行這點是共同的缺陷。

而Wait Free級別和無鎖的主要區(qū)別也就體現(xiàn)在這個吞吐的問題上，在無全局停頓的基礎(chǔ)上，Wait Free進一步保障了任意算法參與線程，都應(yīng)該在有限的步驟內(nèi)完成。這就和無鎖技術(shù)產(chǎn)生了區(qū)別，不只是整體算法時時刻刻存在有效計算，每個線程視角依然是需要持續(xù)進行有效計算。這就要求了多線程在臨界區(qū)內(nèi)不能被細粒度地串行起來，而必須是同時都能進行有效計算。回到上面三叉路口匯聚的例子，就以為著在Wait Free級別下，最終匯聚的道路依舊需要是多車道的，以保證可以同時都能夠有進展。

雖然理論角度存在不少有Wait Free級別的算法，不過大多為概念探索，并不具備工業(yè)使用價值。主要是由于Wait Free限制了同時有進展，但是并沒有描述這個進展有多快。因此進一步又提出了細分子類，以比較有實際意義的Wait-Free Population Oblivious級別來說，額外限制了每個參與線程必須要在預(yù)先可給出的明確執(zhí)行周期內(nèi)完成，且這個周期不能和與參與線程數(shù)相關(guān)。這一點明確拒絕了一些類似線程間協(xié)作的方案（這些方案往往引起較大的緩存競爭），以及一些需要很長很長的有限步來完成的設(shè)計。

上圖實例了一個典型的Wait Free Population Oblivious思路。進行臨界區(qū)操作前，通過一個協(xié)同操作為參與線程分配獨立的ticket，之后每個參與線程可以通過獲取到的ticket作為標(biāo)識，操作一塊獨立的互不干擾的工作區(qū)，并在其中完成操作。工業(yè)可用的Wait Free算法一般較難設(shè)計，例如ticket機制要求在協(xié)調(diào)動作中原子完成工作區(qū)分配，而很多數(shù)據(jù)結(jié)構(gòu)是不容易做到這樣的拆分的。時至今日各種數(shù)據(jù)結(jié)構(gòu)上工業(yè)可用的Wait Free算法依舊是一項持續(xù)探索中的領(lǐng)域。

**4.2 **無鎖不是萬能的

從非阻塞編程的角度看，上面的幾類臨界區(qū)處理方案優(yōu)劣有著顯著的偏序關(guān)系，即Wait Free 》 Lock Free 》 Mutual Exclusion。這主要是從阻塞適應(yīng)性角度進行的衡量，原理上并不能直接對應(yīng)到性能緯度。但是依然很容易給工程師造成一個普適印象，也就是『鎖是很邪惡的東西，不使用鎖來實現(xiàn)算法可以顯著提高性能』，再結(jié)合廣為流傳的鎖操作自身開銷很重的認(rèn)知，很多工程師在實踐中會有對鎖敬而遠之的傾向。那么，這個指導(dǎo)思想是否是完全正確的？

讓我們先來一組實驗：

// 在一個cache line上進行指定步長的斐波那契計算來模擬臨界區(qū)計算負(fù)載uint64_t calc（uint64_t* sequence， size_t size） {

size_t i;

for （i = 0; i 《 size; ++i） {

sequence［（i + 1） & 7］ += sequence［i & 7］;

}

return sequence［i & 7］;

}

{ // Mutual Exclusion

：：std：：lock_guard《：：std：：mutex》 lock（mutex）;

sum += calc（sequence， workload）;

}

{ // Lock Free / Atomic CAS

auto current = atomic_sum.load（：：std：：memory_order_relaxed）;

auto next = current;

do {

next = current + calc（sequence， workload）;

} while （！atomic_sum.compare_exchange_weak（

current， next， ：：std：：memory_order_relaxed））;

}

{ // Wait Free / Atomic Modify

atomic_sum.fetch_add（calc（sequence， workload）， ：：std：：memory_order_relaxed）;

}

這里采用多線程累加作為案例，分別采用上鎖后累加，累加后CAS提交，以及累加后FAA（Fetch And Add）提交三種方法對全局累加結(jié)果做臨界區(qū)保護。針對不同的并發(fā)數(shù)量，以及不同的臨界區(qū)負(fù)載，可以形成如下的三維曲線圖。

其中Latency項除以臨界區(qū)規(guī)模進行了歸一，便于形象展示臨界區(qū)負(fù)載變化下的臨界區(qū)保護開銷趨勢，因此跨不同負(fù)載等級下不具備橫向可比性。Cycles項表示多線程協(xié)同完成總量為同樣次數(shù)的累加，用到的CPU周期總和，總體隨臨界區(qū)負(fù)載變化有少量天然傾斜。100/1600兩個截面圖將3中算法疊加在一起展示，便于直觀對比。

從上面的數(shù)據(jù)中可以分析出這樣一些信息

1、基于FAA的Wait Free模式各方面都顯著勝過其他方法；

2、無鎖算法相比互斥算法在平均吞吐上有一定優(yōu)勢，但是并沒有達到數(shù)量級水平；

3、無鎖算法隨競爭提升（臨界區(qū)大小增大，或者線程增多），cpu消耗顯著上升；

基于這些信息來分析，會發(fā)現(xiàn)一個和之前提到的『鎖性能』的常規(guī)認(rèn)知相悖的點。性能的分水嶺并沒有出現(xiàn)在基于鎖的互斥算法和無鎖算法中間， 而是出現(xiàn)在同為『未使用鎖』的Lock Free和Wait Free算法中間。而且從CPU消耗角度來看，對臨界區(qū)比較復(fù)雜，競爭強度高的場景，甚至Lock Free因為『無效預(yù)測執(zhí)行』過多反而引起了過多的消耗。這表明了鎖操作本身的開銷雖然稍重于原子操作，但其實也并非洪水猛獸，而真正影響性能的，是臨界區(qū)被迫串行執(zhí)行所帶來的并行能力折損。

因此當(dāng)我們遇到臨界區(qū)保護的問題時，可以先思考一下，是否可以采用Wait Free的方法來完成保護動作，如果可以的話，在性能上能夠接近完全消除了臨界區(qū)的效果。而在多數(shù)情況下，往往還是要采用互斥或Lock Free來進行臨界區(qū)的保護。此時臨界區(qū)的串行不可避免，所以充分縮減臨界區(qū)的占比是共性的第一要務(wù)，而是否進一步采用Lock Free技術(shù)來減少臨界區(qū)保護開銷，討論的前提也是臨界區(qū)已經(jīng)顯著很短，不會引起過多的無效預(yù) 測。除此以外，由于Lock Free算法一般對臨界區(qū)需要設(shè)計成兩階段提交，以便支持回滾撤銷，因此往往需要比對應(yīng)的互斥保護算法更復(fù)雜，局部性也可能更差（例如某些場景必須引入鏈表來替換數(shù)組）。綜合來看，一般如果無法做到Wait Free，那么無需對Lock Free過度執(zhí)著，充分優(yōu)化臨界區(qū)的互斥方法往往也足以提供和Lock Free相當(dāng)?shù)男阅鼙憩F(xiàn)了。

4.3 并發(fā)計數(shù)器優(yōu)化案例

從上文針對臨界區(qū)保護的多種方法所做的實驗，還可以發(fā)現(xiàn)一個現(xiàn)象。隨著臨界區(qū)逐漸減小，保護措施開銷隨線程數(shù)量增加而提升的趨勢都預(yù)發(fā)顯著，即便是設(shè)計上效率和參與線程數(shù)本應(yīng)無關(guān)的Wait Free級別也是一樣。這對于臨界區(qū)極小的并發(fā)計數(shù)器場景，依舊會是一個顯著的問題。那么我們就先從鎖和原子操作的實現(xiàn)角度，看看這些損耗是如何導(dǎo)致的。

首先給出一個典型的鎖實現(xiàn)，左側(cè)是鎖的fast path，也就是如果在外層的原子變量操作中未發(fā)現(xiàn)競爭，那么其實上鎖和解鎖其實就只經(jīng)歷了一組原子變量操作。當(dāng)fast path檢測到可能出現(xiàn)沖突時，才會進入內(nèi)核，嘗試進行排隊等待。fast path的存在大幅優(yōu)化了低沖突場景下的鎖表現(xiàn)，而且現(xiàn)代操作系統(tǒng)內(nèi)核為了優(yōu)化鎖的內(nèi)存開銷，都提供了『Wait On Address』的功能，也就是為了支持這套排隊機制，每個鎖常態(tài)只需要一個整數(shù)的存儲開銷即可，只有在嘗試等待時，才會創(chuàng)建和占用額外的輔助結(jié)構(gòu)。

因此實際設(shè)計中，鎖可以創(chuàng)建很多，甚至非常多，只要能夠達到足夠細粒度拆解沖突的效果。這其中最典型的就是brpc中計數(shù)器框架bvar的設(shè)計。

這是bvar中基礎(chǔ)統(tǒng)計框架的設(shè)計，局部計數(shù)和全局匯聚時都通過每個tls附加的鎖來進行臨界區(qū)保護。因為采集周期很長，沖突可以忽略不記，因此雖然默認(rèn)使用了大量的鎖（統(tǒng)計量 * 線程數(shù)），但是并沒有很大的內(nèi)存消耗，而且運行開銷其實很低，能夠用來支持任意的匯聚操作。這個例子也能進一步體現(xiàn)，鎖本身的消耗其實并不顯著，競爭帶來的軟件或硬件上的串行化才是開銷的核心。

不過即使競爭很低，鎖也還是會由一組原子操作實現(xiàn)，而當(dāng)我們自己查看原子操作時，實際是由cache鎖操作保護的原子指令構(gòu)成，而且這個指令會在亂序執(zhí)行中起到內(nèi)存屏障的效果降低訪存重疊的可能性。因此針對非常常用的簡單計數(shù)器，在百度內(nèi)部我們進行了進一步去除局部鎖的改造，來試圖進一步降低統(tǒng)計開銷。

例如對于需要同時記錄次數(shù)和總和的IntRecorder，因為需要兩個64位加法，曾經(jīng)只能依賴鎖來保證原子更新。但隨著新x86機型的不斷普及，在比較新的X86和ARM服務(wù)端機型上已經(jīng)可以做到128bit的原子load/store，因此可以利用相應(yīng)的高位寬指令和正確對齊來實現(xiàn)鎖的去除。

另一個例子是Percentile分位值統(tǒng)計，由于抽樣數(shù)據(jù)是一個多元素容器，而且分位值統(tǒng)計需要周期清空重算，因此常規(guī)也是采用了互斥保護的方法。不過如果引入版本號機制，將清空操作轉(zhuǎn)交給計數(shù)線程自己完成，將sample區(qū)域的讀寫完全分離。在這個基礎(chǔ)上，就可以比較簡單的做到線程安全，而且也不用引入原子修改。嚴(yán)格意義上，異步清空存在邊界樣本收集丟失的可能性，不過因為核心的蓄水池抽樣算發(fā)本身也具有隨機性，在監(jiān)控指標(biāo)統(tǒng)計領(lǐng)域已經(jīng)擁有足夠精度。

除了運行時操作，線程局部變量的組織方式原先采用鎖保護的鏈表進行管理，采用分段數(shù)據(jù)結(jié)合線程編號的方法替換后，做到空間連續(xù)化。最終整體進一步改善了計數(shù)器的性能。

local countget value

bvar：：IntRecorder167

babylon：：IntRecorder137714

bvar：：Percentile93828

babylon：：Percentile6614

**4.4 **并發(fā)隊列優(yōu)化案例

另一個在多線程編程中經(jīng)常出現(xiàn)的數(shù)據(jù)結(jié)構(gòu)就是隊列，為了保證可以安全地處理并發(fā)的入隊和出隊操作，最基礎(chǔ)的算法是整個隊列用鎖來保護起來。

這個方法的缺點是顯而易見的，因為隊列往往作為多線程驅(qū)動的數(shù)據(jù)中樞位置，大量的競爭下，隊列操作被串行很容易影響整體計算的并行度。因此一個自然的改進點是，將隊列頭尾分開保護，先將生產(chǎn)者和消費者解耦開，只追加必要的同步操作來保證不會過度入隊和出隊。這也是Jave中LinkedBlockingQueue所使用的做法。

在頭尾分離之后，進一步的優(yōu)化進入了兩個方向。首先是因為單節(jié)點的操作具備了Lock Free化的可能，因此產(chǎn)生了對應(yīng)的Michael & Scott無鎖隊列算法。業(yè)界的典型實現(xiàn)有Java的ConcurrentLinkedQueue，以及boost中的boost：：queue。

而另一個方向是隊列分片，即將隊列拆解成多個子隊列，通過領(lǐng)取token的方式選擇子隊列，而子隊列內(nèi)部使用傳統(tǒng)隊列算法，例如tbb：： concurrent_queue就是分片隊列的典型實現(xiàn)。

latency

boost：：queue35075

tbb：：concurrent_queue4614

對兩種方式進行對比，可以發(fā)現(xiàn)，在強競爭下，分片隊列的效果其實顯著勝過單純的無鎖處理，這也是前文對于無鎖技術(shù)真實效果分析的一個體現(xiàn)。

除了這類通用隊列，還有一個強化競爭發(fā)布，串行消費的隊列也就是bthread：：ExecutionQueue，它在是brpc中主要用于解決多線程競爭fd寫入的問題。利用一些有趣的技巧，對多線程生產(chǎn)側(cè)做到了Wait Free級別。

整個隊列只持有隊尾，而無隊頭。在生產(chǎn)側(cè)，第一步直接將新節(jié)點和當(dāng)前尾指針進行原子交換，之后再將之前的隊尾銜接到新節(jié)點之后。因為無論是否存在競爭，入隊操作都能通過固定的兩步完成，因此入隊算法是Wait Free的。不過這給消費側(cè)帶來的麻煩，消費同樣從一個原子交換開始，將隊尾置換成nullptr，之后的消費動作就是遍歷取到的單鏈表。但是因為生產(chǎn)操作分了兩部完成，此時可能發(fā)現(xiàn)部分節(jié)點尚處于『斷鏈』狀態(tài)，由于消費者無從知曉后續(xù)節(jié)點信息，只能輪詢等待生產(chǎn)者最終完成第二步。所以理論上，生產(chǎn)/消費算法其實甚至不是Lock Free的，因為如果生產(chǎn)者在兩階段中間被換出，那么消費者會被這個阻塞傳播影響，整個消費也只能先阻塞住。但是在排隊寫入fd的場景下，專項優(yōu)化生產(chǎn)并發(fā)是合理，也因此可以獲得更好的執(zhí)行效率。

latency

tbb：：concurrent_queue4614

bthread：：ExecutionQueue2390

不過為了能利用原子操作完成算法，bthread：：ExecutionQueue引入了鏈表作為數(shù)據(jù)組織方式，而鏈表天然存在訪存跳躍的問題。那么是否可以用數(shù)組來同樣實現(xiàn)Wait Free的生產(chǎn)甚至消費并發(fā)呢？

這就是babylon：：ConcurrentBoundedQueue所希望解決的問題了。

不過介紹這個隊列并發(fā)原理之前，先插入一個勘誤信息。其實這個隊列在《內(nèi)存篇》最后也簡單提到過，不過當(dāng)時粗略的評測顯示了acquire- release等級下，即使不做cache line隔離性能也可以保障。文章發(fā)表后收到業(yè)界同好反饋，討論發(fā)現(xiàn)當(dāng)時的測試用例命中了Intel Write Combining 優(yōu)化技術(shù)，即當(dāng)僅存在唯一一個處于等待加載的緩存行時，只寫動作可以無阻塞提前完成，等緩存行真實加載完畢后，再統(tǒng)一提交生效。但是由于內(nèi)存序問題，一旦觸發(fā)了第二個待加載的緩存行后，對于第一個緩存行的Write Combine就無法繼續(xù)生效，只能等待第二個緩存行的寫完成后，才能繼續(xù)提交。原理上，Write Combine技術(shù)確實緩解了只寫場景下的False Sharing，但是只能等待一個緩存行的限制在真實場景下想要針對性利用起來限制相當(dāng)大。例如在隊列這個典型場景下，往往會同時兩路操作數(shù)據(jù)和完成標(biāo)記，很可能同時處于穿透加載中，此時是無法應(yīng)用Write Combine技術(shù)的。此外，能夠在緩存行加載周期內(nèi)，有如此充分的同行寫入，可能也只有并無真實意義的評測程序才能做到。所以從結(jié)論上講，通常意義上的多線程cache line隔離還是很有必要的。

回到babylon：：ConcurrentBoundedQueue的設(shè)計思路上，其實是將子隊列拆分做到極致，將同步量粒度降低到每個數(shù)據(jù)槽位上。每個入隊和出隊 請求，首先利用原子自增領(lǐng)取一個遞增的序號，之后利用循環(huán)數(shù)組的存儲方式，就可以映射到一個具體的數(shù)據(jù)槽位上。根據(jù)操作是入隊還是出隊， 在循環(huán)數(shù)組上發(fā)生了多少次折疊，就可以在一個數(shù)據(jù)槽位上形成一個連續(xù)的版本序列。例如1號入隊和5號出隊都對應(yīng)了1號數(shù)據(jù)槽位，而1號入隊預(yù)期的版本轉(zhuǎn)移是0到1，而5號出隊的版本轉(zhuǎn)移是2到3。這樣針對同一個槽位的入隊和出隊也可以形成一個連續(xù)的版本變更序列，一個領(lǐng)到序號的具體操作，只需要明確檢測版本即可確認(rèn)自己當(dāng)前是否可以開始操作，并通過自己的版本變更和后續(xù)的操作進行同步。

通過同步量下放到每個元素的方式，入隊和出隊操作在可以除了最開始的序號領(lǐng)取存在原子操作級別的同步，后續(xù)都可以無干擾并行開展。而更連續(xù)的數(shù)據(jù)組織，也解決了鏈表存儲的訪存跳躍問題。生產(chǎn)消費雙端可并發(fā)的特點，也提供了更強的泛用性，實際在MPMC（Multiple Producer Mult iple Consumer）和MPSC（Multiple Producer Single Consumer）場景下都有不錯的性能表現(xiàn)，在具備一定小批量處理的場景下尤其顯著。

責(zé)任編輯：haq