如何提高程序性能

本文主要探討提高程序性能的途徑、方法和最佳實(shí)踐。

總體方向

• 盡可能利用緩存

• 盡可能利用多核

還有一個小方向是盡可能減少內(nèi)存復(fù)制，這個產(chǎn)生出右值引用、移動構(gòu)造函數(shù)、移動賦值等概念。

貌似以上兩條是“很簡單而無干貨的兩句話”，但是卻是確確實(shí)實(shí)的大方向，沿著這兩個大方向，會衍生出很多優(yōu)化方法出來。

沿著這兩個方向，我們的基本方法是分層、折衷與交換。

分層與交換

計(jì)算機(jī)領(lǐng)域中甚至擴(kuò)展到更大范圍，都有一個“魚與熊掌不可兼得”的道理。比如空間（存儲容量、空間復(fù)雜度等）與時間（訪問速度、時間復(fù)雜度等）通常是不可兼顧的。因此產(chǎn)生折衷、分層、“以X換Y”的方法論。

關(guān)于多核并行計(jì)算，有阿姆達(dá)爾定律（英語：Amdahl's law，Amdahl's argument）

以及

其中：

盡可能利用緩存

緩存是填補(bǔ)了存儲系統(tǒng)的不同層級之間的速度差異。

CPU與內(nèi)存的速度差別很大

在CPU流水線的加持下，在精簡指令系統(tǒng)下，通常一條指令只需要一個時鐘周期。而內(nèi)存訪問（假使沒有緩存）通常要耗費(fèi)上百個時鐘周期。兩者差別是上百倍的。直觀的來看也容易理解，內(nèi)存條離CPU在主板上就相隔很遠(yuǎn)，其數(shù)據(jù)總線肉眼可見，而CPU芯片則是很小一塊，其內(nèi)部晶體管是納米級的。

吞吐量與時延

這里說的速度，是時延而不是吞吐量。如果只看吞吐量，內(nèi)存訪問并不慢，因?yàn)槭桥孔x取。如果看時延，內(nèi)存訪問很慢，因?yàn)橐壬习賯€時鐘周期。關(guān)于吞吐量和時延的區(qū)別可以打個比方，就是從幾公里之外的冷凍倉庫里拉一車雪糕到你家里，你要等很久，但是量很大。

芯片內(nèi)的緩存CACHE

緩存是內(nèi)置在芯片里的，分為L1、L2、L3等級別，用L_(N)表示各級緩存，N越小容量越小訪問速度越快，N越大容量越大訪問速度越慢。L1緩存能達(dá)到寄存器級別的訪問速度（即讀寫只需要一個時鐘周期）。

金字塔型的計(jì)算機(jī)存儲系統(tǒng)

計(jì)算機(jī)存儲系統(tǒng)采用分層和折衷的方法，下圖展現(xiàn)了金字塔型的計(jì)算機(jī)存儲系統(tǒng)。越往上容量越小、訪問速度越快；越往下容量越大、訪問速度越慢。不同層級的容量與速度的差別是x10，x100的。數(shù)據(jù)由外存到內(nèi)存，再由內(nèi)存到緩存，再由緩存到寄存器，然后被運(yùn)算器處理。

在多核CPU中，每個核都有自己的L1、L2緩存，而L3及以下的緩存是多核共享的。

image-20221009175138502.png

由于緩存的存在，CPU與內(nèi)存的訪問由直接訪問變成了間接訪問。

CPU <-> 內(nèi)存 
變成了
CPU <-> 緩存 <-> 內(nèi)存</pre>

緩存的工作方式

局部性原理

緩存的工作方式

Cache Line

一個cache line通常有32/64/128字節(jié)，對應(yīng)內(nèi)存中的一塊區(qū)域（映射方法有多種，比如直接映射）

當(dāng)讀取內(nèi)存時，首先看要讀取的內(nèi)存是否在緩存的某個cache line中，如果是，則訪問緩存；否則從內(nèi)存里加載數(shù)據(jù)到緩存的某個cache line中。在寫入內(nèi)存時，也是首先要看寫入的內(nèi)存是否在緩存的某個cache line中，如果是，則寫入到緩存，未來某個時候會回寫到內(nèi)存；否則從內(nèi)存里加載數(shù)據(jù)到緩存的某個cache line中。

對這塊內(nèi)存區(qū)域的寫入，哪怕只是一個字節(jié)，也會使整個cache line失效。

命中率

如果要訪問的內(nèi)存的數(shù)據(jù)已經(jīng)在緩存中了，則成為“命中”，否則就是cache missing。

命中率 = 命中次數(shù) / 總的訪問次數(shù)

命中率很大影響性能，比如：95%命中率（未命中率5%）可能比90%的命中率（未命中率10%）快一倍。這是因?yàn)槲疵卸馁M(fèi)的時間占主要成分，而未命中率5%與10%的差一倍。

提高命中率

盡可能利用緩存就是盡量提升緩存命中率，以下幾種方法都是可以提高命中率的（但注意有些方法在多核環(huán)境下反而對性能有害）：

