---
tags: sysprog
---

# 2019q3 Homework3 (list)

## Merge Sort 實做與效能分析

根據理論分析，我們知道在平均狀況下，Merge Sort 與 Quick Sort 的表現差不多，而 Insertion Sort 的表現會比前兩者差：
| 排序法 | 最佳 | 平均 | 最差 |
| ---------- | ---------- | --------- | --------- |
| insert sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| Quick Sort | $O(nlgn)$ | $O(nlgn)$ | $O(n^2)$ |
| Merge Sort | $O(nlgn)$ | $O(nlgn)$ | $O(nlgn)$ |

而以亂數產生的 linked list 數列做排序實驗，也確實呈現出同樣的趨勢

但光看平均表現還不夠，接下來我將會實驗對 3 種 sorting 各自的最糟狀況和平均狀況進行效能比較：

#### Insertion Sort
根據目前的實做方式，insertion sort 會從 sorted list 的 head 開始尋找新元素該放到哪個位置，所以最糟狀況會出現在「原始數列為 decending order」的情況

static inline void decending_array(uint16_t *operations, uint16_t len)
{
    for (int i = 0; i < len; i++) {
        operations[i] = len - 1 - i;
    }
}


從圖中可以看到最糟狀況和平均狀況表現都差不多，同為 $O(n^2)$

#### Quick Sort
目前 Quick Sort 的實做方法是屬於 fisrt partition ，所以最糟狀況會出現在「原始數列為 ascending order 」的情況

static inline void ascending_array(uint16_t *operations, uint16_t len)
{
    for (int i = 0; i < len; i++) {
        operations[i] = i;
    }
}


可以看到 Quick Sort 平均狀況比 Insertion Sort 好，為 $O(nlogn)$。 但是最糟狀況與 Insertion Sort 相同，為 $O(n^2)$。

#### Merge Sort

對於 Merge Sort 來說，最糟狀況就是「需要進行最多次數值比較」的情況。

從 bottom up 的角度來解釋：
1. 假設有一組數列 {0,1,2,3,4,5,6,7}
2. 最後一次 merge 最糟的情況會出現在 {0,2,4,6} {1,3,5,7}，因為所有元素都至少會被拿來比較 1 次
3. 倒數第二次 merge 最糟的情況會出現在 {0,4} {2,6} 和 {1,5} {3,7}，原因和 step.2 相同
4. 為了讓倒數第二次 merge 可以成為如 step.3 所述的排列，我們可以知道一開始的數值排列必需為{0,4,2,6,1,5,3,7} 或 {4,0,6,2,5,1,7,3} （如果 Merge Sort 實做上沒有用到額外記憶體，後者會比前者更糟，因為會需要多做 4 次 swap）

因此我們知道，對於數列 {0,1,2,3,4,5,6,7} ，Merge Sort 的最糟狀況之一會發生在 {0,4,2,6,1,5,3,7}

以下為我用來產生對 Merge Sort 最糟的數列的函式：

static inline void seperated_array(uint16_t *operations, uint16_t len)
{
    ascending_array(operations, len);
    worst_for_merge_array(operations, len);
}

static void worst_for_merge_array(uint16_t *operations, uint16_t len)
{
    uint16_t tmp[len];

    if (len <= 2)
        return;

    for (int i = 0; i < len; i++) {
        tmp[i] = operations[i];
    }

    for (int even = 0; even < len; even += 2) {
        operations[even / 2] = tmp[even];
    }
    for (int odd = 1; odd < len; odd += 2) {
        operations[len - len / 2 + odd / 2] = tmp[odd];
    }

    worst_for_merge_array(operations, len - len / 2);
    worst_for_merge_array(operations + len - len / 2, len / 2);
}


從結果來看，Merge Sort 的最糟和平均狀況的差距不大，同為 $O(nlogn)$，因此在最糟狀況下比 Insertion Sort 和 Quick Sort 都還要好。

> 奇怪的是：最糟的數列實際跑起來竟然比隨機數列更快。 顯然有地方做錯了，只是目前還不確定是錯在哪裡。
> [name=yxguo]

## 自我檢查事項:

#### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
在 linux 的 list.h 裡，可以看到其函式大多都有 static inline 的前綴，其他則以 `#define` 這種 Macro 形式定義。而如果開啟編譯器最佳化`-O`， static inline 在符合某些條件下也會被展開，以省去 function call overhead，因此執行速度也跟 Macro 一樣快。

