# 2024q1 Homework1 (lab0)
contributed by < [`aa860630`](https://github.com/aa860630/lab0-c) >
### Reviewed by `allenlial666`
- 避免中英混用，例如 function 應翻譯為函式。
- `q_swap` 可以使用 list_move 簡化程式碼。
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz
CPU family: 6
Model: 140
Thread(s) per core: 1
Core(s) per socket: 4
```
## 指定的佇列操作
### `q_new`
在任何佇列操作前都需要一個 head 當作引數傳入，因此我們需要先 malloc 一個記憶體區塊並將其雙向鏈結(prev 和 next)都指向自己，用以之後操作空的佇列。
「空」(empty) 的佇列是指向有效結構，開頭 (head) 的值為 NULL。
在每次 malloc 時都須確認配置記憶體區塊是否成功，使用以下程式碼做確認。
```diff
struct list_head *head = malloc(sizeof(struct list_head));
+ if (!head)
+ return NULL;
```
輸入 `./qtest` 後進行操作
```
cmd> new
l = []
```
### `q_free`
> commit [39ea8d0](???)
:::danger
填入自己帳號對應的 git commit 超連結，例如 https://github.com/aa860630/lab0-c/commit/c3fce364112666dac1d66cd916e040e29fa3b829
:::
```q_free()```用以釋放佇列在記憶體的空間，包括 head 及每個 entry 的 value 跟 list，資料型別如下
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
在刪除每個節點的同時必須記得下一個刪除的物件，這裡透過 `list_for_each_entry_safe (node, safe, l, list)` 可以利用 safe 去記錄下一個被刪除的節點
:::danger
1. 留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
2. 改進你的漢語表達。
:::
輸入```./qtest```後進行操作
```
l = [a b c]
cmd> free
l = NULL
```
### q_insert_head() 和 q_insert_tail()
```q_insert_head()``` 在佇列的第一個位置插入新的節點，在 malloc 一個 element_t 之後一樣要確認記憶體空間是否被創造，確認方法如下
```diff
element_t *new_node = malloc(sizeof(element_t))
+ if (!new_node)
+ return false;
```
透過 ```list_add(&new_node->list, head)``` 可以直接將 new_node 插入在第一個位置，但由於其形態為 element_t，因此要將指標位置改為指向 new_node 的 list
兩個 function 的操作方法一致，差別只在於插入位置
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
輸入```./qtest```後進行操作
```
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
```
> commit [8a8823c](https://github.com/sysprog21/lab0-c/commit/8a8823c02a700dac110b627547208dc858b1724d)
> commit [fdc6218](https://github.com/sysprog21/lab0-c/commit/fdc6218f30bc3ef436568173a5164c80794eeb3a)
### q_remove_head() 和 q_remove_tail()
```q_remove_head()```用來 pop 佇列的第一個節點，可以透過 ```list_del_init()```來移除 head 的下一個節點，但無法同時移除該節點的 value，因此需要以下程式碼來完整 pop 整個節點
```c
if (sp) {
strncpy(sp, node->value, bufsize);
strcat(sp, "\0");
}
```
將 ```node->value```的字串複製到由指標 sp 指向的空間，空間大小為 bufsize，記得在字串後方加入```"\0"```，才能知道字串結束位置
兩個 function 的操作方法一致，差別只在於 pop 節點的位置
輸入```./qtest```後進行操作
```
l = [a b c]
cmd> rh
Removed a from queue
l = [b c]
cmd> rh
Removed b from queue
l = [c]
```
### q_delete_dup
用作刪除佇列中重複的字串，詳情見[Remove Duplicates from sorted list II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/)
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
:::
利用 `list_for_each_entry_safe (cur, safe, head, list)` 去比較 `cur` 與 `safe` 是否一樣。若不一樣，則雙雙移至下個節點，若一樣，則將 `cur` 刪除，並將布林常數 `cmp` 改為 1，雙雙移至下個節點
:::danger
* 改進你的漢語表達。
* 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
```c
if (cmp == 1) {
list_del_init(&cur->list);
free(cur->value);
free(cur);
}
```
由上述程式碼可知當```cmp```為 1 時，無論比較結果為何都需刪除當前節點，確保刪除連續重複字串的最後一個字串。
輸入./qtest後進行操作
```
l = [a b b c c c d]
cmd> dedup
l = [a d]
```
> commit [c3cef8f](https://github.com/sysprog21/lab0-c/commit/c3cef8f958bf7dc7da4a7030bfadf14d41a97597)
### q_swap
將佇列中兩兩節點進行反轉，詳情見 [Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/description/)
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
輸入./qtest後進行操作
```
l = [b a d c e]
cmd> swap
l = [a b c d e]
```
> commit [a371b33](https://github.com/sysprog21/lab0-c/commit/a371b331f2395db4fe3f6e0dd7d71e758b065ce6)
### q_reverse
將整個佇列做反轉
輸入./qtest後進行操作
```
l = [a b c d e]
cmd> reverse
l = [e d c b a]
```
> commit [72bd7b4](https://github.com/sysprog21/lab0-c/commit/72bd7b4949967da616f3f3dd6e1df55d483cb3df)
### q_reverseK
佇列根據引數k為一個單位進行反轉，詳情見[Reverse Node In K-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/description/)
使用```q_size```可知佇列長度，比較 len 與 k 的大小，若 len >= k 就進行反轉(呼叫副函式 ```q_reverse()```)，否則不做任何操作，在反轉後都會將 len - k，直到 len < k
```c
len = q_size(head);
while (len >= k) {
...
len = len - k;
}
```
輸入./qtest後進行操作
```
l = [a b c d e f g]
cmd> reverseK 2
l = [b a d c f e g]
cmd> reverseK 3
l = [d a b e f c g]
```
> commit [c3cef8f](https://github.com/sysprog21/lab0-c/commit/c3cef8f958bf7dc7da4a7030bfadf14d41a97597)
### q_sort
將佇列做排序，在嘗試過 Bubble Sort 後，由於其時間複雜度為 O(n^2^)，不符合系統預計時間，因此以下使用時間複雜度為 O(n\log{n})的 Merge Sort
將 Merge Sort 分為兩個步驟
1. ```mergeSortList``` :利用 slow 指標與 fast指標將佇列拆成兩個等長的佇列，用地回呼叫的方式反覆執行上述動作直至佇列無法再被分割
```c
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
```
2. ```merge``` :兩兩佇列利用```strcmp```去比較字串大小並由小排到大，反覆執行直至合併成原先佇列大小
<s>
</s>
:::danger
使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記中。
:::
參考文件來自[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
在做合併的同時，由於每個佇列已排序，因此當其中一個佇列為空時，只要把另一個佇列剩餘部分接回正在合併的佇列即可
```c
if (t1->next == t1) {
list_splice_tail(&tmp2, &new_queue);
} else if (t2->next == t2) {
list_splice_tail(&tmp1, &new_queue);
```
輸入./qtest後進行操作
```
cmd> ih RAND 4
l = [ndqavs pmdkzpsti dmectanx coowpn]
cmd> sort
l = [coowpn dmectanx ndqavs pmdkzpsti]
```
> commit [a96cac6](https://github.com/sysprog21/lab0-c/commit/a96cac62269135485bd2be0d6daee7b431b9b794)
:::danger
你如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::
### q_ascend 和 q_descend
```q_descend```的功能為在不移動節點的情況下將佇列從最大排到小，過程中勢必會刪除掉一些節點，並回傳佇列剩餘節點數，詳情見[Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/description/)
兩個 function 的操作方法一致，差別只在於由小到大或由大到小
輸入```./qtest```後進行操作
```
l = [f c d a b]
cmd> descend
l = [f d b]
```
> commit [c3fce36](https://github.com/sysprog21/lab0-c/commit/c3fce364112666dac1d66cd916e040e29fa3b829)
> commit [bf41ea4](https://github.com/sysprog21/lab0-c/commit/bf41ea40e07c64b46084a41fe00ae3faf870639a)
### q_merge
將不同佇列，按照順序合併回一個佇列，詳情見[Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/description/)
特別需要注意的是，此處使用的資料型別為```queue_contex_t```
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
> commit [e759807](https://github.com/sysprog21/lab0-c/commit/e759807791592b8d9b4ca989c5328622228ca06e)
## Shuffle
在```qtest.c```裡並沒有可執行 "shuffle" 的指令，為此我們可以新增一個名為 "shuffle" 的命令，同時附上指令說明
```c
ADD_COMMAND(shuffle, "Shuffle the queue","");
```
在同個檔案下新增一個名為```do_shuffle```的 function，在使用者輸入```shuffle```命令的同時呼叫```do_shuffle```
#### Fisher–Yates shuffle
利用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法來實作洗牌（shuffle）
``` c
for (tail = head->prev; tail != head; tail = tail->prev, len--) {
rnd = head->next;
int j = rand() % (len);
for (int k = 0; k < j; k++) {
rnd = rnd->next;
}
if (tail == rnd) {
continue;
}
tmp = rnd->prev;
list_move(rnd, tail);
list_move(tail, tmp);
tail = rnd;
}
```
執行 [lab0-d](https://hackmd.io/@sysprog/linux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) 提供的腳本後，輸出結果如下：
```
$ ./scripts/shuffle.py
Expectation: 41666
Observation: {'1234': 41525, '1243': 41663,'1324': 41579,
'1342': 41841, '1423': 41658,'1432': 41388,'2134': 41665,
'2143': 41717,'2314': 41754, '2341': 41622, '2413': 41814,
'2431': 41890, '3124': 41731, '3142': 41295, '3214': 41560,
'3241': 41845, '3412': 41551, '3421': 41440, '4123': 41516,
'4132': 41858, '4213': 41659, '4231': 41712, '4312': 41493,
'4321': 42224}
chi square sum: 20.929774876398024
```
為了測試洗牌是否足夠隨機，我們透過使用佇列中的4個節點 (l = [1 2 3 4]) 去做測試。在做了$10^6$次發牌，由於出現的可能為 $4!$，因此可得期望值$E = 41666 (= 10^6 / 24)$，chi square sum $X^2 = 20.929774$
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
在```list_sort```函示開始前可見一行指令```__attribute__((nonnull(2,3)))```，避免參數```head```或```cmp```為```NULL```指標。```__attribute__```其實是GCC的一種編譯器指令，當其設定為函數屬性時，可以使編譯器在錯誤檢查方面增強
參考自[GNU GCC compiler](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Function-Attributes.html)()
```c
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp){}
```
將```head->prev```的```next```指向```NULL```，也就是最後一個節點指向```NULL```，若只觀察```next```方向的串列，從原先的環狀鏈結串列變成了單向鏈結串列
```c
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
list sort 在做合併時，兩個要被合併的 sublist必須是 $2^{k+1}$：$2^k$ ( 2 : 1 ) 的平衡狀態，並使用二進制的```count```作為合併與否的依據
* count = 1($0001_2$) | $2^0$
* count = 2($0010_2$) | $2^0$ + $2^0$ ( $2$ 的冪，不合併 )
* count = 3($0011_2$) | $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^1$ + $2^0$
* count = 4($0100_2$) | $2^1$ + $2^0$ + $2^0$ ( $2$ 的冪，不合併 )
* count = 5($0101_2$) | $2^1$ + $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^1$ + $2^1$ + $2^0$
* count = 6($0110_2$) | $2^1$ + $2^1$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^2$ + $2^0$ + $2^0$
* count = 7($0111_2$) | $2^2$ + $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^2$ + $2^1$ + $2^0$
上述例子來自 [yinghuaxia](https://hackmd.io/zcSCoJW3QYi1J1kFnECWaA?view)
在 while 迴圈裡看到的 for 迴圈用來尋找```count```中的least-significant clear bit，藉此將```tail```移到待合併的位置上，當```bits```不為 0 時，sublist 進行排序合併
```if (likely(bits)) {}```用以判斷```count```是否為2的冪，若為2的冪，則```bits```早在 for 迴圈時就被改成0，不會進行合併; 若不為2的冪，```bits```不為0，則會進行排序合併
```c
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
其中```likely```與```unlikely```用在提升程式碼運行效率，這兩個巨集被定義在 [/include/linux/compiler.h ](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h)，按照```__builtin_expect```的定義，要用第一個參數和第二個參數比較，它期望的值是true。第二個值是1。這裏的!!(x)就是為了保證當x本身作為邏輯值為true的時候，其!!(x)值為1
```c
# ifndef likely
# define likely(x) (__branch_check__(x, 1, __builtin_constant_p(x)))
# endif
#define __branch_check__(x, expect, is_constant) ({ \
long ______r; \
static struct ftrace_likely_data \
__aligned(4) \
__section("_ftrace_annotated_branch") \
______f = { \
.data.func = __func__, \
.data.file = __FILE__, \
.data.line = __LINE__, \
}; \
______r = __builtin_expect(!!(x), expect); \
ftrace_likely_update(&______f, ______r, \
expect, is_constant); \
______r; \
})
```
在一些明確的條件下，我們比編譯器更了解哪個分支更有可能發生，gcc 在編譯時會在程式引導下調整 if 分支內程式碼的位置，如果是```likely```修飾過的就調整到前面，因此可以節省跳轉指令帶來的時間開銷
### 用 perf 進行效能比較
使用 perf 進行效能比較，參考至[GNU/Linux 開發工具](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg#%E5%85%88%E4%BE%86%E5%80%8B%E7%AF%84%E4%BE%8B%E6%9A%96%E8%BA%AB%E5%90%A7%EF%BC%81)
```
perf stat --repeat 5 -e instructions,cycles ./qtest -f traces/trace-sort.cmd
```
定義測資
```
option fail 0
option malloc 0
new
ih RAND 500000
time
<sort>
time
```
比較 `q_sort` 與 `list_sort` 這兩個排序的 system time(s)，測試資料筆數分別為10萬筆、50萬筆、100萬筆跟500萬筆資料，如下表所示 :
| 資料數 | q_sort | list_sort |
| --------- | ------ | --------- |
| 100,000 | 0.035 | 0.027 |
| 500,000 | 0.111 | 0.116 |
| 1,000,000 | 0.226 | 0.240 |
| 5,000,000 | 0.654 | 0.653 |
比較 `q_sort` 與 `list_sort` 這兩個排序的效能差別，測試資料筆數為10 萬筆
| 項目 | q_sort | list_sort |
| ---- | ------ | --------- |
|cache-misses |78,5773 |78,9353 |
|cache-references |114,0532 |114,5490 |
|% of all caches refs|68.90% |68.91% |
|instructions |3,7345,3621 |3,7352,0238 |
|cycles |1,8751,4000 |1,8724,0725 |
|insn per cycle |1.99 | 1.99 |
|duration time |0.035 s |0.027 s |
Sign in with Wallet
Connect another wallet