`多處理系統(tǒng)中，使用并發(fā)的方式來提高代碼的效率時(shí)，你需要了解一下有哪些因素會(huì)影響并發(fā)的效率。即使已經(jīng)使用多線程對(duì)關(guān)注進(jìn)行分離，還需要確定是否會(huì)對(duì)性能造成負(fù)面影響。因?yàn)椋?6核機(jī)器上應(yīng)用的速度與單核機(jī)器相當(dāng)時(shí)，用戶是不會(huì)打死你的。

之后你會(huì)看到，在多線程代碼中有很多因素會(huì)影響性能——對(duì)線程處理的數(shù)據(jù)做一些簡(jiǎn)單的改動(dòng)(其他不變)，都可能對(duì)性能產(chǎn)生戲劇性的效果。所以，多言無益，讓我們來看一下這些因素吧，從明顯的開始：目標(biāo)系統(tǒng)有多少個(gè)處理器？

8.2.1 有多少個(gè)處理器？

處理器個(gè)數(shù)是影響多線程應(yīng)用的首要因素。在某些情況下，你對(duì)目標(biāo)硬件會(huì)很熟悉，并且針對(duì)硬件進(jìn)行設(shè)計(jì)，并在目標(biāo)系統(tǒng)或副本上進(jìn)行測(cè)量。如果是這樣，那你很幸運(yùn)；不過，要知道這些都是很奢侈的。你可能在一個(gè)類似的平臺(tái)上進(jìn)行開發(fā)，不過你所使用的平臺(tái)與目標(biāo)平臺(tái)的差異很大。例如，你可能會(huì)在一個(gè)雙芯或四芯的系統(tǒng)上做開發(fā)，不過你的用戶系統(tǒng)可能就只有一個(gè)處理器(可能有很多芯)，或多個(gè)單芯處理器，亦或是多核多芯的處理器。在不同的平臺(tái)上，并發(fā)程序的行為和性能特點(diǎn)就可能完全不同，所以你需要仔細(xì)考慮那些地方會(huì)被影響到，如果會(huì)被影響，就需要在不同平臺(tái)上進(jìn)行測(cè)試。

一個(gè)單核16芯的處理器和四核雙芯或十六核單芯的處理器相同：在任何系統(tǒng)上，都能運(yùn)行16個(gè)并發(fā)線程。當(dāng)線程數(shù)量少于16個(gè)時(shí)，會(huì)有處理器處于空閑狀態(tài)(除非系統(tǒng)同時(shí)需要運(yùn)行其他應(yīng)用，不過我們暫時(shí)忽略這種可能性)。另一方面，當(dāng)多于16個(gè)線程在運(yùn)行的時(shí)候(都沒有阻塞或等待)，應(yīng)用將會(huì)浪費(fèi)處理器的運(yùn)算時(shí)間在線程間進(jìn)行切換，如第1章所述。這種情況發(fā)生時(shí)，我們稱其為超額認(rèn)購(gòu)(oversubscription)。

為了擴(kuò)展應(yīng)用線程的數(shù)量，與硬件所支持的并發(fā)線程數(shù)量一致，C++標(biāo)準(zhǔn)線程庫提供了std::thread::hardware_concurrency()。使用這個(gè)函數(shù)就能知道在給定硬件上可以擴(kuò)展的線程數(shù)量了。

需要謹(jǐn)慎使用std::thread::hardware_concurrency()，因?yàn)榇a不會(huì)考慮有其他運(yùn)行在系統(tǒng)上的線程(除非已經(jīng)將系統(tǒng)信息進(jìn)行共享)。最壞的情況就是，多線程同時(shí)調(diào)用std::thread::hardware_concurrency()函數(shù)來對(duì)線程數(shù)量進(jìn)行擴(kuò)展，這樣將導(dǎo)致龐大的超額認(rèn)購(gòu)。std::async()就能避免這個(gè)問題，因?yàn)闃?biāo)準(zhǔn)庫會(huì)對(duì)所有的調(diào)用進(jìn)行適當(dāng)?shù)陌才?。同樣，?jǐn)慎的使用線程池也可以避免這個(gè)問題。

不過，即使你已經(jīng)考慮到所有在應(yīng)用中運(yùn)行的線程，程序還要被同時(shí)運(yùn)行的其他程序所影響。雖然，在單用戶系統(tǒng)中，使用多個(gè)CPU密集型應(yīng)用程序很罕見，但在某些領(lǐng)域，這種情況就很常見了。雖然系統(tǒng)能提供選擇線程數(shù)量的機(jī)制，但這種機(jī)制已經(jīng)超出C++標(biāo)準(zhǔn)的范圍。這里的一種選擇是使用與std::async()類似的工具，來為所有執(zhí)行異步任務(wù)的線程的數(shù)量做考慮；另一種選擇就是，限制每個(gè)應(yīng)用使用的處理芯個(gè)數(shù)。我倒是希望，這種限制能反映到std::thread::hardware_concurrency()上面(不能保證)。如果你需要處理這種情況，可以看一下你所使用的系統(tǒng)說明，了解一下是否有相關(guān)選項(xiàng)可供使用。

理想算法可能會(huì)取決于問題規(guī)模與處理單元的比值。大規(guī)模并行系統(tǒng)中有很多的處理單元，算法可能就會(huì)同時(shí)執(zhí)行很多操作，讓應(yīng)用更快的結(jié)束；這就要快于執(zhí)行較少操作的平臺(tái)，因?yàn)樵撈脚_(tái)上的每一個(gè)處理器只能執(zhí)行很少的操作。

隨著處理器數(shù)量的增加，另一個(gè)問題就會(huì)來影響性能：多個(gè)處理器嘗試訪問同一個(gè)數(shù)據(jù)。

8.2.2 數(shù)據(jù)爭(zhēng)用與乒乓緩存

當(dāng)兩個(gè)線程并發(fā)的在不同處理器上執(zhí)行，并且對(duì)同一數(shù)據(jù)進(jìn)行讀取，通常不會(huì)出現(xiàn)問題；因?yàn)閿?shù)據(jù)將會(huì)拷貝到每個(gè)線程的緩存中，并且可以讓兩個(gè)處理器同時(shí)進(jìn)行處理。不過，當(dāng)有線程對(duì)數(shù)據(jù)進(jìn)行修改的時(shí)候，這個(gè)修改需要更新到其他核芯的緩存中去，就要耗費(fèi)一定的時(shí)間。根據(jù)線程的操作性質(zhì)，以及使用到的內(nèi)存序，這樣的修改可能會(huì)讓第二個(gè)處理器停下來，等待硬件內(nèi)存更新緩存中的數(shù)據(jù)。即便是精確的時(shí)間取決于硬件的物理結(jié)構(gòu)，不過根據(jù)CPU指令，這是一個(gè)特別特別慢的操作，相當(dāng)于執(zhí)行成百上千個(gè)獨(dú)立指令。

思考下面簡(jiǎn)短的代碼段：

std::atomic<unsigned long> counter(0);
void processing_loop()
{
  while(counter.fetch_add(1,std::memory_order_relaxed)<100000000)
  {
    do_something();
  }
}

counter變量是全局的，所以任何線程都能調(diào)用processing_loop()去修改同一個(gè)變量。因此，當(dāng)新增加的處理器時(shí)，counter變量必須要在緩存內(nèi)做一份拷貝，再改變自己的值，或其他線程以發(fā)布的方式對(duì)緩存中的拷貝副本進(jìn)行更新。即使用std::memory_order_relaxed，編譯器不會(huì)為任何數(shù)據(jù)做同步操作，fetch_add是一個(gè)“讀-改-寫”操作，因此就要對(duì)最新的值進(jìn)行檢索。如果另一個(gè)線程在另一個(gè)處理器上執(zhí)行同樣的代碼，counter的數(shù)據(jù)需要在兩個(gè)處理器之間進(jìn)行傳遞，那么這兩個(gè)處理器的緩存中間就存有counter的最新值(當(dāng)counter的值增加時(shí))。如果do_something()足夠短，或有很多處理器來對(duì)這段代碼進(jìn)行處理時(shí)，處理器將會(huì)互相等待；一個(gè)處理器準(zhǔn)備更新這個(gè)值，另一個(gè)處理器正在修改這個(gè)值，所以該處理器就不得不等待第二個(gè)處理器更新完成，并且完成更新傳遞時(shí)，才能執(zhí)行更新。這種情況被稱為高競(jìng)爭(zhēng)(high contention)。如果處理器很少需要互相等待，那么這種情況就是低競(jìng)爭(zhēng)(low contention)。

在這個(gè)循環(huán)中，counter的數(shù)據(jù)將在每個(gè)緩存中傳遞若干次。這就叫做乒乓緩存(cache ping-pong)，這種情況會(huì)對(duì)應(yīng)用的性能有著重大的影響。當(dāng)一個(gè)處理器因?yàn)榈却彺孓D(zhuǎn)移而停止運(yùn)行時(shí)，這個(gè)處理器就不能做任何事情，所以對(duì)于整個(gè)應(yīng)用來說，這就是一個(gè)壞消息。

你可能會(huì)想，這種情況不會(huì)發(fā)生在你身上；因?yàn)?，你沒有使用任何循環(huán)。你確定嗎？那么互斥鎖呢？如果你需要在循環(huán)中放置一個(gè)互斥量，那么你的代碼就和之前從數(shù)據(jù)訪問的差不多了。為了鎖住互斥量，另一個(gè)線程必須將數(shù)據(jù)進(jìn)行轉(zhuǎn)移，就能彌補(bǔ)處理器的互斥性，并且對(duì)數(shù)據(jù)進(jìn)行修改。當(dāng)這個(gè)過程完成時(shí)，將會(huì)再次對(duì)互斥量進(jìn)行修改，并對(duì)線程進(jìn)行解鎖，之后互斥數(shù)據(jù)將會(huì)傳遞到下一個(gè)需要互斥量的線程上去。轉(zhuǎn)移時(shí)間，就是第二個(gè)線程等待第一個(gè)線程釋放互斥量的時(shí)間：

std::mutex m;
my_data data;
void processing_loop_with_mutex()
{
  while(true)
  {
    std::lock_guard<std::mutex> lk(m);
    if(done_processing(data)) break;
  }
}

接下來看看最糟糕的部分：數(shù)據(jù)和互斥量已經(jīng)準(zhǔn)備好讓多個(gè)線程進(jìn)訪問之后，當(dāng)系統(tǒng)中的核心數(shù)和處理器數(shù)量增加時(shí)，很可能看到高競(jìng)爭(zhēng)，以及一個(gè)處理器等待其他處理器的情況。如果在多線程情況下，能更快的對(duì)同樣級(jí)別的數(shù)據(jù)進(jìn)行處理，線程就會(huì)對(duì)數(shù)據(jù)和互斥量進(jìn)行競(jìng)爭(zhēng)。這里有很多這樣的情況，很多線程會(huì)同時(shí)嘗試對(duì)互斥量進(jìn)行獲取，或者同時(shí)訪問變量，等等。

互斥量的競(jìng)爭(zhēng)通常不同于原子操作的競(jìng)爭(zhēng)，最簡(jiǎn)單的原因是，互斥量通常使用操作系統(tǒng)級(jí)別的序列化線程，而非處理器級(jí)別的。如果有足夠的線程去執(zhí)行任務(wù)，當(dāng)有線程在等待互斥量時(shí)，操作系統(tǒng)會(huì)安排其他線程來執(zhí)行任務(wù)，而處理器只會(huì)在其他線程運(yùn)行在目標(biāo)處理器上時(shí)，讓該處理器停止工作。不過，對(duì)互斥量的競(jìng)爭(zhēng)，將會(huì)影響這些線程的性能；畢竟，只能讓一個(gè)線程在同一時(shí)間運(yùn)行。

回顧第3章，一個(gè)很少更新的數(shù)據(jù)結(jié)構(gòu)可以被一個(gè)“單作者，多讀者”互斥量(詳見3.3.2)。乒乓緩存效應(yīng)可以抵消互斥所帶來的收益(工作量不利時(shí))，因?yàn)樗芯€程訪問數(shù)據(jù)(即使是讀者線程)都會(huì)對(duì)互斥量進(jìn)行修改。隨著處理器對(duì)數(shù)據(jù)的訪問次數(shù)增加，對(duì)于互斥量的競(jìng)爭(zhēng)就會(huì)增加，并且持有互斥量的緩存行將會(huì)在核芯中進(jìn)行轉(zhuǎn)移，因此會(huì)增加不良的鎖獲取和釋放次數(shù)。有一些方法可以改善這個(gè)問題，其本質(zhì)就是讓互斥量對(duì)多行緩存進(jìn)行保護(hù)，不過這樣的互斥量需要自己去實(shí)現(xiàn)。

如果乒乓緩存是一個(gè)糟糕的現(xiàn)象，那么該怎么避免它呢？在本章后面，答案會(huì)與提高并發(fā)潛能的指導(dǎo)意見相結(jié)合：減少兩個(gè)線程對(duì)同一個(gè)內(nèi)存位置的競(jìng)爭(zhēng)。

雖然，要實(shí)現(xiàn)起來并不簡(jiǎn)單。即使給定內(nèi)存位置被一個(gè)線程所訪問，可能還是會(huì)有乒乓緩存的存在,是因?yàn)榱硪环N叫做偽共享(false sharing)的效應(yīng)。

8.2.3 偽共享

處理器緩存通常不會(huì)用來處理在單個(gè)存儲(chǔ)位置，但其會(huì)用來處理稱為緩存行(cache lines)的內(nèi)存塊。內(nèi)存塊通常大小為32或64字節(jié)，實(shí)際大小需要由正在使用著的處理器模型來決定。因?yàn)橛布彺孢M(jìn)處理緩存行大小的內(nèi)存塊，較小的數(shù)據(jù)項(xiàng)就在同一內(nèi)存行的相鄰內(nèi)存位置上。有時(shí)，這樣的設(shè)定還是挺不錯(cuò)：當(dāng)線程訪問的一組數(shù)據(jù)是在同一數(shù)據(jù)行中，對(duì)于應(yīng)用的性能來說就要好于向多個(gè)緩存行進(jìn)行傳播。不過，當(dāng)在同一緩存行存儲(chǔ)的是無關(guān)數(shù)據(jù)，且需要被不同線程訪問，這就會(huì)造成性能問題。

假設(shè)你有一個(gè)int類型的數(shù)組，并且有一組線程可以訪問數(shù)組中的元素，且對(duì)數(shù)組的訪問很頻繁(包括更新)。通常int類型的大小要小于一個(gè)緩存行，同一個(gè)緩存行中可以存儲(chǔ)多個(gè)數(shù)據(jù)項(xiàng)。因此，即使每個(gè)線程都能對(duì)數(shù)據(jù)中的成員進(jìn)行訪問，硬件緩存還是會(huì)產(chǎn)生乒乓緩存。每當(dāng)線程訪問0號(hào)數(shù)據(jù)項(xiàng)，并對(duì)其值進(jìn)行更新時(shí)，緩存行的所有權(quán)就需要轉(zhuǎn)移給執(zhí)行該線程的處理器，這僅是為了讓更新1號(hào)數(shù)據(jù)項(xiàng)的線程獲取1號(hào)線程的所有權(quán)。緩存行是共享的(即使沒有數(shù)據(jù)存在)，因此使用偽共享來稱呼這種方式。這個(gè)問題的解決辦法就是對(duì)數(shù)據(jù)進(jìn)行構(gòu)造，讓同一線程訪問的數(shù)據(jù)項(xiàng)存在臨近的內(nèi)存中(就像是放在同一緩存行中)，這樣那些能被獨(dú)立線程訪問的數(shù)據(jù)將分布在相距很遠(yuǎn)的地方，并且可能是存儲(chǔ)在不同的緩存行中。在本章接下來的內(nèi)容中看到，這種思路對(duì)代碼和數(shù)據(jù)設(shè)計(jì)的影響。

如果多線程訪問同一內(nèi)存行是一種糟糕的情況，那么在單線程下的內(nèi)存布局將會(huì)如何帶來哪些影響呢？

8.2.4 如何讓數(shù)據(jù)緊湊？

偽共享發(fā)生的原因：某個(gè)線程所要訪問的數(shù)據(jù)過于接近另一線程的數(shù)據(jù)，另一個(gè)是與數(shù)據(jù)布局相關(guān)的陷阱會(huì)直接影響單線程的性能。問題在于數(shù)據(jù)過于接近：當(dāng)數(shù)據(jù)能被單線程訪問時(shí)，那么數(shù)據(jù)就已經(jīng)在內(nèi)存中展開，就像是分布在不同的緩存行上。另一方面，當(dāng)內(nèi)存中有能被單線程訪問緊湊的數(shù)據(jù)時(shí)，就如同數(shù)據(jù)分布在同一緩存行上。因此，當(dāng)數(shù)據(jù)已傳播，那么將會(huì)有更多的緩存行將會(huì)從處理器的緩存上加載數(shù)據(jù)，這會(huì)增加訪問內(nèi)存的延遲，以及降低數(shù)據(jù)的系能(與緊湊的數(shù)據(jù)存儲(chǔ)地址相比較)。

同樣的，如果數(shù)據(jù)已傳播，在給定緩存行上就即包含于當(dāng)前線程有關(guān)和無關(guān)的數(shù)據(jù)。在極端情況下，當(dāng)有更多的數(shù)據(jù)存在于緩存中，你會(huì)對(duì)數(shù)據(jù)投以更多的關(guān)注，而非這些數(shù)據(jù)去做了什么。這就會(huì)浪費(fèi)寶貴的緩存空間，增加處理器緩存缺失的情況，即使這個(gè)數(shù)據(jù)項(xiàng)曾經(jīng)在緩存中存在過，還需要從主存中添加對(duì)應(yīng)數(shù)據(jù)項(xiàng)到緩存中，因?yàn)樵诰彺嬷衅湮恢靡呀?jīng)被其他數(shù)據(jù)所占有。

現(xiàn)在，對(duì)于單線程代碼來說就很關(guān)鍵了，何至于此呢？原因就是任務(wù)切換(task switching)。如果系統(tǒng)中的線程數(shù)量要比核芯多，每個(gè)核上都要運(yùn)行多個(gè)線程。這就會(huì)增加緩存的壓力，為了避免偽共享，努力讓不同線程訪問不同緩存行。因此，當(dāng)處理器切換線程的時(shí)候，就要對(duì)不同內(nèi)存行上的數(shù)據(jù)進(jìn)行重新加載(當(dāng)不同線程使用的數(shù)據(jù)跨越了多個(gè)緩存行時(shí))，而非對(duì)緩存中的數(shù)據(jù)保持原樣(當(dāng)線程中的數(shù)據(jù)都在同一緩存行時(shí))。

如果線程數(shù)量多于內(nèi)核或處理器數(shù)量，操作系統(tǒng)可能也會(huì)選擇將一個(gè)線程安排給這個(gè)核芯一段時(shí)間，之后再安排給另一個(gè)核芯一段時(shí)間。因此就需要將緩存行從一個(gè)內(nèi)核上，轉(zhuǎn)移到另一個(gè)內(nèi)核上；這樣的話，就需要轉(zhuǎn)移很多緩存行，也就意味著要耗費(fèi)很多時(shí)間。雖然，操作系統(tǒng)通常避免這樣的情況發(fā)生，不過當(dāng)其發(fā)生的時(shí)候，對(duì)性能就會(huì)有很大的影響。

當(dāng)有超級(jí)多的線程準(zhǔn)備運(yùn)行時(shí)(非等待狀態(tài))，任務(wù)切換問題就會(huì)頻繁發(fā)生。這個(gè)問題我們之前也接觸過：超額認(rèn)購(gòu)。

8.2.5 超額認(rèn)購(gòu)和頻繁的任務(wù)切換

多線程系統(tǒng)中，通常線程的數(shù)量要多于處理的數(shù)量。不過，線程經(jīng)常會(huì)花費(fèi)時(shí)間來等待外部I/O完成，或被互斥量阻塞，或等待條件變量，等等；所以等待不是問題。應(yīng)用使用額外的線程來完成有用的工作，而非讓線程在處理器處以閑置狀態(tài)時(shí)繼續(xù)等待。

這也并非長(zhǎng)久之計(jì)，如果有很多額外線程，就會(huì)有很多線程準(zhǔn)備執(zhí)行，而且數(shù)量遠(yuǎn)遠(yuǎn)大于可用處理器的數(shù)量，不過操作系統(tǒng)就會(huì)忙于在任務(wù)間切換，以確保每個(gè)任務(wù)都有時(shí)間運(yùn)行。如第1章所見，這將增加切換任務(wù)的時(shí)間開銷，和緩存問題造成同一結(jié)果。當(dāng)無限制的產(chǎn)生新線程，超額認(rèn)購(gòu)就會(huì)加劇，如第4章的遞歸快速排序那樣；或者在通過任務(wù)類型對(duì)任務(wù)進(jìn)行劃分的時(shí)候，線程數(shù)量大于處理器數(shù)量，這里對(duì)性能影響的主要來源是CPU的能力，而非I/O。

如果只是簡(jiǎn)單的通過數(shù)據(jù)劃分生成多個(gè)線程，那可以限定工作線程的數(shù)量，如8.1.2節(jié)中那樣。如果超額認(rèn)購(gòu)是對(duì)工作的天然劃分而產(chǎn)生，那么不同的劃分方式對(duì)這種問題就沒有太多益處了。之前的情況是，需要選擇一個(gè)合適的劃分方案，可能需要對(duì)目標(biāo)平臺(tái)有著更加詳細(xì)的了解，不過這也只限于性能已經(jīng)無法接受，或是某種劃分方式已經(jīng)無法提高性能的時(shí)候。

其他因素也會(huì)影響多線程代碼的性能。即使CPU類型和時(shí)鐘周期相同，乒乓緩存的開銷可以讓程序在兩個(gè)單核處理器和在一個(gè)雙核處理器上，產(chǎn)生巨大的性能差，不過這只是那些對(duì)性能影響可見的因素。接下來，讓我們看一下這些因素如何影響代碼與數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。