# [CS:APP](https://hackmd.io/@sysprog/CSAPP) 第 5 章重點提示和練習
:::success
資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv)
:warning: 最佳化來自對系統的充分認知
:::
## Optimization
* [最佳化 vs. 優化](https://www.ptt.cc/bbs/Soft_Job/M.1347718409.A.28B.html)
* 國家教育研究院: [optimize](http://terms.naer.edu.tw/detail/2403595/)
* 最佳化；最優化；優選
* 最佳化之前，務必確保「正確」，否則一切皆是徒勞
* YouTube: [圍棋的走法和宇宙原子總量誰更多？](https://www.youtube.com/watch?v=EidjMIlQ3x4)
* [費馬大定理](https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%A4%A7%E5%AE%9A%E7%90%86) (1995 年，Andrew Wiles 證明定理成立): 當整數 n> 2時，關於 x, y, z 的不定方程式 x^n^ + y^n^ = z^n^ 沒有正整數解，但如果拿計算機，用 x = 3987, y = 4365, n = 12 帶入
* 好像可以推翻費馬大定理？這是計算機能表達的有效位數有限，等式左邊只比右邊大 0.000000002% !
:::info
YouTube: [羅輯思維 85 集: 費馬大定理](https://www.youtube.com/watch?v=bHexlr4b_j8)
* 我們當中的絕大多數人，花了人生的十二年時光，六年小學，六年中學，被數學摧殘，我們只知道數學是敲開大學校門的一個敲門磚，自打上了大學之後，這個東西就被我們當做人生當中最痛苦的經驗，被刪除了。
* 原來數學是如此有魅力，它的魅力是光芒萬丈，吸引那麼多智力卓絕的人，把自己的生命獻祭上去，整個數學史，就是一曲波瀾壯闊的史詩。
* 人類知識領域智力領域的任何豐碑，從來都不是用強烈的目的性建造出來的，它的每一塊磚，每一塊瓦，都是由興趣堆積出來的，興趣不僅導致了最後的成功，而且點亮了其中的每一塊磚，每一塊瓦，每一個人的生命。
:::
* 1946 年就有 binary search 的概念，但到了 1960 年代才有精準的數學分析，而到了 1980/1990 年代，大型系統中的 [binary search 實作的錯誤才被找出](https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues)
* [Binary Search](https://locklessinc.com/articles/binary_search/)
## Code Optimization
* 導讀
* [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/s/Hy72937Me)
* [你所不知道的 C 語言：動態連結器篇](https://hackmd.io/s/HkK7Uf4Ml)
:::info
[slides](https://www.cs.cmu.edu/~213/lectures/10-optimization.pdf)
:::
asymptotic [/ˌæs.ɪmˈtɑː.t̬ɪk] 漸近的
最佳化編譯器的重要性
Code Motion
* 原本的程式碼
```C
void set_row(double *a, double *b, long i, long n) {
for (long j = 0; j < n; j++)
a[n * i + j] = b[j];
}
```
* 轉換為以下: (避免重複的 `n * i` 運算)
```C
long j;
int ni = n * i;
for (j = 0; j < n; j++)
a[ni + j] = b[j];
```
但要注意以下不適用 code motion 的例外狀況:
* C 指標作為參數傳入，見 [From Source to Binary](https://www.slideshare.net/jserv/how-a-compiler-works-gnu-toolchain) Page 36 ~ 38
* [CS:APP 第 2 章提及的浮點數操作議題](https://hackmd.io/s/rJoxSsiuG)
可見到 C 的 array subscripting 會被替換為對應指標操作
2009 年的 [Nehalem](https://en.wikipedia.org/wiki/Nehalem_(microarchitecture)) (採用 45 奈米製程，後期改用 32 奈米製程); 2013 年的 [Haswell](https://en.wikichip.org/wiki/intel/microarchitectures/haswell_(client)) (和 Ivy Bridge 微架構一樣採用 22 奈米製程)
* 延伸閱讀 [CS:APP3 第 6 章](https://hackmd.io/s/H1vQ3vu2z)，提及記憶體操作的成本
[common subexpression elimination](https://en.wikipedia.org/wiki/Common_subexpression_elimination) (CSE)
Optimization Example: Bubblesort
* slide 10-18
Procedure to Convert String to Lower Case ==Page 351==
* slide 21-26
* 延伸閱讀: [Re: [問卦] C程式大神們請進](https://disp.cc/b/163-adct)
```C
static const int ascii_x = 32;
/* Lower to Upper Case; Upper to Lower Case */
static inline char *case_swap(char *in) {
for (int i = 0; in[i] != '\0'; i++)
if (isalpha(in[i]))
in[i] ^= ascii_x;
return in;
}
```
[你所不知道的 C 語言：動態連結器篇](https://hackmd.io/s/HkK7Uf4Ml) 提及 LTO (Link Time Optimization)，有機會對這類案例進行最佳化，但現有技術仍有相當多限制
延伸閱讀: [strict aliasing](http://blog.tinlans.org/2010/01/09/strict-aliasing/)
* 考慮以下程式碼:
```C=
void foo(int *v1, int *v2, int *result, int count) {
while(count--) {
*result += *v1 + *v2;
}
}
```
* 大部分的人都以為編譯器為了做最佳化，會去把 `*v1 + *v2` 的算式往迴圈外面提，然後將 `*v1 + *v2` 的結果存到一個暫時變數上，再把迴圈裡的算式直接用那個暫時變數代換以節省重複運算的時間。不過這是不對的！
* 因為編譯器不知道會不會有人寫 foo(&var, &var, &var, 1000) 來呼叫 foo，所以會假設所有的 pointer 之間都有 aliasing。
* 簡單說就是假設 *result 被改變了，那麼 *v1 和 *v2 的值也會跟著改變
* 所以不能像上面那樣把 *v1 + *v2 的結果視為 [loop invariant](https://en.wikipedia.org/wiki/Loop_invariant)，必須每一次重新計算才行
* 更精確的來說，就是每個 iteration 都要把 *v1 和 *v2 的值從 memory 裡重新 load 出來 (有點類似 volatile 變數的行為)，所以會對執行時期效能有影響
* 當然 strict aliasing 的標準化並不能解決上述的效能問題。
* 上述問題的解法是使用 C99 的 restrict 去修飾 pointer 的 type，==由程式開發者來保證==它們之間絕對不會有 aliasing，讓 compiler 放心的去做最佳化
:::info
loop invariant 是證明某個不變的條件 (稱做 invariant Condition)，這個條件在程式進入迴圈前跟進入迴圈後，此條件仍不變。
以 while 迴圈為例:
```C
while (A) {
// Body
}
```
假設一個 invariant 條件叫做 `X` ，這個 `X` 條件在 while 檢查 A 條件時都維持原狀，一進入 Body 時可能改變 `X` 條件，但一執行完 Body 後 X 又恢復原貌，這種條件就是一個典型的 invariant condition。
證明 loop invariant 需要 3 步驟：
1. initialization: 描述 invariant condition 在迴圈執行第一個 iteration 前，就成立;
2. maintenance: 描述 invariant condition 在迴圈的任一 iteration 執行前跟執行後都維持成立;
3. termination：迴圈執行結束後，invariant condition 能夠展示整體演算法的正確性;
:::
strict-aliasing 衍生的型態問題非常複雜，可見 [C99 and type-punning – making sense of a broken language specification](https://davmac.wordpress.com/2010/02/26/c99-revisited/) 和 [Understanding Strict Aliasing](https://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html)
考慮以下程式碼:
```C
void f(){ *((int *) 0xBAD) = 123; }
```
地址 0xBAD 的內容會是什麼？
> `0xBAD` 這樣用 16 進位數值表達特定人類可理解的意思，稱為 [hexspeak](https://en.wikipedia.org/wiki/Hexspeak)
延伸閱讀: [The Meaning of Memory Safety](https://arxiv.org/pdf/1705.07354.pdf)
這也讓許多 C subset/extension 存在，例如 [Cyclone](https://en.wikipedia.org/wiki/Cyclone_(programming_language))
Cycles Per Element (CPE) ==Page 345==
考慮到以下向量運算操作的程式碼: ==Page 347==
```C
/* data structure for vectors */
typedef struct {
size_t len;
data_t *data;
} vec;
/* retrieve vector element and store at val */
int get_vec_element(*vec v, size_t idx, data_t *val) {
if (idx >= v->len)
return 0;
*val = v->data[idx];
return 1;
```
如果我們施加以下最佳化手段:
* 將 `vec_length` 搬出迴圈
* 避免每次運算都要檢查邊界範圍 (將函數 `get_vec_element` 從迴圈中拿出來，CPE 基本上沒有改變，因爲這些檢測總是預測索引是在界內的，所以是高度可預測的)
* 消去重複的運算
除了上述和處理器架構無關的最佳化，事實上進階最佳化手段往往鎖定現代處理器的特徵: ==Page 357==
- [ ] Superscalar Processor ==Page 360==
- [ ] Loop Unrolling
- [ ] SIMD ==Page 376==
- [ ] Branch Prediction ==Page 379==
回頭閱讀 [CS:APP 第 4 章](https://hackmd.io/s/ByKFm4CFz) 以學習計算機結構。
- [ ] 減少記憶體存取
考慮以下加總函式，而 `ret` 為返回地址:
* sum1
```C
void sum1(int *a, int len, int *ret) {
*ret = 0;
for (int i = 0; i < len; i++)
*ret += a[i];
}
```
* sum2
```C
void sum2(int *a, int len, int *ret) {
int s = 0;
for (int i = 0; i < len; i++)
s += a[i];
*ret = s;
}
```
兩個函式的功能完全一樣，而且 sum1 也來得更直觀些，sum2 有時就會讓人不解為何要引入一個中間變數 s 來保存累加和。
反組譯這兩段程式碼:
* sum1
```C
movl (%edi), %eax
imull （%ecx, %edx, 4）, %eax
mov %eax, (%edi)
```
* sum2
```C
imull (%ecx, %edx, 4), %eax
```
sum1 中對 ret 的 deference 會導致從 `%edi (ret)` 的地址中取值 (*ret) 指派給 `%eax`，然後再從 `%eax` 指定回( %edi) 這個過程。而循環 len 次就會多出 2 * len 道指令。所以 sum2 的效率要高，那麼高多少呢，在 Intel Core i5 M520 2.40GHz 做實驗可得:
注意，這裡的時間單位是 ms (10^-3^s, 讀作 [Milliseconds](https://www.timecalculator.net/milliseconds-to-seconds))。當 len 的長度不斷以 10 的數量級遞增時，`sum2` 的時間優勢其實並不明顯。在 len = 10^8^ 時，差距僅僅是 140 ms（加速因子k = 1.34, k = sum1 時間 / sum2 時間)，得益於現代硬體架構的進化，如此效能差距會縮減。
- [ ] Loop Unrolling
對 sum1 函式的進一步優化:
```C
void sum3(int *a, int len, int *ret) {
int s = 0;
int limit = len - 2;
int i;
for (i = 0; i < limit; i += 3)
s += a[i] + a[i + 1] + a[i + 2];
for ( ; i < len; i++)
s += a[i];
*ret = s;
}
```
len = 10^8^ 時，sum3 相對於 sum2 縮減 172ms (k = 1.74)，相對 sum1 縮減 312ms (k = 2.33)。為什麼會有這種提高？可以看到在循環中步長變為了3，那麼為什麼要是 3 而不是其他呢？
這就需要理解計算機結構。
理想的計算機中 (例如 Alan Turing 的抽象機器)，硬體資源可以是無窮無盡，於每個週期我們都有無限的計算器件可用。看到在第三週期用到了 `jl`, `cmpl`, `incl` 硬體資源，但其實都要用到加法器。
反過來看，真實計算機的硬體資源也不可能無限多。考慮到只能有兩個加法器的狀況，在同一週期，我們只能有兩個涉及加法的指令。那麼就有了如下的現實中的計算版本。顯然效率要比理想版本差，效率拖後約 1 倍。
如何用手頭有限的資源創造最大的效益，就是最佳化的策略。load 指令的週期是一般指令的 3倍，而 load 可以 pipeline 執行，那麼儘量讓 load 做事，就是我們所期望的改進。於是就有上述的 `sum3`:
目的很明顯，儘量減少 `addl`, `cmpl` 和 `jl` 這些指令的執行，這樣就不至於太受加法器資源的限制，另外儘量利用 load 的 pipeline 執行特性。那麼如何減少 `jl` 的執行呢？終於想到了加大每次步長了吧。又為什麼是 3 呢？想到了load的週期是 3 了吧。謎團終於解開，看看最終版本的 sum3 是如何在機器中執行的：
看到 3 步一循環的方法能有效地降低 `jl` 的執行，同時充分地利用了load 的 pipeline 特性。最後，這個版本相對理想版本效率拖後約 0.33倍。
既然能增加性能又為什麼要謹慎呢？問題是，以後呢？再以後呢？讓我們看得遠一點，再遠一點。硬件的發展總是如此之快，加法器會有的，load 會更快的。然後呢，然後就是，你做的優化還得隨著硬體不斷修正。
- [ ] Loop Splitting
繼續 sum1 的討論，如果我們把加法操作改為乘法呢？
```C
void multi1(int *a, int len, int *ret) {
*ret = 1;
for (int i = 0; i < len; i++)
*ret *= a[i];
}
```
書本給予一種最佳化實作:
```C
void multi2(int *a, int len, int *ret) {
int limit = len - 1;
int m0 = 1;
int m1 = 1;
int i;
for (i = 0; i < limit; i += 2) {
m0 *= a[i];
m1 *= a[i + 1];
}
for ( ; i < len; i++)
m0 *= a[i];
*ret = m0 * m1;
}
```
m0 計算偶數下標的乘積，而 m1 計算奇數下標。最後合併。看看到底有多快：
Len = 10^8^，差異 140ms, k = 1.43。另外，由於之前的 loop unrolling 也基本上能猜出個大概了。乘法器件耗費的週期巨大，又由於其 pipeline 特性。所以考慮增加每次循環中的乘法次數，而不必等到乘積結果迭代到下次而產生的延時。
重點提示:
1. 減少對相同函式的呼叫，用一個變數保存返回值
2. 對於隱性增加複雜度的系統函數，特別是在循環中的函式要注意
3. 指標操作所引起的一些意想不到的效果，該再三留意;
4. 利用 profiler 來分析程式瓶頸，著重優化瓶頸函式; ==Page 388==
5. [Amdahl's law](https://en.wikipedia.org/wiki/Amdahl%27s_law)
* [具象解釋](https://chi_gitbook.gitbooks.io/personal-note/content/amdahls_law.html)
* [CS:APP3e-labs Performance Lab 解題報告](http://zxcpyp.com/csapp/2017/11/19/Performance-Lab) / [Performance Lab 筆記](https://github.com/Exely/CSAPP-Labs/blob/master/notes/perflab.md)
* 要求你優化兩個圖片處理函數
* rotate: 把圖片逆時針旋轉 90°
* smooth: 使圖片變平滑
```
Rotate: Version = rotate() function:
Dim 64 128 256 512 1024 Mean
Your CPEs 2.6 2.8 3.9 5.6 8.3
Baseline CPEs 14.7 40.1 46.4 65.9 94.5
Speedup 5.6 14.5 12.0 11.8 11.3 10.5
Smooth: Version = smooth() function:
Dim 32 64 128 256 512 Mean
Your CPEs 19.3 21.7 21.9 22.1 17.8
Baseline CPEs 695.0 698.0 702.0 717.0 722.0
Speedup 36.1 32.1 32.1 32.5 40.6 34.5
```
## 遞迴與最佳化
電腦程式中，副程式直接或間接呼叫自己就稱為遞迴。遞迴算不上演算法，只是程式流程控制的一種。程式的執行流程只有兩種:
* 循序，分支(迴圈)
* 呼叫副程式(遞迴)
迴圈是一種特別的分支，而遞迴是一種特別的副程式呼叫。
不少初學者以及教初學者的人把遞迴當成是複雜的演算法，其實單純的遞迴只是另一種函數定義方式而已，在程式指令上非常簡單。初學者為什麼覺得遞迴很難呢？因為他跟人類的思考模式不同，電腦的兩種思維模式：窮舉與遞迴(enumeration and recursion)，窮舉是我們熟悉的而遞迴是陌生的，而遞迴為何重要呢？因為他是思考好的演算法的起點，例如分治與動態規劃。
分治：一刀均分左右，兩邊各自遞迴，返回重逢之日，真相合併之時。
分治 (Divide and Conquer) 是種運用遞迴的特性來設計演算法的策略。對於求某問題在輸入 S 的解 P(S) 時，我們先將 S 分割成兩個子集合 S~1~ 與 S~2~，分別求其解 P(S~1~) 與 P(S~2~)，然後再將其合併得到最後的解 P(S)。要如何計算 P(S~1~) 與 P(S~2~) 呢？因為是相同問題較小的輸入，所以用遞迴來做就可以了。分治不一定要分成兩個，也可以分成多個，但多數都是分成兩個。那為什麼要均分呢？從下面的舉例說明中會了解。
從一個非常簡單例子來看：在一個陣列中如何找大最大值。迴圈的思考模式是：從前往後一個一個看，永遠記錄著目前看到的最大值。
```Clike
m = a[0];
for (i = 1 ; i < n; i++)
m = max(m, a[i]);
```
分治思考模式：如果我們把陣列在i的位置分成前後兩段 a[0, i - 1] 與 a[i, n]，分別求最大值，再返回兩者較大者。切在哪裡呢？如果切在最後一個的位置，因為右邊只剩一個無須遞迴，那麼會是
```C
int find_m1(int n) {
if (n == 0) return a[0];
return max(find_m1(n - 1), a[n]);
}
```
這是個尾遞迴 (Tail Recursion)，在有編譯優化的狀況下可跑很快，其實你可以發現他的行為就是上面那個迴圈的版本。如果我們把他切在中點:
```C
int find_m2(int left, int right) { // 範圍=[ left,right) 慣用左閉右開區間
if (right - left == 1) return a[left];
int mid = (left + right) / 2 ;
return max(find_max(left, mid), find_max(midi, right);
}
```
效率一樣是線性時間，會不會遞迴到 stack overflow 呢？放心，如果有200 層遞迴陣列可以跑到 2^200^，地球已經毀滅了。
再來看個有趣的問題：假設我們有一個程式比賽的排名清單，有些選手是女生有些是男生，我們想要計算有多少對女男的配對是男生排在女生前面的。若以 0 與 1 分別代表女生與男生，那麼我們有一個 0/1 序列 a[n]，要計算
```
Ans = | {(a[i], a[j]) | i < j 且 a[i] > a[j]} |
```
迴圈的思考方式：對於每一個女生，計算排在他前面的男生數，然後把它全部加起來就是答案。
```C
for (i = 0, ans = 0 ; i < n ;i++) {
if (a[i]==0) {
cnt = num of 1 before a[i];
ans += cnt;
}
}
```
效率取決於如何計算cnt。如每次拉一個迴圈來重算，時間會跑到 O(n^2^)，如果利用類似前綴和 (prefix-sum)的概念，只需要線性時間。
```C
for (i = 0, cnt = 0, ans = 0 ; i <n ;i++) {
if (a[i] == 0)
ans += cnt;
else cnt++;
}
```
接下來看分治思考模式。如果我們把序列在 i 處分成前後兩段 a[0, i - 1] 與 a[i, n]，任何一個要找的 (1, 0) 數對只可能有三個可能：都在左邊、都在右邊、或是一左一右。所以我們可以左右分別遞迴求，對於一左一右的情形，我們若知道左邊有 x 個 1 以及右邊有 y 個 0，那答案就有 xy 個。遞迴終止條件是什麼呢？剩下一個就不必找了。
```C
int dc(int left, int right) { // 範圍=[ left,right) 慣用左閉右開區間
if (right - left < 2) return 0;
int mid = (left + right) / 2; // 均勻分割
int w = dc(left, mid) + dc(mid, right);
計算x = 左邊幾個 1, y = 右邊幾個 0
return w + x * y;
}
```
時間複雜度呢？假設把範圍內的資料重新看一遍去計算 0 與 1 的數量，那需要線性時間，整個程序的時間變成 T(n) = 2T(n/2) + O(n)，結果是O(nlogn)，不好。比迴圈的方法差，原因是因為我們計算 0/1 的數量時重複計算。我們讓遞迴也回傳 0 與 1 的個數，效率就會改善了，用 python改寫：
```python
def dc(left, right):
if right - left == 1:
if ar[left]==0: return 0, 1, 0 # 逆序數，0的數量，1的數量
return 0, 0, 1
mid = (left + right) // 2 #整數除法
w1, y1, x1 = dc(left,mid)
w2, y2, x2 = dc(mid,right)
return w1 + w2 + x1 * y2, y1 + y2, x1 + x2
```
時間效率是 $T(n) = 2T(n/2) + O(1)$，所以結果是 $O(n)$。
如果分治可以做的迴圈也可以，那又何必學分治？第一，複雜的問題不容易用迴圈的思考找到答案；第二，有些問題迴圈很難做到跟分治一樣的效率。你可以不信我講的第一點，我們可以來看看第二點。上述男女對的問題其實是逆序數對問題的弱化版本：給一個數字序列，計算有多少逆序對，也就是
```
| {(a[i], a[j]) | i < j 且 a[i] > a[j]} |。
```
迴圈的思考模式一樣去算每一個數字前方有多少大於它的數，直接做又搞到O(n^2)，有沒有辦法像上面男女對問題一樣，紀錄一些簡單的資料來減少計算量呢？你或許想用二分搜，但問題是需要重排序，就我所知，除非搞個複雜的資料結構，否則沒有簡單的辦法可以來加速。那麼來看看分治。基本上的想法是從中間切割成兩段，各自遞迴計算逆序數並且各自排序好，排序的目的是讓合併時，對於每個左邊的元素可以笨笨地運用二分搜去算右邊有幾個小於它。
```cpp
LL sol(int le, int ri) { // 區間 = [le,ri)
if (ri-le == 1) return 0;
int mid = (ri + le) / 2;
LL w = sol(le, mid) + sol(mid, ri);
LL t = 0;
for (int i = le; i < mid; i++)
t += lower_bound(ar + mid, ar + ri, ar[i]) - (ar + mid); // C++內建二分搜
sort(ar + le, ar + ri);
return w + t;
}
```
時間複雜度呢？即使我們笨笨地把兩個排好序的序列再整個重排，T(n) = 2T(n/2) + O(nlog(n))，結果是 O(nlog~2~(n))，十萬筆資料不需要一秒，比迴圈的方法好多了。為什麼說笨笨地二分蒐與笨笨地重新排序呢？對於兩個排好序的東西要合併其實可以用線性時間。那二分搜呢？沿路那麼多個二分搜其實可以維護兩個註標一路向右就好了。所以事實上不需要複雜的資料結構可以做到 O(nlogn)，熟悉演算法的人其實看得出來，這個方法基本上就是很有名的 merge sort，跟 quick sort 一樣常拿來當作分治的範例。另外，如果merge sort的分割方式如果是 [left, right - 1] [right - 1, right]，右邊只留一個，那就退化成 insertion sort 的尾遞迴。
Tail recursion 是遞迴的一種特殊形式，副程式只有在最後一個動作才呼叫自己。以演算法的角度來說，recursion tree 全部是一脈單傳，所以時間複雜度是線性個該副程式的時間。不過遞迴是需要系統使用 stack 來儲存某些資料，於是還是會有 stack overflow 的問題。但是從編譯器的角度來說，因為最後一個動作才呼叫遞迴，所以很多 stack 資料是沒用的，所以他是可以被優化的。基本上，優化以後就不會有時間與空間效率的問題。
注意: Python 沒有 tail recursion 優化，而且 stack 深度不到 1000。C 要在編譯器開啟最佳化時才會進行 tail recursion 的最佳化。
延伸閱讀:
* [你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl)
* [On Recursion, Continuations and Trampolines](https://eli.thegreenplace.net/2017/on-recursion-continuations-and-trampolines/)
###### tags: `cs:app`, `csapp`
Sign in with Wallet
Connect another wallet