# 2024q1 Homework1 (lab0)
contributed by < [MathewSu-001](https://github.com/MathewSu-001) >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 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
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 94
Model name: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
Stepping: 3
CPU MHz: 3407.998
BogoMIPS: 6815.99
```
## 佇列實作及改進
:::danger
查閱教育部重編國語辭典「[完善](https://dict.revised.moe.edu.tw/dictView.jsp?ID=161584)」，可知：
* 完美、完好
* 完好無缺
於是「完善 queue.c」的寓意跟你現在的投入狀況顯得無關 —— 作業自 2 月 20 日指派以來，遲至 3 月 1 日才見到一項你提交的零星變更，後者不符合作業規範 (缺乏清晰的 git commit message，也難以得知程式碼變更的考量因素，程式碼更是存在若干值得改進之處)，你的程式碼何以自稱完美呢？
改進你的漢語表達。
:::
### <s>完善</s> queue.c
:::danger
詳閱作業規範，避免 [Implement queue function](https://github.com/MathewSu-001/lab0-c/commit/32698586df57faabe4211ced1970103423c5cfc7) 這樣在單一 commit 含入大量彼此無直接關聯的程式碼，務必改進。可用 `git rebase -i` 修改。
參閱「[2023 年 Linux 核心設計/實作課程第一次作業檢討](https://hackmd.io/@sysprog/linux2023-lab0-review)」，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。
:::
### `q_free` 實作
```c
element_t *cur, *next;
list_for_each_entry_safe (cur, next, head, list) {
list_del(&cur->list);
q_release_element(cur);
}
free(head);
```
使用 `list.h` 內提供的 `list_for_each_entry_safe` 來遍歷每個節點。雖然可以利用 `safe` 來確保佇列中的每個鏈結串列都被刪除，但最後佇列的 `head` 不會被刪除，因此需要額外使用 `free` 釋放佇列所配置的記憶體空間。
### `q_insert` 實作
使用 `list.h` 內提供的 `list_add` 跟 `list_add_tail`就可以完成該 function。但需要注意的是需引用`strdup`，根據[該網站](https://en.cppreference.com/w/c/experimental/dynamic/strdup)
>char * strdup( const char *str1 );
Returns a pointer to a null-terminated byte string, which is a duplicate of the string pointed to by . The returned pointer must be passed to free to avoid a memory leak.
在引用完後，需要額外使用 `free`，以防止記憶體洩漏。雖然原本有使用它，但在測試後發現會出現亂碼。猜測原因應該是在函式使用完後就會將暫存記憶體刪除，因此不需要再進行額外的處理。
### `q_reverse` 系列實作
```c
list_for_each_safe (cur, next, head) {
list_move(cur, head);
}
```
使用`list.h`內提供的 `list_for_each_entry_safe` 來走訪每一個節點，`llist_move`提供任一指定節點移動到佇列開頭。
```c
list_cut_position(&rse, tmp_head, cur);
q_reverse(&rse);
list_splice(&rse, tmp_head);
tmp_head = safe->prev;
```
透過上述 code 的步驟，將 k 個節點移動到一個新的佇列上並呼叫 q_reverse，然後再重新接回原來的鏈結串列的前面。
### `q_sort` 實作
以 merge sort 的方法來排序鏈結串列的節點。`q_sort`主要的功能為分割鏈結串列，並且呼叫`merge_list` 。
```c
LIST_HEAD(tmp);
for (; !list_empty(left) && !list_empty(right);) {
char *s1 = list_entry(left->next, element_t, list)->value;
char *s2 = list_entry(right->next, element_t, list)->value;
if (strcmp(s1, s2) >= 0) {
descend ? list_move_tail(left->next, &tmp)
: list_move_tail(right->next, &tmp);
} else {
descend ? list_move_tail(right->next, &tmp)
: list_move_tail(left->next, &tmp);
}
}
```
這段程式碼的核心思想是宣告一個新的佇列開頭 `tmp`，逐一比對兩個鏈結串列的節點，將符合條件的節點移動到 `tmp` 的佇列尾端。由於 `list_move_tail` 的作用是將指定節點移動到佇列尾端，因此兩個鏈結串列中必定會有一個先移完，進而使得 `for` 迴圈終止。
### `q_descend` 系列實作
```c
struct list_head *min = head->prev, *node = head->prev->prev;
for (; node != head;) {
char *s1 = list_entry(min, element_t, list)->value;
char *s2 = list_entry(node, element_t, list)->value;
if (strcmp(s1, s2) <= 0) {
min = node;
node = node->prev;
} else {
list_del(min->prev);
q_release_element(list_entry(node, element_t, list));
node = min->prev;
}
}
```
在概念上，會從鏈結串列尾端做起，並且設置一個變數 `min` 來與它的前一個節點 `node` 做比較。只要 `min` 比較小的話就會將 `node` 刪除；否則 `min` 會被指派更新為 `node` 位址。
### `q_merge` 實作
這一個函式必須要先思考 head 所代表的函義是甚麼，在`q_test.c`中呼叫`q_merge`程式碼為
>len = q_merge(&chain.head, descend);
```graphviz
digraph structs{
node [shape="record"];
rankdir = "LR"
subgraph cluster_1
{
label = "queue_contex_t1";
struct1 [label="size"];
struct2 [label="id"];
node1 [label="chain | {<prev>prev | <next>next}"];
node2 [label="q | {<prev>prev | <next>next}"];
}
subgraph cluster_2 {
label = "queue_contex_t2";
struct3 [label="size"];
struct4 [label="id"];
node3 [label="chain | {<prev>prev | <next>next}"];
node4 [label="q | {<prev>prev | <next>next}"];
}
subgraph cluster_3 {
label="element_t1"
style=filled;
color=lightgrey;
node [shape=record];
struct5[label="char"];
node5 [label="list | {<prev>prev | <next>next}"];
}
subgraph cluster_4 {
label="element_t2"
style=filled;
color=lightgrey;
node [shape=record];
struct6[label="char"];
node6[label="list | {<prev>prev | <next>next}"];
}
node1:next:s -> node3;
node3:prev:s -> node1;
node2:next:s -> node5;
node5:prev:s -> node2;
node4:next:s -> node6;
node6:prev:s -> node4
}
```
因此需要處理的地方是，當已經合而為一個新的已排序佇列後，需要擺放在哪裡。所以我的作法就會是宣告一個新的佇列開頭`tmp`，然後用`list_for_each_entry_safe` 將每一個節點與`tmp`接在一起。最後，用`list_splice`接在佇列`chain`的開頭。
```c
LIST_HEAD(tmp);
list_for_each_entry_safe (cur, next, head, chain) {
count += cur->size;
merge_list(&tmp, cur->q, descend);
}
list_splice(&tmp, list_entry(head->next, queue_contex_t, chain)->q);
```
## 在 qtest.c 提供新的命令 `q_shuffle`
- queue.c
```c
LIST_HEAD(tmp);
LIST_HEAD(new_list);
while (count > 0) {
// srand(time(NULL));
int random_index = rand() % count;
struct list_head *cur = head->next;
for (; random_index > 0; random_index--)
cur = cur->next;
list_cut_position(&new_list, head, cur->prev);
list_move(head->next, &tmp);
list_move(head->prev, head);
list_splice_init(&new_list, head);
--count;
}
list_splice_tail_init(&tmp, head);
```
核心思想為: 以被選中的亂數節點做為區隔線，`new_list` 以及以亂數節點當作佇列開頭的 `head`。運用`list_move` 將亂數節點移動到 `tmp`，並且`head`佇列尾端移動到開頭。最後將`tmp`接回`head`。
- qtest.c
在 `console.h` 可以發現以下
```c
/* Add a new command */
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
`add_cmd` 會在命令列表中添加新命令，要新增一條新命令 `shuffle` 則要實作 `do_shuffle`，並在`qtest.c` 的 `console_init()` 替新命令加上 `ADD_COMMAND`。
```c=
ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", "");
```
最後就是執行 `shuffle.py` 後的成果
### 以統計方法驗證`shuffle`
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
1. 建立假設
給定 list [1 2 3 4] 利用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法來實作洗牌（shuffle），那麼會產生24種不同排列且都具有同等的可能性。
+ $H_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
+ $H_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同
2. 計算 chi-squared test statistic $X^2$
```
Expectation: 41666
Observation: {'1234': 41447, '1243': 41572, '1324': 41435, '1342': 41770, '1423': 41353, '1432': 41504, '2134': 41996, '2143': 41947, '2314': 41898, '2341': 41878, '2413': 41823, '2431': 41675, '3124': 41624, '3142': 41583, '3214': 41863, '3241': 41526, '3412': 41565, '3421': 41274, '4123': 41776, '4132': 41947, '4213': 41657, '4231': 41626, '4312': 41615, '4321': 41646}
chi square sum: 21.197523160370565
```
$X^2$ = 21.197523160370565
3. 選擇顯著水準
根據 [2024 年 Linux 核心設計/實作課程作業 —— lab0]( https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d)
+ [顯著水準（Significance level）α](https://en.wikipedia.org/wiki/Statistical_significance) 代表在虛無假說（$H_0$）為真下，錯誤地拒絕 $H_0$ 的機率，即型一錯誤發生之機率。
α = P(拒絕 $H_0$ | $H_0$ 為真)
我們 alpha 設定為常見的 0.05。
+ [P value](https://zh.wikipedia.org/wiki/P%E5%80%BC)
從 Probability & Statistics 一書找合適的 P value，我們的自由度為 23，$X^2$ 為 21.197523160370565，因為 19.021 < 21.197523160370565 < 22.337，於是 P value 介於 0.5 和 0.3 之間。
4. 統計檢定的結果不拒絕虛無假說
對於要拒絕的虛無假說（$H_0$），觀察到的結果必須具有統計顯著性，即觀察到的 P value 小於預先指定的顯著水準 α。
因為 P value（0.3~0.5）> alpha（0.05），統計檢定的結果不拒絕虛無假說（$H_0$）
也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻。
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
### 解讀`list_sort()`
在分析函式之前，先了解函式的 prototype ，每個函式的宣告都擁有函式屬性 `__attribute__((nonnull()))`，在[5.24 Declaring Attributes of Functions](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Function-Attributes.html)裡有提到
>The keyword `__attribute__` allows you to specify special attributes when making a declaration. This keyword is followed by an attribute specification inside double parentheses.
意思是它用於標記函數的參數，指示這些參數不能為空指針。
而 nonnull(n) 屬性表示函數的第 n 個參數不能為空指針。
在 do-while 迴圈中，對 `likely()` 的用途有很大疑惑
```c
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;
}
```
在 [/include/linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 找到定義，而且有兩種
```c
/*第一種*/
# ifndef likely
# define likely(x) (__branch_check__(x, 1, __builtin_constant_p(x)))
# endif
# ifndef unlikely
# define unlikely(x) (__branch_check__(x, 0, __builtin_constant_p(x)))
# endif
/*第二種*/
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
而不管是第一種或第二種方法，都會是由 `__builtin_expect` 來做決定，而這個巨集是 gcc 的預設巨集，參考[6.61 Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)中給的定義:
> You may use to provide the compiler with branch prediction information. In general, you should prefer to use actual profile feedback for this (), as programmers are notoriously bad at predicting how their programs actually perform. However, there are applications in which this data is hard to collect.
但就這樣的解釋我還是沒有很瞭解使用原因，參考了[Linux內核入門-- likely和unlikely](https://zhuanlan.zhihu.com/p/540841798)後，大致上可以解釋為:
> CPU在處理當前指令的同時，會先取出後面的多條指令進行預處理，如果存在跳轉指令，那麼之前預取的指令都沒有用了，需要從記憶體中重新取出跳轉后的指令繼續執行。
> likely 和 unlikely 的存在讓編譯器判斷條件跳轉的預期值，把“很有可能發生”的條件分支放在順序執行指令段，而不是jmp指令段，如此可避免因執行jmp跳轉指令造成時間浪費。
從以上的分析可以得到 `likely()` 主要的功能
:::success
1. `__builtin_expect(!!(x), 1)` 會告訴編譯器 `!!(x)` 為 `1` 的機率很高，因此編譯器可以根據這樣的訊息對程式碼做優化，加速執行速度
2. `!!(x)` 用於將任何非零值轉換為 1，並將零值保持為零。換句話說，x 為 1 的可能性很高。
:::
再來就是要思考何時會觸發 `likely()` ，也就是何時要進行合併?
那這邊就是根據 count 來判定，依據[lab0 (E)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e)以及 `list_sort` 上的註解解釋
> This merge happens exactly when the count reaches an odd multiple of $2^k$, which is when we have $2^k$ elements pending in smaller lists, so it's safe to merge away two lists of size $2^k$.
>
> After this happens twice, we have created two lists of size $2^(k+1)$, which will be merged into a list of size $2^(k+2)$ before we create a third list of size $2^(k+1)$, so there are never more than two pending.
| count | pending list |merge|
|:-----:|:-------------:|------------------:|
| 1(1) | [1] | No|
| 2(10)| [1,1] |Yes|
| 3(11)| [1,1,1] -> [(2),1] | No|
| 4(100)| [ (2) ,1 , 1] |Yes|
| 5(101)|[(2), 1, 1, 1] -> [(2), (2), 1]|Yes|
| 6(110)|[(2), (2),1 ,1] -> [(4), 1, 1] |Yes|
| 7(111)|[(4), 1, 1, 1] -> [(4), (2), 1]| No|
|8(1000)| [ (4), (2), 1, 1] |Yes|
可以推斷為，只有在 count 為 $2^k-1$ 時才不會進行合併。
再來就是圖解整個 `list_sort` 的運作流程(假設五個節點):
- 進入 `do-while` 迴圈，count = 0，沒有觸發 for 迴圈，也沒有進行合併。
```graphviz
digraph {
rankdir=LR;
node[shape=record];
// 添加節點
node1 [label="15 | {<prev>prev | <next>next}"];
node2 [label="3 | {<prev>prev | <next>next}"]
node3 [label="1 | {<prev>prev | <next>next}"]
node4 [label="4 | {<prev>prev | <next>next}"]
node5 [label="7 | {<prev>prev | <next>next}"]
list[shape=plaintext, style=""]
pending[shape=plaintext, style=""]
tail[shape=plaintext, style=""]
NULL[shape=plaintext, style=""]
node1:prev -> NULL
node2:next -> node3
node3:next -> node4
node4:next -> node5
list -> node2
tail -> pending
pending -> node1
}
```
- count = 1，觸發 for 迴圈，沒有進行合併。
```graphviz
digraph {
rankdir=LR;
node[shape=record];
// 添加節點
node1 [label="15 | {<prev>prev | <next>next}"];
node2 [label="3 | {<prev>prev | <next>next}"]
node3 [label="1 | {<prev>prev | <next>next}"]
node4 [label="4 | {<prev>prev | <next>next}"]
node5 [label="7 | {<prev>prev | <next>next}"]
list[shape=plaintext, style=""]
pending[shape=plaintext, style=""]
tail[shape=plaintext, style=""]
NULL[shape=plaintext, style=""]
node3:next -> node4
node4:next -> node5
node2:prev:s -> node1
list -> node3
tail -> NULL
node1:prev -> NULL
pending -> node2
}
```
- count = 2，觸發 for 迴圈，且進行合併。
```graphviz
digraph {
rankdir=LR;
node[shape=record];
// 添加節點
subgraph cluster_1 {
rank=same;
style=filled;
color=lightgrey;
node [shape=record];
node1 [label="15 | {<prev>prev | <next>next}"];
node2 [label="3 | {<prev>prev | <next>next}"]
label="merge [1,1]"
}
node3 [label="1 | {<prev>prev | <next>next}"]
node4 [label="4 | {<prev>prev | <next>next}"]
node5 [label="7 | {<prev>prev | <next>next}"]
list[shape=plaintext, style=""]
pending[shape=plaintext, style=""]
tail[shape=plaintext, style=""]
NULL[shape=plaintext, style=""]
node3:prev -> node2
node4:next -> node5
node2:next:s -> node1
node2:prev -> NULL
list -> node4
tail -> node2
pending -> node3
}
```
- count = 3，觸發 for 迴圈，沒有合併。
```graphviz
digraph {
rankdir=LR;
node[shape=record];
// 添加節點
subgraph cluster_1 {
rank=same;
style=filled;
color=lightgrey;
node [shape=record];
node1 [label="15 | {<prev>prev | <next>next}"];
node2 [label="3 | {<prev>prev | <next>next}"]
label="merge [1,1]"
}
node3 [label="1 | {<prev>prev | <next>next}"]
node4 [label="4 | {<prev>prev | <next>next}"]
node5 [label="7 | {<prev>prev | <next>next}"]
list[shape=plaintext, style=""]
pending[shape=plaintext, style=""]
NULL[shape=plaintext, style=""]
node3:prev -> node2
node4:prev -> node3
node2:next:s -> node1
node2:prev -> NULL
list -> node5
pending -> node4
}
```
- count = 4，觸發 for 迴圈，並進行合併。
```graphviz
digraph {
rankdir=LR;
node[shape=record];
// 添加節點
subgraph cluster_1 {
rank=same;
style=filled;
color=lightgrey;
node [shape=record];
node1 [label="15 | {<prev>prev | <next>next}"];
node2 [label="3 | {<prev>prev | <next>next}"]
label="merge1"
}
subgraph cluster_2 {
rank=same;
style=filled;
color=lightgrey;
node [shape=record];
node3 [label="1 | {<prev>prev | <next>next}"]
node4 [label="4 | {<prev>prev | <next>next}"]
label="merge2"
}
node5 [label="7 | {<prev>prev | <next>next}"]
tail[shape=plaintext, style=""]
pending[shape=plaintext, style=""]
NULL[shape=plaintext, style=""]
node3:prev -> node2
node3:next -> node4
node2:next:s -> node1
node5:prev -> node3
node2:prev -> NULL
pending -> node5
tail -> node3
}
```
:::info
需要注意的是，這裡的 count 所代表的是上一階段待處理列表（pending list）中的節點數量。因此，合併操作應在待處理列表中節點數量不是 2 的冪( count + 1 != $2^k$ )時發起。
:::
最後所有的 `list` 都合併到 `pending` 後，用 `merge` 函式合併所有待處理列表，`merge_final` 函式重建 prev 鏈接。
### 解讀 `merge` 以及 `merge_final`
運作過程在作業二 [linux2024-homework2](https://hackmd.io/RgOPC_MBSfSjtXawENXqTw)中的 timsort 中有提到。
### 加進 `lab0-c`
將 [linux/lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 以及 [linux/list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 引進 lab0-c 當中：
1. 將不必要的 include 刪除，queue.c 引入 `#include "list_sort.h"`
2. 將 `list_cmp_func_t` 給替換掉，這邊我利用 `strcmp()` 來比較兩值大小
```c
__attribute__((nonnull)) static int cmp(const struct list_head *a,
const struct list_head *b)
{
element_t *ela = NULL, *elb = NULL;
ela = container_of(a, element_t, list);
elb = container_of(b, element_t, list);
return strcmp(ela->value, elb->value);
}
```
3. queue.c 加上的新的函式 `q_listsort`
```c
void q_listsort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
list_sort(head);
if (descend)
q_reverse(head);
}
```
4. qtest.c 加上 listsort 的命令
紀錄在執行 `make` 時出現的一些報錯，以及解決方法。
1. 出現錯誤 `undefind reference to list_sort` ，確認在 queue.c 有加上 `#include "list_sort.h"`，但依舊出現這個錯誤。在 [Risheng1128](https://hackmd.io/@Risheng/linux2023-lab0) 裡發現要在 Makefile 加入 OBJS 變數，新增要編譯出的目標檔案。
```diff
-OBJS := qtest.o report.o console.o harness.o queue.o\
+OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o\
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
shannon_entropy.o \
linenoise.o web.o
```
2. 執行 `git commit` 出現以下報錯
```
list_sort.c:15:11: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
ela = container_of(a, element_t, list);
^
list_sort.c:16:11: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
elb = container_of(b, element_t, list);
^
Fail to pass static analysis.
```
該錯誤原表示我的程式碼中存在空指標的問題，根據報錯訊息是指向 list_head a 和 list_head b 有可能為空指標。因為我在 queue.c 的 q_listsort 有先設立條件確保鏈結串列非空且大於一個節點，可以使用 cppcheck-suppress nullPointer 注釋來告訴 cppcheck 忽略這些特定的警告。
```diff
__attribute__((nonnull)) static int cmp(const struct list_head *a,
const struct list_head *b)
{
element_t *ela = NULL, *elb = NULL;
- ela = container_of(a, element_t, list);
+ ela = container_of(a, element_t, list); // cppcheck-suppress nullPointer
- elb = container_of(b, element_t, list);
+ elb = container_of(b, element_t, list); // cppcheck-suppress nullPointer
return strcmp(ela->value, elb->value);
}
```
### 測試並比較 `mergesort` 與 `list_sort`
參考[Slipet](https://hackmd.io/@Slipet/ryrLNN4Ah#%E5%BC%95%E5%85%A5-liblist_sortc)的實驗方法後，定義實驗的腳本如下:
```
# Test qsort & list_sort
option fail 0
option malloc 0
new
ih RAND 1000000
time
sort/listsort
time
```
首先比較運算時間(四捨五入到小數點第三位)(單位 : s)
| | q_sort | q_listsort |
|---------|----------|-------------|
|第一次 | 0.884 | 0.869 |
|第二次 | 0.989 | 0.897 |
|第三次 | 0.926 | 0.880 |
|第四次 | 0.891 | 0.867 |
|第五次 | 0.892 | 0.878 |
|平均值 | 0.916 | 0.878 |
使用perf 觀察兩者的 instruction 、 cpu cycle 、 cache miss/references
```
$perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f ./traces/trace-test-listsort.cmd
```
| | q_sort | q_listsort |
|---------------------|----------------|-------------|
|**cache-misses** |54,910,492 |48,288,386 |
|**cache-references** |89,689,860 |71,261,586 |
|**instructions** |4,914,653,177 |4,658,927,024|
|**cycles** |6,515,988,823 |6,302,248,693|
|**elapsed time(s)** |1.3629 +- 0.0272|1.34207 +- 0.00609|
從數據上可以得知，運行速度並沒有太大的變化。但在使用 perf 後，可以發現 cache miss/references 是有減少的。那可以印證出lib/list_sort.c 中的演算法的其中一個特點：快取使用效率高，通過深度優先演算法來合併子串列，它減少 cache trashing 現象，提高快取的利用率。
## 針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式
閱讀完 [Timsort](https://en.wikipedia.org/wiki/Timsort) 並且與 [linux/lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 經過比較後，我作出的修改是在合併時增加 Galloping mode，主要基於對 lib/list_sort.c 中鏈結串列的部分有序性考量。特別是在最後的 merge_final 過程中，利用 Galloping mode 可顯著減少比較次數，進而提升效率。
```c
static void gallop_merge(struct list_head *head,
struct list_head *a,
struct list_head *b)
{
struct list_head *tail = head, *tmp = NULL;
while (a && b) {
if (cmp(a, b) <= 0) {
tail->next = a;
a->prev = tail;
tmp = search(tail, b, a, 0);
tail = tmp;
a = tmp->next;
} else {
tail->next = b;
b->prev = tail;
tmp = search(tail, a, b, 1);
tail = tmp;
b = tmp->next;
}
}
if (!b)
b = a;
else
tmp = b;
tail->next = tmp;
do{
tmp->prev = tail;
tail = tmp;
tmp = tmp->next;
}while (tmp);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
```
解釋這段程式碼時，首先比較了 ab 兩個值的大小，然後將較小者直接掛接到 tail->next。假設現在是 a 被掛接到 tail，接下來需要使用 search 函數尋找 b 串列的起始位置在 a 串列的哪個位置中。為了考慮穩定性（stable），也就是確保 a 串列在 b 串列之前，search 函數需要傳入 0 和 1 這兩個參數。
```c
static struct list_head *search(struct list_head *tail,
struct list_head *val,
struct list_head *list,
bool stable)//stable means find a in b
{
struct list_head *head = list;
int k = 0, count = 2;
while (1) {
for (;list && count > 0; count--)
list = list->next;
if (!list || cmp(val, list) < 0 )
break;
else if(!stable && cmp(val, list) == 0)
break;
k += 1;
count = 1 << k;
head = list;
}
while(tail != head){
tail->next->prev = tail;
tail = tail->next;
}
if (stable) {
while (head->next && cmp(val, head) > 0)
head = head->next;
} else {
while (head->next && cmp(val, head) >= 0)
head = head->next;
}
return head;
}
```
timsort 在找尋串列位置使用的方法為：
> In the first stage it performs an exponential search, also known as a galloping search, until finding a k such that R1[$2^(k−1) − 1$] < x <= R1[$2^k − 1$], i.e. a region of uncertainty comprising $2^(k−1) − 1$ $consecutive elements of R1. The second stage performs a straight binary search of this region to find the exact location in R1 for x.
所以第一步我用 count 去找尋 $2^k$ 的位置，然後跟 val 比大小。第二步就用 head 去找尋最後精確位置在哪並回傳。
在執行的報錯：
```
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
```
參考[以 Valgrind 分析記憶體問題](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-b)，執行 `make valgring` 時會跑所有 trace 裡面的檔案，我有改動 scripts/driver.py 加進實驗腳本去做測試。
```
==76268== Invalid read of size 8
==76268== at 0x11059D: cmp (list_sort.c:18)
==76268== by 0x11068E: search (list_sort.c:64)
==76268== by 0x11081A: gallop_merge (list_sort.c:96)
==76268== by 0x11081A: list_sort (list_sort.c:324)
==76268== by 0x1101CE: q_listsort (queue.c:260)
==76268== by 0x10B1A8: do_listsort (qtest.c:653)
==76268== by 0x10E2FB: interpret_cmda (console.c:181)
==76268== by 0x10E8B0: interpret_cmd (console.c:201)
==76268== by 0x10ECB1: cmd_select (console.c:610)
==76268== by 0x10F59D: run_console (console.c:705)
==76268== by 0x10D6ED: main (qtest.c:1338)
==76268== Address 0xfffffffffffffff8 is not stack'd, malloc'd or (recently) free'd
==76268==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer==76268== 8 bytes in 1 blocks are still reachable in loss record 1 of 46
==76268== at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76268== by 0x10DF11: calloc_or_fail (report.c:234)
==76268== by 0x10E849: parse_args (console.c:149)
==76268== by 0x10E849: interpret_cmd (console.c:200)
==76268== by 0x10ECB1: cmd_select (console.c:610)
==76268== by 0x10F59D: run_console (console.c:705)
==76268== by 0x10D6ED: main (qtest.c:1338)
```
更新後
```c
static struct list_head *search(struct list_head *tail,
struct list_head *val,
struct list_head *list,
bool stable)//stable means find a in b
{
struct list_head *begin = NULL, *end = list;
int k = 0, count = 2;
while (list) {
begin = end;
for (;end->next && count > 0; count--)
end = end->next;
if (stable ? cmp(val, end) < 0 : cmp(val, end) <= 0)
break;
k += 1;
count = 1 << k;
}
while(tail != begin){
tail->next = list;
list->prev = tail;
tail = list;
list = list->next;
}
if (stable) {
while (begin->next && cmp(val, begin) > 0)
begin = begin->next;
} else {
while (begin->next && cmp(val, begin) >= 0)
begin = begin->next;
}
return begin;
}
```
```c
static void gallop_merge(struct list_head *head,
struct list_head *a,
struct list_head *b)
{
struct list_head *tail = head, *tmp = NULL;
while (a && b) {
if (cmp(a, b) <= 0) {
tail->next = a;
a->prev = tail;
tmp = search(tail, b, a, 0);
tail = tmp;
a = tmp->next;
} else {
tail->next = b;
b->prev = tail;
tmp = search(tail, a, b, 1);
tail = tmp;
b = tmp->next;
}
}
if (!b)
tmp = a;
else
tmp = b;
tail->next = tmp;
do{
tmp->prev = tail;
tail = tmp;
tmp = tmp->next;
}while (tmp);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
```
## 整合 tic-tac-toe 遊戲
### 將 jserv/ttt 專案的程式碼部分整合進 lab0-c
- 將 Linux 核心的 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 標頭檔與 `hlist` 相關的程式碼抽出，成為 `hlist.h`
> [a35050b](https://github.com/MathewSu-001/lab0-c/commit/a35050b08e1793c8bc465e36fa9d61d1e0913196)
- 修改 `qtest` 程式，使其新增 `ttt` 命令
在 `lab0-c` 中增添檔案夾 `agents` 裡面有 `mcts.[ch]`，在 Makefile 加入 OBJS 變數，新增要編譯出的目標檔案。
```diff
OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o\
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
+ agents/mcts.o ttt.o game.o \
shannon_entropy.o \
linenoise.o web.o
```
在`qtest.c` 的 `console_init()` 替新命令加上 `ADD_COMMAND`。
```c=
ADD_COMMAND(ttt, "Play Tic-tac-toe game", "");
```
>[4078611](https://github.com/MathewSu-001/lab0-c/commit/40786116e6ac2df0dfeacfa72c23044e05df66d4)
### 使用 MCTS 演算法，確保使用定點數來取代原本的浮點數運算
觀察 `mcts.c` 的程式碼中，主要有兩個部份是需要將浮點數改成定點數：
1. 在函式 `simulate` 裡要計算 score ，於程式碼中是設定玩家贏得 1.0 分、平手 0.5 分、輸則得 0 分，這部份應該要改成整數。
2. 計算 uct_score 的方法需要做改動
```c
static inline double uct_score(int n_total, int n_visits, double score)
{
if (n_visits == 0)
return DBL_MAX;
return score / n_visits +
EXPLORATION_FACTOR * sqrt(log(n_total) / n_visits);
}
```
以下為改動內容：
參考 [vax-r](https://hackmd.io/@vax-r/linux2024-homework1#Fixed-point-operation-with-MCTS) 同學後以及閱讀 [Q (number format)](https://en.wikipedia.org/wiki/Q_(number_format)) 後，理解到需要預留給 fraction 幾個 bits 是一門學問。因此我先考慮到的點是 UCT score 的最大值會是多少
$$UCT=\cfrac{w_i}{n_i} + c \sqrt{\cfrac{ln(N_i)}{n_i}}$$
最大值會出現在當 $n_i=1$ 時，且 $w_i=n_i$ ，也就是我只走訪過這個節點一次且勝利，所以式子會變成
$$UCT=1+c\sqrt{ln(N_i)}$$
於程式碼中最大迭代次數為 $N_i=100000$，一般設 $c=\sqrt{2}$
$$UCT=1+\sqrt{ln(100000)}=12.513$$
這邊我使用 `unsigned` 來當成我設計之定點數的資料型態。以 32 bits 來說如果 fraction 取到 16 bits 的話，定點數的值會超過 $2^{19}$ ，再做四則運算會有遺失整數部分的資料，所以最後選擇只取 8 bits，以 Texas Instruments version 來表示我的定點數表示法即是 UQ23.8 。
我將所有 score 的資料型態從 `double` 改為 `unsigned`。另外在原本的 [jserv/ttt](https://github.com/jserv/ttt) 中，贏家、輸家、平手給予的分數在 `calculate_win_value` 以及 `simulate` 也要改為定點數。
```diff
unsigned calculate_win_value(char win, char player)
{
if (win == player)
- return 1.0;
+ return 1U << frac_bits;
if (win == (player ^ 'O' ^ 'X'))
- return 1.0;
+ return 0U;
- return 0.5;
+ return 1U << (frac_bits - 1);
}
```
然後就會出現此錯誤
```
qtest: agents/mcts.c:137: mcts: Assertion `node' failed.
Aborted (core dumped)
```
分析原因為在一開始的時候，所有節點的 UCT 都一樣是 0 ，所以在 `select_move` 函式會回傳 NULL ，所以多新增一個但段機制讓系統隨機選擇一個節點。
```c
if (!best_node) {
while (1) {
best_node = node->children[rand() % N_GRIDS];
if (best_node)
break;
}
}
```
>[bf884d1](https://github.com/MathewSu-001/lab0-c/commit/bf884d1e8f68bf5785fb2c02a831ed765d59a554)
再來是改動計算 uct_score 的方法，這邊同樣參照 [Q (number format)](https://en.wikipedia.org/wiki/Q_(number_format)) 裡的數學計算方法取代原先的乘法和除法
```c
unsigned fixed_mul(unsigned a, unsigned b)
{
unsigned result;
result = a * b;
/* Rounding; mid values are rounded up*/
result += (1U << (frac_bits - 1));
return result >> frac_bits;
}
unsigned fixed_div(unsigned a, unsigned b)
{
unsigned result = a << frac_bits;
/* Rounding: mid values are rounded up. */
result += (b >> 1);
return result / b;
}
```
- 改進 `log` 實做
在 C 語言中， `log` 函數用於計算給定數字的自然對數（底數 e）。參考 [Natural logarithm](https://en.wikipedia.org/wiki/Natural_logarithm) 中的敘述，可以了解到如何透過泰勒展開式對自然對數使用進行近似。
$$ln(x) = 2\cdot ((\cfrac{x - 1}{x + 1}) + \cfrac{1}{3}(\cfrac{x-1}{x+1})^3 + \cfrac{1}{5}(\cfrac{x-1}{x+1})^5 \cdots)$$
```c
unsigned fixed_log(unsigned n)
{
unsigned result = 0;
unsigned tmp = fixed_div(n - (1U << frac_bits), n + (1U << frac_bits));
unsigned ratio = fixed_mul(tmp, tmp);
int k = 0;
while (k < 50) {
unsigned ttmp = fixed_div(tmp, (2 * k + 1) << frac_bits);
tmp = fixed_mul(tmp, ratio);
k++;
result += ttmp;
}
return result << 1;
}
```
然後設計一個程式可以比較透過 `log` 以及自定義的 `fixed_log` 的結果差距，考慮到 `fixed_log` 的輸入是目前節點的親代節點的模擬次數，所以會是整數且最大值為 100000 ，每次增加 1.0 且泰勒展開之項次設為 50，比較後結果如下
將最大值縮小到 1000 後，結果圖如下
發現兩者結果差距很大，而且 `fixed_log` 會是以階梯式上升。我認為原因是出在泰勒展開的項次太少，且 fraction 只有到小數點 8 位造成精度不正確。
所以我做出的改動就是將原本 score 的資料型態從 `unsigned` 改為 `unsigned long`，Texas Instruments version 定點數表示法變成 UQ47.16；然後泰勒展開項次改成 100 次。
將最大值縮小到 1000 後，結果圖如下
>[5912270](https://github.com/MathewSu-001/lab0-c/commit/59122702c417dbe3b68262a38b5047a7ca004fee)
:::info
可以看到 x 在小數目的精確度是有明顯變好，但是當 x 超過 10000 時獲得的值都是一樣的，可能泰勒展開的項次增加會讓結果會變好，但是就會讓效能下降，這部份的取捨有待研究。
:::
- 改進 `sqrt` 實做
參考 [第三週測驗一](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-1) 的作法，因為資料型態是 `unsigned long` ，所以 m 的初始值要從 63 開始減去。另外在最後第 16 行計算得出 z 值需要再乘以 $2^{frac\_bits/2}$ ，解釋如下：
假設我們有一個數 $x$，它的表示是定點數，形式為：
$$x_{fixed}=x*2^{frac\_bits}$$
在計算平方根時，由於平方根的性質，結果 z 需要被調整
$$\sqrt{x_{fixed}}=\sqrt{x*2^{frac\_bits}}=\sqrt{x}*2^{frac\_bits/2}$$
```c==
unsigned long fixed_sqrt(unsigned long x)
{
if (!x || x == (1U << frac_bits))
return x;
unsigned long z = 0;
unsigned long m = 1UL << ((63 - __builtin_clz(x)) & ~1UL);
for (; m; m >>= 2) {
unsigned long b = z + m;
z >>= 1;
if (x >= b) {
x -= b;
z += m;
}
}
z <<= (frac_bits >> 1);
return z;
}
```
與浮點數計算比較後結果如下
>[559ab34](https://github.com/MathewSu-001/lab0-c/commit/559ab3428071615176ad2ab1eb146ca3c3d2216d)
### 允許使用者切換「人 vs.電腦」或「電腦 vs.電腦」的對弈
當切換到「電腦 vs.電腦」的對弈，我引入的另一個演算法是使用 `negamax`，並且新增函式 `show_time` 可以在螢幕顯示當下的時間 (含秒數)。
```c
void show_time(){
time_t rawtime;
struct tm *timeinfo;
char buffer[80];
time(&rawtime);
timeinfo = localtime(&rawtime);
strftime(buffer, sizeof(buffer), "%Y-%m-%d %H:%M:%S", timeinfo);
printf("Current time: %s\n", buffer);
}
```
並且在 `qtest.c` 引入新的 `option` : `opponent` 來決定是誰再跟電腦對奕。
```c
add_param("opponent", &opponent, "Choose ttt opponent: human(0) or computer(1).", NULL);
```
>[b8fc80d](https://github.com/MathewSu-001/lab0-c/commit/b8fc80db4830392e9dbe9d7af065f36ce16c6843)
Sign in with Wallet
Connect another wallet