1. 提高空間局部性

   1. 優(yōu)先使用順序存儲數(shù)據(jù)結(jié)構(gòu)，比如PODArray、底層為順序表的hash map；

   2. 用順序掃描替代隨機(jī)訪問。

2. 提高時間局部性

   1. 讓聲明變量和使用變量的位置盡量靠近。

3. 避免cache line失效。

盡可能利用多核

當(dāng)前CPU芯片的晶體管規(guī)模仍舊遵循摩爾定律，而CPU的單核主頻和運(yùn)算能力已經(jīng)沒有太大發(fā)展了（受到物理特性的限制），而CPU核的數(shù)量在增長。因此一定要利用好多核。

how-to-make-program-faster-img1.png

減少多線程之間的影響

利用好多核的要義就是盡量減少多線程之間的互相干擾，包括且不限于鎖、緩存。

以一個分布式計(jì)數(shù)器作為例子。

讀寫鎖

使用std::shared_mutex 實(shí)現(xiàn)讀寫鎖，代碼如下：

class DistributedCounter {
public:
 typedef long long value_type;
 static std::string name() { return "lockedcounter"; };

private:
 value_type count;
 std::shared_mutex mutable mtx;
public:
 DistributedCounter() : count(0) {}

 void operator++() { std::unique_lock<std::shared_mutex> lock(mtx); ++count; }
 value_type get() const { std::shared_lock<std::shared_mutex> lock(mtx); return count; }

多個線程只有一個鎖，因此線程之間干擾很厲害，效率損失很大。

分桶-讀寫鎖

先設(shè)置多個桶，每個桶都有計(jì)數(shù)器和讀寫鎖，先哈希分片到一個桶上，再對該桶用鎖。

class DistributedCounter
{
 typedef size_t value_type;
 struct bucket
 {
 std::shared_mutex sm;
 value_type count;
 };

 static size_t const buckets{ 128 };
 std::vector<bucket>counts{ buckets };
public:
 static std::string name() { return"lockedarray"; }

 void operator++() {
 size_t index = std::hash<std::thread::id>()(std::this_thread::get_id()) % buckets;
 std::unique_lock<std::shared_mutex> ul(counts[index].sm); counts[index].count++;
 }
 value_type get() { return std::accumulate(counts.begin(), counts.end(), (value_type)0, [](auto acc, auto& x) { std::shared_lock<std::shared_mutex> sl(x.sm); return acc + x.count; }); }
};

多個線程因?yàn)楣５淖饔?，對?nèi)存的訪問分散在不同的桶上，因此線程間的干擾小了很多。但是線程間關(guān)于緩存的干擾比較大。

分桶-獨(dú)占cacheline-讀寫鎖

由于一個cache line有32/64/128字節(jié)，前面的方法會導(dǎo)致多個桶會被裝入一個cache line中，而對cache line中哪怕一個字節(jié)的修改都會使得cache line處于“被修改”狀態(tài)，導(dǎo)致其他CPU核的同一個內(nèi)存位置的cache line失效。

假設(shè)b1, b2, b3, b4能夠被裝入一個cache line中，有4個線程t1, t2, t3, t4處在4個CPU核c1, c2, c3, c4中。t1, t2, t3, t4分別訪問b1, b2, b3, b4。那么會產(chǎn)生4個CPU核的L1緩存中都有一個cache line緩存了b1, b2, b3, b4。當(dāng)線程t1修改了b1時，雖然并沒有修改b2,b3,b4，但是卻導(dǎo)致其他三個核的cache line失效。假如這時t2要訪問b2，明明可以從自己的核的緩存中取值，卻不得不以cache missing的邏輯從內(nèi)存重新加載數(shù)據(jù)。

為了讓每個桶獨(dú)占cache line，加入padding把桶所占的內(nèi)存“撐開”。代碼如下：

class DistributedCounter
{
 typedef size_t value_type;
 struct bucket
 {
 std::shared_mutex sm;
 value_type count;
 char padding[128]; // “撐開”內(nèi)存，獨(dú)占一個cache line。
 };

 static size_t const buckets{ 128 };
 std::vector<bucket>counts{ buckets };
public:
 static std::string name() { return"lockedarray"; }

 void operator++() {
 size_t index = std::hash<std::thread::id>()(std::this_thread::get_id()) % buckets;
 std::unique_lock<std::shared_mutex> ul(counts[index].sm); counts[index].count++;
 }
 value_type get() { return std::accumulate(counts.begin(), counts.end(), (value_type)0, [](auto acc, auto& x) { std::shared_lock<std::shared_mutex> sl(x.sm); return acc + x.count; }); }
};

分桶-獨(dú)占cacheline-原子變量

原子變量通常比鎖更輕量，因?yàn)榭梢跃幾g成特殊的CPU機(jī)器指令，例如 LOCK ADD X, Y 、XCHG等。代碼如下：

class DistributedCounter
{
 typedef size_t value_type;
 struct bucket
 {
 std::shared_mutex sm;
 std::atomic<value_type> count;
 char padding[128]; // “撐開”內(nèi)存，獨(dú)占一個cache line。
 };