* [C99 6.7.4.5](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
>Making a function an inline function **suggests** that calls to the function be as fast as possible. The extent to which such suggestions are effective is
**implementation-defined**.

根據 C99 規格書可以看到，標注 inline 的函式呼叫要盡量變快，但怎麼變快還是得看編譯器的實做，有可能最終 inline 根本沒有效果，因此通常會將 inline 解釋成一種對編譯器的「建議」。

因為我是用 gcc 編譯程式，接下來看看 gcc 對 inline 是怎麼處理的：
* [6.45 An Inline Function is As Fast As a Macro](https://gcc.gnu.org/onlinedocs/gcc/Inline.html)
> By declaring a function inline, you can direct GCC to make calls to that function faster. One way GCC can achieve this is to integrate that function’s code into the code for its callers. This makes execution faster by eliminating the function-call overhead

關於 inline 怎麼變快，gcc 的主要作法是把 function 整合進 caller function，藉此去除 function-call overhead

> When a function is both inline and static, if all calls to the function are integrated into the caller, and the function’s address is never used, then the function’s own assembler code is never referenced.

在兩個條件下，static inline 的建議會被採納 ( 不會有 function call )：
1. all calls to the function are integrated into the caller.
2. function’s address is never used

:::info
疑問：
關於第1點的反例，什麼樣的情況算是 call to the function isn't integrated into the caller？
:::

那麼， function call 有什麼 overhead？
1. 將欲帶入 callee function 的參數先存到暫存器
2. 執行 `callq` 跳到 callee function 的起點
3. 調整 stack pointer，需要多一個 call stack 紀錄 callee function（被呼叫的函式）中的變數、function call 後要回到哪個地址繼續執行等資訊
5. 執行 `retq` 返回 caller function 的中斷點

由以下程式做個測試

#include <stdlib.h>
#include <stdio.h>

static inline int max(int a, int b)
{
	return (a > b) ? a : b;
}

int main()
{
	int a = 3;
	int b = 7;
	int c = max(a, b);
	printf("%d\n", c);
}

在不開啟編譯器最佳化`-O`的情況下，就算標注了inline也不會被展開，因此我們可以看到組語中依然有 function call `callq`

gcc -g -o test test.c
gdb test
(gdb) layout asm

0x64a <max>                push   %rbp                                          # Save the current frame pointer into the stack                                                 
0x64b <max+1>           mov    %rsp,%rbp                               # Advance the frame pointer to the current value of the stack pointer.                                             
0x64e <max+4>           mov    %edi,-0x4(%rbp)                    # Copy arg'a' into stack                                       
0x651 <max+7>	     mov    %esi,-0x8(%rbp)	             # Copy arg'b' into stack  
0x654 <max+10>          mov    -0x4(%rbp),%eax       										
0x657 <max+13>          cmp    %eax,-0x8(%rbp)										
0x65a <max+16>          cmovge -0x8(%rbp),%eax										
0x65e <max+20>          pop    %rbp											           
0x65f <max+21>          retq											               

0x660 <main>               push   %rbp											           
0x661 <main+1>          mov    %rsp,%rbp											   
0x664 <main+4>          sub    $0x10,%rsp											   
0x668 <main+8>          movl   $0x3,-0xc(%rbp)                                         
0x66f <main+15>         movl   $0x7,-0x8(%rbp)
0x676 <main+22>         mov    -0x8(%rbp),%edx										
0x679 <main+25>         mov    -0xc(%rbp),%eax											       
0x67c <main+28>         mov    %edx,%esi				       # Copy 'b' into register esi							           
0x67e <main+30>         mov    %eax,%edi				       # Copy 'a' into register edi							           
0x680 <main+32>         callq  0x64a <max>				# function call max()							           
0x685 <main+37>         mov    %eax,-0x4(%rbp)                  										       
0x688 <main+40>         mov    -0x4(%rbp),%eax											       
0x68b <main+43>         mov    %eax,%esi											           
0x68d <main+45>         lea    0xa0(%rip),%rdi											       
0x694 <main+52>         mov    $0x0,%eax											           
0x699 <main+57>         callq  0x520 <printf@plt>											   
0x69e <main+62>         mov    $0x0,%eax											           
0x6a3 <main+67>         leaveq											                       
0x6a4 <main+68>         retq

但如果有開啟編譯器最佳化，那麼只要 inline function 內部沒有特定行為就會直接被展開，效果如同 Macro：

gcc -O -g -o test test.c
gdb test
(gdb) layout asm

0x66a <main>                               sub    $0x8,%rsp
0x66e <main+4>                          mov    $0x7,%edx                         
0x673 <main+9>                          lea    0xaa(%rip),%rsi           
0x67a <main+16>                        mov    $0x1,%edi                         
0x67f <main+21>                         mov    $0x0,%eax                         
0x684 <main+26>                        callq  0x540 <__printf_chk@plt>         
0x689 <main+31>                        mov    $0x0,%eax                         
0x68e <main+36>                        add    $0x8,%rsp                         
0x692 <main+40>                        retq

最佳化過後的組語難以直接解釋，不過至少可以確定原本 `callq <max>` 不見了。

#### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
* 統一命名，增加 linux 核心程式碼的易讀性、一致性。
* 定義的操作都足夠單純、通用，不存在什麼需要最佳化的地方，所以統一實作可以增加可重用性。

#### linked list 採用環狀是基於哪些考量？
* linked list 主要可以分為 4 種排列組合 :
1. singly 和 doubly
2. circular 和 non-circular
* 選用 doubly，是因為 overhead 成本不算太多，並且 singly 能做到的 doubly 都能做到，甚至某些操作以 doubly 實作效率會高出很多，比如 `reverse`
* 選用 circular，是因為以 doubly 為前提，那麼 non-circular 其實沒有什麼好處：在 list 之外，同樣需要 2 個額外的指標，一個指向 list head 一個指向 list tail。 那還不如做成 circular，以一種結構 `list_head` 就能表示每一個節點

#### list_for_each_safe 和 list_for_each 的差異在哪？"safe" 在執行時期的影響為何？

在一般 for_each 中，當我們對當前節點進行**刪除**，就會無法再找到下一個節點來進行新一輪操作。

為了解決此問題，safe 版會事先紀錄下一個節點的位置，讓開發者可以安全、放心的刪除當前節點。

看起來 safe 版比一般版作用範圍更廣更好用，但即便如此一般版本也沒有被淘汰，我認為這是因為 safe 版本執行上需要花費額外成本：
1. 除了「當前節點」， safe 版需要多用 1 個指標表示「下一個節點」
2. 更新節點時，需要多 1 次記憶體操作（ 更新當前節點 + 紀錄下一節點 ）

#### for_each 風格的開發方式對程式開發者的影響為何？
for_each 是一種對程式邏輯的抽象化 (abstraction)。

這種作法使程式開發者不用知道 for_each 的內部實做細節，他只需知道「它會依序拜訪每一節點，但注意不能用來刪除節點」的使用方法

而這麼設計有其好處：
1. 開發者可以把注意力放在更高層次的程式邏輯
2. 將來如果要擴充或重構 list_for_each，更容易控制對其他程式碼造成的衝突

#### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* 確保程式碼的 Correctness 和 Performance
* 後續重構或擴充原本函式後，跑個 unit test 就能知道程式碼有沒有被改壞掉

#### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
* 檢查 unit test 的覆蓋率
目前的 `tests/` 目錄下有針對 list.h 的每個 function 做檢查。 但如果我在 list.h 多加了一個 function，很不巧是有問題的，那麼就算把 `tests/` 目錄底下的所有 unit test 都跑過也檢查不出來。 因此需要多一支程式檢查 unit test 的覆蓋率，告訴開發者 list.h 中有哪些 function 是沒被呼叫(測試)過的。

## 參考資料
1. [The Call Stack](https://www.youtube.com/watch?v=5xUDoKkmuyw)
2. [Function calls in C: a practical example](http://gghh.name/dibtp/2015/11/11/function-calls-in-c-practical-example.html)
3. [bauuuu1021的共筆](https://hackmd.io/@jD9XFdyQS0iyAaFMPYi5Ww/rkqu6rqBV?type=view#2019q1-Homework1-list)
4. [colinyoyo26的共筆](https://hackmd.io/@colinyoyo26/2019q3list)
5. [colinyoyo26的github](https://github.com/colinyoyo26/linux-list)
6. [kksweet8845的共筆](https://hackmd.io/@kksweet8845/2019q3homework3list)
7. [Why are all the linked lists circular in the Linux Kernel?](https://www.quora.com/Why-are-all-the-linked-lists-circular-in-the-Linux-Kernel)
8. [Unit Test: 核心觀念](https://medium.com/@ji3g4kami/unit-test-%E6%95%99%E5%AD%B8-ba39e54fcbc5)
9. [Unit Test: 覆蓋率](https://medium.com/@ji3g4kami/unit-test-%E6%95%99%E5%AD%B8-%E8%A6%86%E8%93%8B%E7%8E%87-9bfcd9f2fa7e)
10. [When will the worst case of Merge Sort occur?](https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur)
11. [Abstraction](https://en.wikipedia.org/wiki/Abstraction)