C++性能優化常用技巧

一. 選擇合適的數據結構

1.1 map與unordered_map的選擇

如果僅僅只需要使用到快速查找的特性，那么unordered_map更加合適，他的復雜度是O(1)。如果還需要排序以及范圍查找的能力，那么就選擇map。

1.2 vector與list的選擇

通常情況下，順尋存儲一些數據，然后通過下標進行查找，就選擇vector。那么什么時候選擇list呢？常見的一個用法就是在LRU 緩存的實現中，我們會使用list來存放緩存結點，而不是vector，主要原因就在于list的插入和刪除是高效的。

1.3 unordered_map與自定義查找表的選擇

如果不需要復雜的哈希函數，僅通過數組下標的形式就能完成哈希，比如key是26個字母或者連續的數字。此時只需要定義一個數組就能實現哈希存儲（自定義查找表）。

二. 選擇合適的算法

算法對性能的影響是值得考慮的，以排序算法舉例：

快速排序：適合數據比較均勻的場景，如果數據已經有序或者接近有序，此時快速排序會退化到O(n*n)的復雜度。
堆排序：適合求topK問題。
歸并排序：O(n)的空間復雜度，但是排序性能不會因為數據本身已經有序而退化。
冒泡排序：一般情況下不推薦此排序。性能較差。

三. 避免不必要的拷貝

3.1 使用引用

引用可以直接與被引用對象共享同一份存儲，可以認為引用是給對象起一個別名。如下示例代碼：

// 形參使用引用
void show(const std::string& str)
{// do something
}std::vector<std::string> strs;
/*
對strs進行填充
*/
// 使用引用接收返回值，前提是函數返回對象的引用
const std::string& str = strs[1];

3.2 使用移動語義

移動語義一般用在初始化對象或者給對象賦值時，可以避免對象的拷貝。如下代碼：

std::string stra = "abc";
// 拷貝stra對象
std::string strb = stra;
// 移動strb的資源到strc中
std::string strc = std::move(strb);

3.3 返回值優化（RVO）

通常編譯器都有RVO優化的功能，它允許直接在調用者的棧幀上構造對象，從而避免了額外的拷貝和資源析構的開銷。如下代碼：

class A {
public:A() {}~A() {}A(const A& rhs) {}A(A&& rhs) {}
};int func()
{A a;return a;
}int main()
{A a = func();return 0;
}

上述代碼中，返回值優化之后，類A的構造函數和析構函數只被調用一次，不會產生臨時變量的構造與析構，以及拷貝構造的過程。

四. 合適的內存管理

4.1 智能指針

在管理動態內存時，智能指針可以幫助我們實現更可靠的內存管理，避免內存泄漏等嚴重問題。C++11中提供了unique_ptr和shared_ptr兩個智能指針，那么該如何選擇呢？

shared_ptr：共享智能指針。一個對象可能在多個地方被共享。
unique_ptr：獨占智能指針。一個對象只能被一個智能指針對象所擁有。

通常情況下，如果能明確是獨占的場景，那么就選擇unique_ptr，雖然shared_ptr也能保證正確性，但是后者性能要比前者差30%。因為uniqe_ptr更接近裸指針，而shared_ptr內部實現相對復雜（引用計數、控制塊等）。

4.2 內存池

內存池是一個預先申請和分配好的內存區域。在需要申請內存資源時，可以直接在內存池中獲取，在釋放內存時，將內存返還給內存池。從而避免了頻繁的內存分配和釋放的過程。google的tcmalloc就提供了這樣的功能。

4.3 對象池

對象池同樣也是一種預先申請和分配內存的技術，區別于內存池的是，其針對的是特定的類對象的內存管理。如果一個類型需要頻繁的進行對象的創建和釋放，并且對象的創建比較耗時。那么我們可以選擇使用池化技術，預先創建好一定數量的對象，放到對象池中。其實很多池化技術都屬于這個范疇，只是針對不同場景，有其獨特的叫法，如MySQL的連接池、線程池等等。

4.4 棧內存的管理

通常我們只需要管理堆內存，而棧內存交給操作系統來管理。但是棧內存的申請和初始化依舊是由程序員來控制的，而操作系統只負責內存的分配和釋放。考慮如下場景：

