# 2023q1 Homework1 (quiz1)
contributed by < [Huaxin](https://github.com/p96114175) >
> [題目](https://hackmd.io/@sysprog/linux2023-quiz1)
## 開發環境
```
gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 24
On-line CPU(s) list: 0-23
每核心執行緒數： 1
每通訊端核心數： 16
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 151
Model name: 12th Gen Intel(R) Core(TM) i9-12900F
製程： 2
CPU MHz： 2400.000
CPU max MHz: 5100.0000
CPU min MHz: 800.0000
BogoMIPS: 4838.40
虛擬： VT-x
L1d 快取： 384 KiB
L1i 快取： 256 KiB
L2 快取： 10 MiB
```
## 回答測驗一
:::danger
注意作業書寫規範：中英文間用一個半形空白字元區隔。
程式碼縮排亦有相關規範，請依循！
:notes: jserv
:::
:::success
好的
:::
首先從[Linux 核心 linked list 實作](https://hackmd.io/@sysprog/c-linked-list)你可以發現
> #define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
可以知道 `AAA` 表示 `type` ， `BBB` 表示 `member` ，再從
```
struct item *pivot = list_first_entry(head, AAA, BBB);
```
可以得知 `AAA` 為 `item` 而 `BBB` 為 `list` ，另外針對下列程式碼的 `CCC` 和 `DDD` , `EEE`
```
CCC (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
DDD (&itm->list, &list_less);
else
EEE (&itm->list, &list_greater);
}
```
從程式碼內容我們可以知道 `CCC` 在迭代 (iteration)所操作的節點，其中 `itm` 來自 `list_entry((head)->next, __typeof__(*entry), member)`，`is` 來自 `list_entry(entry->member.next, __typeof__(*entry), member)` ，可以得知 `CCC` 為 `list_for_each_entry_safe` 。
對 `item` 和 `pivot` 使用 `cmpint` 比較值，若 `item` 小於 `pivot` ，便可以通過 `if` 判斷式，執行 `DDD (&itm->list, &list_less)` ，將 `item` 節點移動至 `list_less` 節點的尾端，若 `item` 大於 `pivot` ，將 `item` 節點移動至 `list_greater` 節點的尾端，可以得知 `DDD` 和 `EEE` 為 `list_move_tail`
**原理的部分**
```c
struct item *pivot = list_first_entry(head, AAA, BBB);
```
1. 先取出 `head` 的第一個entry且以一個指標 `pivot` 指著
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node5 [label="5"]
node4 [label="4"]
node3 [label="3"]
node2 [label="2"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
pivot [shape=none, label="pivot"]
pivot->node5
head->node5->node4->node3->node2->null0
{rank=same;node5 pivot}
}
```
```c
list_del(&pivot->list);
```
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node5 [label="5"]
node4 [label="4"]
node3 [label="3"]
node2 [label="2"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
pivot [shape=none, label="pivot"]
pivot->node5
head->node4->node3->node2->null0
}
```
```c
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
list_move_tail(&itm->list, &list_less);
else
list_move_tail(&itm->list, &list_greater);
}
```
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node5 [label="5"]
node4 [label="4"]
node3 [label="3"]
node2 [label="2"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
pivot [shape=none, label="pivot"]
list_less [shape=none,label="list_less"]
list_geater [shape=none,label="list_geater"]
empty1[label=""][shape=plaintext]
empty2[label=""][shape=plaintext]
head->empty1
list_geater->empty2
pivot->node5
list_less->node4->node3->node2->null0
}
```
```c
list_sort(&list_less);
```
持續重複此流程，直到 `list_empty(head)` 為 `true` ，返回 `return`
1.
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node4 [label="4"]
node3 [label="3"]
node2 [label="2"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
pivot [shape=none, label="pivot"]
pivot->node4
head->node4->node3->node2->null0
{rank=same;node4 pivot}
}
```
2.
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node4 [label="4"]
node3 [label="3"]
node2 [label="2"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
pivot [shape=none, label="pivot"]
pivot->node4
head->node3->node2->null0
}
```
3.
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node4 [label="4"]
node3 [label="3"]
node2 [label="2"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
pivot [shape=none, label="pivot"]
list_less [shape=none,label="list_less"]
list_geater [shape=none,label="list_geater"]
empty1[label=""][shape=plaintext]
empty2[label=""][shape=plaintext]
head->empty1
list_geater->empty2
pivot->node4
list_less->node3->node2->null0
}
```
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
```
先將指定的 `pivot` 插入 linked list `head` 的開頭，再將 `list_less` 的所有 node 都插入到 `head` 的開始，然後把 `list_greater` 的所有 node 都插入到 `head` 的 結束位置中， `FFF` 則為 `list_splice_tail`。
1.
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node2 [label="2"]
head [shape=none, label="head"]
head->node2
}
```
2.
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node3 [label="3"]
node2 [label="2"]
head [shape=none, label="head"]
head->node2->node3
}
```
3.
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node4 [label="4"]
node3 [label="3"]
node2 [label="2"]
head [shape=none, label="head"]
head->node2->node3->node4
}
```
4.
```graphviz
digraph {
rankdir=LR
node [shape="block"]
node5 [label="5"]
node4 [label="4"]
node3 [label="3"]
node2 [label="2"]
head [shape=none, label="head"]
head->node2->node3->node4->node5
}
```
:::success
**延伸問題**
- [x] 解釋程式碼運作原理
- [ ] 針對 [Quick sort](https://en.wikipedia.org/wiki/Quicksort) 提出程式碼的改進方案並實作
- [ ] 引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
- [ ] BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻
:::
## 回答測驗二
```c
#define MAX_DEPTH 512
```
```c
struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
INIT_LIST_HEAD(&stack[i]);
```
我們可以看見測驗2指定了`MAX_DEPTH = 512`的`stack`，用來模擬遞迴的功能，並用了 `INIT_LIST_HEAD` 針對 `stack` 中每一部分進行初始化，從上至下依序為 `stack[0], stack[1], stack[2] ...stack[MAX_DEPTH-1]`。
```c
int top = -1;
list_splice_init(head, &stack[++top]);
```
將 `head` 的所有 `node` 都插入到 `stack[0]` 的開始位置中
```c
int top = -1;
list_splice_init(head, &stack[++top]);
```
```c
while (top >= 0) {
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
```
此時 `top` 為 `0` 符合進入`while loop` 的條件，將剛存進 `stack[0]` 的 `node` 都插入到 `partition` 的開始位置中，接著再將 `top` 減一，使 `top` 為 `-1`。
```c
if (!list_empty(&partition) && !list_is_singular(&partition)) {
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
```
我們可以得知這時的 `partition` 已符合 `if` 的條件式，我們用 `pivot` 指向 `partition` 中的第一個 `node`，再用 `list_del` 把 `pivot` 所指向的 `node` 從 `partition` 取出來並初始化。
```c
struct item *itm = NULL, *is = NULL;
GGGG (itm, is, &partition, list) {
list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
```
從上方程式碼可以判斷出， `GGGG` 為 `list_for_each_entry_safe ` 用來 iterate `partition` 中的 `node`。
* 用 `list_del` 取出每一個 `node`
* 接著將其和 `pivot` 進行 `cmpint`
* 若是 `node` 小於 `pivot`，便會將該 `node` 移動到另一個 linked list `list_less` 的開頭
* 若是 `node` 大於 `pivot`，便會將該 `node` 移動到另一個 linked list `list_greater` 的開頭
```c
HHHH (&pivot->list, &list_less);
```
* 從上方可判斷出 `HHHH` 為 `list_move_tail` 。
結束 `interation` 後，使用 `list_move_tail` 把 `pivot` 移至 `list_less` 的尾端
```c
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
list_splice_tail(&list_less, JJJJ);
```
* 我們從 `list_splice_tail` 得知， `IIII` 和 `JJJJ` 為 `&stack[++top]`
* 透過 `if` 來分別檢測 `list_greater` 和 `list_less` 是否為空。
* 使用 `list_splice_tail` 將 `list_greater` 放入 `stack[0]`
* 使用 `list_splice_tail` 將 `list_less` 放入 `stack[1]`
由於符合 `while loop` 的條件，`while loop` 會持續運作直到 `if (!list_empty(&partition) && !list_is_singular(&partition)) {` 無法被滿足，這時候 `stack` 會呈現由大至小頭部向尾部的分佈，也就是 `stack` 頂端僅存一個 `node` ，便跳至 `else`，也就是下方程式碼
```c
else {
top++;
list_splice_tail(&partition, &stack[top]);
while (top >= 0 && list_is_singular(&stack[top])) {
struct item *tmp =
list_first_entry(&stack[top], struct item, list);
list_del(&tmp->list);
INIT_LIST_HEAD(KKKK);
list_add_tail(&tmp->list, head);
}
```
* 先針對 `top` 累加一次
* 並對剛才只含有一個 `node` 的 `partition` 放回至 `stack[top]` 的開頭位置中
* 接下來在 `while loop`中使用 `list_del` 把 `tmp` 從 `stack[top]` 中移開，並放至 `head` 中，我們可以知道 `KKKK` 為 `stack[top--]`，將被移走 'node' 的 `stack[top]` 進行初始化，並把 `top` 減一
* 結束 `while loop` 後，可以在 `head` 中發現排序後的結果
:::success
延伸問題:
1. 解釋上方程式碼運作原理，指出設計和實作的缺失
2. 比較測驗 1 和測驗 2 的程式碼，設計實驗來分析二者效能，解釋為何非遞迴的實作未能總是比遞迴的實作快
3. 提出效能改進方案，特別是避免依賴 MAX_DEPTH
4. 引入 Introsort，也就是 quick sort 和 heap sort (或其他可避免前者 O(n2) 最差時間複雜度的演算法)。加入 heapsort 的原因為，當 quicksort 迭代 2∗log(n) 次後還排序完成，那就很可能會得到 O(n2) 時間複雜度。此時切換為 heap sort 能將其時間複雜度控制在 O(nlogn)
:::
## 回答測驗三
Sign in with Wallet
Connect another wallet