CS:APP 第 5 章重點提示和練習

資料整理: jserv

最佳化來自對系統的充分認知

Optimization

• 最佳化 vs. 優化
• 國家教育研究院: optimize
  • 最佳化；最優化；優選
• 最佳化之前，務必確保「正確」，否則一切皆是徒勞
  • YouTube: 圍棋的走法和宇宙原子總量誰更多？
  • 費馬大定理 (1995 年，Andrew Wiles 證明定理成立): 當整數 n> 2時，關於 x, y, z 的不定方程式 xⁿ + yⁿ = zⁿ 沒有正整數解，但如果拿計算機，用 x = 3987, y = 4365, n = 12 帶入
    
  • 好像可以推翻費馬大定理？這是計算機能表達的有效位數有限，等式左邊只比右邊大 0.000000002% !

YouTube: 羅輯思維 85 集: 費馬大定理

• 我們當中的絕大多數人，花了人生的十二年時光，六年小學，六年中學，被數學摧殘，我們只知道數學是敲開大學校門的一個敲門磚，自打上了大學之後，這個東西就被我們當做人生當中最痛苦的經驗，被刪除了。
• 原來數學是如此有魅力，它的魅力是光芒萬丈，吸引那麼多智力卓絕的人，把自己的生命獻祭上去，整個數學史，就是一曲波瀾壯闊的史詩。
• 人類知識領域智力領域的任何豐碑，從來都不是用強烈的目的性建造出來的，它的每一塊磚，每一塊瓦，都是由興趣堆積出來的，興趣不僅導致了最後的成功，而且點亮了其中的每一塊磚，每一塊瓦，每一個人的生命。

• 1946 年就有 binary search 的概念，但到了 1960 年代才有精準的數學分析，而到了 1980/1990 年代，大型系統中的 binary search 實作的錯誤才被找出
  • Binary Search

Code Optimization

• 導讀
  • 你所不知道的 C 語言：編譯器和最佳化原理篇
  • 你所不知道的 C 語言：動態連結器篇

slides

asymptotic [/ˌæs.ɪmˈtɑː.t̬ɪk] 漸近的

最佳化編譯器的重要性

Code Motion

• 原本的程式碼
  ​​​​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 運算)
  ​​​​long j;
  ​​​​int ni = n * i;
  ​​​​for (j = 0; j < n; j++)
  ​​​​    a[ni + j] = b[j];
  

但要注意以下不適用 code motion 的例外狀況:

• C 指標作為參數傳入，見 From Source to Binary Page 36 ~ 38
• CS:APP 第 2 章提及的浮點數操作議題

可見到 C 的 array subscripting 會被替換為對應指標操作

2009 年的 Nehalem (採用 45 奈米製程，後期改用 32 奈米製程); 2013 年的 Haswell (和 Ivy Bridge 微架構一樣採用 22 奈米製程)

• 延伸閱讀 CS:APP3 第 6 章，提及記憶體操作的成本

common subexpression elimination (CSE)

Optimization Example: Bubblesort

• slide 10-18

Procedure to Convert String to Lower Case Page 351

• slide 21-26
• 延伸閱讀: Re: [問卦] 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 語言：動態連結器篇 提及 LTO (Link Time Optimization)，有機會對這類案例進行最佳化，但現有技術仍有相當多限制

延伸閱讀: strict aliasing

• 考慮以下程式碼:
  ​​​​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，必須每一次重新計算才行
  • 更精確的來說，就是每個 iteration 都要把 *v1 和 *v2 的值從 memory 裡重新 load 出來 (有點類似 volatile 變數的行為)，所以會對執行時期效能有影響
• 當然 strict aliasing 的標準化並不能解決上述的效能問題。
  • 上述問題的解法是使用 C99 的 restrict 去修飾 pointer 的 type，由程式開發者來保證它們之間絕對不會有 aliasing，讓 compiler 放心的去做最佳化

loop invariant 是證明某個不變的條件 (稱做 invariant Condition)，這個條件在程式進入迴圈前跟進入迴圈後，此條件仍不變。

以 while 迴圈為例:

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 和 Understanding Strict Aliasing

考慮以下程式碼:

void f(){ *((int *) 0xBAD) = 123; }

地址 0xBAD 的內容會是什麼？

0xBAD 這樣用 16 進位數值表達特定人類可理解的意思，稱為 hexspeak

延伸閱讀: The Meaning of Memory Safety

這也讓許多 C subset/extension 存在，例如 Cyclone

Cycles Per Element (CPE) Page 345

考慮到以下向量運算操作的程式碼: Page 347

