# 2024q1 Homework1 (lab0)
contributed by < [`kkkkk1109`](https://github.com/kkkkk1109) >
### Reviewed by `Kuanch`
* 未完成 `lib/list_sort.c` 部分
* 研讀論文〈Dude, is my code constant time?〉[我](https://hackmd.io/QDxYHCXIQ7SQ-k7cM34Vcw?both#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89)傾向至少將程式碼一一和文章對應，譬如它是如何計算執行時間、怎麼做後處理、如何計算統計量等等；或參考 [vax-r](https://hackmd.io/@vax-r/linux2024-homework1#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89) 同學，他以記錄自身的問題以及解答撰寫本節
* Git 部分
都在 `master` 上開發，並沒有開新分支，故無法練習使用 `git rebase`或其他操作；建議可以先試試看新增新分支後只提交一個 commit 再試著 `git rebase`；可以用一些圖形管理去看 git tree，[stackoverflow](https://stackoverflow.com/questions/1064361/unable-to-show-a-git-tree-in-terminal) 也有命令列的使用方法。
另外，一些 commit message 可以再補充，如 commit [1568416](https://github.com/kkkkk1109/lab0-c/commit/156841697c2d7413f068b3ab7f0fd506d44a8663)，可以參考 commit [a0b17c1](https://github.com/vax-r/lab0-c/commit/a0b17c1e9e5086839eba8e8c16a1b01085978b61)
> 既然你認為同學做不好，示範一次好的做法，並說明為何你的方式較好，這樣才有程式碼審查的效果。 :notes: jserv
### Reviewed by `Lccgth`
在佇列操作中的子標題觀感不一致，例如 `q_new` 和 q_free。
在佇列操作中比起列出程式碼連結，應列出各個函式的 git commit 紀錄，當日後發現函式實作能更加優化時，根據 commit 紀錄能夠輕易看出每個版本間的差別。
避免非必要的項目縮排，筆記內有多處條列，例如 q_swap、q_sort、q_shuffle。
q_ascend & q_descend 中的 graphviz 圖有錯誤無法顯示。
在研讀 list_sort.c 中將程式碼貼上時要注意排版。
### 開發環境
```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
Byte Order: Little Endian
Address sizes: 45 bits physical, 48 bits virtual
CPU(s): 2
On-line CPU(s) list: 0,1
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 2
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-9700KF CPU @ 3.60GHz
Stepping: 12
CPU MHz: 3599.999
BogoMIPS: 7199.99
Hypervisor vendor: VMware
Virtualization type: full
L1d cache: 64 KiB
L1i cache: 64 KiB
L2 cache: 512 KiB
L3 cache: 24 MiB
NUMA node0 CPU(s): 0,1
```
## 指定的佇列操作
### q_new
:::danger
在此列出 git commit 對應的超連結。
:::
建立 `list_head` 的記憶體，並且若失敗的話，則返回 `NULL`。使用 `INIT_LIST_HEAD`，來進行初始化。
> commit [a575e70](https://github.com/sysprog21/lab0-c/commit/a575e7090045de59eed7b3ac39eec2a1e1a596f5)
### q_free
:::danger
使用你 fork 之後的 lab0-c 對應的 commit 超連結。
:::
剛開始實作時，尚未理解將 `list_head` 此結構加入 `element_t` 中的概念，因此釋放記憶體僅有考慮到 `list_head` 的記憶體。
> commit [d315cd2](https://github.com/sysprog21/lab0-c/commit/d315cd2b5cfa00b30a656bfb5f2723505dd0970f)
:::danger
列出同學的 GitHub 帳號名稱。
:::
隨著詳閱 `list.h` 並和[MathewSu-001](https://github.com/MathewSu-001/lab0-c) 討論，發現有許多的巨集可以使用，這邊使用了以下巨集
1. `list_for_each_entry_safe` : 刪除節點的同時，可保留下個節點的地址。
2. `list_del` : 將此 `list_head` 從 linkedlist 中移除，並釋放記憶體。
3. `q_element_release` : 釋放 `element_t` 佔用的記憶體。
### q_insert_head & q_insert_tail
建立 `element_t`，並且使用 `strdup` 來複製字串 `s`，若失敗則~~釋放此記憶體~~使用 `q_element_release` 釋放此 `element_t`。使用巨集 `list_add` 和 `list_add_tail` 來插入佇列。
> commit: [`q_insert_head`](https://github.com/sysprog21/lab0-c/commit/4574073a146366f70827643a5538bcdb4cdebcb0) [`q_insert_tail`](https://github.com/sysprog21/lab0-c/commit/4687e63c9ba59c579d7a7fb20b89f48390e6e124)
### q_remove_head & q_remove_tail
利用巨集 `list_first_entry` 和 `list_last_entry` 分別找出佇列的第一個節點和最後一個節點，並使用 `strncpy` 將此節點字串複製至 `sp` 中。
> commit: [`q_remove_head`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L73) [`q_insert_tail`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L88)
### q_delete_mid
將 `rn` 設為順著 `next` 方向移動的節點，`ln` 為順著 `prev` 方向移動的節點，當雙方 **交會於一點** 或 **`rn` 下個節點為 `ln`**，則可以判斷 `rn` 為中間點。並使用巨集 `list_entry` 將其記憶體釋放。
> commit: [`q_delete_mid`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L117)
### q_delete_dup
* **初始想法**
於已完成排序的佇列中，刪除重複的節點，因此只需要考慮相鄰的節點是否重複即可。
利用布林函數 `dup` 判斷是否有重複字串的情形，並使用巨集 `list_for_each_entry_safe` 逐一走訪佇列中的節點，若有出現重複的情形，將 `dup` 設置為 ` true`，並釋放節點`node`，再繼續檢查下兩節點是否重複，若無，刪除原重複節點，並將 ` dup` 設為 ` false`。
> commit: [`q_delete_dup`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L138)
### q_swap
利用三個指標 `fir`, `mid`, `sec` 來完成 `swap` 的動作，並分兩次進行，利用巨集 `list_for_each_safe` 來逐一走訪整個佇列中的節點。
以下為圖例
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="Head",color =green style=filled]
e1 [label="1",color =lightblue2 style=filled]
e2 [label="2", color=lightblue2 style=filled]
e3 [label="3",color =green style=filled]
e4 [label="4"]
e5 [label="5"]
// next 方向
head -> e1
e1 -> e2
e2 -> e3
e3 -> e4
e4 -> e5
e5 -> head
// prev 方向
head -> e5
e5 -> e4
e4 -> e3
e3 -> e2
e2 -> e1
e1 -> head
// pointer 初始化
}
```
第一次:
1. 將 `fir` 的`next` 連向 `mid`
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="fir",color =green style=filled]
mid [label="mid",color =lightblue2 style=filled]
sec [label="sec", color=lightblue2 style=filled]
e3 [label="3",color =green style=filled]
e4 [label="4"]
e5 [label="5"]
// next 方向
head -> sec [color =green style=filled]
mid -> sec
sec -> e3
e3 -> e4
e4 -> e5
e5 -> head
// prev 方向
head -> e5
e5 -> e4
e4 -> e3
e3 -> sec
sec -> mid
mid -> head
// pointer 初始化
}
```
2. 將 `sec` 的 `prev` 指向 `fir`
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="fir",color =green style=filled]
mid [label="mid",color =lightblue2 style=filled]
sec [label="sec", color=lightblue2 style=filled]
e3 [label="3",color =green style=filled]
e4 [label="4"]
e5 [label="5"]
// next 方向
head -> sec [color =green style=filled]
mid -> sec
sec -> e3
e3 -> e4
e4 -> e5
e5 -> head
// prev 方向
head -> e5
e5 -> e4
e4 -> e3
e3 -> sec
sec -> head[color =green style=filled]
mid -> head
// pointer 初始化
}
```
3. 將 `mid` 的 `prev` 指向 `sec`
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="fir",color =green style=filled]
mid [label="mid",color =lightblue2 style=filled]
sec [label="sec", color=lightblue2 style=filled]
e3 [label="3",color =green style=filled]
e4 [label="4"]
e5 [label="5"]
// next 方向
head -> sec [color =green style=filled]
mid -> sec
sec -> e3
e3 -> e4
e4 -> e5
e5 -> head
// prev 方向
head -> e5
e5 -> e4
e4 -> e3
e3 -> sec
sec -> head[color =green style=filled]
mid -> sec[color =green style=filled]
// pointer 初始化
}
```
進入下次迴圈
第二次:
1. 將 `mid` 的 `next` 指向 `fir`
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="head",color =green style=filled]
fir [label="fir",color =lightblue2 style=filled]
mid [label="mid", color=lightblue2 style=filled]
sec [label="sec",color =green style=filled]
e4 [label="4"]
e5 [label="5"]
// next 方向
head -> mid [color =green style=filled]
fir -> mid
mid -> fir[color =blue style=filled]
sec -> e4
e4 -> e5
e5 -> head
// prev 方向
head -> e5
e5 -> e4
e4 -> sec
sec -> mid
mid -> head[color =green style=filled]
fir -> mid[color =green style=filled]
// pointer 初始化
}
```
2. 將 `fir` 的 `next` 指向 `sec`
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="head",color =green style=filled]
fir [label="fir",color =lightblue2 style=filled]
mid [label="mid", color=lightblue2 style=filled]
sec [label="sec",color =green style=filled]
e4 [label="4"]
e5 [label="5"]
// next 方向
head -> mid [color =green style=filled]
fir -> sec[color =blue style=filled]
mid -> fir[color =blue style=filled]
sec -> e4
e4 -> e5
e5 -> head
// prev 方向
head -> e5
e5 -> e4
e4 -> sec
sec -> mid
mid -> head[color =green style=filled]
fir -> mid[color =green style=filled]
// pointer 初始化
}
```
3. 將 `sec` 的 `prev` 指向 `fir`
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="head",color =green style=filled]
fir [label="fir",color =lightblue2 style=filled]
mid [label="mid", color=lightblue2 style=filled]
sec [label="sec",color =green style=filled]
e4 [label="4"]
e5 [label="5"]
// next 方向
head -> mid [color =green style=filled]
fir -> sec[color =blue style=filled]
mid -> fir[color =blue style=filled]
sec -> e4
e4 -> e5
e5 -> head
// prev 方向
head -> e5
e5 -> e4
e4 -> sec
sec -> fir[color =blue style=filled]
mid -> head[color =green style=filled]
fir -> mid[color =green style=filled]
// pointer 初始化
}
```
如此一來，便完成了將兩個相鄰的節點 `swap`，若 `mid` 或 `sec` 其中一個達到 `head` ，則代表只剩 `tail` 這個節點，其餘節點均已 `swap` 。
> commit: [`q_swap`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L161)
### q_reverse
使用巨集 list_for_each_safe ，由於此巨集可使用 `safe` 存取 `node` 的下個節點，對 `node` 的 `list_head` 操作不會影響下個節點的造訪。將 `node` 的`next` 指向 `node` 的 `prev`，並將 `node` 的 `prev` 指向 `safe` 。 走訪結束後，再將 `head` 進行以上操作即可完成 `reverse`。
> commit: [`q_reverse`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L184)
### q_reverse_K
使用巨集 list_for_each_safe ，並引入 `count` 來記錄已經過幾個節點，當達到 `k` 個節點時，將此 `K` 個節點利用巨集 `list_cut_position` 分割出來，並以 `new_head` 紀錄此分割串列， 再進行`reverse` ，再使用 巨集 `list_splice`，將反轉後的佇列接回原本的佇列。
> commit: [`q_reverse_K`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L199)
### q_sort
* **初始想法**
使用 `merge_sort`，找出佇列的中點，使用巨集`cut_list_position` 將佇列分割，並進行遞迴。並在 `merge` 的過程中， 加入新的 `list_head`，將左右佇列較小的節點利用 `list_tail` 加入此新的佇列，並回傳此佇列。
參考 [`WangHanChi`](https://hackmd.io/@wanghanchi/linux2023-lab0#q_sort)的操作，運用到了[你所不知道的 C 語言: linked list 和非連續記憶體 ](https://hackmd.io/@sysprog/c-linked-list) **指標的指標** 操作，讓我較了解**指標的指標**的操作。
#### `q_sort`
1. 方法為先將 `環狀佇列` 的頭尾斷開，將其當成 `單向佇列` 來實作，並呼叫 `merge_divide` ，將佇列進行分割。
2. 將以排序好的佇列的 `prev` 給連接回去。
#### `merge_divide`
1. 在 [`q_delete_mid`](https://hackmd.io/GriGLbnPQAWgoRPcpk9XiA?view#q_delete_mid)中，我使用找中點的方式為利用兩節點往 `prev` 和 `next` 的方向找尋，而這邊則是學習使用 `龜兔賽跑` 的方式找中點。
2. 將中點和他的 `prev` 連結斷開，分割成 `left` 和 `right` 佇列，並進行遞迴，最後返回 `merge_two_nodes`
#### `merge_two_nodes`
1. 將所接收到的 `left` 和 `right` 佇列進行合併排序，這邊使用了 **指標的指標** `indirect` 來存取指標`m_head` 的指標，`**iter` 來進行迭代。
2. 將`left` 和 `right` 的第一個元素進行比較，將 `iter` 指向較小的指標，利用 `indirect` 存取此較小的指標，並繼續迭代，
3. 目前 `iter`指向的是較小的指標的下一個節點，將此節點和上次的較大節點比較，較小的會再由 `iter` 來存取，持續迭代直到其中一個佇列指向 `NULL`，並將 `indirect` 指向另一個佇列中剩餘的節點，完成合併。
> commit: [`q_sort`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L253) [`merge_divide`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L239) [`merge_two_nodes`](https://github.com/kkkkk1109/lab0-c/blob/master/queue.c#L223)
### q_ascend & q_descend
1. 利用雙向鏈結的特性，從 `tail` 造訪整個佇列，將`tail` 設為 `min` ，`cur` 設為 `min` 的`prev`。
2. 比較`min` 和 `cur` 的大小
`cur` > `min` ，將此節點移除，將 `cur` 往左移一格
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="head"]
e1 [label="1"]
e2 [label="10"]
e3 [label="2"]
e4 [label="8"][color = lightblue style=filled]
cur [label="cur"][color = lightblue style=filled]
e5 [label="5"][color = green style=filled]
min [label="min"][color = green style=filled]
// next 方向
head -> e1
e1 -> e2
e2 -> e3
e3 -> e4
e4 -> e5
//e5 -> head
min -> e5
cur -> e4
// prev 方向
//head -> e5
e5 -> e4
e4 -> e3
e3 -> e2
e2 -> e1
e1 -> head
// pointer 初始化
}
```
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="head"]
e1 [label="1"]
e2 [label="10"]
e3 [label="2"][color = lightblue style=filled]
cur [label="cur"][color = lightblue style=filled]
e5 [label="5"][color = green style=filled]
min [label="min"][color = green style=filled]
// next 方向
head -> e1
e1 -> e2
e2 -> e3
e3 -> e5
cur -> e3
//e5 -> head
min -> e5
// prev 方向
//head -> e5
e5 -> e3
e3 -> e2
e2 -> e1
e1 -> head
// pointer 初始化
}
```
`cur` = `min` ，`cur` 和 `min` 都往左一格
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="head"]
e1 [label="1"]
e2 [label="10"][color = lightblue style=filled]
e3 [label="2"][color = green style=filled]
cur [label="cur"][color = lightblue style=filled]
e5 [label="5"]
min [label="min"][color = green style=filled]
// next 方向
head -> e1
e1 -> e2
e2 -> e3
e3 -> e5
cur -> e2
//e5 -> head
min -> e3
// prev 方向
//head -> e5
e5 -> e3
e3 -> e2
e2 -> e1
e1 -> head
// pointer 初始化
}
```
直到最後 會呈現 `ascend` 的排列
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="head"]
e1 [label="1"]
e3 [label="2"]
e5 [label="5"]
// next 方向
head -> e1
e1 -> e3
e3 -> e5
//e5 -> head
// prev 方向
//head -> e5
e5 -> e3
e3 -> e1
e1 -> head
// pointer 初始化
}
```
`q_descend` 僅將判斷大小相反即可。
> 程式碼: [`q_ascend`](https://github.com/25077667/lab0-c/blob/dev/queue.c#L401) [`q_descend`](https://github.com/25077667/lab0-c/blob/dev/queue.c#L412)
### q_merge
於 `queue.h` 中可以看到結構 `queue_contex_t`
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
* `q` 可指向此佇列的 `head`
* `chain` 可前往下個佇列
* `size` 表示了此佇列中含有的節點數
* `id` 表示了此佇列的編號
而 `q_merge` 要將這些佇列結合至第一個佇列，並進行排序，可以使用我們於 `q_sort` 中使用的 `merge_two_nodes` 來合併這些佇列。
1. 利用巨集 `list_entry` 來找出第一個佇列 `first`，並使用 `q_size` 計算其包含幾個節點
2. 由於我們使用的是 `merge_two_nodes`，將此環狀鏈結頭尾斷開。
3. 開始逐一走訪各個佇列，並將佇列中的環狀鏈結頭尾斷開，呼叫 `merge_two_nodes` 將 佇列`first` 和各個佇列合併排序。
4. 所有佇列合併後，再將每個節點的 `prev` 指向前一個節點，即完成 `merge`
> 程式碼: [`q_merge`](https://github.com/25077667/lab0-c/blob/dev/queue.c#L401)
## Make test
使用 `make test` 測試，在電腦上為100分
```shell
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
:::danger
保留關鍵訊息作為討論。
:::
顯示 ` trace-17-complexity` 是滿分，但是上傳至github卻是95分，問題應該是出在 `simulation` 中。
## 使用 Valgrind 排除 qtest 實作的記憶體錯誤
### 筆記
[Valgrind](https://valgrind.org/) 是一種以 `shadow value` 的方式，來偵測記憶體的使用錯誤
* dynamic Binary Instrumentation (DBI) :著重於二進位執行檔的追蹤與資訊彙整
* dynamic Binary Analysis (DBA):強調對收集資訊的分析
> VEX IR 在 Valgrind 採用執行導向的方式，以 just-in-time (JIT) 編譯技術動態地把機械碼轉為 IR，倘若觸發特定工具感興趣的事件 (如記憶體配置)，就會跳躍到對應的處理工具，後者會插入一些分析程式碼，再把這些程式碼轉換為機械碼，儲存到 code cache 中，以利後續需要時執行。
> An intermediate representation (IR) is the data structure or code used internally by a compiler or virtual machine to represent source code.
> 
### Valgrind 運用
```shell
$ valgrind -q --leak-check=full ./qtest
cmd> option simulation 1
cmd> it
Probably constant time
cmd> ih
Probably constant time
cmd> rh
Probably constant time
cmd> rt
Probably constant time
cmd> option simulation 0
cmd>
```
---
## Dude, is my code constant time?
### 論文提及方法
1. Measure execution time
以兩種不同類別的資料輸入程式，並重複計算其運行時間，使用 `fix-vs-random` 的方式。
* Classes definition
* class 1 : 通常為固定資料類別(可能含有特殊情況)
* calss 2 : 為隨機資料類別
2. Apply post-processing
* Cropping:可以對資料進行裁減，以避免發生正偏態分配
* Higer-order processing: *高階處理?*
3. Apply statistical test
* t-test: 使用 Welch’s t-test ，用以查看兩個獨立樣本的平均值是否明顯地不同。
* Non-parametric tests
* Pre-processing:
在進行統計前，先捨棄大於 `p` 百分比的資料，來限制分布範圍，避免出現極端值。
於 `dutect` 中，有進行上述所說的 ` pre-processing `
但於 `lab0/dutect` 中，卻看不到此蹤影。
### 分析 `lab0/dudect`
#### `constant.c`
針對 `insert_head` 、`insert_tail` 、`remove_head` 和 `remove_tail` 進行 `dudect` 方法測試
#### `ttest.c`
關於 `t-test` 的步驟
1. `t_init` : 初始化 `t` 的值
2. `t_push` : 得到樣本資料?
3. `t_compute`:計算 平均值 和 變異數 ，並得到`t` 值
#### `fixture.c`
主要 `dutect` 的實作，且和 `dutect` 中的`update_statistic` 比對，可以發現明顯少了一大部分
```diff
static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
for (size_t i = 0; i < N_MEASURES; i++) {
int64_t difference = exec_times[i];
/* CPU cycle counter overflowed or dropped measurement */
if (difference <= 0)
continue;
- // t-test on cropped execution times, for several cropping thresholds.
- for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
- if (difference < ctx->percentiles[crop_index]) {
- t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
- }
- }
- // second-order test (only if we have more than 10000 measurements).
- // Centered product pre-processing.
- if (ctx->ttest_ctxs[0]->n[0] > 10000) {
- double centered = (double)difference - ctx->ttest_ctxs[0]->mean[ctx->classes[i]];
- /* do a t-test on the execution time */
t_push(t, difference, classes[i]);
}
}
```
將缺失的部分補上，主要參考 [`dutect.h`](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 和 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023)
### 於[課堂筆記](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ)中問到為何使用 ttest之方法
首先，此一論文是為了測試程式是否能夠在常數時間內完成，且不侷限特定平台也可完成。
常見的檢定方式有 [Z-test](https://en.wikipedia.org/wiki/Z-test)和 [T-test](https://en.wikipedia.org/wiki/Student%27s_t-test)， Z-test 建立在樣本數夠大，且已有母體的變異數，才會使用 Z-test。而在此論文中，母體的變異數是無法取得的，因此無法使用 Z-test。
T-test 主要分為 One-sample t-test、Two-sample t-tests 和 Paired-tests。
* One-sample t-test 是用來檢測母體的平均值是否為預設的特定值
* Two-sample t-tests 是用來測量兩個群組的平均值是否有差異
* Paired-tests 是對於同個群組，兩次不同測量的平均值是否有差異
論文所比較的是兩個不同的類別 fix vs random ，以此情況該使用 Two-sample t-tests，來比較在不同輸入的情形下，兩者的平均值是否有差異。
該注意的是 Two-sample t-tests 的使用也有限制，若兩群組的大小、變異數相同，可以使用此 T-test，但在大小和變異數不同的情況下，則使用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)。此論文中提到，會對資料進行 Cropping，來去除極端值，因此可以假定兩群組的數量不一定相同，因此使用 Welch's t-test 來進行測量。
---
## 整合網頁伺服器
於一終端機A輸入，表示正在監聽，等待埠號 `9999` 的網路連線
```
$ ./qtest
cmd> web
listen on port 9999, fd is 3
```
於另一終端機B輸入
```shell
$ curl 127.0.0.1:9999/new
l = []
$ curl 127.0.0.1:9999/ih/a
l = [a]
$ curl 127.0.0.1:9999/ih/b
l = [b a]
$ curl 127.0.0.1:9999/ih/sort
l = [sort b a]
c$ curl 127.0.0.1:9999/sort
l = [a b sort]
```
:::danger
command 是「命令」，而非「指令」(instruction)
:::
終端機A接收到B的<s>指令</s>命令，並插入字串和排列
```shell
listen on port 9999, fd is 3
cmd> l = []
cmd> l = [a]
cmd> l = [b a]
cmd> l = [sort b a]
cmd> l = [a b sort]
```
---
## 實作 `q_shuffle`
利用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法來實作洗牌（shuffle）
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
:::info
收到
:::
實作方法如下，先取得佇列的大小 `size`，並於 `0`~ `size-1` 中隨機選取數值 `random` ，並將從頭數第 `random` 節點和最尾端的節點交換，接著令 `size-1` ，代表剩餘要交換的節點數。
持續以上步驟，直到所有節點均交換完畢。
但在交換時，要考慮到以下情況，`old` 為從前面數來的節點， `new` 為尾端節點。
* `old` == `new` :跳過此次交換
* `old` 和 `new` 相鄰:
若是 `old` 在 `new` 前面，將 `new` 節點移除佇列，再插入於 `prev1` 後方。
* `old` 和 `new` 並無相鄰:
將 `old` 和 `new` 移除佇列，並將 `old` 插入於 `prev2` 後方；將 `new` 插入於 `prev1` 後方
:::info
因為多考慮到了節點 `new` 在 `old` 前方，和同學 [`MathewSu-001`](https://github.com/MathewSu-001/lab0-c)討論後發現不會發生此情況，而修改程式碼。
:::
> commit [d891c51](https://github.com/sysprog21/lab0-c/commit/d891c51110f5c5c704295be1b2686fc69cf5070a)
:::danger
使用 `git diff` 或 `diff -u` 來產生程式碼之間變異列表，不要憑感覺填入，注意位移量。
:::
使用 LAB0(D)中的[測資](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)以下為輸出結果
```
xpectation: 41666
Observation: {'1234': 41563, '1243': 41586, '1324': 41533, '1342': 41693,
'1423': 41699, '1432': 41954, '2134': 41872, '2143': 41515,
'2314': 41680, '2341': 41674, '2413': 41487, '2431': 41595,
'3124': 41607, '3142': 41399, '3214': 41710, '3241': 41967,
'3412': 41173, '3421': 41848, '4123': 41798, '4132': 41890,
'4213': 41526, '4231': 41546, '4312': 41712, '4321': 41973}
chi square sum: 20.723947583161333
```
可以看到符合Uniform distribution
---
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
在`list_sort.c` 中， `__attribute__((nonnull())` 出現了很多次，並查看此程式碼的使用方法。
:::danger
更新 GCC 手冊超連結的版本。
:::
:::info
已更改
:::
在 [GCC 的 6.33.1 Common Function Attributes](https://gcc.gnu.org/onlinedocs/gcc-13.2.0/gcc/Function-Attributes.html) 中，可以看到 `attribute` 的解釋
> Function attributes are introduced by the __attribute__ keyword in the declaration of a function, followed by an attribute specification enclosed in double parentheses.
並解釋道可以利用不同的 `attribute` 來進行`declaration` 。
於 nonull 中，解釋道
> The nonnull attribute specifies that some function parameters should be non-null pointers
以 `list_sort.c` 中的 `merge` 舉例
```c
__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
```
可以知道引入參數 `list_cmp_t cmp`、`struct list_head *a` 和 `struct list_head *b` 不能為 `NULL`。
且若 `nonull` 雙括號中無特別說明第幾個參數，如下
```c
__attribute__((nonnull));
```
即代表所有參數均不能為 `NULL`。
**`merge`**:
說明如下
> Returns a list organized in an intermediate format suited to chaining of merge() calls: null-terminated, no reserved
or sentinel head node, "prev" links not maintained.
意思為此函式的使用為會返回一個 **中繼** 的格式，並非最終的格式，由最終節點為 `null` ， 指標 `prev` 並沒有指向其該指向的地址，也可以佐證。
此函式使用了 指標 `head` 和 指標的指標 `tail`，來進行合併，方法如下
使用 `cmp` 比較 `a` 和 `b` 的大小:
* `a` < `b`:
```c
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
```
令 `*tail` 指向 `a`， `tail` 指向 `tail->next` 的指標，並讓 `a=a->next` ，繼續進行比較。
* `a` >= `b`:
```c
else {，，
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
```
換令 `*tail` 指向 `a`，`tail` 一樣指向 `tail->next` 的指標。
上述兩種清況接考慮到，若下個節點不存在，則將剩餘的串列直接連上。使用此方法不須額外使用記憶體，而是直接利用兩串列的記憶體來完成合併排序。
**`merge_final`**:
用於進行最後一次合併，且將先前雜亂的 `prev` 給重新接上和頭尾相連，使之變回雙向環狀鏈結。
```c
struct list_head *tail = head;
u8 count = 0;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
/* Finish linking remainder of list b on to tail */
tail->next = b;
```
令 `tail` = `head` ，利用 `tail` 來慢慢連接下個節點。讓我覺得有趣的地方是，這邊在 `a` 或 `b` 為 NULL 的情況下，使用了不同的方法。
```c
if (!a)
break;
...
if (!b) {
b = a;
break;
}
tail->next = b;
```
若 `a` 較小，且為 NULL，則跳出迴圈，令 `tail` 接上 `b` ；反之，則令 `b` 為 `a` ，最後還是令 `tail` 接上 `b`，只不過此時的 `b` 為 `a` 。
```c
do {
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
```
接下來是將 `b` 序列中的 `prev` 接上，此時可以看到使用了 `unlikely`，查看關於 `unlikely` 的巨集
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
`!!(x)` 是為了讓值只會有 0 或 1， 接下來查看 `--builtin_expect`
[GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)對於 `--builtin_expect` 的說明中，可以幫助 compiler 做 branch prediction。
> You may use `__builtin_expect` to provide the compiler with branch prediction information.
在上學期修的 [Computer Architecture](https://wiki.csie.ncku.edu.tw/arch/schedule)中，CPU在 pipeline 中會做 branch prediction，預先設定 branch 會跳往哪個分支。而在此就是可以先和編譯器說明何者為**較可能跳往**的分支，來幫助編譯器最佳化。
另外在 [likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/) 文章中也有以 `likely` 來實際看編譯會發生什麼變化
> 給一段簡單的 c 程式，使用 likely 巨集:
```c
#include <stdio.h>
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
void foo();
void bar();
int main(char *argv[], int argc)
{
if (likely (argc == 2))
foo();
else
bar();
}
```
> 組譯出來的結果會是(ARM gcc 8.2, with O2 optimization):
```assembly
main:
cmp r1, #2
push {r4, lr}
bne .L2
bl foo
.L3:
mov r0, #0
pop {r4, pc}
.L2:
bl bar
b .L3
```
:::info
可以發現他使用的是 `bne` ，並馬上連接跳往 `foo`。
:::
> 那如果我們將likely改成unlikely，我們會得到
```assembly
main:
cmp r1, #2
push {r4, lr}
beq .L6
bl bar
.L3:
mov r0, #0
pop {r4, pc}
.L6:
bl foo
b .L3
```
變成了 `beq` ，並馬上連接跳往 `bar`。
回到程式碼中，說明中提到
> If the merge is highly unbalanced (e.g. the input is already sorted), this loop may run many iterations.Continue callbacks to the client even though no element comparison is needed, so the client's cmp() routine can invoke cond_resched() periodically.
不懂這樣子的情境為何，猜測為若持續在迴圈中，會無法呼叫 `con_reshed()` 來進行 kernal preemption，因此要讓他加以判斷來去定期呼叫 `con_reshed()`。
**`list_sort`**
於 [`lab0(E)`](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e) 中說明道
> 用 bottom up 實作 merge sort 對 cache 較友善，因為過程中就是一直合併，cache 被參照到的機會更大。
> 而 top down 是會先做 partition 再來 merge，但 partition 本身對 cache 不友善，在 cache 移進移出（內容不斷更新，導致 cache thrashing
cache thrashing 是當所需要使用記憶體大於 L1 快取的容量時，會持續地發生 cahce miss，導致運用效能下降。因為 `top down` 需要先存取整個陣列的大小，進行分割後再合併，導致 cache line 要持續更新。`bottom up` 則是只有進行合併過程，過程中只要確保合併量不超出 L1 容量，則可避免 cache thrashing。
而此合併方式為只要 ${3 \times 2^{K}}$ 能夠放入 L1 cache，則保持以 2:1 的方式合併。假設有 ${3 \times 2^{K}}$ 個節點，則將 ${2^{K}}$ 和 ${2^{K}}$ 合併成 ${2^{K+1}}$ ，並留下 ${2^{K}}$ 個節點。
接下來即是如何判斷是否該合併?可利用 `count` 來觀察:
`count` 為待合併中節點數量，以 binary形式來看可以更容易判斷
| count | 節點數 | pending list |
|:-----:|:----------------------------:|:-----------------------------------------:|
| 1 | ${2^{0}} = 1$ | [1] |
| 10 | ${2\times2^{0}} = 2$ | [1,1] |
| 11 | ${3\times2^{0}} = 3$ | [1,1,1] -> [**(2)**,1] |
| 100 | ${2^{1} +2\times2^{0} } = 4$ | [ (2) ,1 , 1] |
| 101 | ${2^{1} +3\times2^{0} } = 5$ | [ (2) ,1 ,1 ,1] -> [**(2)**, **(2)** ,1] |
| 110 | ${3\times2^{1} } = 6$ | [ (2) ,(2) ,1, 1] ->[ **(4)** ,1 , 1] |
| 111 | ${2^{2}+ 3\times2^{0}} = 7$ | [ (4) ,1 , 1, 1] -> [ (4), **(2)**, 1] |
| 1000 | ${2\times2^{2} } = 8$ | [ (4), (2), 1, 1] |
由上方的表格，可以發現只有在 `count` 為非 **2的冪** 時才會進行合併，且當進行 ${3\times2^{K}}$ 合併時，會發現此時 `count` 第 `K` 個位元為 `1`， 第 `0~(K-1)` 個位元會為 `0`。
以 `count` 為 5 和 6 舉例
`count` 為 5 = 10++1++ :非2的冪，進行 ${3\times2^{0}}$ 合併，底線位元為第 0 位為 1。
`count` 為 6 = 1++1++0 :非2的冪，進行 ${3\times2^{1}}$ 合併，底線位元為第 1 位為 1，第 0 (0~k-1) 位為 0。
接下來看 `list_sort` 的程式碼
宣告 `count` 、 `pending` 、 `list` ，其中 `list` 序列的第一位。並檢查序列內節點個數是否可排序，並將環狀鏈結頭尾，看成單向鏈結。
```c
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
head->prev->next = NULL;
}
```
使用 `tail` 來存取指向 `pending` 的指標
```c
size_t bits;
struct list_head **tail = &pending;
```
使用 `bits` 來找到 `count` 中為零的位元，並讓 `tail` 持續往前一位節點移動。
```c
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
使用 `likely(bits)` 成立時進行合併，`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;
}
```
在看這裡的時候一直有疑問，經過上面的 `for` 迴圈後，最後 `bits` 不是會為 0 嗎? 不就不會合併了
若以前面的表格來看 `count` 為 3、5、6、7 時，會進行合併，可是 3 和 7 時， `bits` 會為 0。
實際畫圖後和參考 [lab0(E)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e)後發現，在程式中，`count` 為 2、4、5、6 時，`bits` 在經過 `for` 迴圈後不為 0，會進行合併，才發現由於會在最後再將節點加入 `pending`，而非加入節點後再排序。
```c
do{
for {
...
}
if {
...
}
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
這時也理解，`for` 迴圈是用來計算需將 `tail` 往前幾位來進行合併。
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
當 `count` 為 5 時， `pending` 是指向第五個節點，此時進行合並會將 [5] 、[3 ,4] 進行合併。
```graphviz
digraph G {
rankdir=LR;
node[shape=none]
pd [label=pending]
tl [label = "*tail"]
subgraph n1 {
style=filled;
color=lightgrey;
node [shape=record color = blue];
hn1 [label="<head>1 | {<prev>prev | <next>next}"];
}
node [shape=record color = blue];
hn2 [label="<head>2 | {<prev>prev | <next>next}"];
subgraph n3 {
style=filled;
color=lightgrey;
node [shape=record color = red];
hn3 [label="<head>3 | {<prev>prev | <next>next}"];
}
subgraph n4 {
style=filled;
color=lightgrey;
node [shape=record color = red];
hn4 [label="<head>4 | {<prev>prev | <next>next}"];
}
subgraph n5 {
style=filled;
color=lightgrey;
node [shape=record color = black];
hn5 [label="<head>5 | {<prev>prev | <next>next}"];
}
hn1:next->hn2:head[color = blue]
hn3:prev->hn1:head[color = red]
hn3:next->hn4:head[color = red]
hn5:prev->hn3:head
pd->hn5
tl->hn5
}
```
經過 `for` 迴圈後，會令 `tail` 往前一位，指向節點 3 ，並將 [3, 4] 和 [1, 2] 合併。
```graphviz
digraph G {
rankdir=LR;
node[shape=none]
pd [label=pending]
tl [label = "*tail"]
subgraph n1 {
style=filled;
color=lightgrey;
node [shape=record color = blue];
hn1 [label="<head>1 | {<prev>prev | <next>next}"];
}
node [shape=record color = blue];
hn2 [label="<head>2 | {<prev>prev | <next>next}"];
subgraph n3 {
style=filled;
color=lightgrey;
node [shape=record color = red];
hn3 [label="<head>3 | {<prev>prev | <next>next}"];
}
subgraph n4 {
style=filled;
color=lightgrey;
node [shape=record color = red];
hn4 [label="<head>4 | {<prev>prev | <next>next}"];
}
subgraph n5 {
style=filled;
color=lightgrey;
node [shape=record color = black];
hn5 [label="<head>5 | {<prev>prev | <next>next}"];
}
hn1:next->hn2:head[color = blue]
hn3:prev->hn1:head[color = red]
hn3:next->hn4:head[color = red]
hn5:prev->hn3:head
pd->hn5
tl->hn3
}
```
當 `list` 中的節點都進到 `pending` 後，則會跳離迴圈，將剩餘的節點合併。
```c
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
跳離這個迴圈時，會剩餘 `list` 和 `pending` 兩串列尚未合併，呼叫 `merge_final` 進行
1. 兩串列合併
2. 接回 `head`
3. 將 `prev` 連接上前一位節點，完成環狀雙向鏈結
```c
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
...
merge_final(priv, cmp, head, pending, list);
}
```
### 將 list_sort 引入 lab0
將上述的函式加入 `lab0` 中，並定義巨集 `likely` 和 `unlikely` ，使用 `strcmp` 來完成 `cmp`。
> [commit](https://github.com/sysprog21/lab0-c/commit/397d1a40d6eb468e32cc0873e230d776ffc7e82e)
### 比較效能
## 相關 git 操作
使用 `git log --oneline` 查看先前 `commit` 的紀錄
```shell
git log --oneline
```
使用 `git rebase -i <commit>` 決定要修改哪些 `commit`
### 引入 [tic-tac-toe](https://github.com/jserv/ttt)
預先設置會是使用 [negamax AI](https://en.wikipedia.org/wiki/Negamax) 進行對羿，而 negamax 是 [minimax](https://en.wikipedia.org/wiki/Minimax) 的一種變形。
當在進行對局時，會下對於對自己勝率最大的位置，同時，這步對於對手來說，是最壞的情況;而對手同樣也會下對自己勝率最大的位置，對我們而言，就是最壞的情況。
圖來自[網站](https://programmermagazine.github.io/201407/htm/focus3.html)
而節點更新須考慮三個情況，我方下、對方下、終端節點。當輪到我方時，則須選擇勝利最大化
```c
if maximizingPlayer
bestValue := -∞
for each child of node
val := minimax(child, depth - 1, FALSE))
bestValue := max(bestValue, val);
return bestValue
```
輪到對方下時，則選擇其勝利最小化(我方最大化)
```c
else
bestValue := +∞
for each child of node
val := minimax(child, depth - 1, TRUE))
bestValue := min(bestValue, val);
return bestValue
```
而為終端節點時，代表有其中一方勝利
```c
if depth = 0 or node is a terminal node
return the heuristic value of node
```
negamax 則簡化了此計算過程，透過 $max(a,b) = -min(-a,-b)$來計算每個節點的權重，而最後只要找出最大值即可。
### 顯示時間
在 [`time.h`](https://man7.org/linux/man-pages/man0/time.h.0p.html) 可引用時間的函式庫，使用 `struct tm *localtime()` 可獲取當下時間，並選擇對應的表示方式顯示。
```clike
struct tm date = *localtime(&t);
printf(" %d /%d /%d %d:%d:%d\n",date.tm_year + 1900,date.tm_mon + 1,date.tm_mday,date.tm_hour,date.tm_min,date.tm_sec);
```
便可依照格式顯示當下時間和秒數
```
kkkkk1109@kkkkk1109-GF65-Thin-10UE:~/lab0-c$ ./time_test
2024 /9 /1 15:39:49
```
:::info
加入 ttt 但只有在下棋時會更新時間
:::
Sign in with Wallet
Connect another wallet