C++工程師在進(jìn)行并發(fā)優(yōu)化時(shí)所作的工作

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

一、背景

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 SIMD

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

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

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

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

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

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

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

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

3.2 OoOE

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

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

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

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

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

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

3.3 TMAM

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

}

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

程序的IPC只有1，內(nèi)部瓶頸也顯示集中在『后端』內(nèi)部的部件利用效率（大多時(shí)間只利用了一個(gè)port），此時(shí)亂序執(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)同時(shí)進(jìn)行兩路無依賴計(jì)算，提高了指令并行度，通過工具分析也可以確認(rèn)到效果。

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

struct Line {

char data［64］;

};

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

Line* line = lines［i］;

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

line-》data［j］ += j;

}

}

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

可以看到，這一次的瓶頸到了穿透緩存后的內(nèi)存訪存延遲上，但同時(shí)內(nèi)存訪問的帶寬并沒有被充分利用。這是因?yàn)橹噶畲翱趦?nèi)雖然并發(fā)度不低，不過因?yàn)榫彺鎸哟蜗到y(tǒng)的特性，內(nèi)層循環(huán)中的多個(gè)訪存指令，其實(shí)最終都是等待同一行被從內(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)中一次性計(jì)算多行數(shù)據(jù)，可以在盡量在停頓到來的指令窗口內(nèi)，讓更多行出于同時(shí)從內(nèi)存系統(tǒng)進(jìn)行傳輸。從統(tǒng)計(jì)指標(biāo)上也可以看出，瓶頸重心開始從穿透訪存的延遲，逐步轉(zhuǎn)化向訪存帶寬，而實(shí)際的緩存?zhèn)鬏敳考﨔ill Buffer也開始出現(xiàn)了滿負(fù)荷運(yùn)作的情況。

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

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

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

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

4.1 什么是臨界區(qū)

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

4.1.1 Mutual Exclusion

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

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

**4.1.2 **Lock Free

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

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

**4.1.3 **Wait-Free

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

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

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

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

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

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

讓我們先來一組實(shí)驗(yàn)：

// 在一個(gè)cache line上進(jìn)行指定步長的斐波那契計(jì)算來模擬臨界區(qū)計(jì)算負(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ū)保護(hù)。針對不同的并發(fā)數(shù)量，以及不同的臨界區(qū)負(fù)載，可以形成如下的三維曲線圖。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

local countget value

bvar：：IntRecorder167

babylon：：IntRecorder137714

bvar：：Percentile93828

babylon：：Percentile6614

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

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

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

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

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

latency

boost：：queue35075

tbb：：concurrent_queue4614

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

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

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

latency

tbb：：concurrent_queue4614

bthread：：ExecutionQueue2390

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

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

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

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

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

責(zé)任編輯：haq