/* 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 章 以學習計算機結構。

• 減少記憶體存取

考慮以下加總函式，而 ret 為返回地址:

• sum1

void sum1(int *a, int len, int *ret) {
    *ret = 0;
    for (int i = 0; i < len; i++)
        *ret += a[i];
}

• sum2

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
  ​​​​movl (%edi), %eax
  ​​​​imull （%ecx, %edx, 4）, %eax
  ​​​​mov %eax, (%edi)
  

• sum2
  ​​​​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^-3s, 讀作 Milliseconds)。當 len 的長度不斷以 10 的數量級遞增時，sum2 的時間優勢其實並不明顯。在 len = 10⁸ 時，差距僅僅是 140 ms（加速因子k = 1.34, k = sum1 時間 / sum2 時間)，得益於現代硬體架構的進化，如此效能差距會縮減。

• Loop Unrolling

對 sum1 函式的進一步優化:

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⁸ 時，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 的討論，如果我們把加法操作改為乘法呢？

void multi1(int *a, int len, int *ret) {
    *ret = 1;
    for (int i = 0; i < len; i++)
        *ret *= a[i];
}

書本給予一種最佳化實作:

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⁸，差異 140ms, k = 1.43。另外，由於之前的 loop unrolling 也基本上能猜出個大概了。乘法器件耗費的週期巨大，又由於其 pipeline 特性。所以考慮增加每次循環中的乘法次數，而不必等到乘積結果迭代到下次而產生的延時。

重點提示:

1. 減少對相同函式的呼叫，用一個變數保存返回值
2. 對於隱性增加複雜度的系統函數，特別是在循環中的函式要注意
3. 指標操作所引起的一些意想不到的效果，該再三留意;
4. 利用 profiler 來分析程式瓶頸，著重優化瓶頸函式; Page 388
5. Amdahl's law
   • 具象解釋

• CS:APP3e-labs Performance Lab 解題報告 / Performance Lab 筆記
  • 要求你優化兩個圖片處理函數
  • 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₁ 與 S₂，分別求其解 P(S₁) 與 P(S₂)，然後再將其合併得到最後的解 P(S)。要如何計算 P(S₁) 與 P(S₂) 呢？因為是相同問題較小的輸入，所以用遞迴來做就可以了。分治不一定要分成兩個，也可以分成多個，但多數都是分成兩個。那為什麼要均分呢？從下面的舉例說明中會了解。

從一個非常簡單例子來看：在一個陣列中如何找大最大值。迴圈的思考模式是：從前往後一個一個看，永遠記錄著目前看到的最大值。

m = a[0];
for (i = 1 ; i < n; i++)
    m = max(m, a[i]);

分治思考模式：如果我們把陣列在i的位置分成前後兩段 a[0, i - 1] 與 a[i, n]，分別求最大值，再返回兩者較大者。切在哪裡呢？如果切在最後一個的位置，因為右邊只剩一個無須遞迴，那麼會是

int find_m1(int n) {
    if (n == 0) return a[0]; 
    return max(find_m1(n - 1), a[n]);
}

這是個尾遞迴 (Tail Recursion)，在有編譯優化的狀況下可跑很快，其實你可以發現他的行為就是上面那個迴圈的版本。如果我們把他切在中點:

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²⁰⁰，地球已經毀滅了。

再來看個有趣的問題：假設我們有一個程式比賽的排名清單，有些選手是女生有些是男生，我們想要計算有多少對女男的配對是男生排在女生前面的。若以 0 與 1 分別代表女生與男生，那麼我們有一個 0/1 序列 a[n]，要計算

Ans = | {(a[i], a[j]) | i < j 且 a[i] > a[j]} |

迴圈的思考方式：對於每一個女生，計算排在他前面的男生數，然後把它全部加起來就是答案。

for (i = 0, ans = 0 ; i < n ;i++) {
    if (a[i]==0) { 
        cnt = num of 1 before a[i];
        ans += cnt;
    }
}

效率取決於如何計算cnt。如每次拉一個迴圈來重算，時間會跑到 O(n²)，如果利用類似前綴和 (prefix-sum)的概念，只需要線性時間。

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 個。遞迴終止條件是什麼呢？剩下一個就不必找了。

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改寫：

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)，有沒有辦法像上面男女對問題一樣，紀錄一些簡單的資料來減少計算量呢？你或許想用二分搜，但問題是需要重排序，就我所知，除非搞個複雜的資料結構，否則沒有簡單的辦法可以來加速。那麼來看看分治。基本上的想法是從中間切割成兩段，各自遞迴計算逆序數並且各自排序好，排序的目的是讓合併時，對於每個左邊的元素可以笨笨地運用二分搜去算右邊有幾個小於它。

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₂(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語言：遞迴呼叫篇
• On Recursion, Continuations and Trampolines

tags: cs:app, csapp