# Introduction to Hardware Efficiency in Cpp
###### tags: `c++`
[video](https://www.youtube.com/watch?v=Fs_T070H9C8)
## Making software fast

效能提升來自於方方面面：

* 軟體架構
* 減少不必要的工作
* 使用更高效的語言
* 善用硬體

想要提升效能到極致那善用硬體這個是躲不掉的

## 硬體提升的種類

主要可分為密集計算類型(受限於 cpu 能力)、密集記憶體存取類型(受限於記憶體)，而不同類型的程式有不同類型的策略

> 以前學的時候好像叫 CPU 密集和 IO 密集？我覺得記憶體密集是 IO 密集的子集

### 確認方式

基本上可以用以下工具然後透過 hardware performance counter 檢查：

* intel 的 vtune
* amd 的 uprof
* pmu-tools
* perf
* LIKWID

通常記憶體密集型會有一堆 data cache miss ，而計算密集會有大量使用向量單元、除法器、分支預測錯誤等

### 密集計算類型

密集計算的特徵為：

* 使用的資料都是基本型別或是 class member 使用幾個基本型別
* 訪問資料都是訪問 array 或 vector 這種連續記憶體
* 其他各種 container: map/tree/set/list/... ，只要走訪是依靠訪問 pointer 的都不是
* 都是 0~N 或 N~1 這種連續訪問
* 常見發生的功能
* 影像處理
* 音頻處理
* 機器學習
* 科學計算
* 通訊

### 記憶體密集型

基本上不是屬於計算密集那就是屬於記憶體密集

## AoS to SoA: 記憶體密集轉型成計算密集

部份情況下記憶體密集型可以轉換成計算密集型，計算密集型比記憶體密集型好的地方在於 CPU 處理速度遠快於記憶體，所以效能提升比較明顯

舉例(structure of array)：

class student {
    string name;
    double average;
};

vector<student> students;

轉換成 array of structure

class students {
    vector<string> name;
    vector<double> average;
};

這是一種常用於遊戲引擎加速的 data oriented design 的技巧

另一種例子是矩陣計算 AB + C 的時候，仔細觀察下面存取資料 `b[k][j]` 並非線性存取，這意味著這是個 memory bounding

for(int i = 0;i < n; i++) {
    for(int j = 0;j < n; j++) {
        for(int k = 0;k < n; k++) {
            c[i][j] = a[i][k] * b[k][j] + c[i][j];
        }
    }
}

利用 loop interchange 轉成下面樣子，讓資料訪問變成線性訪問

for(int i = 0;i < n; i++) {
    for(int k = 0;k < n; k++) {
        for(int j = 0;j < n; j++) {
            c[i][j] = a[i][k] * b[k][j] + c[i][j];
        }
    } 
}

## 最佳化計算密集：vectorization

### Intro
現代處理器中有個特別的處理單元稱為向量處理，概念是原本一條指令會吃一個 input 然後產出一個 output ，透過這個裝置可以一條指令一次吃四個 input 產出八個 output ，增加處理的資料吞吐量

for(int i = 0;i < n; i++) {
    A[i] = B[i] + C[i];
}

變成

for(int i = 0;i < n; i += 4) {
    vec4 B_tmp = load4(B + i);
    vec4 C_tmp = load4(C + i);
    vec4 A_tmp = add4(B_tmp, C_tmp);
    store4(A_tmp, A + i);
}

通常編譯器會主動幫你向量化，這會提升二到六倍的效能，很難在這之上繼續最佳化這部分的 code ，自動向量化可以透過以下編譯器選項開啟：

* clang
* `-Rpass=loop-vectorize -Rpass-analysis=loop-vectorize`
* gcc
* `-fopt-info-vec-all`

### Limits
向量化看起來好處多多，既不用手動操作又可以提升很多效能，但他仍然有其限制在：

* 必須是 simple type
* basic data tyee
* small class
* 編譯器知道你的瓶頸會出現在 memory 而不是 computation
* 迴圈數量可以在執行前就確定
* 不可以邊執行邊更改迴圈條件
* 不可以給個不確定的範圍，比如： `while(ch == '\0')`
* 迴圈內不可太複雜
* 不可以一堆 if else 在迴圈內部
* 迴圈必須獨立存在(外部的更動不會影響迴圈的行為)
* 必須是線性走訪
* 不能 pointer aliasing
* 不能處理的兩個資料同屬一個資料集合， ex: two pointer in same array

### Fixing
對於不符合自動向量化的程式也可以做一些人為修改或是告知，讓編譯器更好向量化，以下是幾個可能遇到的情形和對應的解決辦法：
* loop 內有複雜的判斷
* loop unswitching
* 把跟 loop 無關的判斷移出 loop
* loop fission
* 把 loop 拆成兩部分：可向量化的 A 部分 loop ，不可向量化的 B 部分 loop
* 中途從 loop 內 return/break
* loop sectioning
* 簡單講其實跟 loop fission 滿像的，都是拆 loop 成小 loop ，重點在於怎麼利用小 loop 的結果在後續應用，詳請可以 [codee/glossary-loop-sectioning](https://www.codee.com/knowledge/glossary-loop-sectioning/)
* 非線性走訪記憶體
* Array Of Structure
* 前面提過的技巧
* loop interchange
* 常用在 matrix 相關計算
* pointer aliasing
* 用 `__restrict__`
* 保證兩個 pointer 是獨立的
* 不過也有機會兩個是相互依賴，那就看要怎麼改 code

## 記憶體密集型

因為處理器速度遠快於記憶體，所以處理器通常是 data starving ，解決辦法就是加上 data cache 盡可能的加速資料存取，但也要程式本身是 cache friendly 才能發揮出效能，而現今主流的範式 OOP 恰好不能很好的運用 cache

### 何時會發生 data cache miss ?

* 需要對 pointer dereference 的時候 ( `*` 和 `->` )
* pointer data member
* heap allocated object
* vector of pointers
* chasing pointer
* ex: linked list 的走訪需要訪問 next pointer 到達下一個 linked list
* 隨機走訪記憶體的時候
* 查詢任意複雜結構的時候
* ex: hash_map/set/...

### 何時會發生 data hit

* 線性走訪連續記憶體
* 資料大小和 data cache hit 成正比
* 效能巔峰只可能發生在 array 上
* 盡可能的保存小資料
* 需要同時被訪問的資料應該被擺在一起
* 需要接連被訪問的資料應該按順序擺在隔壁
* linked list 的 node 應該放在隔壁
* binary tree 有 left/right ，其中一個應該被放在隔壁

---

**切記！最佳化一開始都是先推論，因此一定要做測量，因為很有可能推論錯誤**

---

## 案例 1: 在 vector 中分別取得 max 和 min

如果是分成兩個 loop 執行，其一找 max ，其二找 min ，那會占用 memory 頻寬導致速度慢於同個 loop 同時尋找 max min ，因此，**同個 loop 就能解決的事就用同個 loop 解決**

> stl 提供了 `std::minmax_element`，不過速度有點慢...

## 案例 2: 比較三種 linked list 的走訪效率

三種 linked list 分別是：

* random linked list
* node 位於任意位置
* compact linked list
* node 都在一起但不保證相連的 node 相鄰
* sequentail linked list
* 保證相連的 code 也相鄰

三種排列方式根據資料大小不同其走訪時間分別是：
* small size (128)
* random >= compact >= sequentail
* medium size (1M)
* random > compact >> sequential
* large size (64M)
* random >> compact >> sequential

但是要弄出 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 的處理更快一些

## 案例 3: vector of pointer

vector of pointer 常見於 OOP 的多型，不過無法保證 pointer of object 可以完美的相鄰擺放將導致大量的 data cache miss ，另， OOP 多型依靠 virtual function table ，本質上也是 array of function pointer ，因此也會產生 instruction cache miss

I-cache miss 又可以分為：

* small virtual function
* large virtual function

參考 [The true price of virtual functions in C++](https://johnysswlab.com/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 有以下幾個好處：

* 能線性訪問
* 不用 malloc/free
* 小的 function 可以被 inline
* 不會被 virtual function 拖累速度
* 所有 object 會被連續分配在同一塊記憶體上

缺點就是沒有多型少了些彈性，講者的一篇 blog 可以做到多型的 vector [process polymorphic classes in lighting speed](https://johnysswlab.com/process-polymorphic-classes-in-lighting-speed)，本質上是利用 variant 達到這種效果

## 案例 4: class size 和 memory layout

基本上 class size 和執行效率呈正相關，原因有以下幾個：

* class size 變多則放入 cache 的資料也變多，如果資料有些是沒用的就會浪費掉 cache
* 從 memory 讀取大資料的 class 會占用記憶體頻寬

解決辦法是：

* 把會一起用到的資料宣告的時候放在一起，增加被 cache 在一起的機會
* 把無用的資料放到另一個 class 避免佔用 cache

## 其他最佳化建議

* 對於非線性走訪的結構來說最好採用較優的 memory layout
* 用 n-array tree 取代 pointer tree
* 用更好的 memory layout tree
* ex: van Emde Boas layout
* 選用 cache firendly 的 map
* ex: hash map with open addressing
* 選用更快的 stl
* ex: EA stl (美商藝電那個 EA)
* 對於其他資料結構應該盡可能的 compact

## 什麼時候不要最佳化？

全部最佳化不見得是好事，可能會帶來其他麻煩，因此在適當的時機選對時間最佳化才是最好的，以下提供幾個要不要最佳化的判斷依據：

要講判斷依據前要先講清楚最佳化的範圍，如果資料可以在 L1 cache 就裝完就稱為小資料基本上也不用最佳化，基本上是 16~32 KB ，如果資料 L3 cache 還裝不下就是大資料，大概是幾個 MB ，這種也不用最佳化

* 部分技巧只在大資料但是裝不滿 L3 cache 有用
* hash map / binary tree
* 小的 vector 最佳化效果不明顯
* 如果資料結構生命週期太短也不值得去最佳化
* 時常最佳化的時間會大於真的執行時間

## 結論

* 有效率的使用合理的記憶體頻寬
* 盡可能保持小資料
* 常用到的要放在一起
* 線性走訪不要隨機訪問
* 用 vector of objects 不要用 vector of pointer
* 不要重複從記憶體讀同個資料