# 2024q1 Homework1 (lab0)
contributed by < [steven523](https://github.com/steven523) >
### Reviewed by `SuNsHiNe-75`
- 注意標點符號的使用，有些地方都沒有「句號」。
- 請把完整程式碼移除，如要討論才將要討論之部分「重點列出」。
- 如有終端機相關的訊息，可在「程式區塊」的點點後加上「shell」。
### Reviewed by `stevendd543`
- `q_free` 有提到「q_release_element 刪除 entry 時不會發生錯誤」，具體錯誤原因可以清楚描述。
- `q_ascend` 中前段的漢語表達讓讀者不容易，可透過 ChatGPT 修飾。
- 注意標點符號的使用，有些地方都沒有「句號」。
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz
CPU family: 6
Model: 165
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
CPU max MHz: 5000.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
```
## 指定的佇列實作
### `q_new`
:::danger
allocate 翻譯為「配置」，以區格 dispatch (分發/分配) 的翻譯
>已更改
:::
使用 `malloc` 為佇列 `new` 配置一個動態記憶體空間，如果成功配置足夠大小的空間給 `new` 指標，則透過 `INIT_LIST_HEAD` 做初始化使 `new` 的 prev 和 next 皆指向自己，否則返回 `NULL`
```c
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
if (new) {
INIT_LIST_HEAD(new);
return new;
} else {
return NULL;
}
}
```
### `q_free`
:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
>已更改
:::
用 `list.h` 的巨集 `list_for_each_entry_safe` 逐一走訪整個佇列並透過 `safe` 紀錄每個迭代當前節點的下一個節點，以致逐一走訪節點的過程中安全使用 `q_release_element` 刪除目前的節點
:::danger
- [ ] traverse (動詞) 和 traversal (名詞)
根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse
): (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)
* to pass or move over, along, or through.
* to go to and fro over or along.
其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。
當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。
還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。
在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。
遍歷 (Ergodic) 源於以下二個希臘詞：
* ergon (對應英語的 work)
* odos (對應英語的 path 或 way)
最初這是由奧地利物理學家波茲曼 ([Ludwig Boltzmann](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。
因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
```c
void q_free(struct list_head *head)
{
if (head) {
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list)
q_release_element(entry);
free(head);
} else
return;
}
```
:::danger
說好的進度呢？
:::
### `q_insert_head`
新增一個 `element_t` 並使用 `malloc` 為其配置記憶體空間，接著使用 `list.h` 中的 `list_add` 將節點插入佇列開頭。但是在測試時出現以下訊息：
```shell
cmd> new
l = []
cmd> ih a
ERROR: Need to allocate and copy string for new queue element
```
這個錯誤提示是在說建立新的佇列元素時需要為其分配記憶體並複製字串
所以我使用 `strdup` 這個函式來複製參數 s 並配置記憶體空間給它
```diff
element_t *new = malloc(sizeof(element_t));
if (new) {
+ new->value = strdup(s);
+ if (!new->value) {
+ q_release_element(new);
+ return false;
+ }
- new->value = s;
list_add(&new->list, head);
return true;
}
```
### `q_insert_tail`
與 `q_insert_head` 差不多的做法，新增一個 `element_t` 並使用 `malloc` 為其配置記憶體空間，接著使用 `strdup` 來複製參數 s 並配置記憶體空間給它，最後使用 `list.h` 中的 `list_add_tail` 將節點插入佇列尾端
```
cmd> new
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> it c
l = [b a c]
cmd> it 7
l = [b a c 7]
```
### `q_remove_head`
:::danger
避免非必要的項目縮排 (即 `* `, `- ` 或數字)，以清晰、明確，且流暢的漢語書寫。
授課教師在大學教書十餘年，見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。為此，要求學員書寫開發紀錄，並隨時做好「當主管問起，就能清晰解釋自己的投入狀況」，是強調讓學員「翻身」的本課程所在意的事。
濫用條列 (或說 bullet) 來展現，乍看很清爽，但在面試的場合中，就很難用流暢的話語說明。反之，若平日已有這方面的練習，則面試過程中，才可充分展現自己專業之處。
:::
利用 `list.h` 裡的 `list_first_entry` 將第一個節點的位址取出，接著使用 `list_del_init` 移除頭節點後讓節點的前後相連
最後將移除的節點數值複製到 sp ，並且複製字串到 sp 時為其加上 null terminator 的空間
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *delement = list_first_entry(head, element_t, list);
list_del_init(head->next);
/*If sp is non-NULL and an element is removed, copy the removed string to
*sp (up to a maximum of bufsize-1 characters, plus a null terminator.)*/
if (sp) {
strncpy(sp, delement->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return delement;
}
```
### `q_remove_tail`
同 `q_remove_head` ，使用 `list_last_entry` 將最後一個節點的位址取出，並改用 `list_del_init(head->next);` 移除尾節點
```shell
l = [a b c d e]
cmd> rh
Removed a from queue
l = [b c d e]
cmd> rh
Removed b from queue
l = [c d e]
cmd> rt
Removed e from queue
l = [c d]
cmd> rt
Removed d from queue
l = [c]
```
### `q_size`
首先判斷佇列是否為空或不存在，再來用 `list.h` 中的 `list_for_each` 逐一走訪佇列中的每個節點並將長度數值 + 1
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int len = 0;
struct list_head *node;
list_for_each (node, head)
len++;
return len;
}
```
### `q_delete_mid`
參考第一周教材提到的[快慢指標](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List:~:text=%E7%9A%84%E6%8C%87%E6%A8%99%EF%BC%8C%E6%90%AD%E9%85%8D-,%E5%BF%AB%E6%85%A2%E6%8C%87%E6%A8%99,-%E7%9A%84%E6%8A%80%E5%B7%A7%E4%BE%86)來實作，在每次迴圈中 `fast` 都會比 `indir_slow` 移動兩倍的距離，直到 `fast` 或`fast->next` 指回 `head`，此時 `slow` 就會剛好在佇列中間的位置
接著使用 `list_del_init` 確保在移除目標節點後前後節點相連
最後利用 `list_entry` 找出目標節點並使用 `q_release_element` 釋放記憶體空間
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head **indir_slow = &head->next;
for (struct list_head *fast = head->next;
fast != head && fast->next != head; fast = fast->next->next)
indir_slow = &(*indir_slow)->next;
struct list_head *delement = *indir_slow;
list_del_init(delement);
q_release_element(list_entry(delement, element_t, list));
return true;
}
```
### `q_delete_dup`
為一個排序後的鏈結串列刪除所有有重複字串的節點
想法是使用 `list_for_each_entry_safe` 逐一走訪節點，且能得到當前的以及下一個 `element_t` 的位址
使用 strcmp 比對兩者的 `value` 是否相同，相同的話則透過 `list_del_init` 和 `q_release_element` 來移除並釋放該重複節點的記憶體空間
宣告一個變數 `flag` 用來確認如果字串相同，則在下一個迴圈就會以相同方法移除另一個重複的節點
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
但在做輸入 `gdb ./qtest` 測試後發現以下錯誤
```
l = [b a a]
cmd> dedup
Program received signal SIGSEGV, Segmentation fault.
__strcmp_avx2 () at ../sysdeps/x86_64/multiarch/strcmp-avx2.S:775
775 ../sysdeps/x86_64/multiarch/strcmp-avx2.S: No such file or directory.
```
:::danger
access 的翻譯是「存取」，而非「訪問」(visit)
>已更改
:::
意思是在呼叫 `strcmp` 函式時存取了無效的記憶體位址，檢查過後發現是當透過 `list_for_each_entry_safe` 走訪到最後一個節點時，該節點的 next 是指向 `head`，但 `head` 的型態是 `list_head`，所以它沒有 `value` 可以存取，進而發生 sagemetation fault
所以我多加了一個判斷式，判斷當前節點的下一個節點是否指向 `head`
```diff
list_for_each_entry_safe (element, next, head, list) {
- if (strcmp(element->value, next->value) == 0) {
+ if (&next->list != head && strcmp(element->value, next->value) == 0) {
list_del_init(&element->list);
q_release_element(element);
flag = true;
}
```
### `q_swap`
宣告 `cur` 指標指向 `head`，再宣告兩個指標指向第一個節點和第二個節點
在每次迴圈時將指標兩兩交換，並在迴圈結束前將兩個指標皆往後移動兩個節點，直到其中一個指標指向 `head`
要注意更新鏈結指標的順序，如果更新邏輯有誤可能會導致鏈結結構錯亂，例如重複處理節點或形成循環鏈結
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
```
l = [a b c d]
cmd> swap
l = [b a d c]
cmd> rh
Removed b from queue
l = [a d c]
cmd> swap
l = [d a c]
```
:::danger
改進你的漢語表達。
:::
### `q_reverse`
使用 `list_for_each` 走訪佇列，透過 `list_del` 將當前的節點移除，接著用 `list_add` 將其移至開頭，走訪完後即完成反轉，但是在測試報出以下錯誤訊息：
```
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
```
意思是形成了一個無窮迴圈，這個無窮迴圈導致程式運行時間超過了限制
後來想到了原因，首先 `list_for_each` 巨集如下：
```c
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
可以發現這個 `node` 指向的節點在被移至佇列開頭後，進入下個迴圈前仍然指向開頭節點的下一個節點。因此每次迴圈都會做佇列前二節點互相交換的操作，從而導致了一個無限循環。
所以使用 `list_for_each_safe` 走訪並透過 `safe` 儲存下個節點，在每次迴圈結束時 `node` 會指向 `safe`，就能透過 `node` 逐一將節點移至開頭，最後實作佇列反轉的效果
```diff
- list_for_each (cur, safe, head) {
+ list_for_each_safe (cur, safe, head) {
list_del(cur);
list_add(cur, head);
}
```
不過後來在 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#:~:text=delete%20from%20one%20list%20and%20add%20as%20another%27s%20head) 中找到其實可以只利用 `list_move` 來實作 `list_del` + `list_add` 的功能，所以修改函式進一步精簡程式碼
```diff
+ list_for_each_safe (cur, safe, head) {
- list_del(cur);
- list_add(cur, head);
+ list_move(cur, head);
}
```
```
l = [a b c d]
cmd> reverse
l = [d c b a]
```
### `q_reverseK`
將每一組的 k 個節點逐一移至最前面實作佇列反轉，接著迭代每一組
使用 `q_size` 紀錄佇列整體長度，來確保最後剩下不足 k 個節點不會做反轉排列，並透過間接指標 `reverse_node` 紀錄 `cur->next` 的位址，`tmp` 用來紀錄每一組的 `head`
:::danger
「當前」一詞可能會造成閱讀的困難。例如下面的「當前組」是「當 前面一組」，抑或「目前這組」呢？
你可回想國中和高中的教材中，「當前」出現次數較高，還是「目前」較高呢？若是後者較頻繁出現，為何你現在不依據中學教材的方式來書寫？
>已更改
:::
利用 `q_reverse` 做法為目前這組實作反轉後</s> ，此時 `cur` 會指向該組的最後一個節點，並將 `cur->next` 指派給 `cur`，此時 `cur` 就會指向下一組的第一個節點
所以下一次迭代就會從 `*reverse_node` 指向的節點開始逐一移至該組最前面，實作反轉
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head) || k < 2)
return;
int len = q_size(head);
for (struct list_head *cur = head->next; cur != head && cur->next != head;cur = cur->next) {
struct list_head **reverse_node = &cur->next, *tmp = cur->prev;
for (int i = 1; i < k; i++) {
if (len >= k)
list_move(*reverse_node, tmp);
}
len -= k;
}
}
```
### `q_sort`
在 trace-15-perf.cmd 的文件裡有提到測試 sort 要求時間複雜度必須為 $O(n\log{n})$ ，若使用像 bubble sort 這種時間複雜度為 $O(n^2)$ 的排序法會造成測試失敗，所以選擇 merge sort 以符合期待。
參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C) merge sort 的實作，我使用三個函式呈現
:::danger
你如何確保現有的測試方式/資料已涵蓋排序演算法的最差狀況？
:::
#### `q_sort`
執行 merge_sort 前要先將 `head` 斷開，使其變成單向鏈結串列來避免產生無窮迴圈
最後要再迭代一次排序後的鏈結串列，因為當前排序過後是單向鏈結串列，所以要將 `prev` 指標更新，也需將佇列的尾巴與開頭相互連結，讓其變回循環雙向鏈結串列，以維持 `list_head` 的型態
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = merge_sort(head->next);
struct list_head *cur = head, *n = head->next;
while (n) {
n->prev = cur;
cur = n;
n = n->next;
}
cur->next = head;
head->prev = cur;
}
```
#### `merge_sort`
如果鏈結串列為空或只包含一個節點，則直接返回。
先透過快慢指標的方法來尋找中間節點，再呼叫 `merge_list` 將第一個節點開頭的佇列及中間節點開頭的佇列，合併成一個有序的佇列。
其中 `slow->next = NULL;` 是必須要將第一個節點開頭的串列尾巴指向 `NULL`。
```c
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast, *slow = head;
for (fast = head->next; fast && fast->next; fast = fast->next->next) {
slow = slow->next;
}
struct list_head *left, *right;
right = slow->next;
slow->next = NULL;
left = merge_sort(head);
right = merge_sort(right);
return merge_list(left, right);
}
```
#### `merge_list`
使用 `list_entry` 可以取得 `left` 指向的 `struct list_head` 結構中 `element_t` 的指標，然後再透過 `element_t` 裡 `value` 的值做比較，比較後將 `value` 較小的放到新的佇列裡，然後將 `ptr` 移至下一個位置，當迭代完成後，將剩下的節點加入佇列
運用 indirect pointer 的技巧避免佇列合併過程中創建額外節點的記憶體空間
```c
struct list_head *merge_list(struct list_head *left, struct list_head *right)
{
struct list_head *head = NULL, **ptr = &head;
for (; left && right; ptr = &(*ptr)->next) {
if (strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) < 0) {
*ptr = left;
left = left->next;
} else {
*ptr = right;
right = right->next;
}
}
if (left) {
*ptr = left;
} else {
*ptr = right;
}
return head;
}
```
執行結果
```
cmd> new
l = []
cmd> ih RAND 5
l = [rmlts bgxaxcfpq ldienge rrspzs mrvlz]
cmd> sort
l = [bgxaxcfpq ldienge mrvlz rmlts rrspzs]
```
### `q_ascend`
題目是說如果目刪除具有較小值在右側的節點，結果為升序的佇列。
一開始的想法是利用從佇列的第一個節點開始比對右側的每個節點，但這個方法會用到雙層迴圈，不過思考後發現可以從佇列尾端比對，只需要單層迴圈即可
方法是先利用 `q_reverse` 將佇列反轉，以 `min` 儲存最小值，並用 `list_for_each_entry_safe` 逐一比對當前節點與 `min` 的大小，如果比 `min` 大就刪掉，否則將其指派給 `min`
最後的結果會是降序的佇列，所以要再用 `q_reverse` 將其反轉回來
```c
int q_ascend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
element_t *cur, *safe;
q_reverse(head);
char *min = list_entry(head->next, element_t, list)->value;
list_for_each_entry_safe (cur, safe, head, list) {
if (strcmp(cur->value, min) > 0) {
list_del_init(&cur->list);
q_release_element(cur);
} else {
min = cur->value;
}
}
q_reverse(head);
return q_size(head);
}
```
```
l = [6 1 5 3 2 4]
cmd> ascend
l = [1 2 4]
```
不過在與 [ollieni](https://hackmd.io/@NIYINGCHIH) 討論時發現 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#:~:text=of%20list%20entry.-,list_for_each_entry_safe_reverse,-%C2%B6) 裡面的 `list_for_each_entry_safe_reverse` 可以實作從佇列尾端走訪，但 `list.h` 裡並沒有看到相關實作，不過可以將 `list_for_each_entry_safe` 巨集裡面的所有 `->next` 改成 `->prev` 實作相同功能，以省去我原本還要將佇列做兩次反轉的方法
### `q_descend`
與 `q_ascend` 做法類似，只差在刪除的是具有較大值在右側的節點
```
l = [f d b a c]
cmd> descend
l = [f d c]
```
### `q_merge`
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_0 {
node [shape=record];
head_c [label="head|{<prev>prev|<next>next}"];
size0 [label="{size}"];
style=bold;
label=queue_chain_t
}
head_c:next:e -> chain:w
chain:prev:w -> head_c:e
chain:next->head_c:x
head_c:prev->chain:x
subgraph cluster_1 {
node [shape=record];
q [label="q"];
chain [label="chain|{<prev>prev|<next>next}"];
size1 [label="{size}"];
id [label="{id}"];
style=bold;
label=queue_contex_t
}
head [label="head|{<prev>prev|<next>next}"];
q:right:e -> head:n
subgraph cluster_2 {
node [shape=record];
value [label="{value}"];
head_e [label="head|{<prev>prev|<next>next}"];
style=bold;
label=element_t
}
head:next:e -> head_e:w
head_e:prev:w -> head:e
head_e:next -> head:s
head:prev -> head_e:s
}
```
從 `queue.h` 可以了解 `queue_contex_t` 的架構描述
* `q` 用來指向 queue 的 head
* `chain` 用來將每一個 `queue_contex_t` 結構串連起來
* `size` 表示這個 queue 的長度
* `id` 表示每一個 queue 唯一的編號
接著從 `qtest.c` 發現有宣告 `queue_chain_t` 的結構，並從`do_new` 函式可以發現，他是用來當 `queue_contex_t` 結構的 `head`，並且每次配置一個新的 `queue_contex_t` 結構的記憶體空間，都會將此結構插入到佇列的尾端
同時在 `qtest.c` 的 `do_merge` 函式可以發現它傳入的參數是 `queue_chain_t` 結構的 head，因為 `qtest.c` 裡面有宣告 `q_chain_t` 的結構，所以邊界條件不用判斷 `!head`，所以設置 `list_empty(head)` 與 `list_is_singular(head)` 為邊界條件即可
想法就是逐一將所有佇列合併到第一個佇列，與 `q_sort` 差不多，執行 `merge_list` 前要先將 `head` 斷開，使其變成單向鏈結串列來避免產生無窮迴圈，最後要再迭代一次排序後的佇列，讓他變回循環雙向鏈結串列
其中要加上 `INIT_LIST_HEAD(pos->q)` 將原本的串列做初始化
```
l = [a e m]
l = [b o r]
l = [c d r]
cmd> merge
l = [a b c d e m o r r]
```
## 在 `qtest` 提供新的命令 `shuffle`
參考 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行 shuffle，做法是從 1 到 n 之間隨機出一個數字和最後一個數 n 交換，然後從 1 到 n-1 之間隨機出一個數和倒數第二個數 n-1 交換..
假設有一長度為 $n$ 的陣列，其洗牌演算法的條件：
* 會有 $n!$ 種不同的排列組合
* 必須可以產生出每一種結果
* 所有結果出現的機率相等
此為提供的 pseudocode
```c
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
在 `queue.c` 按照上述程式碼實作 `q_shuffle`
迴圈從佇列最後一個元素開始，每次迭代皆會隨機挑一個數並以 `cur` 指標紀錄節點位置，接著將其數值與 `end` 的數值做交換
`end` 會透過 `end = end->prev` 紀錄每次迭代最後一個節點的位置。
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *end = head->prev;
for (int i = q_size(head); i > 0; i--) {
int ran = rand() % i;
struct list_head *cur = head;
for (int j = 0; j <= ran; j++) {
cur = cur->next;
}
swap(list_entry(cur, element_t, list),
list_entry(end, element_t, list));
end = end->prev;
}
}
```
交換節點數值的方法透過以下 `swap` 函式來執行
```c
void swap(element_t *n1, element_t *n2)
{
char *tmp = n1->value;
n1->value = n2->value;
n2->value = tmp;
}
```
接著在 `qtest.c` 裡的 `console_init` 中加上以下新命令，並寫一個 `do_shuffle` 呼叫我們實作的 `q_shuffle`
```c
ADD_COMMAND(shuffle, "Shuffle the nodes of the queue", "");
```
不過在我編譯時出現以下錯誤：
```
qtest.c: In function ‘do_shuffle’:
qtest.c:1027:9: error: implicit declaration of function ‘q_shuffle’; did you mean ‘do_shuffle’? [-Werror=implicit-function-declaration]
```
意思是編譯器在 `do_shuffle` 中找不到 `q_shuffle` 函式的聲明，並將其視為一個隱式函式聲明，所以導致編譯錯誤
:::danger
file 的翻譯是「檔案」，而非「文件」(document)
>已更改
:::
後來我在 `qtest.c` 檔案中添加 `void q_shuffle(struct list_head *head);`，這樣編譯器就可以找到這個函式的聲明，並正確地編譯 `do_shuffle`
```
cmd> new
l = []
cmd> ih RAND 8
l = [fvthxutit raywmvk pkylr qijibeiyd vjxyloj vggmsyzyb hnwspnomd cmisexmr]
cmd> shuffle
l = [pkylr vjxyloj vggmsyzyb raywmvk hnwspnomd fvthxutit qijibeiyd cmisexmr]
cmd> shuffle
l = [qijibeiyd cmisexmr hnwspnomd fvthxutit vggmsyzyb raywmvk pkylr vjxyloj]
```
---
### 以統計的原理來分析你的實作
根據作業說明：[統計方法驗證 shuffle](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d#%E7%B5%B1%E8%A8%88%E6%96%B9%E6%B3%95%E9%A9%97%E8%AD%89-shuffle)
將測試程式新增到 `scripts/shuffle.py`
#### 1. 先計算 chi-squared test statistic
$X^2 = \sum_{i=1}^n {(O_i - E_i)^2 \over E_i}$
執行 `$ python3 scripts/shuffle.py`
在測試 shuffle 1000000 次後，24種結果各自的頻率如下表：
|排列組合| 觀察到的頻率| 期待的頻率 |   ${(O_i - E_i)^2 \over E_i}$|
|--------|--------|--------|------|
|[1, 2, 3, 4]|41,432|41,666|1.31416502664|
|[1, 2, 4, 3]|41,588|41,666|0.14601833629|
|[1, 3, 2, 4]|41,972|41,666|2.24729995680|
|[1, 3, 4, 2]|41,910|41,666|1.42888686219|
|[1, 4, 2, 3]|41,562|41,666|0.25958815341|
|[1, 4, 3, 2]|41,637|41,666|0.02018432294|
|[2, 1, 3, 4]|41,607|41,666|0.08354533672|
|[2, 1, 4, 3]|41,544|41,666|0.35722171554|
|[2, 3, 1, 4]|41,860|41,666|0.90327845245|
|[2, 3, 4, 1]|41,403|41,666|1.66008256132|
|[2, 4, 1, 3]|41,900|41,666|1.31416502664|
|[2, 4, 3, 1]|41,338|41,666|2.58205731292|
|[3, 1, 2, 4]|41,522|41,666|0.49767196275|
|[3, 1, 4, 2]|41,759|41,666|0.20757932126|
|[3, 2, 1, 4]|41,841|41,666|0.73501176018|
|[3, 2, 4, 1]|41,568|41,666|0.23049968799|
|[3, 4, 1, 2]|41,556|41,666|0.29040464647|
|[3, 4, 2, 1]|42,060|41,666|3.72572361158|
|[4, 1, 2, 3]|41,691|41,666|0.01500024000|
|[4, 1, 3, 2]|41,730|41,666|0.09830557288|
|[4, 2, 1, 3]|41,708|41,666|0.04233667738|
|[4, 2, 3, 1]|41,640|41,666|0.01622425958|
|[4, 3, 1, 2]|41,502|41,666|0.64551432822|
|[4, 3, 2, 1]|41,670|41,666|0.00038400614|
|Total|||18.1624633994|
$X^2$ = 18.1624633994
#### 2. 決定自由度（degrees of freedom）
對於 N 個隨機樣本而言，自由度為 N - 1
而本次實驗有 24 個結果，故自由度為 23
#### 3. 選擇顯著水準
從 [Chi-Square Distribution Table](https://www.oreilly.com/library/view/making-sense-of/9780470074718/appa-sec003.html) 找合適的 P value，我們的自由度為23
可看到 17.187 < 18.1624633994 < 19.021，所以其 P value 介於 0.7 和 0.8 之間
而 $\alpha$ 設為常見的 0.05
#### 4. 統計檢定的結果不拒絕虛無假說
對於要拒絕的虛無假說（$H_0$），觀察到的結果必須具有統計顯著性，即觀察到的 P value 要小於預先指定的顯著水準 $\alpha$
因為 P value（0.7~0.8）> $\alpha$（0.05），統計檢定的結果不拒絕虛無假說（$H_0$）
從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的
---
## 研讀 Linux 核心原始程式碼的 `lib/list_sort.c`
閱讀 [Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e) , [`list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 以及 [linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list)
#### `list_sort`
一開始會將鏈結串列透過 `head->prev->next = NULL;` 將頭尾分開
另外在註解中有提到：
```
* - All lists are singly linked and null-terminated; prev
* pointers are not maintained.
```
意思是說雖然輸入的是循環雙向鏈結串列，但在此函式裡會將其視為單向的
相關變數宣告為以下：
```c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0;
```
將 head 的第一個節點指派給 list，然後將 pending 指向 NULL
之後會進入 do while 迴圈，他會一步步把 list 裡面的節點移到 pending 中，並將 count +1，直到 list 為空，而 list 和 pending 分別為：
* list：原始未排序的鏈結串列，且隨著 while 迴圈一步步減少節點數
* pending：為 **list of lists**，可理解為「串起來的串列」，lists 代表已合併且排序好的串列，list 則是將這些 **lists** 串起來的串列
一開始會看到以下 for 迴圈，他的用途是讓 tail 往前移動到要 merge 的位置，而移動的條件是根據 count 的二進制值最小位有多少連續的 1 來移動 tail 多少步
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
在 for 迴圈執行期間， bits 會慢慢向右移一個位元，所以當迴圈跑完後最小位全部連續的 1 會不見，下表為範例：
| count | count 二進位 | tail 往前移動步數 | bits 二進位值在迴圈跑完後|
| ----------- | --------- | ----------- | -------|
| 0 | 0000 | 0 | 0000 |
| 1 | 000==1== | 1 | 0000 |
| 2 | 0010 | 0 | 0010 |
| 3 | 00==11== | 2 | 0000 |
| 4 | 0100 | 0 | 0100 |
| 5 | 010==1== | 1 | 0010 |
| 6 | 0110 | 0 | 0110 |
| 7 | 0==111== | 3 | 0000 |
再來會根據 `if(bits)` 判斷是否該在 pending 上進行合併 ( merge )，並依 tail 移動的步數來判斷要合併哪兩個串列，最後從 list 新增一個節點，以下表例：
| count | tail 往前移動步數 | bits | pending 狀態
| ------ | ------ | ----- | -------|
| 0 | 0 | 0000 | 從 list 新增一節點
| 1 | 1 | 0000 | 從 list 新增一節點
| 2 | 0 | ==0010== | 合併第 0 跟第 1 個串列，並從 list 新增一節點
| 3 | 2 | 0000 | 從 list 新增一節點
| 4 | 0 | ==0100== | 合併第 0 跟第 1 個串列，並從 list 新增一節點
| 5 | ==1== | ==0010== | 合併第 1 跟第 2 個串列，並從 list 新增一節點
| 6 | 0 | ==0110== | 合併第 0 跟第 1 個串列，並從 list 新增一節點
| 7 | 3 | 0000 | 從 list 新增一節點
以下圖例是 do while 根據 count 值，list 和 pending 的狀態：
一開始：
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
null[label=NULL,shape=none]
{rank="same"; list}
{rank="same"; pend}
pend [label="pending", shape="plaintext"]
list [label="list", shape="plaintext"]
node6 [label="6|{<left>prev|<right>next}"]
node9 [label="9|{<left>prev|<right>next}"]
node11 [label="11|{<left>prev|<right>next}"]
node2 [label="2|{<left>prev|<right>next}"]
node15 [label="15|{<left>prev|<right>next}"]
node5 [label="5|{<left>prev|<right>next}"]
node1 [label="1|{<left>prev|<right>next}"]
node13 [label="13|{<left>prev|<right>next}"]
pend -> null
node6:right:e -> node9:w
node9:right:e -> node11:w
node11:right:e -> node2:w
node2:right:e -> node15:w
node15:right:e -> node5:w
node5:right:e -> node1:w
node1:right:e -> node13:w
list -> node6:n
}
```
count = 0
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
{rank="same"; list}
{rank="same"; pend}
pend [label="pending", shape="plaintext"]
list [label="list", shape="plaintext"]
node6 [label="6|{<left>prev|<right>next}"]
node9 [label="9|{<left>prev|<right>next}"]
node11 [label="11|{<left>prev|<right>next}"]
node2 [label="2|{<left>prev|<right>next}"]
node15 [label="15|{<left>prev|<right>next}"]
node5 [label="5|{<left>prev|<right>next}"]
node1 [label="1|{<left>prev|<right>next}"]
node13 [label="13|{<left>prev|<right>next}"]
pend -> node6:n
node9:right:e -> node11:w
node11:right:e -> node2:w
node2:right:e -> node15:w
node15:right:e -> node5:w
node5:right:e -> node1:w
node1:right:e -> node13:w
list -> node9:n
}
```
count = 1
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
{rank="same"; list}
{rank="same"; pend}
pend [label="pending", shape="plaintext"]
list [label="list", shape="plaintext"]
node9 [label="9|{<left>prev|<right>next}"]
node6 [label="6|{<left>prev|<right>next}"]
node11 [label="11|{<left>prev|<right>next}"]
node2 [label="2|{<left>prev|<right>next}"]
node15 [label="15|{<left>prev|<right>next}"]
node5 [label="5|{<left>prev|<right>next}"]
node1 [label="1|{<left>prev|<right>next}"]
node13 [label="13|{<left>prev|<right>next}"]
pend -> node9:n
node9:left:s -> node6:n
node11:right:e -> node2:w
node2:right:e -> node15:w
node15:right:e -> node5:w
node5:right:e -> node1:w
node1:right:e -> node13:w
list -> node11:n
}
```
count = 2 ( 紅色為執行 merge )
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
{rank="same"; list}
{rank="same"; pend}
pend [label="pending", shape="plaintext"]
list [label="list", shape="plaintext"]
node9 [label="9|{<left>prev|<right>next}", color=red]
node6 [label="6|{<left>prev|<right>next}", color=red]
node11 [label="11|{<left>prev|<right>next}"]
node2 [label="2|{<left>prev|<right>next}"]
node15 [label="15|{<left>prev|<right>next}"]
node5 [label="5|{<left>prev|<right>next}"]
node1 [label="1|{<left>prev|<right>next}"]
node13 [label="13|{<left>prev|<right>next}"]
pend -> node11:n
node11:left:s -> node6:n
node6:right -> node9
node2:right:e -> node15:w
node15:right:e -> node5:w
node5:right:e -> node1:w
node1:right:e -> node13:w
list -> node2:n
}
```
count = 3 ( 藍色為已排序的串列 )
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
{rank="same"; list}
{rank="same"; pend}
pend [label="pending", shape="plaintext"]
list [label="list", shape="plaintext"]
node9 [label="9|{<left>prev|<right>next}",color=blue]
node6 [label="6|{<left>prev|<right>next}",color=blue]
node11 [label="11|{<left>prev|<right>next}"]
node2 [label="2|{<left>prev|<right>next}"]
node15 [label="15|{<left>prev|<right>next}"]
node5 [label="5|{<left>prev|<right>next}"]
node1 [label="1|{<left>prev|<right>next}"]
node13 [label="13|{<left>prev|<right>next}"]
pend -> node2:n
node2:left:s ->node11:n
node11:left:s -> node6:n
node6:right -> node9
node15:right:e -> node5:w
node5:right:e -> node1:w
node1:right:e -> node13:w
list -> node15:n
}
```
count = 4
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
{rank="same"; list}
{rank="same"; pend}
pend [label="pending", shape="plaintext"]
list [label="list", shape="plaintext"]
node9 [label="9|{<left>prev|<right>next}",color=blue]
node6 [label="6|{<left>prev|<right>next}",color=blue]
node11 [label="11|{<left>prev|<right>next}", color=red]
node2 [label="2|{<left>prev|<right>next}", color=red]
node15 [label="15|{<left>prev|<right>next}"]
node5 [label="5|{<left>prev|<right>next}"]
node1 [label="1|{<left>prev|<right>next}"]
node13 [label="13|{<left>prev|<right>next}"]
pend -> node15:n
node15:left:s -> node2:n
node2:right ->node11
node11:left:s -> node6:n
node6:right -> node9
node5:right:e -> node1:w
node1:right:e -> node13:w
list -> node5:n
}
```
count = 5
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
{rank="same"; list}
{rank="same"; pend}
pend [label="pending", shape="plaintext"]
list [label="list", shape="plaintext"]
node9 [label="9|{<left>prev|<right>next}", color=red]
node6 [label="6|{<left>prev|<right>next}", color=red]
node11 [label="11|{<left>prev|<right>next}", color=red]
node2 [label="2|{<left>prev|<right>next}", color=red]
node15 [label="15|{<left>prev|<right>next}"]
node5 [label="5|{<left>prev|<right>next}"]
node1 [label="1|{<left>prev|<right>next}"]
node13 [label="13|{<left>prev|<right>next}"]
pend -> node5:n
node5:left:s -> node15:n
node15:left:s -> node2:n
node2:right -> node6
node6:right -> node9
node9:right -> node11
node1:right:e -> node13:w
list -> node1:n
}
```
count = 6
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
{rank="same"; list}
{rank="same"; pend}
pend [label="pending", shape="plaintext"]
list [label="list", shape="plaintext"]
node9 [label="9|{<left>prev|<right>next}",color=blue]
node6 [label="6|{<left>prev|<right>next}",color=blue]
node11 [label="11|{<left>prev|<right>next}",color=blue]
node2 [label="2|{<left>prev|<right>next}",color=blue]
node15 [label="15|{<left>prev|<right>next}", color=red]
node5 [label="5|{<left>prev|<right>next}", color=red]
node1 [label="1|{<left>prev|<right>next}"]
node13 [label="13|{<left>prev|<right>next}"]
pend -> node1:n
node1:left:s -> node5:n
node5:right -> node15
node15:left:s -> node2:n
node2:right -> node6
node6:right -> node9
node9:right -> node11
list -> node13:n
}
```
count = 7
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
{rank="same"; list}
{rank="same"; pend}
pend [label="pending", shape="plaintext"]
list [label="list", shape="plaintext"]
node9 [label="9|{<left>prev|<right>next}",color=blue]
node6 [label="6|{<left>prev|<right>next}",color=blue]
node11 [label="11|{<left>prev|<right>next}",color=blue]
node2 [label="2|{<left>prev|<right>next}",color=blue]
node15 [label="15|{<left>prev|<right>next}",color=blue]
node5 [label="5|{<left>prev|<right>next}",color=blue]
node1 [label="1|{<left>prev|<right>next}"]
node13 [label="13|{<left>prev|<right>next}"]
pend -> node13:n
node13:left:s -> node1:n
node1:left:s -> node5:n
node5:right -> node15
node15:left:s -> node2:n
node2:right -> node6
node6:right -> node9
node9:right -> node11
}
```
#### `merge` & `merge_final`
兩者的共通點都是將兩個已排序好的串列做合併。
但差別就是 `merge_final` 會重建 `prev` 指標的鏈接，將結果轉換為一個循環雙向鏈結串列，在 list 為空時執行。
在 list_sort.c 裡面有用到 `__attribute__((nonnull))` 這個函式屬性
* 此屬性用於告訴 compiler 該函式的某些參數不能為 NULL。
* 在 list_sort.c 的例子中，`__attribute__((nonnull(2,3,4)))` 表示 compiler 可以對第 2、3、4 個參數為 NULL 時發出警告。
以及 `likely` `unlikely` 這兩個巨集，他們被定義在 [/include/linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 中
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
* `__built_expect()`是 gcc 的內建函式，用來將 branch 的相關資訊提供給 compiler，告訴 compiler 設計者期望的比較結果，以便對程式碼改變分支順序來進行優化
* 而這兩個巨集，可以讓 compiler 在編譯 assembly code 的時候做一些最佳化，可以告訴 compiler 某段 if 敘述為 true 的機率較高或低，讓 compiler 把對應程式碼接在判斷的後面
* 如果程式碼被放到比較相近的位置，那他們就可能一起被搬到 cache 中，使 cache hit 機率上升，就有可能提升程式的執行效能。
:::warning
翻閱計算機組織/結構的教科書，從 branch prediction 的角度去確認上述說法。
:::
### 嘗試引入到 `lab0-c` 專案
:warning: 品質是價值與尊嚴的起點
創建並複製 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 程式碼到 lab0-c
另外 list_sort.c 裡面有使用到下列兩個巨集，所以也需要加入到程式碼開頭
```c
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
```
接著將宣告 list_cmp_func_t 的定義加入到程式碼開頭
```c
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
const struct list_head *, const struct list_head *);
```
* 為一個 Function Pointer ，並且第二以及第三個參數不能為 NULL
根據 list_sort.c 裡的註解實作 `cmp_function`
>The comparison function @cmp must return > 0 if @a should sort after
@b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
sort before @b *or* their original order should be preserved.
* if (a > b) return > 0
* if (a < b) return <= 0 或保留其原本排序
* list_sort 是 **stable sort**，所以沒必要區分 a < b 和 a == b 的情況
```c
int cmp_function(void *priv, const struct list_head *a, const struct list_head *b)
{
element_t *a_entry = list_entry(a, element_t, list);
element_t *b_entry = list_entry(b, element_t, list);
if (strcmp(a_entry->value, b_entry->value) <= 0)
return 0;
else
return 1;
}
```
參照 qtest.c 裡的 `do_sort` 函式實作 `do_linux_sort`。
與實作 `q_shuffle` 一樣的做法，因為要執行 `list_sort(NULL, current->q, cmp_function);`，所以要添加下列函式聲明才可以正確編譯 `do_linux_sort`。
```c
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
```
最後從 `qtest.c` 裡的 `console_init` 加入新命令
```c
ADD_COMMAND(linux_sort, "Linux Sort queue in ascending/descening order", "");
```
不過在編譯時出現以下錯誤訊息：
```
error: unknown type name ‘u8’
```
在 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的第 56 行有宣告一個型態為 u8 的變數，意思是 **unsigned 8-bit integer**，被定義在 [/tools/include/linux/types.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/types.h) 裡，我的做法是直接自己定義
```c
typedef unsigned char u8;
```
在 `Makefile` 中，`OBJS` 變數通常用來存放需要編譯的目標檔案。當新增一個 `list_sort.c` 檔案後，需要將 `list_sort.o` 加入到 `OBJS` 變數中。
```diff
- OBJS := qtest.o report.o console.o harness.o queue.o\
+ OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o\
```
這樣在執行 `make` 命令時，`list_sort.c`才會被編譯成`list_sort.o`目標檔案。
```
cmd> new
l = []
cmd> ih RAND 10
l = [lrwuv zvwqvcdc bqlunk uptmb mgrqphizi fwifqt abwfjcil vtysowf gusbrqrzv lizyyagzl]
cmd> linux_sort
l = [abwfjcil bqlunk fwifqt gusbrqrzv lizyyagzl lrwuv mgrqphizi uptmb vtysowf zvwqvcdc]
```
### 比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
閱讀並學習如何使用 [Perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg#perf)
在 [perf stat](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg#perf-stat) 提供的範例中提到將 `array[i][j]++` 的 i，j 對調改成 `array[i][j]++` 會同時降低許多 cache reference 和 cache miss 次數，主要是因為：
* 多維陣列通常是以 **Row-major** 的方式儲存在記憶體中
* 在改進程式後的資料讀取方式從原本 column-major 變成 row-major，好處是因為他利用了**空間局部性** (Spatial locality) 的優點
>空間局部性：當一個記憶體區塊被載入快取時，相鄰的區塊也很可能會被載入。
* 當程式能夠利用空間局部性的優點時，除了能減少 cache-reference 次數外，命中率也會上升，而不須從 main memory 中重新載入
* 無論是 cache reference 還是 cache miss，都是需要花費時間的，只差在時間長短，因此將兩者次數降低相對也代表著執行時間更短
學習如何寫 [shell scripts](https://linux.vbird.org/linux_basic/centos7/0340bashshell-scripts.php)，優點是可以一次執行多個命令
首先新增 `test_linux_sort.sh` 和 `test_sort.sh` 兩個 shell scripts 用來執行效能測試
```bash
#!/bin/bash
for i in ./traces/traces_perf_linux_sort/*.cmd
do
perf stat --repeat 5 -o "${i%.cmd}"_report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i"
done
```
檢測的項目有 cache-misses, branches, instructions 和 context-switches
接著在 `./lab0-c/traces` 新增以下兩個目錄，分別存放用來測試 `linux_sort` 與 `sort` 的命令檔
```
.
├── traces_perf_linux_sort
│ ├── RAND_1000.cmd
│ ├── RAND_10000.cmd
│ ├── RAND_100000.cmd
│ └── RAND_1000000.cmd
└── traces_perf_sort
├── RAND_1000.cmd
├── RAND_10000.cmd
├── RAND_100000.cmd
└── RAND_1000000.cmd
```
`RAND_1000.cmd` 內容：
```cmd
option fail 0
option malloc 0
new
ih RAND 1000
linux_sort
free
```
輸入 `chmod u+x *.sh` 為 `.sh` 檔設定執行權限，否則會遇到 `Permission denied`
最後輸入 `./test_linux_sort.sh` 就會在 traces_perf_linux_sort 目錄下為每個 cmd 檔新增一個 report，點開後即可看到以下效能分析內容
```
# started on Wed Mar 27 21:22:44 2024
Performance counter stats for './qtest -v 0 -f ./traces/traces_perf_linux_sort/RAND_1000.cmd' (5 runs):
8422 cache-misses ( +- 23.38% )
84,9436 branches ( +- 0.09% )
582,1613 instructions ( +- 0.07% )
0 context-switches
0.0010624 +- 0.0000258 seconds time elapsed ( +- 2.43% )
```
實驗結果
**sort**
| # node | cache-misses | branches | instructions | context-switches | time |
|:------:|:-----------:|:--:|:--:|:--:|:--:|
|1000|1,2426|85,7773|578,5872|0|0.0011827|
|10000|7,2960|636,5969|4503,6733|0|0.007541|
|100000|436,9531|6447,4547|4,5055,1876|10|0.1036|
|1000000|9829,0049|6,7463,1160|46,2739,7185|8|1.2517|
**list_sort**
| # node | cache-misses | branches | instructions | context-switches | time |
|:------:|:-----------:|:--:|:--:|:--:|:--:|
|1000|8422|84,9436|582,1613|0|0.0010624|
|10000|3,2865|629,6853|4570,8874|0|0.0063344|
|100000|226,5870|6387,2396|4,5985,1778|1|0.078921|
|1000000|7861,2101|6,6845,0006|47,4151,1080|7|1.1422|
在 [Linux 核心的 list_sort 實作](https://hackmd.io/@sysprog/c-linked-list#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-list_sort-%E5%AF%A6%E4%BD%9C:~:text=linux%20kernel%20lists-,Linux%20%E6%A0%B8%E5%BF%83%E7%9A%84%20list_sort%20%E5%AF%A6%E4%BD%9C,-%E5%9C%A8%20linux/list_sort) 提到，除了 list_sort 是以 bottom up 來實作之外，他相較於一般的 merge_sort 擁有更有效利用 cache 的合併方式，合併時機是當有 $3 \times 2^k$ 個節點時會合併前兩個 $2^k$，使其維持著合併：不合併為 2：1 的比例，這樣更能實現空間局部性。
所以從空間局部性來看，list_sort 可以使 cache 中現存的資料更容易被用到，所以 cache miss 在節點數量越多時的差距會越來越大，進而影響執行時間。而 merge sort 通常需要額外的記憶體空間來儲存很多個子串列，然後一次合併，這時通常會發生很多 cache-misses，在空間局部性的表現上較差，甚至導致 cache trashing。
branch 次數的部份，list_sort 是使用迭代的算法，它通常較少涉及到函式的重複呼叫，只透過循環來完成任務，這相較於一般 merge_sort 遞迴的算法 branch 次數會更少，因為遞迴的本質是將大問題分解成小問題，但這會重複呼叫同個函式比較多次
## 將 [jserv/ttt](https://github.com/jserv/ttt) 專案的程式碼部分整合進 lab0-c
Sign in with Wallet
Connect another wallet