# 2019q1 Homework1 (list)
contributed by < `cjwind` >
## 自我檢查清單
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
macro 會在 preprocess 階段被處理。其中 `#define name replacement` 會在 preprocess 時將程式碼中的 `name` 都取代為 `replacement`。指令 `cpp` 是 C preprocessor。
一般的 function call 需要 push 參數、local variable、return address 等資料到 stack，並且跳到該 function 執行，執行完 function 要再跳回 caller。
### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
這類註解可以用相關工具如 Doxygen 自動產生程式碼的文件。
`@` 代表 function parameter。[Ref](https://www.kernel.org/doc/html/v4.19/doc-guide/kernel-doc.html#function-parameters)
Linux kernel 用 [Sphinx](http://www.sphinx-doc.org/en/master/) 產生文件。
### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
`list_for_each` 註解提到 list 的 node 以及 head 在 iterate 過程中不能修改，否則會導致 undefined behavior。
`list_for_each_safe` 註解提到在 iterate 過程中可以 delete current node（iterator 所在的那個 node），其他對 list 的修改會造成 undefined behavior。
實作上，這個 doubly linked list 是 circular，而且 head 是不含資料的 node，所以可以把 head 當作 traverse 的終點。
從 `tests/list_for_each.c` 可以看到兩者的使用方式。差異在 safe 版本可以在 traverse 過程中 delete current node。
### for_each 風格的開發方式對程式開發者的影響為何？
可以不用管底層是如何實作就能 traverse，例如 PHP 的 foreach 可以 traverse array 跟 object public attribute。
### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
用來確認 list 的各項功能操作是否符合預期。
unit test 是用來確認一個「unit」（可以是 function 或 class 或更大的 module 等）的功能是否符合預期的測試，也可以當作程式碼的使用說明──test 怎麼用，production code 就怎麼用。
軟體開發上，有 unit test 可以確保對程式碼的修改沒有造成原本功能壞掉或製造出 bug（在 test 涵蓋到的範圍內）。一般 unit test 都能一鍵執行，開發人員可以快速知道寫的功能是否符合預期、有沒有改壞東西，縮短開發、測試以及 debug 需要的時間。能快速取得回饋以及得知有無改壞原有功能，對 refactor 有很大幫助。
### `LIST_POISONING` 這樣的設計有何意義？
在 `list_del()` 裡讓從 list 移除的 node 的 `prev` 及 `next` 指向特定 address。從註解看起來，應該是有些系統會定義某些 address 有特定功能，例如 access 某個 address 是非法操作之類的？如果程式去 access 這樣的 address 系統會有對應處理？
這樣做可以避免被移除的 node 依然透過 `prev` 跟 `next` 操作 list 中的 node（指向 `NULL` 也能避免），不過註解也有提到移除的 node 要被當作 `uninitialized node`，access `prev` 跟 `next` 是不安全的。
`list_del_init()` 則是 `list_del()` 後再次 initialize node，讓 `prev` 跟 `next` 都指向自己。
*為什麼不只提供 `list_del_init()` 就好？要保留會讓 node 處於 uninitialized state 的 `list_del()`？*
### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
在 `tests/common.h` 增加 macro `assert_equal()`，改進原本 `assert(a == b)` 的可讀性。
```clike
#define assert_equal(expected, actual) assert(expected == actual)
```
例如檢查 sort 結果的 assert
```clike
assert(item->i == values[i]);
```
可以改寫為
```clike
assert_equal(values[i], item->i);
```
原本想用 function 實作：
```clike=
void assert_equal(uint16_t expected, uint16_t actual)
{
assert(expected == actual);
}
```
但發現這樣做在 assert fail 時印出的訊息會像下面變成印出 `common.h` 那行，反而不利閱讀。
```
list_mergesort: tests/common.h:8: assert_equal: Assertion `expected == actual' failed.
```
用 macro 跟原本一樣會印出比較確切的資訊：
```
list_mergesort: tests/list_mergesort.c:35: main: Assertion `values[i] == item->i + 1' failed.
```
## Sorting
:::warning
可先解析 example 目錄下的 insert/quick sort 程式碼
:notes: jserv
:::
範例 insertion 跟 sort sort 的 `main()` 都是先準備 input 資料、做 sort、最後確認 sorting 結果。
### Insertion sort
`list_insertsort()` 把原本 list `head` 的 node 先放到 `list_unsorted`，接著一個個從 `list_unsorted` 拿 item、call `list_insert_sorted()` 放到 head list 的對應位置。
`list_insert_sorted(entry, head)` traverse `head` list，進行比較，找到對應位置時用 `list_add_tail()` 把 `entry` 放到找到位置的 `item` 前面。
`list_add_tail()` 更 general 來說是「把 node 放到某個 node 前面」。
example 的實作下，worst case 是 sorted list 而非反向的 sorted list。
### Quick sort
建立兩個 list `list_less` 跟 `list_greater`，分別放小於 pivot 的 item 跟大於等於 pivot 的 item。
拿 `head` list 的第一個 item 當 pivot，並且將 pivot item 從 `head` list 移除。
traverse head list 的 entry，比較 enty 與 pivot，使用 `list_move_tail()` 及 `list_move()` 將 entry 分別移到 `list_less` 跟 `list_greater`。traverse 結束後，`head` list 會變成 empty。
recursive 對 `list_less` 及 `list_greater` 做排序，之後兩者皆為 sorted。
最後先把 pivot 放回 `head` list。接著將 `list_less` 所有 node 接到 `head` list 前面，所以 pivot 會在所有小於它的 item 後面。再把 `list_greater` 所有 node 接到 `head` list 的後面，也就是 pivot 後面，完成排序。
### 效能
三種 sort 的 time complexity：
| | Insertion | Quick | Merge |
|-------| ------------- | --------------- | --------------- |
| Avg | $\Theta(n^2)$ | $\Theta(nlogn)$ | $\Theta(nlogn)$ |
| Worst | $O(n^2)$ | $O(n^2)$ | $O(nlogn)$ |
#### 測量方式
以 `gettimeofday()` 取得執行 sort 前後的時間計算各 sort 所需時間。
```clike=
struct timeval stop, start;
gettimeofday(&start, NULL);
sort(list);
gettimeofday(&stop, NULL);
```
average case 以相同 random data 作為 input 執行三種 sort。
worst case 則以反向 sorted data 作為 input。insertion sort 最簡單的 worst case 是反向的 sorted data ([Wiki](https://en.wikipedia.org/wiki/Insertion_sort#Best,_worst,_and_average_cases))，但以 example 的實作而言是已經排好的 sorted data。
#### 測量結果
Insertion Sort 的 average case 與 worst case：
Quick Sort 的 average case 與 worst case：
Merge Sort 的 average case 與 worst case：
merge sort 的 worst case 效能比 average case 好，顯然反向 sorted data 不是 merge sort 的 worst case。
三種 sort 的 average case 與 worst case：
quick sort 及 merge sort 在 average case 差不多，而 insertion sort 明顯比較差。但到了 worst case，反而是 quick sort 所需時間的增長較多。
#### Improve Quick Sort
example 的 quick sort 挑 pivot 都挑 list 的第一個 item，在 sorted data 的情況會挑到最大或最小的，導致在分成「比 pivot 大」跟「比 pivot 小」兩堆時 item 都在某一堆、沒有分堆的作用。
如果修改成從第一個 item、最後一個 item、中間 item 三個中選中間值的 item 當作 pivot，可以避免總是挑到最大或最小的 item 當 pivot。[如此修改](https://github.com/cjwind/linux-list/commit/47b0b071e671d7e60b666a4f779fb9ebe4555b1c)後，再以反向 sorted data （sequential input）以及 random data 當作 input 的結果如下：
可以看到 sequential input 的 performance 變好，random input 也跟之前差不多。
只看 merge sort 跟改進後 quick sort，兩者變得接近：
當然，對於修改後的 quick sort，sequential data 已經不是它的 worst case，反而是相對好的 case，因為選中間 item 會選到可以將 item 分成差不多大小兩邊的 pivot。如果不幸三個 item 正好是最大、次大、第三大的 item（最小亦然），效能提升便不顯著。
## Trace Note
list 使用上先 initialize 一個 type 為 `struct list_head` 的 head node，它不含資料。list 的各項操作都會使用這個 head node。
封裝：自訂 struct 放資料及 `struct list_head`，如 `struct listitem`，就可以讓自訂的 struct 成為 list node。
### list splice 系列
```clike
void list_splice(struct list_head *list, struct list_head *head)
```
`list` 跟 `head` 分別是兩個 list 的 head。
`list_splice()` 把 `list` 的所有 node 接到 `head` 的最前面，但是 `list` 這個 node 不會被修改、會變成 `uninitialized node`。
`list_splice_init()` 先做了 `list_splice()` 再 initialize `list` node。
`list_splice_tail()` 是把 `list` 的 node 接到 `head` 的最後面。
### `list_cut_position`
`head_to` 如果不是空的 list，cut 完原本 `head_to` list 裡的 node 會沒有 head。test 也沒有這種用法。
## 作業要求
* Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
* GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* 解釋以下巨集的原理
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
* 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
* linked list 採用環狀是基於哪些考量？
* 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
* 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？
* 從 [linux-list](https://github.com/sysprog21/linux-list) 學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，實作出 merge sort
* 附上你的修改過程，也需要讓 `qtest` 得以支援
* 可將 [dict](https://hackmd.io/s/B1Bq5Jat7) 裡頭的測試資料拿來作效能分析的輸入
* 思考提升排序效率的方法，需要做平均和最壞狀況的分析
###### tags: `Linux 核心設計 2019`
Sign in with Wallet
Connect another wallet