c++
效能提升來自於方方面面:
想要提升效能到極致那善用硬體這個是躲不掉的
主要可分為密集計算類型(受限於 cpu 能力)、密集記憶體存取類型(受限於記憶體),而不同類型的程式有不同類型的策略
以前學的時候好像叫 CPU 密集和 IO 密集?我覺得記憶體密集是 IO 密集的子集
基本上可以用以下工具然後透過 hardware performance counter 檢查:
通常記憶體密集型會有一堆 data cache miss ,而計算密集會有大量使用向量單元、除法器、分支預測錯誤等
密集計算的特徵為:
基本上不是屬於計算密集那就是屬於記憶體密集
部份情況下記憶體密集型可以轉換成計算密集型,計算密集型比記憶體密集型好的地方在於 CPU 處理速度遠快於記憶體,所以效能提升比較明顯
舉例(structure of array):
轉換成 array of structure
這是一種常用於遊戲引擎加速的 data oriented design 的技巧
另一種例子是矩陣計算 AB + C 的時候,仔細觀察下面存取資料 b[k][j]
並非線性存取,這意味著這是個 memory bounding
利用 loop interchange 轉成下面樣子,讓資料訪問變成線性訪問
現代處理器中有個特別的處理單元稱為向量處理,概念是原本一條指令會吃一個 input 然後產出一個 output ,透過這個裝置可以一條指令一次吃四個 input 產出八個 output ,增加處理的資料吞吐量
變成
通常編譯器會主動幫你向量化,這會提升二到六倍的效能,很難在這之上繼續最佳化這部分的 code ,自動向量化可以透過以下編譯器選項開啟:
-Rpass=loop-vectorize -Rpass-analysis=loop-vectorize
-fopt-info-vec-all
向量化看起來好處多多,既不用手動操作又可以提升很多效能,但他仍然有其限制在:
while(ch == '\0')
對於不符合自動向量化的程式也可以做一些人為修改或是告知,讓編譯器更好向量化,以下是幾個可能遇到的情形和對應的解決辦法:
__restrict__
因為處理器速度遠快於記憶體,所以處理器通常是 data starving ,解決辦法就是加上 data cache 盡可能的加速資料存取,但也要程式本身是 cache friendly 才能發揮出效能,而現今主流的範式 OOP 恰好不能很好的運用 cache
*
和 ->
)
切記!最佳化一開始都是先推論,因此一定要做測量,因為很有可能推論錯誤
如果是分成兩個 loop 執行,其一找 max ,其二找 min ,那會占用 memory 頻寬導致速度慢於同個 loop 同時尋找 max min ,因此,同個 loop 就能解決的事就用同個 loop 解決
stl 提供了
std::minmax_element
,不過速度有點慢…
三種 linked list 分別是:
三種排列方式根據資料大小不同其走訪時間分別是:
但是要弄出 sequentail node 的 linked list 那必須得自己搞個 allocator
至於 compact node ,我覺得其實 compact linked list 是 random linked list 的一種極端情況,所以部分時候可以受益於 cache ,但大多時候還是會 miss ,因此還是遠遜於 sequential linked list
當然 sequentail linked list 能在 small size 就稍微贏過 compact node 不全然是 data cache ,處理器中有個機制是 data prefetch ,亦即在處理 i 個資料的時候處理器會想說下一步應該是要處理 i + 1 的資料,因此提前先幫你載入到 cache 中,這樣就會再比沒有 data prefetch 的處理更快一些
vector of pointer 常見於 OOP 的多型,不過無法保證 pointer of object 可以完美的相鄰擺放將導致大量的 data cache miss ,另, OOP 多型依靠 virtual function table ,本質上也是 array of function pointer ,因此也會產生 instruction cache miss
I-cache miss 又可以分為:
參考 The true price of virtual functions in C++, large virtual function 跟 non-virtual 的差異不是太大,但是 small virtual function 跟 non-virtual 差異較大,因此建議把 small virtual function 盡可能的 inline
解決 vector of pointer 無法相鄰導致 cache miss 的辦法是: value of objects , value of objects 分配的時候會被分在一起,這樣就沒有 cache miss 的問題, vector of object 有以下幾個好處:
缺點就是沒有多型少了些彈性,講者的一篇 blog 可以做到多型的 vector process polymorphic classes in lighting speed,本質上是利用 variant 達到這種效果
基本上 class size 和執行效率呈正相關,原因有以下幾個:
解決辦法是:
全部最佳化不見得是好事,可能會帶來其他麻煩,因此在適當的時機選對時間最佳化才是最好的,以下提供幾個要不要最佳化的判斷依據:
要講判斷依據前要先講清楚最佳化的範圍,如果資料可以在 L1 cache 就裝完就稱為小資料基本上也不用最佳化,基本上是 16~32 KB ,如果資料 L3 cache 還裝不下就是大資料,大概是幾個 MB ,這種也不用最佳化