void func()
{for (int i = 0; i < 999999; ++i) {char data[1000000];// do something}
}

上述data在每一次循環都需要分配一次內存，然后對其進行操作。如果data的創建可以放到循環體之外進行也不影響程序的正確性。那么data的內存分配只需要一次即可。
事實上，我們還可以繼續優化。因為這塊內存很大，函數也可能會被頻繁調用，每次調用都會重復申請一大塊內存。所以考慮創建一個靜態的data變量，或者靜態的全局變量。只要它能滿足程序的正確性要求。何樂而不為呢？當然靜態變量在多線程環境下會存在數據競爭的問題。此時還可以考慮使用threadlocal變量。

五、減少函數調用

5.1 使用內聯函數

一次函數調用涉及兩次指令跳轉。如果一個函數頻繁調用，可以使用內聯機制來避免函數的調用。C++11提供了inline關鍵字，來告訴編譯器被修飾的函數可以在調用處進行替換。一般這樣的函數是一些功能簡單，代碼行較少的函數。當然是否內聯取決于編譯器，inline只是給編譯器建議。是否內聯可通過查看匯編代碼來確認。

5.2 減少函數遞歸調用

函數遞歸通常寫起來比較方便，并且也更好理解。但是函數遞歸帶來的開銷是巨大的，隨著遞歸深度的加深，性能也會受到影響。稍有不慎，甚至會造成棧溢出。所以應該盡量避免使用遞歸函數，考慮使用迭代或者只使用尾遞歸（編譯器優化，只需要當前的棧幀空間，無需開辟新空間）的方式。

六、多線程處理

多線程可以利用多核特性，同時處理多個任務，從而提高程序性能。多線程常常涉及數據競爭的問題，為了提高多線程的性能，應減少數據競爭，常見的方法有：

使用原子變量。
使用讀寫鎖。
降低鎖的持有時間。
使用線程池模型，重復利用線程資源，利用多隊列減少工作線程間的數據競爭。
使用無鎖數據結構，避免頻繁的線程上下文切換。
減少需要共享的狀態。

七、編譯器優化

在考慮性能問題之前，首先得開啟編譯器優化，很多時候，代碼雖然寫的不是最優的，但是在開啟編譯優化之后，往往能達到很好的優化效果。常見的優化選項：

O0：不做任何優化。
O1：主要對代碼的分支，常量以及表達式等進行優化。
O2：會嘗試更多的寄存器級的優化以及指令級的優化。
O3：在O2的基礎上進行更多的函數內聯優化，因此目標代碼會更大，但執行速度會更快。

八、指令級優化

8.1 SIMD指令

SIMD（單指令多數據）指的是具有多個處理元件的計算機同時對多個數據執行相同操作的過程。以加法為例，通常情況下，我們需要先取操作數1，再取操作數2，然后求和。而SIMD指令則支持同時取多個操作數，然后執行求和運算。也就是說取操作數的過程是并行的。在gcc中可以通過添加ftree-vectorize編譯選項，或者開啟O2優化，就可以讓編譯器使用SIMD優化代碼。

九、提高緩存命中率

CPU有3級緩存L1、L2、L3，其中L1離核心最近，因此速度也最快。由于緩存有大小限制，因此只有少量的數據和指令會被加載到緩存中，所以經常會出現緩存無法命中的問題。因此提高cache命中率就可以提高程序性能。

9.1 選擇合適的數據結構

數據結構多使用連續的存儲，如vector，而少使用list、map這種非連續存儲類型。因為連續的內存通常會被一起加載到緩存中。

9.2 內存對齊

內存不對齊的情況下，cpu可能需要夸多個內存行去獲取數據。從而增加了cpu的訪存次數，也增加了緩存不命中的可能性。

9.3 減少條件分支

程序中的條件判斷，如 if-else 語句，可以通過邏輯重組或使用分支預測優化來提高緩存命中率。在某些情況下，消除不必要的條件判斷或將其重構為更高效的形式可以減少緩存行的加載和卸載，從而提高性能。例如，使用gcc的提供的關鍵字__builtin_expect來告訴編譯器哪個分支命中的概率最高，從而實現優化。