 static size_t const buckets{ 128 };
 std::vector<bucket>counts{ buckets };
public:
 static std::string name() { return"lockedarray"; }

 void operator++() {
 size_t index = std::hash<std::thread::id>()(std::this_thread::get_id()) % buckets;
 counts[index].count++;
 }
 value_type get() { return std::accumulate(counts.begin(), counts.end(), (value_type)0, [](auto acc, auto& x) { return acc + x.count.load(); }); }
};

原子變量的訪問時可以指定memory order，默認(rèn)用的是理論上最慢卻能保證結(jié)果一定正確的 順序一致性 的memory order，在這個例子里可以用最快卻最不嚴(yán)格的 relaxed memory order。在此不再贅述。

以下是以上4個方法在128核服務(wù)器上的測試結(jié)果：

how-to-make-program-faster-img2.png

可以看出性能差別很大。

其他方法

其他方法還包括無鎖編程、自旋鎖、pthread的讀寫鎖，linux系統(tǒng)里的futex。

無鎖編程從理論上看是最好的，因?yàn)榫€程之間幾乎完全不干擾。

多核的性能必須在多核的機(jī)器上測試

多核相關(guān)的優(yōu)化，在核數(shù)少的機(jī)器上可能并不能凸顯出來對于性能方面帶來的好處，在核多的機(jī)器上才能凸顯出來性能的提升。

同樣，要根據(jù)實(shí)際運(yùn)行的機(jī)器的特性，做多核和緩存方面的性能優(yōu)化。

單核的流水線

保證每個CPU核的執(zhí)行流水線被充分使用，除了上面的緩存方面的優(yōu)化外（cache missing就會破壞流水線），以下列出一些方法，這些方法也會幫助提高執(zhí)行流水線的利用率。

1. 使用[likely]，[unlikely] 幫助分支判斷；

2. 盡量用const T &，幫助編譯器優(yōu)化；

3. 加 __restrict 關(guān)鍵字幫助編譯器優(yōu)化；

4. 右值情況用右值，減少內(nèi)存拷貝；

5. 選擇合適的memory order，保證正確的前提下盡量少限制指令亂序，指令亂序會提高流水線利用率。

最佳實(shí)踐總結(jié)

1. 盡量避免讓每個線程獨(dú)立訪問的對象或者變量能夠放在同一個cache line上；

2. 只讀的內(nèi)存與經(jīng)常寫入的內(nèi)存盡量不要放在一起，避免被放在同一個cache line上；

3. 把多線程共享的部分盡量分成線程獨(dú)享的分片（分桶）；

4. 盡量避免讓頻繁寫入的內(nèi)存區(qū)域影響其他的內(nèi)存讀寫，即讓該區(qū)域獨(dú)占cache line；

5. 同時訪問的幾個變量或?qū)ο蠹媳M量放在一起；

6. 利用VTune等工具找到cache方面的瓶頸。

另外介紹下C++17的新特性：

• std::hardware_destructive_interference_size 若兩個對象的內(nèi)存地址距離 大于 std::hardware_destructive_interference_size，則不會在一個cache line。

• std::hardware_constructive_interference_size 若兩個對象的內(nèi)存地址距離 小于 std::hardware_destructive_interference_size，則會在一個cache line。

不斷地解決問題并產(chǎn)生新問題

這是一種規(guī)律，舊的問題解決了，并產(chǎn)生新的問題。

由于CPU的頻率受限于物理定律而無法再有效提升，發(fā)展了多核CPU，即一個CPU芯片中包含多個“小CPU“，我們稱之為CPU核心。

隨后發(fā)現(xiàn)內(nèi)存訪問是瓶頸，因?yàn)閮?nèi)存不僅訪問速度慢，而且還不能多核同時訪問。為了解決這個問題引入了核內(nèi)緩存，讓每個CPU核都能并行地獲取運(yùn)算所需要的數(shù)據(jù)。

但這又帶來了新的問題：多個CPU核中的緩存的數(shù)據(jù)如何同步（同一塊內(nèi)存的數(shù)據(jù)可能會被緩存在多個CPU核內(nèi)）。

解決這個問題就引入了MESI協(xié)議。為了在實(shí)施MESI協(xié)議時盡量少“拖累”CPU（即讓CPU核不用等同步完成），于是引入了存儲緩沖區(qū)（store buffer）和無效隊(duì)列（invalidate queue）的概念。

另外為了保證CPU執(zhí)行流水線的效能，編譯器和CPU可能會打亂指令執(zhí)行順序。

但這些優(yōu)化可能讓程序的執(zhí)行結(jié)果變得不正確。因此，為了既保證正確又保證并行性，就引入了內(nèi)存順序（memory order）的概念……

參考資料

1. https://semiwiki.com/ip/312695-white-paper-scaling-is-falling/

2. https://courses.cs.washington.edu/courses/cse378/09wi/lectures/lec15.pdf

3. https://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size

4. https://courses.cs.washington.edu/courses/cse378/09wi/lectures/lec15.pdf