# 2024q1 Homework1 (lab0)
contributed by < `vax-r` >
### Reviewed by `Vincent550102`
1. 將多個實作細節分別提交為獨立的，以便未來的追蹤與 rebase 操作更加便捷與清晰。
> commit [41264c5](https://github.com/vax-r/lab0-c/commit/41264c5acf292b0d0cc6501911c30f5530a1da41)
:::warning
> [name=I-HSIN Cheng]
> 針對您的 review ，我的回覆如下
> 感謝您建議要做的改進，確實是我在提交 commit 偷懶的結果，為了養成良好的習慣您提出的改動是必要。
:::
### Reviewed by `weihsinyeh`
1. 在開發紀錄中問很多問題，讓讀者也很想思考。
2. 閱讀 commit b5c56e0 提及的三篇論文的部份剛好跟我的理解相反，可以解釋是如何思考的，這樣可以讓讀者更清楚明白。
3. Massif-Visualizer 視覺化記憶體成圖片。
4. 有時候忘記句號或問號。缺點就是會以為下面那段程式碼跟這句話有關連。像是以下敘述、如下就可以不用句號，但像「也正是此作業測試 constant time implementation 的方法」就可以加句號。
:::warning
> [name=I-HSIN Cheng]
> 針對您的 review ，我的回覆如下
> 1. 這三篇論文我只有閱讀其中兩篇並且沒有理解完整，待我完成閱讀並理解後會再重新思考該 `list_sort` 實作的優勢與劣勢，並參照您的筆記，感謝您提出這點。
> 2. 我的電腦無法安裝 Massif-visualizer
> 3. 感謝提醒，標點符號是我很大的問題我會進行改進。
:::
### Reviewed by `vestata`
1. 實作速度迅速，開發紀錄完整豐富，非常值得參考。
2. 在實作 `shuffle` 命令的部份，我是依照 [Fisher–Yates shuffle wiki](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Pencil-and-paper_method) 採用 `pick` 從前面開始選取，測試結果是正常的。此開發紀錄針對從後面選 `pick` 沒有解釋。
3. 針對 比較 timsort 與 list_sort 有完善的測試場景，值得參考。關於比較結果可以表格整理方便檢閱，而非直接貼上結果。
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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
Address sizes: 36 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
CPU family: 6
Model: 42
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 7
CPU max MHz: 3800.0000
CPU min MHz: 1600.0000
BogoMIPS: 6800.09
```
## 原始檔個別作用
再開始實作程式碼之前，清楚閱讀作業要求並理解整個專案架構應該是第一步，此專案底下有許多的 C 程式和標頭檔，以下逐個解說他們的用途
* `console.[ch]` : Implementation of Command line Interface
* `harness.[ch]` : (To be edited)
* `linenoise.[ch]` : Command-line Auto-complete (We shouldn't be bothered by it)
* `list.h` : Linux-like doubly-linked list implementation
* `log2_lshift16.h` : (To be edited)
* `qtest.c` : Implementation of testing code
* `queue.[ch]` : Queue Implemenation
* `random.[ch]` : (To be edited)
* `report.[ch]` : Reports of errors
* `shannon_entropy.c` : (To be edited)
* `web.[ch]` : (To be edited)
首先我們實作 `queue.c` 當中的程式碼並嘗試通過 `make test`
## 實作指定佇列操作
仔細閱讀 C Programming Lab 後，原先程式要求是以鏈結串列所實作一個存放 strings 的佇列，然而我們的作業要求是實作 *a chain of circular queues* ，並非單純一個queue，而是被鏈結串列所串連在一起的多個環狀佇列。
本作業第一個要求是完成 lab0-c 當中的程式碼並通過 `make test` 之所有測試，通過測驗前先理解題目測驗方式非常重要，所以我先閱讀 `Makefile` 以了解整理專案架構還有 `make test` 所執行之指令。
可以發現 `make test` 利用 `scripts/driver.py` 來測試我們的程式實作，實際理解 `driver.py` 之行為後不難發現, 它就是將 `scripts/traces` 底下的 `.cmd` 檔案當作程式的測試資料，總共有 17 項測試要通過，我們逐步實作並改進 <s>優化</s> 每個函式。
同時所有 `struct list_head` 之操作都應該參考 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)，並且注意所有操作都應該盡量 **in-place**
### `q_new`
`qtest.c` 當中只有 `do_new()` 函式會呼叫 `q_new()`，可以發現在呼叫的時候已經幫我們配置好 `queue_context_t` 結構，我們需要做的是配置一個 `struct list_head` 並回傳，如果配置失敗則回傳 `NULL`
我的第一個問題是，到底什麼是 `NULL` ? pointer是指向某個記憶體位址，`NULL` 以直覺來說是虛無，不存在的意思，但電腦當中哪裡是所謂虛無，不存在的記憶體位址? 我參閱 C11 規格書可以發現以下敘述
> An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.66) If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.
另外還有提到
> The macro NULL is defined in <stddef.h> (and other headers) as a null pointer constant;
也就是我們所認知的 null 其實在 C 語言當中是被分為 null pointer constant 還有 null pointer 等等
我們這裡提到的 `NULL` 是一個 null pointer constant 的 macro
實作此函式時原先利用 `calloc` 來配置記憶體給 `struct list_head` ，不過經過 `make check` 後會出現以下錯誤訊息
```shell
ERROR: Attempted to free unallocated block. Address = 0x559d85e60f70
ERROR: Attempted to free unallocated or corrupted block. Address = 0x559d85e60f70
Segmentation fault occurred. You dereferenced a NULL or invalid pointermake: *** [Makefile:57: check] Aborted (core dumped)
```
之後將程式碼經過以下修改後通過檢測，仍需進一步探討 `calloc` 和 `malloc` 除了 `calloc` 會將配置的記憶體區段做初始化以外還有哪些差異
```diff
struct list_head *q_new()
{
- struct list_head *new_qhead = calloc(1, sizeof(struct list_head));
+ struct list_head *new_qhead = malloc(sizeof(struct list_head));
```
仔細閱讀 [malloc(3)](https://man7.org/linux/man-pages/man3/malloc.3.html) 後， `calloc` 和 `malloc` 差異在 `calloc` 會檢查 integer overflow ，除此之外配置記憶體方式是一樣的，所以理論上不應該出現錯誤，詳細檢查後原來是在 `q_remove_head, q_remove_tail` 之後，`./qtest.c` 利用 `q_release_element` 來釋放記憶體空間，但是 `q_release_element` 的實作直接引入 `test_free` 而非利用 `free` ，造成若沒有使用指定的 `test_malloc, test_calloc` 來配置記憶體空間，則 `test_free` 時檢查一定會出錯。
因此我本想改寫 `q_release_element` 使得函式內部呼叫 `free` 而非 `test_free` ，我本來認為在編譯時會因 `harness.h` 的巨集而使 `free` 被展開成 `test_free`，如下
```diff
static inline void q_release_element(element_t *e)
{
- test_free(e->value);
- test_free(e);
+ free(e->value);
+ free(e);
}
```
但這樣的程式碼經過編譯執行後會產生以下錯誤
```shell
$ ./qtest
cmd> new
l = []
cmd> ih apple
l = [apple]
cmd> rh apple
munmap_chunk(): invalid pointer
Aborted (core dumped)
```
利用 gdb 測試後發現 `q_release_element` 當中的 `free` 並不會因為 function hooking 的機制而展開成 `test_free` ，反而是變成錯誤版本的 `free` 。
我思考是否因為 `static inline` 的關係使得巨集無法產生作用？但我發現我連 `static` 還有 `inline` 放在函式前面具體會產生什麼作用都不了解，於是我查閱規格書 C99 來學習 `static` 和 `inline` 分別代表什麼，放在一起又會產生什麼效果。
`static` 除了表示 storage duration 以外，作為函式的 storage-class specifier ，代表該函式具有 internal linkage 。
`inline` 同樣也是 function specifier ，代表該函式的呼叫應該越快越好。
**C99 (6.2.2.3)**
> If the declaration of a file scope identifier for an object or a function contains the storageclass specifier static, the identifier has internal linkage.
**C99 (6.7.4.6)**
> Any function with internal linkage can be an inline function
**C99 (6.7.4.5)**
> A function declared with an inline function specifier is an inline function. The function specifier may appear more than once; the behavior is the same as if it appeared only once. Making a function an inline function suggests that calls to the function be as fast as possible.
**C99 (6.2.2.2)**
> In the set of translation units and libraries that constitutes an entire program, each declaration of a particular identifier with external linkage denotes the same object or function. **Within one translation unit, each declaration of an identifier with internal linkage denotes the same object or function.** Each declaration of an identifier with no linkage denotes a unique entity.
**Translation Unit**
(From C99 (5.1.1.1))
> A source file together with all the headers and source files included via the preprocessing directive #include is known as a preprocessing translation unit. After preprocessing, a preprocessing translation unit is called a translation unit.
### `q_insert_head` / `q_insert_tail`
> [commit 8ccdf1b](https://github.com/vax-r/lab0-c/commit/8ccdf1b68428059a173de5416e481677098491d5)
實作這兩個函式時，原先我利用 `calloc` 來配置新的記憶體區段給 `element_t` 使用，並且使用 `strncpy` 來配置記憶體空間給需要複製的字串，不過如此一來會造成和上述 `q_new()` 相同的記憶體錯誤，經過以下修改後得以通過檢測，不過仍需進一步探討 `strcpy` 和 `strncpy` 兩個看似只差在有沒有限制複製字元數的函式，底下配置記憶體之方式有何處不同
```diff
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
- element_t *new_ele = calloc(1, sizeof(element_t));
+ element_t *new_ele = malloc(sizeof(element_t));
if (!new_ele)
return false;
INIT_LIST_HEAD(&new_ele->list);
- new_ele->value = strndup(s, strlen(s))
+ new_ele->value = strdup(s);
```
### `q_free`
在實作此函式時發現進行 `make test` 後會顯示錯誤訊息。
經過上述修正 `q_new`, `q_insert_head` 和 `q_insert_tail` 後得以通過 `make test`
### `q_delete_mid`
此題對應 [Leetcode 2095](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) ，作法有數種，先前我使用快慢指標的方法在 leetcode 平台上解題，不過此處我避免 `cur->next->next` 此類的操作，因此我採用讓兩個指標朝相反方向行走， `first` 不斷朝自身的 `next` 方向行走， `second` 不斷朝自身 `prev` 方向行走，當兩個 pointer 交匯之前即停止，此時 `first` 指向的 `struct list_head` 即是我們應該刪除的節點
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *first = head->next;
struct list_head *second = head->prev;
while((first != second) && (first->next != second)) {
first = first->next;
second = second->prev;
}
element_t *node = list_entry(first, element_t, list);
list_del(first);
free(node->value);
free(node);
return true;
}
```
**q_delete_dup**
此題對應到 [Leetcode 82](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) ，要將環狀佇列當中所有重複出現的元素節點刪除，只要重複就全部刪除不會將最後一個留下，原本我在 leetcode 當中的解法如下
```c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode *head){
if (!head || !head->next)
return head;
struct ListNode *pnode, *cnode, *nnode;
pnode = NULL;
cnode = head;
nnode = head->next;
while (nnode) {
if (cnode->val == nnode->val) {
nnode = nnode->next;
continue;
}
else if (cnode->next != nnode) {
if (cnode == head)
head = nnode;
else
pnode->next = nnode;
}
else {
pnode = cnode;
}
cnode = nnode;
nnode = cnode->next;
}
if (pnode && pnode->next != cnode)
return NULL;
return head;
}
```
透過 `cnode, nnode` 的元素比較來決定要刪除何者, 但在此作業中我採用較保守之方法，一個一個節點進行刪除，而非一次拔掉一整段串列，透過 `list_for_each_entry_safe` 並逐個檢查 `cur, tmp` 的 `value` 如果相同就把 `cur` 刪除
實作時本來認為 `list_del` 會跟著把嵌入被刪除之 `struct list_head` 結構體的 `element_t` 也跟著刪除，因此我先進行字串成員的刪除再進行 `list_del` ，但閱讀 `list.h` 當中對於 `list_del()` 的註解後看到 `list_del()` 的作用是 **remove** 而非 `delete` ，因此我做了對應的修正
:::info
> list_del() - Remove a list node from the list
不過在 [Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 中關於 `list_del` 的描述如下
> deletes entry from list.
:::
:::warning
太好了，你發現可以貢獻 Linux 核心的機會：澄清用語
> [name=I-HSIN Cheng] 感謝老師提醒，待完成作業後會嘗試提交 patch
:::
:::warning
已經嘗試提交 patch 給 linux kernel community
[patch](https://lkml.org/lkml/2024/3/11/1)
:::
```diff
/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
bool dup = false;
element_t *cur, *tmp;
list_for_each_entry_safe (cur, tmp, head, list) {
if (&tmp->list != head && !strcmp(cur->value, tmp->value)) {
- free(cur->value);
list_del(&cur->list);
+ free(cur->value);
+ free(cur);
dup = true;
} else if (dup) {
- free(cur->value);
list_del(&cur->list);
+ free(cur->value);
+ free(cur);
dup = false;
}
}
return true;
}
```
### `q_swap`
此題對應到 Leetcode 24 ，原本我的實作是使用 for 迴圈走訪整個佇列並對其中節點兩兩交換，為了維持 linux-style 的程式碼，我希望盡量利用 `list_for_each` 等函式或巨集，所以我進行以下的修改。
```diff
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
- for (first = head->next, second = head->next->next;
- first != head && second != head;
- first = first->next, second = first->next) {
+ struct list_head *first, *second;
+ list_for_each_safe (first, second, head) {
first->prev->next = second;
second->prev = first->prev;
first->next = second->next;
first->prev = second;
second->next->prev = first;
second->next = first;
}
}
```
然而上述程式碼會遇到若佇列當中的節點個數是奇數，則 `head` 也會被交換的情況發生，因此進行以下修正
```diff
list_for_each_safe (first, second, head) {
+ if (second == head)
+ break;
```
我認為若能在 `list.h` 當中新增 `list_swap` 實作，能改進程式碼的可讀性
```c
/**
* list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
* @entry1: the location to place entry2
* @entry2: the location to place entry1
*/
static inline void list_swap(struct list_head *entry1,
struct list_head *entry2)
{
struct list_head *pos = entry2->prev;
list_del(entry2);
list_replace(entry1, entry2);
if (pos == entry1)
pos = entry2;
list_add(entry1, pos);
}
```
:::warning
若你留意 Linux 核心原始程式碼，使用到 `<linux/list.h>` 的程式碼往往更善於使用 `list_splice` 及其相關函式，避免只交換二個節點，你可以思考為何如此。
:::
### `q_reverseK`
此題解法有數種，我採用的方法如下，預先配置一個新的 `struct list_head` `new_head` , 每次從原本 `head` 所指向的環形雙向佇列取下 k 個 node 並進行反轉之後放到 `new_head` 後面，總共進行 `times` 次。我認為可以改進的部分有以下幾點
* 計算要拔取的區塊方式目前採用 `int times = q_size(head) / k` , 是否有不使用除法的方式來計算?
* 每次透過 `list_for_each` 並輔以 `j` 來找尋第 k 個 node 的做法使得程式碼顯得不優雅並且可讀性不佳
* `list_cut_position` 在 [Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 當中清楚提及， `list` 也就是以下的 `tmp` ， **list should be an empty list or a list you do not care about losing its data.**
但此處明顯的我們配置的 `tmp` 是用來當作每 k 個節點的 linked list 的暫存 head ，我們明顯 **care about losing its data or not** ，或許有其他 macro 或實作可以更安全地確保 `tmp` 的資料不會流失
```c
/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head)
return;
int times = q_size(head) / k;
struct list_head *tail;
LIST_HEAD(tmp);
LIST_HEAD(new_head);
for (int i=0; i < times; i++) {
int j = 0;
list_for_each(tail, head) {
if (j >= k)
break;
j++;
}
list_cut_position(&tmp, head, tail->prev);
q_reverse(&tmp);
list_splice_tail_init(&tmp, &new_head);
}
list_splice_init(&new_head, head);
}
```
### `q_sort`
此處 sorting 的方法我參考〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)〉當中非遞迴版本的 mergesort ，值得注意的是處理排序過程我是把鏈結串列當成單向鍵結串列而非原本的環形佇列來處理，因此最後在 `q_sort` 函式中應該將排序好的鍵結串列進行處理，重新建構成環形佇列
:::warning
思考如何利用環形佇列的角度直接進行 merge sort ， linux-style 的鍵結串列有 `head` 這個特殊節點幫我們判斷鍵結串列的起點，可以不需要把環形佇列結構拆開，利用 `head` 來幫助判斷即可
:::
之後進行 `scripts/traces/trace-15-perf.cmd` 的測試中，上述非遞迴版本的 merge sort 將每個節點逐一合併速度太慢，決定先採用遞迴版本作法，修改如下
```diff
if (!head || !head->next)
return head;
- struct list_head *result = NULL;
- struct list_head *stack[1000];
- int top = 0;
- stack[top++] = head;
+ struct list_head *first = head;
+ struct list_head *last = head->prev;
- while (top) {
- struct list_head *left = stack[--top];
-
- if (left) {
- struct list_head *slow = left;
- struct list_head *fast;
-
- for (fast = left->next; fast && fast->next; fast = fast->next->next)
- slow = slow->next;
- struct list_head *right = slow->next;
- slow->next = NULL; /* Split the list into two */
-
- stack[top++] = left;
- stack[top++] = right;
- } else {
- result = mergeTwolists(result, stack[--top]);
- }
+ while (first != last && first->next != last) {
+ first = first->next;
+ last = last->prev;
}
- return result;
+ struct list_head *l1 = head;
+ struct list_head *l2 = first->next;
+ l2->prev = head->prev;
+ l1->prev = first;
+ first->next = NULL;
+
+ return mergeTwolists(mergesort(l1), mergesort(l2));
}
```
:::warning
先前學過關於 Tail-Call-Recursion 的知識，此處雖然做出遞迴呼叫的程式碼也在最後一行，但是當成傳入函式的參數來使用，並且呼叫了兩次，不確定這樣的做法是否有利用到 Tail-Call-Recursion ，應該進一步探討
> 關鍵在於用 stack 模擬遞迴操作的成本較高 :notes: jserv
:::
**q_ascend / q_descend**
參考 [Leetcode solution](https://leetcode.com/problems/remove-nodes-from-linked-list/solutions/4152665/beats-99-using-iterative-approach/)
由於原題當中使用的鍵結串列是 linear singly linked list , 所以在 function 開頭要先 reverse , 不過我們的 queue 都是 circular doubly linked list , 所以只需要將走訪的方向從 `next` 變為 `prev` 即可
我認為若能引進 `list_for_each_entry_safe_reverse` , 可以更有效並安全的完成此函式的要求
```c
/* Remove every node which has a node with a strictly less value anywhere to
* the right side of it */
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
element_t *right = list_entry(head->prev, element_t, list);
element_t *left = list_entry(head->prev->prev, element_t, list);
while (&left->list != head) {
if (strcmp(right->value, left->value) > 0) {
left = list_entry(left->list.prev, element_t, list);
right = list_entry(right->list.prev, element_t, list);
} else {
list_del(&left->list);
free(left->value);
free(left);
left = list_entry(right->list.prev, element_t, list);
}
}
return q_size(head);
}
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
element_t *right = list_entry(head->prev, element_t, list);
element_t *left = list_entry(head->prev->prev, element_t, list);
while (&left->list != head) {
if (strcmp(right->value, left->value) < 0) {
left = list_entry(left->list.prev, element_t, list);
right = list_entry(right->list.prev, element_t, list);
} else {
list_del(&left->list);
free(left->value);
free(left);
left = list_entry(right->list.prev, element_t, list);
}
}
return q_size(head);
}
```
### `q_merge`
此 function 的作用是將所有連結在一起的 circular linked list 合併到第一個 entry 當中 , 而剩下所有的 list_head 也應該被重新初始化確保他們是空的, 此處邏輯和 `q_sort` 使用的 merge sort 一樣, 只是只需要合併的過程, 原本想利用 `mergeTwolists` 直接實作 , 但是這題的情況不涉及鍵結串列的分割, 直接傳入 circular linked list 的第一個 `struct list_head` 結構來進行合併即可
因此以相同邏輯撰寫一個 helper function `__merge`
```c
/* Helper function for q_merge(), merge two lists together */
int __merge(struct list_head *l1, struct list_head *l2)
{
if (!l1 || !l2)
return 0;
LIST_HEAD(tmp_head);
while (!list_empty(l1) && !list_empty(l2)) {
element_t *ele_1 = list_first_entry(l1, element_t, list);
element_t *ele_2 = list_first_entry(l2, element_t, list);
element_t *ele_min =
strcmp(ele_1->value, ele_2->value) < 0 ? ele_1 : ele_2;
list_move_tail(&ele_min->list, &tmp_head);
}
list_splice_tail_init(l1, &tmp_head);
list_splice_tail_init(l2, &tmp_head);
list_splice(&tmp_head, l1);
return q_size(l1);
}
```
---
## 研讀論文〈Dude, is my code constant time?〉
此論文討論到許多在理論時間複雜度上看似 constant time 的實作卻存在 timing leakage ，造成資安上的漏洞，作者採用 Student's t test 當中的 Two-sample t-tests 來進行實驗測試，嘗試在不用模擬硬體的情況下做出可以偵測 timing leackage 的工具 deduct。
首先此論文對於每種*看似* constant time 的演算法實作進行測試的時候分別利用兩組測資，一組是固定測資（全部固定為某個值），另一組則是隨機測資，這樣的測試稱為 fix-vs-random tests ，並且整個實驗建立在一個假設底下，稱為 null assumption
**null assumption**
直觀的闡述如論文中所述，可以解釋為 "the two timing distributions are equal" ，研究 two samples t-tests 的 null hypothesis 則是提到兩組測資產生的結果分佈的平均值應該相等，更嚴格的說兩組結果的變異數 (variance) 也應該相等。
套用 null assumption 的 Student's t-test 也被稱為 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) ，也正是此作業測試 constant time implementation 的方法
論文當中提到一個經典例子是字串比較（應用於對應密碼），常見做法是一個一個字元比較若找到不相符的字元則直接回傳 false ，此做法會造成 timing leakage ，其中一個對應的解決辦法是不管有沒有找到不相符的字元都會檢查到最後一個字元，如此一來就能較好的避免 timing leakage
### 解釋 simulation 做法
在 `./qtest.c` 當中 simulation 若被設為1，則會對 `queue_insert` 以及 `queue_remove` 進行檢查來確認他們是否符合 constant time
觀察程式可以發現檢查 `q_insert_head` 是否符合 constant time 實作的函式是 `is_insert_head_const()` ，但是怎麼找都找不到 `is_insert_head_const()` 的函式定義，原來是我對 C 語言貧乏的了解使我沒有看到原來 `is_insert_head_const(), is_insert_tail_const(), is_remove_head_const(), is_remove_tail_const()` 全都是使用一個優雅的函式介面，定義在 `dudect/fixture.h` 當中
其中 `##` operator 的意思可以參閱 C11 規格書
> If, in the replacement list of a function-like macro, a parameter is immediately preceded or followed by a ## preprocessing token, the parameter is replaced by the corresponding argument’s preprocessing token sequence;
不過我在進一步閱讀此函式介面，發現來源是從 `./dudect/constant.h` 當中的巨集開始，而我無法理解此處巨集應用的意思，於是我先去閱讀 [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor) ，利用 `gcc -E -P` 來觀察這些巨集展開後的程式碼
以 `./dudect/constant.h` 當中這段巨集的程式碼為例
```c
#define DUT_FUNCS \
_(insert_head) \
_(insert_tail) \
_(remove_head) \
_(remove_tail)
#define DUT(x) DUT_##x
enum {
#define _(x) DUT(x),
DUT_FUNCS
#undef _
};
```
透過 `gcc -E -P` 層層解析 ， `DUT_FUNCS` 會展開成以下程式碼
```c
_(insert_head) _(insert_tail) _(remove_head) _(remove_tail)
```
經過 `#deinfe _(x) DUT(x),` 的處理後會變成
```c
DUT(insert_head), DUT(insert_tail), DUT(remove_head), DUT(remove_tail),
```
而 `DUT(x)` 也是一個巨集，於是將以上程式碼轉化成
```c
DUT_insert_head, DUT_insert_tail, DUT_remove_head, DUT_remove_tail,
```
所以最後 `enum` 當中包含的成員就會是
```c
enum {
DUT_insert_head, DUT_insert_tail, DUT_remove_head, DUT_remove_tail,
};
```
`dudect/fixture.h` 當中實際定義了四個函式原型
```c
bool is_insert_head_const(void);
bool is_insert_tail_const(void);
bool is_remove_head_const(void);
bool is_remove_tail_const(void);
```
`dudect/fixture.c` 當中則寫了函式的實作
```c
bool is_insert_head_const(void) { return test_const("insert_head", DUT(insert_head)); }
bool is_insert_tail_const(void) { return test_const("insert_tail", DUT(insert_tail)); }
bool is_remove_head_const(void) { return test_const("remove_head", DUT(remove_head)); }
bool is_remove_tail_const(void) { return test_const("remove_tail", DUT(remove_tail)); }
```
實際執行測試 constant time 的函式為 `doit` ，在閱讀 [dudect](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 的原始碼後，我認為 `doit` 對應到 dudect 的 [`dudect_main`](https://github.com/oreparaz/dudect/blob/a18fdee2386b63466502e9cb273cb14226679b4b/src/dudect.h#L419) ，而在 `dudect_main` 當中論文作者會將測量後的第一批結果丟棄，包括在 `update_statistics` 當中也是
相較於此作業的 `update_statistics` ， dudect 的 `update_statistics` 的 `for` 迴圈是從 10 開始進行 t value 的計算，而非 0
於是我將 `./dudect/fixture.c` 當中的 `update_statistics` 修改如下
```diff
static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
- for (size_t i = 0; i < N_MEASURES; i++) {
+ for (size_t i = 10; i < N_MEASURES; i++) {
```
另外 `dudect_main` 當中再呼叫 `update_statistics` 之前會先呼叫 `prepare_percentile` 函式，目的是要為每次 cropping measurements 設置不同的 threshold ，我不了解原因，可能還需重新研讀論文。並且我注意到在 dudect 的 examples 當中，每種不同的實驗的 `number_measurements` 也就是量測次數有非常大的差異，應該探討設置不同的測量次數之意義。
目前我依照 dudect 完成了對應的 `prepare_percentile` 實作並成功通過 `traces/trace-17-complexity.cmd` 測試
```c
static int cmp(const int64_t *a, const int64_t *b) { return (int)(*a - *b); }
static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
size_t array_position = (size_t)((double)size * (double)which);
assert(array_position < size);
return a_sorted[array_position];
}
/*
set different thresholds for cropping measurements.
the exponential tendency is meant to approximately match
the measurements distribution, but there's not more science
than that.
Reference : https://github.com/oreparaz/dudect/blob/master/src/dudect.h
*/
static void prepare_percentiles(int64_t *exec_times) {
qsort(exec_times, N_MEASURES, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < N_MEASURES; i++) {
exec_times[i] = percentile(exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / N_MEASURES)), N_MEASURES);
}
}
```
但按照論文的內容，我認為我對於 `q_insert_head, q_insert_tail, q_remove_head, q_remove_tail` 的實作都並非 constant time 實作，因為牽涉過多的分支處理，遇到記憶體配置失敗就會立刻結束函式，尤其是當 `q_insert_head`, `q_insert_tail` 在分配 `element_t` 的空間就失敗時，時間肯定和成功配置有十分顯著的差異，因為牽涉到是否呼叫 `strdup` 。
應該進一步探討何時會引發記憶體配置失敗還有各種記憶體缺失問題。
:::warning
TODO: 預先配置記憶體在 [memory pool](https://en.wikipedia.org/wiki/Memory_pool)，並搭配 [TLSF](http://www.gii.upv.es/tlsf/main/docs.html) 一類的演算法來管理記憶體配置。
:::
### 解釋 Student's t-distribution
Student's t-distribution ，又稱為 t distribution ， $t_v$ ，它是一個連續的機率分佈函數， Normal Distribution 可以稱作是 t distribution 的一個特例。
$t_v$ 的分佈型態由參數 $v$ 決定， $v = 1$ 時 $t_v$ 就是 standard Cauchy distribution ，當 $v \rightarrow \infty$ 時， $t_v$ 就變成 Normal distribution 。
在以數學的角度理解 t distribution 之前，我們需要先理解兩個概念
* Degrees of freedom
* Gamma function
[**Degrees of freedom 亂度**](https://en.wikipedia.org/wiki/Degrees_of_freedom_(statistics))
亂度的概念可以解釋為，量測某個參數的實驗中，獨立的量測數值個數減掉 intermediate steps 使用的參數個數。 例如量測 $N$ 個獨立點的變異數 variance ，獨立量測數值的個數為 $N$ ，而 intermediate step 使用的參數 (在這裡就是平均數) 只有一個，所以亂度為 $N-1$ 。
而事實上幾何意義上的亂度才真正定義了這個詞。 在幾何中， degree of freedom 代表某些特定向量子空間的維度，首先我們從 normal distributed 則資料中抽取 $n$ 筆資料，每次抽樣都是獨立的。
$X_1, \cdots, X_n$ ，這些樣本又可以表示成 n-dimentional random vector 如下
$\left(
\begin{array}{ccc}
X_1\\
\vdots\\
X_n\\
\end{array}
\right)$
因為此 random vector 可以出現在 n-dimensional space 當中任何地方，所以它的亂度是 $n$。
如果讓 $\overline{X}$ 表示這 n 筆樣本的 sample mean ，則此 random vector 可以被分解為以下的形式
$\left(
\begin{array}{ccc}
X_1\\
\vdots\\
X_n\\
\end{array}
\right) =
\overline{X}
\left(
\begin{array}{ccc}
1\\
\vdots\\
1\\
\end{array}
\right) +
\left(
\begin{array}{ccc}
X_1 - \overline{X}\\
\vdots\\
X_n - \overline{X}\\
\end{array}
\right)$
等號右手邊第二個向量是由 $\sum_{i=1}^n (X_i - \overline{X}) = 0$ 所定義的，前 n-1 個元素可以是任何數字，但是一旦前 n-1 個數字決定後，這個限制會決定第 n 個數字，因此這個向量的亂度是 n-1 。此向量又稱為 residual vector ，代表 least-squares projection onto the (n-1)-dimensional orthogonal complement of this subspace 。
同時上述向量的 residual sum-of-squares 為 $\sum_{i=1}^n (X_i - \overline{X})^2$
**Gamma function**
Gamma function $\Gamma$ 通常用來作為 factorial function 在 complex numbers 當中的延伸。不過由於亂度通常是正整數，此處就不做深入探討。 當 $n$ 為正整數時，$\Gamma(n) = (n-1)!$ 。
理解上述概念之後，回到正題也就是 Student's t-distribution ，如果用機率分佈函數來表示可以寫成下式
$f(t) = \cfrac{\Gamma(\cfrac{v+1}{2})}{\sqrt{\pi v} \Gamma(\cfrac{v}{2})} (1 + \cfrac{t^2}{v})^{-(v+1)/2}$
當 $v > 1$ 且為偶數時， $f(t) = \cfrac{(v-1)(v-3)\cdots 5\cdot 3}{2 \sqrt{v} (v-2)(v-4)\cdots 4\cdot 2} (1 + \cfrac{t^2}{v})^{-(v+1)/2}$
當 $v > 1$ 且為奇數時， $f(t) = \cfrac{(v-1)(v-3)\cdots 4\cdot 2}{2 \sqrt{v} (v-2)(v-4)\cdots 5\cdot 3} (1 + \cfrac{t^2}{v})^{-(v+1)/2}$
做圖後可以觀察到此機率分佈函數是對稱的，並且和平均數0變異數1的常態分佈長得很相似，並且隨著亂度 $v$ 越變越大， t distribution 的機率分佈函數會長得越來越像常態分佈 (mean = 0, variance = 1) ，因此 $v$ 也被稱為 normality parameter 。
---
## Valgrind + 自動測試程式
### Valgrind Intro
:::warning
**注意事項**
從 [The Valgrind Quick Start Guide](https://valgrind.org/docs/manual/quick-start.html#quick-start.intro) 得知，利用 Valgrind 當中的工具 Memcheck 檢查程式的記憶體問題時，盡量不要開啟編譯器優化，例如加上 `-O2` 進行編譯的話，可能會檢查到很多不存在的 uninitialised-value errors
另外 Valgrind 無法檢查所有種類的記憶體錯誤，以下引用自 [The Valgrind Quick Start Guide](https://valgrind.org/docs/manual/quick-start.html#quick-start.intro)
> For example, it can't detect out-of-range reads or writes to arrays that are allocated statically or on the stack.
:::
所謂的 DBA 全名是 Dynamic Binary Analysis ，而 DBI (Dynamic Binary Instrumentation) 則是實作 DBA 的一種方法，在執行的時候把做分析的程式碼加到被分析的程式碼當中
> **Instrumentation** 代表追蹤程式執行、診斷錯誤、衡量效能的能力
Valgrind 之所以強大（同時慢）的原因是它的實作著重在 **shadow value** 的概念上，並且它實作了完整的九種需求如下
1. 提供 shadow registers
2. 提供 shadow memory
3. instrument read/write instructions
4. instrument read/write system calls
5. instrument start-up allocations
6. instrument system call (de)allocations
7. instrument stack (de)allocations
8. instrument heap (de)allocations
9. transparent execution, but with extra output
以上九種需求的核心概念就是所有 register 和 memory 都要自己做一份並確保可以在各種情境下安全使用 (利用 multi-thread) ，我十分好奇 shadow value 的實作是如何達成的，是使用軟體模擬的方式還是做更多的記憶體配置？
另外 Valgrind 的運作方式是利用 dynamic binary re-compilation 把要檢查的 client 程式和 tool 的程式壓到同一個 process 當中並且共享資源 (此處也提醒我，尚未將 `fork() , clone()` 還有 linux 當中的 thread 、 process 搞清楚， man page 尚未閱讀完畢) ，這也造成 Valgrind 的複雜與困難
### Massif
參照 [Massif: a heap profiler](https://valgrind.org/docs/manual/ms-manual.html)
Massif 可以量測你的程式用了多少的 heap memory ，並有以下好處：
* 加速你的程式，小型的程式可以更好地利用電腦的快取並避免 paging
* 減少耗盡 swap space 的可能
而且可以偵測到一些傳統 leak-checkers 無法檢測之問題，例如某塊記憶體區段有指標指向它，但卻從沒使用到。
利用 `ms_print` 可以視覺化記憶體的用量，先在 `Makefile` 新增命令如下
```diff
+check-massif: qtest
+ valgrind --tool=massif ./$< -v 3 -f traces/trace-massif.cmd
+
```
其中 `traces/trace-massif.cmd` 的內容只要複製 `traces/trace-17-complexity.cmd` 並稍做修改即可，例如我想先測試 `q_insert_head`
```
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
option simulation 1
it
option simulation 0
```
:::warning
TODO: 使用圖片展現視覺化圖表
:::
進行 `make check-massif` 後可以獲得一個輸出檔案，通常會稱為 `massif.out.<pid>` ，之後利用 `ms_print` 可以輸出此檔案內容並提供一個視覺化的圖表告訴我們記憶體隨著程式執行的用量。
```shell
MB
1.233^#
|# ::
|# :: :
|# : :
|# : : :: :
|# : : : :
|# :: : : : : :
|# :: : : : : :
|# : :: :: : : : : : :
|# : :: :: : : : : : : :
|# : :: :: : : : : : :: : :: :
|# : :: :: :: : : :: : : : : : ::::
|# : :: : :: : ::: :: :: : : : : @@: :::@
|# : :: : : :: : : : : :: : ::: : : @ : :::@
|# :@@:::: : : : :: : : ::: :: : ::: : : @ : :::@
|# :@ : :: : : : :: : : ::: :: :: : ::: : : :: @ : :::@
|# :@ : :: : ::: ::: ::@@ :::: ::: :: :: : ::: :: : : :: @ : :::@
|# :@ : :: : : : :: ::@ ::: : ::: :: :: ::::::: : : : :: @ : :::@
|#:::@ : :: :@: : ::: ::@ ::: : ::: :: :: ::: ::: : : :::: @ : :::@
|#: :@ : :: :@: : ::: :::@ ::: : ::: :: :::::: ::::: : :::: @ : :::@
0 +----------------------------------------------------------------------->Gi
0 14.57
Number of snapshots: 56
Detailed snapshots: [1 (peak), 4, 10, 19, 48, 55]
```
以上的圖表顯示 Massif 對這個程式進行 56 次的 snapshot ，注意 massif 只有在 heap allocation/deallocation 才會做 snapshot ，並且分為三個類型
* `.` : normal snapshot
* `@` : detailed snapshot
* `#` : peak snapshot, only taken after a deallocation happens
**實驗：嘗試減少 heap memory 用量**
第一步我先將 `./qtest.c` 當中引入 `harness.h` 的程式碼註解掉，先測試利用原本的 `malloc` 和 `strdup` 的記憶體用量，並得出以下結果。
```shell
KB
637.3^#
|#
|# :
|# : : :
|# @ : : :: :
|# : @ @ : : :: : :
|# : @ @ : : :: : : :
|# :: : @ @ :: : :: : :::
|# :: : :@ @ :: : : : :: : :::
|# ::: : : :@ @ :: : : : :: : :::: :
|# ::: : : : :@ @ :: :: : : :: : :::: :
|# :::@ ::: : :@@:@ :@ :: :: :: : :: :: :::: :
|# :::@ ::: : :@ :@ :@:: :: : :: : :: : :: :: :::: :
|# : :::@ : ::: : :@ :@ :@: :: :::: : :: :::: :: @::: : :
|# : :::@ : :@::: : :@ :@ :@: :: :::: : :: ::::::: : @::: : :
|# : :::@ : :@::: : :@ :@::@: :: :::: :: :: ::::::::: @::: : ::
|# : :::@ :::@::: : :::::@ :@::@: ::: :::: :: ::@::::::::: @::::: ::
|# : :::@::::@::: : ::: :@ :@::@: ::: :::: :: ::@::::::::: @:::::: ::
|# :: :::@::::@::: ::::: :@ :@::@: :::@:::::::::::@:::::@:::: @:::::: ::
|#:::::::@::::@::: ::::: :@ :@::@: ::::@:::::::::::@:::::@:::::@:::::@:::
0 +----------------------------------------------------------------------->GB
0 2.870
Number of snapshots: 89
Detailed snapshots: [1 (peak), 9, 14, 25, 27, 30, 38, 53, 63, 73, 83]
```
觀察 peak snapshot 的詳細資訊，發現這次 snapshot 配置的 heap memory 達到 50.95% ，其中 `q_insert_head` 當中使用的 `malloc` 佔了 36.6% (239,088B)， `strdup` 佔了 12.07% (78,648B)。
之後引入 `harness.h` 當中的 `test_malloc, test_strdup` 等函式再重新執行一遍 `make check-massif` ，發現 heap memory 同樣會在前面的時間達到 peak ，分析較詳細的執行內容，發現同樣是 peak snapshot ，使用 `test_malloc` 卻使得 heap memory 用量來到87.56%，其中 `test_malloc` 就佔了86.41% ， `test_strdup` 也達到 37.01% 。
更仔細分析 `test_malloc` 使用 1,113,210B ， `q_insert_head` 的第 44 行原本使用 `malloc` 處也變成636,288B ，遠高於原本的 239, 088B。
並且 `test_strdup` 也用到了 476,754B ，遠高於原本的 78, 648B。
觀察 `harness.c` 當中程式碼，可以發現 `test_malloc` 的實作利用一個雙向鍵結串列的結構來記錄所有分配的記憶體，這樣紀錄的方式也增加了額外 heap memory 的開銷
### Linux signal
[signal(7)](https://man7.org/linux/man-pages/man7/signal.7.html) 中提及， signal 的行為是由 **signal disposition** 所決定，而當 signal 傳送後被接收到時， **signal handler** 則會執行對應函式。
signal disposition 是一個 per-process attribute ，分為以下五種
* **Term** : 預設行為是終止接收的 process
* **Ign** : 預設行為是忽略該 signal (signal 請其他process 忽略自己？ 那為何不要不發送 signal 就好？ 此處應該釐清)
* **Core** : 預設行為是終止該 process 並進行 [dump core](https://man7.org/linux/man-pages/man5/core.5.html) （也就是產生 core dump file）
* **Stop** : 預設行為是停止該 process
* **Cont** : 預設行為是將目前被停止的 process 繼續進行
:::warning
Ign 的情境與除錯器 / ptrace 有關，注意看手冊。
:::
通常 signal handler 被呼叫時 function stack 也會被放置在 normal process stack ，透過 [signalstack(2)](https://man7.org/linux/man-pages/man2/sigaltstack.2.html) 可以改變這樣的行為並把 function stack 放到不同的 stack 當中。
文中提及利用 [pause](https://man7.org/linux/man-pages/man2/pause.2.html) 、 [sigsuspend](https://man7.org/linux/man-pages/man2/sigsuspend.2.html) 等系統呼叫可停下 caller 並等待直到接收到一個 signal ，同時又提到透過 signal handler 接收 signal 的方式是非同步的 (asynchronously) ，而同步接收 signal 的方式則是阻擋目前的執行內容直到一個 signal 被傳送，那利用 [pause](https://man7.org/linux/man-pages/man2/pause.2.html) 、 [sigsuspend](https://man7.org/linux/man-pages/man2/sigsuspend.2.html) 停下等待 signal 的方式是否也是同步？
最有趣的部分我認為是 **signal mask** ，每個 process 當中的 thread 都有自己獨立的 signal mask ，用來代表該 thread 目前阻擋著的 signals 的集合。
此處引發我思考， linux 當中的 signal 又和 interrupt 有何不同？看上去功能有數個雷同之處，並且如果善用 signal 是否就能模擬 context switch？而且處理 signal 竟然也有分同步非同步的作法，我過往開發應用程式或網站後端撰寫 API 的經驗讓我想起，那些 API 跟此處的 signal handler 十分相似， 網路請求、封包則可以對應到 signal ，了解 linux kernel 如何高效的處理 signal 或許對於我後端開發能力能有進一步的提升。
:::warning
UNIX 的 signal 可以視為對底層硬體事件 (如中斷) 的可程式化包裝。
:::
---
## 整合網頁伺服器
:::info
這台電腦目前在實驗室中，只能透過 ssh 遠端連線操作，無法開啟網頁瀏覽器，待週間到實驗室再持續進行此部分。
> 請愛用 ssh port forwarding
:::
首先測試 `qtest` 當中的 `web` 指令是否能正常運作
```shell
cmd> web
listen on port 9999, fd is 3
```
接著打開另一個終端機，並輸入以下<s>指令</s> 命令：
```shell
$ curl 127.0.0.1:9999/new
l=[]
```
同時可以看到原先執行 `qtest` 的終端機也有對應輸出
```shell
cmd> l=[]
```
但此時若是開啟瀏覽器並在 url bar 輸入 `127.0.0.1:9999/`
則會出現以下訊息
```shell
$ ./qtest
cmd> web
listen on port 9999, fd is 3
cmd> Unknown command '.'
cmd> Unknown command 'favicon.ico'
```
同時正常來說，因為 `linenoise` 套件的幫助，可以幫我們在 console 完成命令的 autocomplete ，但要是開啟網頁瀏覽器，則此 autocomplete 功能會失靈。
:::warning
到此處我還不理解 `read` 阻塞時為何會造成 `linenoise` 套件無法執行，閱讀[作業說明(三)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-c) 時看到不懂之處（例如 `fd_set` )本想 Google 搜尋，但想到老師說需要的資料都在第一手開發資源例如 man page 等文件中，並且也都幫我們找好了，雖然內容很大量，但我決定收起偷懶的想法確實閱讀超連結當中的教材。果然一打開 [select(2)](https://man7.org/linux/man-pages/man2/select.2.html) 就看見關於 `FD_SET` 等我有疑問的內容。此處讓我更深體會到耐心閱讀看似乏味且[冗長](https://dict.revised.moe.edu.tw/dictView.jsp?ID=137180) <s>攏長</s>的 man page 以及開發者文件、規格書的重要性。
:::
命令列使用 `linenoise()` 的流程是在 `run_console()` 中的迴圈會呼叫 `linenoise() -> line_raw() -> line_edit()` ，其中 `line_raw()` 會傳遞 `STDIN_FILENO, STDOUT_FILENO` 進入 `line_edit()` 。查閱 [stdin(3)](https://man7.org/linux/man-pages/man3/stdout.3.html) ，可以敘述如下
> On program startup, the integer file descriptors associated with the streams stdin, stdout, and stderr are 0, 1, and 2, respectively. The preprocessor symbols STDIN_FILENO, STDOUT_FILENO, and STDERR_FILENO are defined with these values in <unistd.h>.
也就是 `STDIN_FILENO, STDOUT_FILENO` 實際上是 stdin, stdout 的 file descriptors ，分別為 `0, 1` ，此處也注意到函式 `enable_raw_mode()` 會將終端調整到 raw mode ，但什麼是 raw mode ?
研讀 [Entering raw mode](https://viewsourcecode.org/snaptoken/kilo/02.enteringRawMode.html) ，通常 STDIN_FILENO 此 file descriptor 都在 **canonical mode** ，必須按下 `ENTER` 才能使 `read` 讀取字元， raw mode 代表不需要按下 `ENTER` ，有輸入時 `read` 就會讀取。
再來觀察 `line_edit()` 程式碼，以下呼叫函式 `write()` 以達成在 terminal 顯示 `cmd>` 也就是 `prompt` 所包含之文字。
```c
if (write(l.ofd, prompt, l.plen) == -1)
return -1;
```
而程式碼當中的 `read` 則是用來讀取使用者輸入，一次讀一個字元進入 `c` 當中，而開啟瀏覽器時會造成 `linenoise` 套件被停止使用，指導教材提供建議要使用 [select(2)](https://man7.org/linux/man-pages/man2/select.2.html) 。
閱讀[作業說明：整合網頁伺服器](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-c) 還有 [tiny-web-server 程式碼](https://github.com/7890/tiny-web-server/blob/master/tiny.c)。
`listenfd` 對應到 `console.c` 當中的 `web_fd` 。
`open_listenfd` 對應到 `web.c` 當中的 `web_open` 。
`main` 則部分和 `do_web` 有關。
首先我發現 `web` 命令執行後， `linenoise` 套件會失效是因為 `do_web` 函式當中，如果成功開啟 web server 並監聽 port 9999 ， `use_linenoise` 變數會被設為 `false` ，如果強制將 `use_linenoise` 設為 `true` ，反而導致瀏覽器嘗試傳送請求給 web server 時會出現無限延遲。
一旦使用 `web` 命令後， `linenoise` 套件被關閉並且程式使用 `cmd_select` 來同時控制 command line input 和網頁瀏覽器請求。 若將 `linenoise` 函式強制引入 `cmd_select` 當中會發生什麼事呢？是否能順利讓 `linenoise` 套件運作？
```diff
- char *cmdline = readline();
+ char *cmdline = linenoise(prompt);
```
執行結果會發現，開啟 web server 之後 `linenoise` 套件會間隔性的能夠使用，而不能使用的時候就是 `line_edit` 當中的 `read` 被阻塞的時候。
### 整合網頁伺服器與 linenoise 套件
經過以上對於 `linenoise` 套件與網頁伺服器啟動時的測試後，我發現原本位於 `cmd_select` 當中的 `select()` 是用來同時監控 input file descriptor 和 web socket file descriptor ，若在這個 `select()` 被呼叫之前使用 `linenoise` 套件，會造成 web request 送入的 command 被阻塞在 `line_edit()` 當中。
若將 `linenoise()` 擺在 `select()` 之後才執行，也就是確認是 std input file descriptor 變為 ready 時才使用，則會導致我們必須按下兩次 Enter 按鍵才能正確執行一次命令，因為第一次 Enter 按鍵用來通知 `select()` 這個 fd 的狀態改變，第二次 Enter 按鍵則是用來跳出 `line_edit()` 函式。
因此我認為使用 `select()` 來同時監控 std input 和 web file descriptors 的時機會是在 `line_edit()` 函式當中，不管是 command-line 送入的命令或者是 web request 送入的命令，在 `cmd_select()` 處都先送入 `linenoise()` 函式當中並最後在 `line_edit()` 處以 `select()` 監控並判斷處理。我做的更改在以下的 commit 連結當中。
[Introduce eventmux callback function for linenoise](https://github.com/vax-r/lab0-c/commit/3d0777cf07b40cb542576aa8052c6364e8581185)
和 [作業說明](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-c) 不同之處有數點
* `cmd_select` 不再分開處理 web request 和 std input file descriptor ，一律送進 `linenoise()` 當中至 `line_edit()` 才以 `select()` 監控。
* 將處理不同 file descriptor 的函式實作在 `web.c` 當中並以 function hook 的方式註冊在 `linenoise` 套件當中並使用，以達成更模組化的程式碼也方便後人維護。
以上的變更也提交一個 [Pull Request](https://github.com/sysprog21/lab0-c/pull/162) 至 lab0-c 原本的 repository 當中。 code review 的過程更是深刻體驗到 code review 金字塔的實際意義，我在過往多數開發時間都只是在這個金字塔的最下層，也就是只求 correct ，剩下寫出優雅的程式碼、易維護、可重用等面向沒有考慮到也沒有能力考慮到，經過跟老師實際進行 code review 的過程才能體會到真的有強度的 code review 是如何進行以及該考慮的面向等等。
:::warning
TODO: 描述你的發現和變更
:::
以下闡述我的發現與變更
* **程式碼的優雅性與模組化** : 一開始我的實作是將實作於 `web.c` 當中的 `web_eventmux()` （原本命名不是這樣，以下再闡述）直接在 `linenoise` 當中進行呼叫。我原本認為將功能實作與不同套件中的函式即是一種模組化的呈現，不過老師告訴因為 `linenoise` 應該維持高度獨立所以不應該在程式碼當中呈現任何跟其他套件（例如 `web`）相關之內容，應該採用註冊 function hook 的作法將 `web.c` 當中所實作的函式引入 `linenoise` ，我發現這樣的寫法在未來在進行維護時會讓兩個套件更獨立，若變更 `web.c` 之內容，不會直接影響到 `linenoise` ，反之亦然，兩組套件之間不會在實作上高度相關。
* **命名的重要** ： 原本的實作中我依照 `cmd_select()` 的命名將新實作的函式命名為 `web_select()` ，但 `select()` 是一個函式的名稱，這樣的命名會讓之後維護的人無法一眼輕易理解函式的功能，老師在命名與 commit message 上細心的程度令我印象深刻，當下雖然覺得繁瑣，畢竟原先我認為這不是寫程式的重點，不過後來想，如果我是之後要來維護這段程式碼的人，而他的函式、變數命名不清， commit message 簡短帶過，那會讓我的工作時間大增僅僅是為了理解前人寫的模糊不清的程式碼，而非解決問題本身。相比到時候才搞懂所需花費的時間，現在由我這個第一手開發者盡量詳細的闡述 commit message 與細心易懂的命名，兩者時間相比我所花的時間根本不值一提，是非常有價值的投資。
### select() with RIO
select() ，可以監控數個 file descriptors (有數量限制，只能在 `FD_SETSIZE` 以下)，等待直到某些 file descriptors 能夠在不被阻塞的情況下執行 I/O operations。
**fd_set**
一個用來表示 file descriptors 集合的結構體， `fd_set` 當中最多可以有 `FD_SETSIZE` 個 file descriptors 。
**File descriptor sets**
`select()` 最多可以監控三個 filie descripters 集合，分別對應到不同的事件。 並且應該注意在 `select()` 結束並 return 時，每個 file descriptros sets 的狀態都會被改變為 ready ，所以若在迴圈當中使用 `select()` ，必須確保集合在每次呼叫之前都被重新初始化。
File descriptors sets 可以利用以下巨集操作
* **`FD_ZERO()`** : remove all fd from set. 在初始化 fd set 的第一步應該使用。
* **`FD_SET()`** : adds `fd` to `set`.
* **`FD_CLR()`** : removes `fd` from `set`.
* **`FD_ISSET()`** : test if a file descriptor is still present in a set.
閱讀 [CS:APP Ch10](https://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 當中提到 system level I/O 對於建立一個高可用性並穩定的服務的重要性。 在某些情況下， `read(), write()` 傳送的 bytes 數量會比 application request 更少，此行為稱為 **short counts** ，有以下幾種情況會出現此行為。
* Encountering EOF on reads
* Reading text lines from a terminal
* Reading and writine network sockets
該章節示範的 RIO 套件提供以下兩種函式
* Unbuffered input and output functions
* Buffered input functions
---
## 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試改進
在閱讀程式碼時， `list_sort` 也是運用到了 pointer to pointer 的技巧，我發現此處我無法快速理解程式碼，我之前認為我已經了解 pointer to pointer 不就是一個可以消除例外的手法，我認為我已經理解它的使用方法，但顯然沒有，我依然不懂，所以我重新閱讀 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) ，並找出三題 leetcode 當中 linked list 相關題目來寫並嘗試利用 pointer to pointer 技巧。
首先我發現 pointer to pointer 之所以能看似消除 node is list head 這種特例情況的原因。先回想我們以往最熟悉的作法是使用 pointer to node 並且判斷透過移動該 pointer 尋找到對應的節點並對該節點做操作 (操作該節點當中的 pointer to next node 成員) ，由於我們實際操作的本體是節點本身，而指標有可能沒有指到節點，因此有特例產生。
此時我們若利用 pointer to pointer ，我們就是將操作的本體從節點本身，轉移到 pointer to node ，在以下所謂有品味的 `remove_list_node` 當中，與其說改變了目標前一個節點的 `next` 成員的指向，不如說我們直接更換了該節點的 `next` 成員。
```c
void remove_list_node(List *list, Node *target)
{
// The "indirect" pointer points to the *address*
// of the thing we'll update.
Node **indirect = &list->head;
// Walk the list, looking for the thing that
// points to the node we want to remove.
while (*indirect != target)
indirect = &(*indirect)->next;
*indirect = target->next;
}
```
更清楚的說，原本我們容易把 `remove_list_node` 這樣的操作想成，*把目標節點前一個節點的 `next` 成員重新指到目標節點的下一個節點*，這樣思考沒有錯不過不優雅，觀察上述程式碼，當我們把操作的本體從節點轉移到 pointer to node 身上時，因為 pointer to node 在以上的例子裡是所有節點都有的，因此不會有特例產生。
觀察 `lib/list_sort.c` 當中的函式 `merge` ，首先 `__attribute__((nonnull(2,3,4)))` 可以參照 [6.30 Declaring Attributes of Functions](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Function-Attributes.html) 的解說，意思很簡單就是表示這個函式的第 2, 3, 4 個參數不能是 null 。並且可以注意到函式的第一個參數 `priv` ，可以再 `/lib/test_list_sort.c` 當中看到 `priv` 是用來使得 `check` 這個函式經過 KUnit 測試後可以 failed 。
另外我認為如果能對 `merge` 進行以下改寫，能夠提升程式碼的可讀性，性能部分還需設計實驗測試。
```diff
- for (;;) {
+ for (; a && b;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
} else {
*tail = b;
tail = &b->next;
b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
}
}
+ *tail = (struct list_head *) ((uintptr_t) a | (uinptr_t) b);
```
`list_sort` 函式的註解當中詳細解釋了 `list_sort` 的運作方式，內容提到這個排序函式實際上是利用 merge sort 來進行排序並且它還提到
> This mergesort is as eager as possible while always performing at least 2:1 balanced merges.
另外在[第134行](https://github.com/torvalds/linux/blob/ab0a97cffa0bb3b529ca08b0caea772ddb3e0b5c/lib/list_sort.c#L134)提及了 `fully-eager bottom-up mergesort` ，什麼是 full-eager mergesort ? 我查閱許多資料皆找不到相關定義。
:::warning
該閱讀指定論文，而非訴諸 Google 搜尋。
:::
我認為此處 eager 的定義就是盡量執行 2:1 的 balanced merges ，給定兩個大小 $2^k$ 的 linked lists ，一但我們有另外 $2^k$ 個元素，則這兩個 linked lists 就會被合併成一個大小為 $2^{k+1}$ 的 linked list 。所以當 $3\cdot 2^k$ 個元素可以被放入 cache 當中的話就可以避免 cache thrashing ，這麼做在多數情況（所有資料都可以放入 L1 cache時）會表現得比較快。
`count` 代表在 pending lists 當中的元素數量。每次對兩個大小為 $2^k$ 的串列進行合併的時候，就會對 `count` 做增加的動作，也就是把 bit k 設為 1 然後把 bits k-1 .. 0 給清空為 0 。
merge 會在 `count` 達到 $2^k$ 的奇數倍時執行，也就是在較小的那個 pending list 大小剛好為 $2^k$ 時。 當這樣的 merge 發生兩次後我們會得到兩個大小為 $2^{k+1}$ 的鍵結串列，在出現第三個大小為 $2^{k+1}$ 的鍵結串列之前我們就會將這兩個鍵結串列再度合併為一個大小 $2^{k+2}$ 的鍵結串列，從而保證 pending lists 不會超過兩個。
大小為 $2^k$ 的鍵結串列之數量除了由 `count` 的第 k 個 bit 來決定以外，還要加上另外兩項資訊
1. The state of bit k-1 (when k == 0, consider bit -1 always set)
2. Whether the higher-order bits are zero or non-zero (i.e. is count >= 2^(k+1))
綜合以上敘述，總共有六種狀態需要區分。以下 `x` 代表一些隨機的 bits ，而 `y` 代表一些隨機的 non-zero bits 。
* 0. `00x` : 0 pending of size $2^k$, x pending of sizes < $2^k$
* 1. `01x` : 0 pending of size $2^k$, ($2^{k-1}$ + x) pending of sizes < $2^k$
* 2. `x10x` : 0 pending of size $2^k$, ($2^k$ + x) pending of sizes < $2^k$
* 3. `x11x` : 1 pending of size $2^k$, ($2^{k-1}$ + x) pending of size < $2^k$
* 4. `y00x` : 1 pending of size $2^k$, ($2^k$ + x) pending of sizes < $2^k$
* 5. `y01x` : 2 pending of size $2^k$, ($2^{k-1}$ + x) pending of sizes < $2^k$
從狀態2轉換到3或者從狀態4轉換到5都會獲得一個 list of size $2^k$ ，直得注意的是從 5轉換到2 之前 ( merge 之前)，所有的 lower-order bits 都是11，也代表每個較小 size 的串列都各有一個。
並且進行排序的時候有幾項 invariants
* all lists are singly linked and null-terminated; prev pointers aren't maintained.
* pending is a prev-linked "list of lists" of sorted sublists awating further merging.
* each of the sorted sublists is power-of-two in size.
* sublists are sorted by size and age, smallest and newest at front.
* There're 0 to 2 sublists of each size
* a pair of pending sublists are merged as soon as the number of following pending elements equals their size.
* each round consists of:
* merging the 2 sublists selected by the highest bit which flips when count is incremented
* adding an element from the input as a size 1 sublist
觀察程式碼與理解上述解說後，思考 `count` 是多少時才會進行 merge ，可以發現分為兩種情形：
* 目前 `count + 1` 為 2 的冪，則不合併
* 目前 `count + 1` 不為 2 的冪，則合併
### 引入 list_sort 到 lab0-c 當中
基於 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的基礎，我進行微調後實作並引入到 lab0-c 之程式碼當中。
> [commit 7ab64a2abcd66933cf23b0b015c3dfe3691e59e3](https://github.com/vax-r/lab0-c/commit/7ab64a2abcd66933cf23b0b015c3dfe3691e59e3)
* 去除 `priv` : 在 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 有提到， `priv` 對於排序本身並無作用，於是我在實作過程中去除 `priv`
* `u8` : 在[第 56 行](https://github.com/torvalds/linux/blob/d206a76d7d2726f3b096037f2079ce0bd3ba329b/lib/list_sort.c#L56) 可以看到 `count` 的型別為 `u8` ，實際查閱 linux kernel 文件得知這是一個針對不同硬體架構的延伸型態，多數為 `unsigned char` ，於是我在此處使用 `unsigned char` 來代替 `u8` 。
* `cmpfunc` 實作 ： 我參閱 [lib/test_list_sort.c](https://github.com/torvalds/linux/blob/master/lib/test_list_sort.c) 當中實作 `cmp` 函式的方法，此處因為是比較字串所以使用 `strcmp` 來進行比較，可以思考是否利用 `-` 來達成相同效果。
### 論文閱讀
閱讀 [commit b5c56e0](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 提及的三篇論文，紀錄在 [Mergesort 論文閱讀與見解](https://hackmd.io/@vax-r/mergesort-paper)，我認為 `list_sort` 更為接近 Queue Sort 但是稍有優化， Queue Sort 在每個 iteration 都會進行合併，而 `list_sort` 在 pending lists 的元素個數加一為二的冪時不會進行合併。
### 比較並改進 list_sort
首先對 `list_sort` 插入元素後進行 sort ，並計算 cpucycles ，進行五次取平均。
| num of elements | sorting algorithm | cpu cycles |
| -------- | -------- | -------- |
| 10000 | list_sort | 12741897.6 |
| 50000 | list_sort | 82460294.8 |
| 100000 | list_sort | 196961467.6 |
接下來對原本的 merge sort based qsort 進行測試。
| num of elements | sorting algorithm | cpu cycles |
| -------- | -------- | -------- |
| 10000 | merge_sort | 15771425.2 |
| 50000 | merge_sort | 61703857.2 |
| 100000 | merge_sort | 185685734.6 |
在 50000 和 100000 的情況下 merge sort 居然比 `list_sort` 使用更少的 cpucycles ，需要更深的探討，實驗設計可能有問題。
:::warning
未能充分考慮資料的分佈。
:::
## 實作 `shuffle` 命令
### 實作 Fisher-Yates shuffle Algorithm
參見 [commit bc7211f029b65d0ee3521fc5737f07deaeef1c91](https://github.com/vax-r/lab0-c/commit/bc7211f029b65d0ee3521fc5737f07deaeef1c91)
我的做法是參考 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 當中的 `list_for_each_prev_safe` ，從最後一個節點反向走訪，並且 `pos` 代表最後一個未被抽到的節點， `pick` 則是從前面數來第 `r` 個節點，最後將 `pos` 和 `pick` 交換。
然而實際執行時會發現產生的序列排列結果十分固定，參考 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023#%E5%9C%A8-qtest-%E6%96%B0%E5%A2%9E-shuffle-%E5%91%BD%E4%BB%A4) 發現 `pick` 應該從 `pos` 開始往前數 `r` 個，因此做了以下修改。
```diff
for (pos = head->prev, tmp = pos->prev; pos != head && len;
pos = tmp, tmp = pos->prev, len--) {
- int r = rand() % len;
- struct list_head *pick = head->next;
- while (r--)
- pick = pick->next;
+ struct list_head *pick = head->prev;
+ for (int r = rand() % len; r > 0; r--)
+ pick = pick->prev;
```
### 統計方法驗證
利用 [lab0-d](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d) 提供之測試腳本進行實驗，結果如下
```shell
Expectation: 41666
Observation: {'1234': 41992, '1243': 41881, '1324': 41916, '1342': 41741, '1423': 41910, '1432': 41835, '2134': 41302, '2143': 41607, '2314': 41540, '2341': 41489, '2413': 41217, '2431': 41266, '3124': 41528, '3142': 41488, '3214': 41722, '3241': 42061, '3412': 41475, '3421': 41596, '4123': 41716, '4132': 41747, '4213': 41816, '4231': 41996, '4312': 41588, '4321': 41571}
chi square sum: 30.248787980607688
```
將以上數據作圖如下
可以觀察到 shuffle 產生的結果大致符合 uniform distribution
## 比較 timsort 與 list_sort
> Timsort: commit [4f3fced](https://github.com/vax-r/Sorting-Lab/commit/4f3fced9792cd4f9fafb9535bbe5936cdeb98060)
將作業二的 timsort 程式碼進行變更並引入 `list_sort` 進行比較。
利用不同的資料分佈來測試並量測排序演算法當中的比較次數與花費的 cpu cycle 。總共1000 筆資料，每種資料分佈都進行五次試驗並取平均。
**隨機資料分佈**
透過 `rand()` 函式建立隨機資料。
```shell
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 12779
CPU Clock Ellapsed: 153
List is sorted
==== Testing list_sort ====
Comparisons: 8674
CPU Clock Ellapsed: 126
List is sorted
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 11940
CPU Clock Ellapsed: 93
List is sorted
==== Testing list_sort ====
Comparisons: 8725
CPU Clock Ellapsed: 81
List is sorted
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 11825
CPU Clock Ellapsed: 94
List is sorted
==== Testing list_sort ====
Comparisons: 8687
CPU Clock Ellapsed: 82
List is sorted
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 12486
CPU Clock Ellapsed: 149
List is sorted
==== Testing list_sort ====
Comparisons: 8690
CPU Clock Ellapsed: 126
List is sorted
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 11983
CPU Clock Ellapsed: 147
List is sorted
==== Testing list_sort ====
Comparisons: 8718
CPU Clock Ellapsed: 126
List is sorted
```
經過以上測試， timsort 平均耗費的 CPU clock 是 127.2 ，比較次數需要 12202.6 次 ， list_sort 平均耗費的 CPU clock 是 108.2 ，比較次數需要 8698.8 次。
**單調遞減資料分佈**
程式碼當中預設是將資料排序成單調遞增的串列，若給進的資料是完全相反排序也就是單調遞減的資料，那 timsort 和 list_sort 各自表現如何？
產生資料只需要把 `create_sample` 函式進行以下變更
```diff
static void create_sample(struct list_head *head, element_t *space, int samples)
{
printf("Creating sample\n");
for (int i = 0; i < samples; i++) {
element_t *elem = space + i;
- elem->val = rand();
+ elem->val = samples - i;
```
之後執行程式五次並觀察結果
```shell
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 999
CPU Clock Ellapsed: 13
List is sorted
==== Testing list_sort ====
Comparisons: 4940
CPU Clock Ellapsed: 42
List is sorted
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 999
CPU Clock Ellapsed: 8
List is sorted
==== Testing list_sort ====
Comparisons: 4940
CPU Clock Ellapsed: 27
List is sorted
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 999
CPU Clock Ellapsed: 12
List is sorted
==== Testing list_sort ====
Comparisons: 4940
CPU Clock Ellapsed: 41
List is sorted
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 999
CPU Clock Ellapsed: 9
List is sorted
==== Testing list_sort ====
Comparisons: 4940
CPU Clock Ellapsed: 28
List is sorted
$ ./timtest
Creating sample
==== Testing timsort ====
Comparisons: 999
CPU Clock Ellapsed: 8
List is sorted
==== Testing list_sort ====
Comparisons: 4940
CPU Clock Ellapsed: 26
List is sorted
```
驚奇地發現在單調遞減的資料分佈上， timsort 表現是優於 list_sort 非常多的！ 從比較次數上 timsort 只需要 999 次比較而 list_sort 需要將近 5000 次，而 CPU clock cycle 只需要 10 次左右。
**幾乎排序好的資料分佈**
把 `create_sample` 改寫為以下形式，在幾乎是單調遞增的數列當中安插10個隨機大小的數字。
```c
static void create_sample(struct list_head *head, element_t *space, int samples)
{
printf("Creating sample\n");
int rand_index[10];
for (int i = 0; i < 10; i++)
rand_index[10] = rand() % samples;
for (int i = 0; i < samples; i++) {
element_t *elem = space + i;
elem->val = i;
for (int j = 0; j < 10; j++) {
if (rand_index[j] == i) {
elem->val = rand();
break;
}
}
list_add_tail(&elem->list, head);
}
}
```
執行數次後結果都是 timsort 較優，以下列出其中一次的結果。
```shell
Creating sample
==== Testing timsort ====
Comparisons: 2000
CPU Clock Ellapsed: 17
List is sorted
==== Testing list_sort ====
Comparisons: 6025
CPU Clock Ellapsed: 53
List is sorted
```
**全部相同的資料分佈**
如果把串列當中每個數值都固定為 100 ，執行程式進行比較後可以發現如以下的結果。
```shell
Creating sample
==== Testing timsort ====
Comparisons: 999
CPU Clock Ellapsed: 8
List is sorted
==== Testing list_sort ====
Comparisons: 5036
CPU Clock Ellapsed: 36
List is sorted
```
和單調遞減的資料分佈結果非常類似， timsort 不管是在比較次數或耗費的 CPU clock 數量都遠少於 `list_sort`。
**worst case**
最後考慮會讓 merge sort 產生 worst case 的資料分佈，也就是大小交替的資料分佈例如 `[5, 2, 4, 3, 10, 6, 8]` 也就是不停升降的資料分佈。將 `create_sample` 改寫為以下形式
```c
static void create_sample(struct list_head *head, element_t *space, int samples)
{
printf("Creating sample\n");
int pre;
for (int i = 0; i < samples; i++) {
element_t *elem = space + i;
elem->val = rand();
if (i > 0) {
while (i % 2 && (elem->val - pre) <= 0)
elem->val = rand();
while (!(i % 2) && (elem->val - pre) >= 0)
elem->val = rand();
}
pre = elem->val;
list_add_tail(&elem->list, head);
}
}
```
編譯並執行程式數次 （以下為其中一次的結果）
```shell
Creating sample
==== Testing timsort ====
Comparisons: 11984
CPU Clock Ellapsed: 85
List is sorted
==== Testing list_sort ====
Comparisons: 8707
CPU Clock Ellapsed: 71
List is sorted
```
可以觀察到在大小交替的數列當中，也就是會使 merge sort 產生 worst case 的資料分佈中， timsort 在 CPU Clock 或比較次數皆大於 list_sort 。
### Conclusion and thoughts
可以發現 timsort 在資料完成排序或幾乎完成排序 （不管是升序還是降序）的情況下表現都是大幅優於 list_sort 。但在隨機資料分佈以及 worst case 情況下都是 list_sort 優於 timsort ，這可能也導致 timsort 現階段還沒辦法取代 list_sort 的原因，畢竟多數需要排序的場景都是隨機資料分佈。
此處引發我思考什麼場景會有幾乎排序好的資料分佈需要做排序？還有是否有可能發生完全反序的資料分佈（這種場景也不用排序了直接反轉比較快）。
我分析會讓 timsort 在隨機資料分佈與交替資料分佈表現比 list_sort 差的最主要原因是沒有控制 run 的最小 size ，同樣是 queue merge sort 的變形， timsort 在交替資料分佈或隨機資料分佈的情況下很容易產生很短的 run 也就造成比 list_sort 還要多次 merge 的呼叫。
作業二當中我有嘗試利用 insertion 的方式控制 run 的大小，不過效果並不好，應持續嘗試其他方法，應該能優化目前版本的 timsort 。
---
## 亂數產生器
### Entropy
Entropy 的核心概念是 "informational value" ，在 Claude Shannon 提出的理論中被提出，他提出在資料傳輸系統中由三個元件組成， 來源資料、傳輸通道和接收者，**Fundamental problem of communication** 想探索接收者能否由傳輸通道的輸出資料判斷來源資料是什麼。 Entropy 代表的是來源資料能被傳輸通道進行無缺失壓縮的機率上限。白話來說， 一組訊息的 informational value 代表此訊息的出現有多出乎意料，而量化出乎意料的程度就利用 **informantion content** ，也稱為**self-information** 。一個事件 $E$ 的 information content 可以定義為一個隨著 $E$ 發生機率 $p(E)$ 而下降的函數。可以由以下函數來描述這個關係 (事實上也只有 log 函數能完美符合這些定義)
$$
log_2(\cfrac{1}{p(E)})
$$
於是我們定義 information content 的公式為
$$
I(E) = - lg(p(E)) = lg(\cfrac{1}{p(E)})
$$
Entropy 的定義有數種，以 Shannon entropy 來說，它代表需要問幾次是非題來猜中一個隨機值，定義如下
$$
H(X) = - \sum_{\eta \in \chi} p^X(\eta) \cdot lg(p^X(\eta))
$$
$-lg(p^X(\eta))$ 代表的即是字元 $\eta$ 的 informational content ，所以 Shannon Entropy 表示某字串所有字元之 informational content 的期望值，因此可以解讀如下
$$
H(X) = - E[lg(p^X(\eta))]
$$
:::danger
注意書名號的使用，即 `〈` 和 `〉`，非「小於」和「大於」符號。
:::
閱讀〈[由大數法則理解訊息熵的數學意義](https://hackmd.io/@8dSak6oVTweMeAe9fXWCPA/ryoegPgw_)〉，從資料壓縮編碼的角度來理解 Shannon Entropy ，也是一開始 Shannon 提出他的理論時採用的模型。透過大數法則推導找到 **$\epsilon-$ high-probability set** 字串集合的方法，從而發現想找到壓縮後 error probability 小於 $\epsilon$ 的字串集合，此集合總位元個數大約是 $2^{n \cdot H(S)}$ ，原本每個字串是 n 個位元，因此壓縮比會是 $H(S)$ 。換言之， **$H(S)$ 越大的字串集合越不適合壓縮**，因為如果要完整保留原字串集合的資訊，則壓縮後的集合位元數量依舊會很大。
Shannon Entropy 發生極大值的狀況會是在 $P(s_1) = P(s_2) = \cdots = P(s_n) = \cfrac{1}{n}$ 時，也就是 uniform distribution ，因為我們難以從前面資訊預測接下來出現的字元，因此更可能認為該字串是亂數產生的。
到此處才釐清亂度 Entropy 與壓縮之關聯，也加深我對 Entropy 的認識，並非只是搞懂數學推導即可， Entropy 愈大代表資訊量愈高，要在不喪失原本資訊量情況下進行壓縮勢必得使用到更多位元，反之若 Entropy 很小，代表此字串集合十分容易預測，可以用更少的位元來表示原本的資訊，壓縮帶來的好處就更大。英文字串就是很好的例子，因為最前面幾個字元的組合通常就很好預測後面會接上的字元，因此對英文字串進行壓縮的效益高。
### 分析與實作
首先透過 `option entropy 1` 來計算每個字串的 shannon entropy ，測試如下。
```
l = [aaaabbbbbb(9.38%) aaaaaaaaaaaaaaaa(0.00%) abcdefghijk(40.62%) abcdefg(32.81%) abcdedf(29.69%)]
```
可以發現字串當中若有越多不同的字元出現，且出現次數越一致，則 entropy 數值愈高。
`shannon_entropy.c` 當中利用 `log2_lshift16.h` 計算2的對數的方式很類似定點數運算，不過我不理解程式使用的數字意義，尚待釐清。
---
## 整合 tic-tac-toe 遊戲功能
### Basic setups
在 `console.c` 的 `init_cmd()` 當中新增 `ttt` 命令如下
```diff
+ ADD_COMMAND(ttt, "Do tic-tac-toe game", "");
```
同時實作 `do_ttt` 函式。
> [commit 7927fbf](https://github.com/vax-r/lab0-c/commit/7927fbf8c733e2bda246596815c9ef7f7d19cf46)
### Support negamax AI
為了讓使用者可以跟電腦對局，其中一種實作是 [negamax AI](https://en.wikipedia.org/wiki/Negamax) 。
我們利用 64 位元版本的 `mt19937` 亂數產生器與 [Zobrist hashing](https://en.wikipedia.org/wiki/Zobrist_hashing) 來支援 negamax 的實作。
> [commit 9e6133d](https://github.com/vax-r/lab0-c/commit/9e6133d5fc73842dc2e6fc6a04c97138c12abb98)
目前已能在 lab0-c 當中利用 `ttt` 命令和 negamax AI 玩井字遊戲，並將相關人工智慧實作演算法歸納在 `game_agents` 目錄之下。
### Monte Carlo Search Tree
MCST 是一個透過不斷增長 search tree 來做出選擇的演算法，表現最佳的領域會是在 deterministic problem 並且 solution space 是有限的情況，大量被應用在遊戲模擬（尤其是下棋類的遊戲）當中。每一次迴圈當中都從 root $R$ 重複以下四步驟， root $R$ 實際上就代表當前的遊戲狀態
1. Selection ： $R$ 選擇子節點直到達到末端節點，而子節點的選擇方式正是 MCST 的精髓，一般來說還可以分為隨機選擇或搭配權重選擇。
2. Expansion ： 若此遊戲並未結束，末端節點可長出更多子節點
3. Simulation ： 通常也稱為 playout 或 rollout ，讓節點 $C$ 完成一次對局的模擬。
4. Backpropagation ： 把節點 $C$ 進行 playout 的結果沿著原路傳回 root ，並且會透過這個結果更新路上節點的權重。
每一步的最終選擇即是所有模擬結果當中做最多次的選擇。
但是在 Selection 的時候最大的問題是在一開始只有很少量的 simulation result 時，有可能會過度偏向某個不正確的選則，從而影響後面模擬的選擇（因為 selection 會從過去的模擬結果給的權重做選擇，會往錯的選擇越鑽越深），所以我們必須在 exploration 和 exploitation 之間做平衡。
其中一個作法是利用 UCT (Upper Confidence Bound 1 applied to trees) 來給節點權重，公式如下
$$
\cfrac{w_i}{n_i} + c \sqrt{\cfrac{ln(N_i)}{n_i}}
$$
* $w_i$ 代表第 i 次決定後該節點贏的次數
* $n_i$ 代表該節點在第 i 次決定後共做幾次模擬
* $N_i$ 代表該節點的父節點在第 i 次決定後共做幾次模擬
* $c$ 代表 exploration parameter ，通常定為 $\sqrt{2}$ 。
此公式的前後兩項分別對應到 exploitation 和 exploration ，當某個節點贏的次數越多，該節點的 exploitation power 越高，而在模擬次數很少時， 後面那一項容易比較高。
使用 UCT 的 MCTS 已經被證明會收斂成 [minimax](https://en.wikipedia.org/wiki/Minimax) ，但實際上最基本的 MCTS 只有在 Monte Carlo Perfect games 才會收斂。不過 MCTS 有個優勢，它不需要特別給定 evaluation function ，所以幾乎可以適用於任何遊戲規則。特別是在高 branching factor 的遊戲中表現較傳統演算法更優（因此圍棋、西洋棋這類 high branching factor 的遊戲非常適合用 MCTS)。
在 high branching factor 遊戲當中，要建構出包含所有選擇所產生的搜尋樹太耗費成本， MCTS 事實上並不會推導出所有可能結果，而是根據每一輪的 selection, expansion, simulation 與 backpropagation 來建構這棵樹。所以決定節點權重的方法非常重要，因為每一次 selection 都是選擇當前節點的子節點中最高權重的節點往下走，例如上述提到的 UCT 是一種選擇，但這也有機會讓這棵樹往完全錯誤的方向長下去。
### Fixed-point operation with MCTS
目前 [jserv/ttt](https://github.com/jserv/ttt) 當中實作的 MCTS 大量運用到浮點數運算，並且用來評估井字遊戲對局評分的函式當中也存在浮點數運算，我們的目標是將他們全部修改為定點數運算。由於定點數沒有固定規格，由我們自己設計，當中非常關鍵的一環在於[挑選 scaling factors](https://en.wikipedia.org/wiki/Fixed-point_arithmetic#Choice_of_scaling_factors) 也就是 fractional bits 的數量。
先考慮原本浮點數運算的精度，在 jserv/ttt 當中使用 `double` 這個資料型別進行浮點數運算，根據 [IEEE 754-1985](https://en.wikipedia.org/wiki/Double-precision_floating-point_format) 的規範， `double` 使用 64 bit 作為儲存數字的記憶體空間，最小可以表示到小數點後 308 位（10 進位表示法），但我們現在要考量的是二進位表示法， exponent 欄位若全為零，在依據 biased exponent 運算可知最小的 exponent 會是 $2^{-1022}$ ，另外加上 fraction bits 有 52 位元所以用二進位表示來說 double precision 最小表示範圍是到小數點後第 1074 位。
如果想用定點數完整取代浮點數 `double` 的話 scaling factor 至少需要挑選 $2^{-1074}$ ，也就需要 1075 位元的資料空間，是 17 bytes 的大小，過度浪費空間，並且 scaling factor 越大，在位移運算時造成的誤差也越多。
:::warning
參見 [Q (number format)](https://en.wikipedia.org/wiki/Q_(number_format))
> [name=I-HSIN Cheng] 感謝老師，正在閱讀並改進我的實作
:::
此處我使用 `unsigned` 來當成我設計之定點數的資料型態， msb 為 sign bit ，接下來的 23 bits 為整數部分，最後 8 bits 為 scaling bits 也就是 $2^8$ 為 scaling factor ，原因是在原本使用浮點的 MCTS 當中，會使用到的最大值是 3.552684 左右，最小值是 0.0 。取 8 bits 為 scaling bits 的話小數點部分的最大值是 0.996094 ，另外因為 `log, uct_score` 等函式的運算可能會使分母大於分子，需要讓分子先進行位移再做除法，如果 32 bits 的資料型態當中取到 16 bits 來當 scaling bits 就有可能在這個 shift 的過程遺失整數部分的資料，因此權衡之下我選擇 8 bits 作為 scaling bits 。以 Texas Intruments 的 Q number format 來表示我的定點數表示法即是 Q23.8 。
利用以上定點數設計，我將 MCTS 當中浮點數運算進行以下更動。
首先在 `game.h` 當中定義一個定點數型別並寫清楚 scaling factor 。
```c
/* Self-defined fixed-point type, using last 10 bits as fractional bits,
* starting from lsb */
#define FIXED_SCALE_BITS 8
#define FIXED_MAX (~0U)
#define FIXED_MIN (0U)
#define GET_SIGN(x) ((x) & (1U << 31))
#define SET_SIGN(x) ((x) | (1U << 31))
#define CLR_SIGN(x) ((x) & ((1U << 31) - 1U))
typedef unsigned fixed_point_t;
```
`calculate_win_value` 原本的作用是自己贏的話就回傳 `1.0` ，輸的話回傳 `0.0` ，平手則回傳 `0.5` 。此處的變更很簡單，將 `1.0, 0.0, 0.5` 全部更換成自定義定點數的形式。
```diff
fixed_point_t calculate_win_value(char win, char player)
{
if (win == player)
- return 1.0;
+ return 1U << FIXED_SCALE_BITS;
if (win == (player ^ 'O' ^ 'X'))
- return 0.0;
+ return 0U;
- return 0.5;
+ return 1U << (FIXED_SCALE_BITS - 1);
}
```
另外一處重點變更在 `uct_score` 的計算函式。
`DBL_MAX` 變更為 `FIXED_MAX` ， `score / n_visits` 則是先將 `n_visits` 轉變為定點數 `n_visits * (1U << FIXED_SCALE_BITS)` 和 `score` 相除也就是 `score / (fixed_point_t) (n_visits * (1U << FIXED_SCALE_BITS))` ，最後記得定點數相除還要再乘上 scaling factor 。
棘手的地方在 `EXPLORATION_FACTOR * sqrt(log(n_total) / n_visits)` 這一項， `sqrt()`, `log()` 本身就使用浮點數運算，因此我們要設計對應的定點數運算來取代他們。
**Fixed point logarithm**
> [commit e106d93](https://github.com/vax-r/lab0-c/commit/e106d93c94a9b3aa174028cf7565a4570b11ec3d)
原本參考 [第三週測驗 測驗三](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-3) 的方法來計算 logarithm ，但考慮到我們是利用定點數模擬小數運算，直接取整數會喪失過多精度，失去利用定點數的意義，於是我利用泰勒展開來求定點數的 logarithm 。
因為 `log(x)` 實際上是取 natural logarithm 也就是 $ln(x)$ ，我們利用以下泰勒展開公式
$$
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
fixed_point_t fixed_log(fixed_point_t v)
{
fixed_point_t y = ((v - (1U << FIXED_SCALE_BITS)) << (FIXED_SCALE_BITS)) / (v + (1U << FIXED_SCALE_BITS));
fixed_point_t ans = 0U;
for (unsigned i = 1; i < 20; i += 2) {
fixed_point_t z = (1U << FIXED_SCALE_BITS);
for (int j = 0; j < i; j++) {
z *= y;
z >>= FIXED_SCALE_BITS;
}
z <<= FIXED_SCALE_BITS;
z /= (i << FIXED_SCALE_BITS);
ans += z;
}
ans <<= 1;
return ans;
}
```
有幾個細節需要注意，由於 $\cfrac{x - 1}{x + 1}$ 利用定點數除法會變成 0 ，因此我把做完除法後乘上 scaling factor 的運算移到分子，讓分子先乘上 scaling factor 再進行除法。不過此方法也會造成些微誤差產生，應探討是否有更好的處理方法。
另外 `z /= (i << FIX_SCALE_BITS)` 部分也採用相同方法來避免除法的結果因為取整數而變成 0 。將上述結果和原先使用 `log()` 函式計算的對數值繪圖比較（繪圖時將定點數由以下函式轉為浮點數來比較）
```c
double fixed_to_double(fixed_point_t x)
{
double ans = 0.0;
unsigned tmp = (x >> FIXED_SCALE_BITS) & FIXED_MAX;
ans += (double) tmp;
for (int i = 1; i <= FIXED_SCALE_BITS; i++) {
if (x & (1U << (FIXED_SCALE_BITS - i)))
ans += (double) 1 / (1U << i);
}
return ans;
}
```
在 x 變大時，對數值的誤差會越大，初步推測是泰勒展開之項次太少，不過將項次調製 98 次方甚至以上，雖然誤差有變小，但越往更後面的項次算所能逼近的程度越少。將項次調成 98 次方後繪圖如下
此處我發現一個嚴重的錯誤，雖然上圖的繪圖結果看似不錯，定點數運算計算對數值的結果跟浮點數運算趨勢與實際值都十分貼近，但 MCTS 的 utc score 大多是分佈在 0.0 ~ 3.55 之間，因此模擬之數值應該從 0 開始進行到 ５ 並且每次增加 0.001 ，如此進行後我發現整數部分為 0 的純小數進行對數運算後答案會是負數，但我的定點數設計並未考量到負數，會使負數被解讀為非常大的數字，此處需要重新改進並探討如何儲存 sign bit 。
:::danger
原本設計底下 $\cfrac{x - 1}{x + 1}$ 在 $0 \le x < 1$ 的情況下會大於 0。
:::
經過改進後我重新設計定點數格式與運算方式，由於我的定點數 `fixed_point_t` 本質是 `unsigned` ，任何加減乘除都遵循阿貝爾群的封閉性，才導致 $0\le x < 1$ 時， $x - 1$ 會變成一個很大的數，利用原先二補數的概念 $x = -2^{31} + \sum_{i=0}^{30} x_i \cdot 2^i$ ，而我只希望保留數字部分因此可以利用取負號將原本的負號消去 $x = 2^{31} - \sum_{i=0}^{30} x_i \cdot 2^i$ ，定點數採用 sign and magnitude 的設計，修正 `fixed_log()` 函式如下
```diff
fixed_point_t fixed_log(fixed_point_t v)
{
+ if (!v || v == (1U << FIXED_SCALE_BITS))
+ return 0;
+ fixed_point_t numerator = (v - (1U << FIXED_SCALE_BITS));
+ int neg = 0;
+ if (GET_SIGN(numerator)) {
+ neg = 1;
+ numerator = CLR_SIGN(numerator);
+ numerator = (1U << 31) - numerator;
+ }
+ fixed_point_t y =
+ (numerator << FIXED_SCALE_BITS) / (v + (1U << FIXED_SCALE_BITS));
```
> [commit 7c92cea](https://github.com/vax-r/lab0-c/commit/7c92cea858f21789050c48e1bb0f7df9717b0bdd)
於是得到修正的繪圖如下
放大 0~5 的區間來確認在 MCTS 運算可以正常運作
:::warning
原先做圖利用 gnuplot ，不過後續為了使 x-axis 使用浮點數改用 python 的 matplotlib
:::
**Fixed point Square root**
此數我利用逼近法求平方根，作法如下
```c
fixed_point_t fixed_sqrt(fixed_point_t x)
{
if (!x || x == (1U << FIXED_SCALE_BITS))
return x;
fixed_point_t s = 0U;
for (int i = (31 - __builtin_clz(x | 1)); i >= 0; i--) {
fixed_point_t t = (1U << i);
if ((((s + t) * (s + t)) >> FIXED_SCALE_BITS) <= x)
s += t;
}
return s;
}
```
將原本使用 `math.h` 當中 `sqrt()` 函式得出的平方根值和我設計的定點數平方根值從 0~100 的區間繪圖比較如下
定點數之平方根和原本浮點數運算得出之平方根幾乎無異。但如果將 0~1 區間內的小數做開平方根並繪圖如下，可以發現在此區間存在明顯誤差。
這是當前我的定點數與它搭配的開平方根運算無法避免的誤差，因為精度不足所以計算 0~1 區間小數的平方根沒辦法找到夠小的數來逼近。
此修正版本的定點數運算使 MCTS 相較上個版本（看似隨機做選擇的糟糕版本）有了顯著的進步，目前運用 MCTS 的 AI 能在多數情況找到能使自己勝出的路線。應該設計實驗方法來評比 AI 在遊戲中的表現來真正量化進步的程度。
> [commit 7c92cea](https://github.com/vax-r/lab0-c/commit/7c92cea858f21789050c48e1bb0f7df9717b0bdd)
定點數運算的本質比想像中單純的多，和我們國小剛學小數點運算使用的其實是相同的邏輯，不過因為乘法導致 overflow 與除法時分子小於分母造成結果直接變零等情況，使得我們在運算設計上必須更小心並選擇適當的 scaling factor 。
:::warning
這是本次作業的關鍵，你該針對場景去設計合適的定點數表示法和提供對應運算。
:::
### Reinforcement Learning
#### 原理
首先了解 RL 的原理以及實作方法，紀錄在 [RL 筆記](https://hackmd.io/@vax-r/reinforcement_learning) 。
#### 訓練模型
需要將所有浮點數運算皆改成我設計的定點數運算，此處原本 ttt 專案當中使用的 `INITIAL_MULTIPLIER` 是十進位的 0.0001 ，但我的定點數最小只能表示到十進位的 0.00390625 ，因此以這個值取代為 `INITIAL_MULTIPLIER` 。
### 電腦 v.s. 電腦
目前已能使一個電腦 v.s. 電腦的對奕局運作。
> [commit 9410e7e](https://github.com/vax-r/lab0-c/commit/9410e7e93ec2ddd4af77932f58444b8a05c86eb6)
**Linux Process v.s. Thread**
:::danger
避免說無助於溝通的話。
:::
<s>很多人曾經聽說</s> linux 當中是沒有區分 thread 和 process 的，我本來也認為兩者是相同的，經由閱讀 [fork(2)](https://man7.org/linux/man-pages/man2/fork.2.html) 和 [clone(2)](https://man7.org/linux/man-pages/man2/clone.2.html) 歸納出以下數點不同處來區分 linux 當中的 process 和 thread (搭配〈[看漫畫學 Linux](https://hackmd.io/@sysprog/linux-comic#%E8%A1%8C%E7%A8%8B%E8%A1%A8)〉講解非常生動且清晰)。
剛看到 [fork(2)](https://man7.org/linux/man-pages/man2/fork.2.html) 和 [clone(2)](https://man7.org/linux/man-pages/man2/clone.2.html) 內容時，兩者都描述函式是用來 "create a child process" ，但仔細閱讀內文可以發現， `fork()` 創造的子行程和原先的親代行程幾乎是雙胞胎，各自有自己的記憶體空間而內容完全一樣（這也造成某些共享資源的問題，例如 file descriptor 或 mutex ），子行程會從親代行程呼叫 `fork()` 處繼續執行。
呼叫 `clone()` 時若帶參數 `fn` ，則創造的子行程會執行 `fn` 函式並在該函式結束時也結束自己生命週期，而且 `clone()` 產生的子行程可以和親代行程共享記憶體空間。
特別注意 `clone()` 的一個標籤 `CLONE_THREAD` ，當此標籤被設定時，子行程會和呼叫 `clone()` 的行程被放在同一個 thread group 當中， thread groups 代表一群享有相同 PID 的行程之集合，這個 PID 又稱為 TGID (thread group identifier) ，並且它的親代行程會和呼叫 `clone()` 的進程之親代行程一樣。 Thread group 當中不同的行程有各自的 TID (thread ID) ，當呼叫 `clone()` 時不具備 `CLONE_THREAD` 此標籤，則建立的行程會同時建立一個新的 thread group 並且該 TGID 和自己的 TID 一樣。
總結來說， `fork()` 和 `clone()` 不同，不過可以透過傳遞特定參數進入 `clone()` 而達到跟 `fork()` 相同的效果，並且 thread 和 process 就執行單元上都是 `task_struct` ，但 process 可以理解為 thread group 當中只有一個 thread 的情況， thread 則指一個 thread group 底下的某個 thread ，所以嚴格來說 thread 和 process 並不相同。注意 signal 也是有區分 process-directed 跟 thread-directed 的。Linux 也針對 thread 支援 [nptl(7)](https://man7.org/linux/man-pages/man7/nptl.7.html) 。
:::warning
process 在作業系統的語境中，譯作「行程」，而避免父權主義的遺毒，可將 parent process 翻譯為「親代行程」，而非「父行程」或「母行程」，不僅更中性，也符合英文原意。若寫作「父」，則隱含「母」的存在，但以行程管理來說，沒有這樣成對關連性。若用「上代」會造成更多的混淆，在漢語中，「上一代」沒有明確的血緣關係 (例如「[炎黃子孫](https://dict.revised.moe.edu.tw/dictView.jsp?ID=155219)」與其說是血緣關係，不如說是傾向文化認同)，但「[親](https://dict.concised.moe.edu.tw/dictView.jsp?ID=25345)」的本意就是指名血緣和姻親關係。
延伸閱讀:
* [「新中國」和「中華民族」—— 梁啟超悔之莫及的發明](https://www.thenewslens.com/article/122516)
* [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
**coroutine**
`jmp_buf` 定義在 [/source/setjmp/setjmp.h](https://elixir.bootlin.com/glibc/glibc-2.29/source/setjmp/setjmp.h#L45) 當中，功能是用來儲存呼叫 `setjmp()` 函式的 caller 當前狀態，這個 buffer 會被 `longjmp()` 使用來將控制權轉換回原本的 `setjmp()` 位置。
`setjmp()` 、 `lonjmp()` 負責進行 nonlocal gotos ， `setjmp()` 會動態設定一個標籤使得 `longjmp()` 轉移控制權時會回到該標籤位置。正常呼叫 `setjmp()` 的回傳值是 0 ，但若是透過呼叫 `longjmp()` 而回到 `setjmp()` 位置再進行一次呼叫，則回傳值會是一個假值。詳細參考 [setjmp(3)](https://man7.org/linux/man-pages/man3/longjmp.3.html) 。
我參考 [coro](https://github.com/sysprog21/concurrent-programs/blob/master/coro/coro.c) 的實作，利用 `setjmp()` 和 `longjmp()` 還有 `jmp_buf` 實作 coroutine ，將任務拆分成三大類：
* 監聽鍵盤事件 （尚未實作）
* 電腦對奕
* 結束並重置
其中電腦對奕還會再細拆成 AI.1, AI.2 還有繪製棋盤三種對局任務，透過一個雙向鍵結串列儲存這三種對局任務的狀態，在上述三大類基本任務中要是完成函式就會透過 `longjmp(sched, 1)` 回到排程器的 main loop 當中進行下一輪的對局。
過程中發現一個有趣的現象，若將程式碼撰寫如下
```c
for (int i = 0; i < TIMES; i++) {
static int ntasks = 2;
setjmp(sched);
/* More implementation */
}
```
則在其他函式中呼叫 `longjmp(sched, 1)` 回到上述迴圈當中 `setjmp(sched)` 位置處繼續執行時，就算 `ntasks` 的值被變更過，回到 `setjmp(sched)` 處時也會變回 2 ，若是將 `ntasks` 定義為全域變數則不會產生此行為。
:::warning
注意上述實作是 stackful 抑或 stackless 的 coroutine
:::
實作過程中加入處理監聽鍵盤事件的處理，首先要用下列命令讓 Ctrl+Q 預設行為關閉，使 terminal 可以讀取到 Ctrl+Q 的字元，並將 STDIN_FILENO 轉為 raw mode 和 non-blocking
```shell
$ stty start '^-' stop '^-'
```
目前排程器利用 FIFO 來實作，理想上是讓監聽鍵盤事件的 coroutine node 間接的安插在 AI.1 和 AI.2 之間，但未考量到安插監聽鍵盤事件 coroutine 的適當方法，使得大量 coroutine 被安插進入排程器的鍵結串列當中造成很大的延遲，過程也發現我對 coroutine 不理解造成設計上的缺失，目前正在改進並重新閱讀教材。
重新設計之後我使排程器的 job queue 雙向鍵結串列只有 AI.1 , AI.2, draw_board 這三種任務進入排程，但在進行這三種任務時密集呼叫監聽鍵盤事件的函式 `listen_keyboard()` ，呼叫的時候透過 `coroutine_add()` 將當前 coroutine 狀態存入排程器當中，在 `listen_keyboard()` 結束時呼叫 `coroutine_switch()` 以接續執行 job queue 中第一個 coroutine 。
> [commit e100efb](https://github.com/vax-r/lab0-c/commit/e100efb6b95277494636b73d3f87ae740dbd0422)
此處尚需探討除了 FIFO 是否有其他對於此情境更合適的排程演算法，以及我的實作並沒有將監聽鍵盤事件封裝成 coroutine 加入排程，而是透過密集的函式呼叫達成。
為了將四種任務皆包裝為 coroutine ，我將排程器實作改為 premmptive 並使用 round-robin 排程演算法使 AI.1, AI.2, 監聽鍵盤事件和繪製棋盤這四種 coroutine 輪流進行
首先研讀 [preempt_sched](https://github.com/sysprog21/concurrent-programs/blob/master/preempt_sched/task_sched.c) 和 [signal(7)](https://man7.org/linux/man-pages/man7/signal.7.html) ，內容記錄在 [Linux Signal 解說](https://hackmd.io/@vax-r/linux-signal) ，注意並思考 user context 的操作與函式還有執行緒的關係。
將 AI.1 、 AI.2 、 監聽鍵盤事件和繪製棋盤分別包裝成四個 coroutine ，由 `struct task_struct` 實作 coroutine ，將電腦對奕的 main loop 重新改寫成以下後完成將各任務包裝成 coroutine 並以 preemptive scheduler 實作 round robin 排程演算法來完成電腦對奕。
```c
char win = check_win(table);
while (win == ' ') {
task_add(mcts_callback, &mcts_arg);
task_add(listen_keyboard, "");
task_add(negamax_callback, &negamax_arg);
task_add(listen_keyboard, "");
task_add(drawboard_callback, &drawboard_arg);
task_add(listen_keyboard, "");
while (!list_empty(&task_main.list) || !list_empty(&task_reap)) {
preempt_enable();
coro_timer_wait();
preempt_disable();
}
win = check_win(table);
}
```
完整實作如下
> [commit db3e5e9](https://github.com/vax-r/lab0-c/commit/db3e5e9211069ffeeb29aaa9fa0e84f38b1923c0)
### PRNG 實作比較
MCTS 當中利用 PRNG 產生亂數以隨機挑選每次 simulation 下個要移動的位置，原本的實作當中利用 glibc 的函式 `rand()` 產生亂數，以 4x4 棋盤來說，每次最多可能有 15 種不同的選項，我分別利用 0~14 來代表不同選項，利用 `rand()` 進行 1 億次抽樣，同時利用 `perf stat` 量測程式效能表現，分佈如下。
```
Performance counter stats for './qtest -f ./traces/trace-random.cmd' (5 runs):
1626.42 msec task-clock # 1.000 CPUs utilized ( +- 0.18% )
4 context-switches # 2.459 /sec ( +- 32.98% )
0 cpu-migrations # 0.000 /sec
74 page-faults # 45.499 /sec ( +- 0.27% )
61,2229,7720 cycles # 3.764 GHz ( +- 0.16% ) (83.21%)
26,8089,2190 stalled-cycles-frontend # 43.79% frontend cycles idle ( +- 0.12% ) (83.21%)
13,3587,8649 stalled-cycles-backend # 21.82% backend cycles idle ( +- 1.49% ) (66.86%)
76,8898,7881 instructions # 1.26 insn per cycle
# 0.35 stalled cycles per insn ( +- 0.01% ) (83.45%)
16,9079,0692 branches # 1.040 G/sec ( +- 0.02% ) (83.45%)
332,1066 branch-misses # 0.20% of all branches ( +- 1.72% ) (83.28%)
1.62679 +- 0.00293 seconds time elapsed ( +- 0.18% )
```
可以看出這並非 uniform-distribution 而且產生不同數字的次數差距很大，並且程式耗費了 61,2229,7720 個 cycles ，而 stalled-cycles-frontend 和 stalled-cycels-backend 分別造成了 43.79% 的 frontend cycles idle 和 21.82% backend cycles idle。
如果置換成 `mt19937_rand()` 結果如下
```
Performance counter stats for './qtest -f ./traces/trace-random.cmd' (5 runs):
610.13 msec task-clock # 0.999 CPUs utilized ( +- 1.08% )
6 context-switches # 9.834 /sec ( +- 47.73% )
0 cpu-migrations # 0.000 /sec
75 page-faults # 122.925 /sec ( +- 0.33% )
22,7022,8449 cycles # 3.721 GHz ( +- 0.88% ) (83.26%)
6,4230,2906 stalled-cycles-frontend # 28.29% frontend cycles idle ( +- 2.92% ) (83.26%)
2733,7515 stalled-cycles-backend # 1.20% backend cycles idle ( +- 16.95% ) (66.51%)
54,0244,2759 instructions # 2.38 insn per cycle
# 0.12 stalled cycles per insn ( +- 0.03% ) (83.26%)
5,0011,6533 branches # 819.694 M/sec ( +- 0.03% ) (83.33%)
97,2145 branch-misses # 0.19% of all branches ( +- 0.15% ) (83.64%)
0.61093 +- 0.00654 seconds time elapsed ( +- 1.07% )
```
同樣無法產生常態分佈的選擇情況下， 使用 `mt19937_rand()` 的程式只耗費了 0.61093 秒， cpu cycles 和閒置的 cycles 都有顯著進步。
如果使用其他實作例如 SplitMix64, Xoroshiro128+, PCG64 呢？我參考了 [testingRNG](https://github.com/lemire/testingRNG/tree/master?tab=readme-ov-file#visual-summary) 的結果，挑選通過 big crush test 的 PRNG 實作來測試。
首先挑選 **wyhash** 實作，同樣抽樣 1 億次並將結果做圖如下
```c
static inline uint64_t wyhash64_stateless(uint64_t *seed) {
*seed += 0x60bee2bee120fc15;
__uint128_t tmp;
tmp = (__uint128_t)*seed * 0xa3b195354a39b70d;
uint64_t m1 = (tmp >> 64) ^ tmp;
tmp = (__uint128_t)m1 * 0x1b03738712fad5c9;
uint64_t m2 = (tmp >> 64) ^ tmp;
return m2;
}
```
```shell
Performance counter stats for './qtest -f ./traces/trace-random.cmd' (5 runs):
259.85 msec task-clock # 0.999 CPUs utilized ( +- 1.14% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
74 page-faults # 284.780 /sec ( +- 0.33% )
9,5142,8394 cycles # 3.661 GHz ( +- 0.05% ) (83.05%)
3,5113,2154 stalled-cycles-frontend # 36.91% frontend cycles idle ( +- 0.15% ) (83.04%)
1418,5802 stalled-cycles-backend # 1.49% backend cycles idle ( +- 2.19% ) (66.09%)
17,0034,1834 instructions # 1.79 insn per cycle
# 0.21 stalled cycles per insn ( +- 0.02% ) (83.04%)
1,0024,6846 branches # 385.788 M/sec ( +- 0.04% ) (83.88%)
7369 branch-misses # 0.01% of all branches ( +- 2.41% ) (83.94%)
0.26022 +- 0.00300 seconds time elapsed ( +- 1.15% )
```
值得注意的是 wyhash 同樣執行 1 億次抽樣並重複五次的時候，耗費的 cpu cycles 僅有 9,5142,8394 個，遠少於 mt19937 和 glibc 的 `rand()` ，並且執行時間僅有 0.26022 秒。
接下來測試 **splitmix64**
```c
#define GOLDEN_GAMMA 0x9E3779B97F4A7C15
static inline uint64_t splitmix64_r(uint64_t *seed) {
uint64_t z = (*seed += GOLDEN_GAMMA);
// David Stafford's Mix13 for MurmurHash3's 64-bit finalizer
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9;
z = (z ^ (z >> 27)) * 0x94D049BB133111EB;
return z ^ (z >> 31);
}
```
```shell
Performance counter stats for './qtest -f ./traces/trace-random.cmd' (5 runs):
320.89 msec task-clock # 0.999 CPUs utilized ( +- 0.56% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
75 page-faults # 233.726 /sec
11,8232,7575 cycles # 3.685 GHz ( +- 0.06% ) (83.46%)
4,8203,8956 stalled-cycles-frontend # 40.77% frontend cycles idle ( +- 0.08% ) (83.46%)
2212,7194 stalled-cycles-backend # 1.87% backend cycles idle ( +- 0.91% ) (66.93%)
23,0055,8252 instructions # 1.95 insn per cycle
# 0.21 stalled cycles per insn ( +- 0.02% ) (83.47%)
1,0028,7116 branches # 312.529 M/sec ( +- 0.02% ) (83.46%)
6612 branch-misses # 0.01% of all branches ( +- 16.37% ) (82.68%)
0.32131 +- 0.00181 seconds time elapsed ( +- 0.56% )
```
結果是 splitmix64 耗費的時間與 cpu cycles 都略高於 wyhash ，不過兩者都優於 mt19937 ，於是我選擇將 MCTS 當中取隨機數字的函式實作替換成 wyhash。
> [commit dd3b429](https://github.com/vax-r/lab0-c/commit/dd3b4297e3ac9dc6cc92cee8442d5c60cbfdc2cf)
:::warning
當你著手一系列實驗後，應該會驚訝於亂數的分佈與最初預期不同，這揭露潛在的資訊安全議題，相關討論見:
* [Dissecting Lemire's nearly divisionless random](https://shufflesharding.com/posts/dissecting-lemire)
* [Fast Random Integer Generation in an Interval](https://arxiv.org/abs/1805.10941)
* [My notes on understanding Lemire's nearly divisionless random](https://sts10.github.io/2020/10/10/lemire-neaarly-divisionless-random.html)
後續改進 [Issue #32](https://github.com/jserv/ttt/issues/32)。
:::
### AI load average
閱讀 [include/linux/sched/loadavg.h](https://elixir.bootlin.com/linux/v5.3/source/include/linux/sched/loadavg.h) 和 [Linux Load Averages: Solving the Mystery](https://www.brendangregg.com/blog/2017-08-08/linux-load-averages.html) 先理解 Linux 核心 計算 load average 方式。 Linux 核心 利用 EWMA 計算 load average ，並且會依照不同時間間隔分別計算三個 load averages ，分別是 1 分鐘、 5 分鐘、 15 分鐘，對於不同的時間有不同的 smoothing factor ，計算時採定點數運算， factional bits 是 11 位，由於會使用到乘法運算，乘法後的數 fractional bits 會達到 22 位，整數部分會有 11 位元被遺棄，因此此定點數運算的精度是 10 bits integer 和 11 bits fractional 。
計算 load average 的函式 `calc_load` 利用 `newload = load * exp + active * (FIXED_1 - exp)` 來更新 load average ， `active` 代表目前**系統運行和阻塞的行程總數**，但在 [include/linux/average.h](https://elixir.bootlin.com/linux/latest/source/include/linux/average.h) 本來就有定義可以使用的 ewma 結構體巨集，此處為何不重用？目前推測是因為計算 load average 的 smoothing factor 不是 2 的指數不符合該巨集規範，若能找到合適且符合 2 的指數的 smoothing factor ，我認為可以在此處重用 [include/linux/average.h](https://elixir.bootlin.com/linux/latest/source/include/linux/average.h) 的 ewma 巨集。
我在 [kernel/sched/loadavg.c](https://elixir.bootlin.com/linux/v5.3/source/kernel/sched/loadavg.c) 的 `calc_global_nohz` 當中發現 `active = active > 0 ? active * FIXED_1 : 0;` 的指令為何不使用 shift 來替代乘法？已知 `FIXED_1` 是 `(1 << FSHIFT)` ，於是我進行以下小實驗嘗試量測使用 `*` 與 `<<` 的差別。撰寫以下程式
```c
#define FSHIFT 11
#define FIXED_1 (1<<FSHIFT)
int main(void)
{
long x = 2342800;
x = x * FIXED_1;
return 0;
}
```
編譯並確認不要開啟優化選項
```shell
$ gcc -O0 -o out test.c
```
之後利用 `objdump` 先觀察對應組合語言輸出
```shell
$ objdump -Slz out
...
0000000000001129 <main>:
main():
1129: f3 0f 1e fa endbr64
112d: 55 push %rbp
112e: 48 89 e5 mov %rsp,%rbp
1131: 48 c7 45 f8 90 bf 23 movq $0x23bf90,-0x8(%rbp)
1138: 00
1139: 48 c1 65 f8 0b shlq $0xb,-0x8(%rbp)
113e: b8 00 00 00 00 mov $0x0,%eax
1143: 5d pop %rbp
1144: c3 ret
...
```
改寫程式利用 `<<` 重新編譯並觀察組合語言輸出
```shell
$ objdump -Slz out
...
0000000000001129 <main>:
main():
1129: f3 0f 1e fa endbr64
112d: 55 push %rbp
112e: 48 89 e5 mov %rsp,%rbp
1131: 48 c7 45 f8 90 bf 23 movq $0x23bf90,-0x8(%rbp)
1138: 00
1139: 48 c1 65 f8 0b shlq $0xb,-0x8(%rbp)
113e: b8 00 00 00 00 mov $0x0,%eax
1143: 5d pop %rbp
1144: c3 ret
...
```
兩種寫法在編譯器優化關閉時組合語言輸出是一樣的，此處令我震驚但也讓我開始思考何時該使用 shift operators 而何時使用 `*, /` 的效能也能相同？
> 這案例太單純，GCC 產生指令時的模式比對就會選擇上述的位移指令，你可改為藉由函式呼叫來傳遞參數，並變更位移量。 :notes: jserv
目前 AI 對亦採用的兩種演算法 MCTS 和 negamax ，前者可能因為樹狀結構可能運用到大量節點，後者則是牽涉遞迴呼叫，因此系統堆疊空間的使用是關鍵，我認為可以用樹中的節點數來作為計算 MCTS load average 的單位， negamax 則是利用堆疊深度來計算。 smoothing factor 則需要再研究如何挑選才合適。
Sign in with Wallet
Connect another wallet