# 2024q1 Homework1 (lab0)
contributed by < [`Lccgth`](https://github.com/Lccgth) >
:::danger
修正 GitHub 超連結
:::
### Reviewed by `lintin528`
在 `list_sort` 、 `timsort` 、 `q_sort` 的比較中，除了執行時間上的不同可以嘗試使用 [perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 來分析 `cache` 的使用狀況，觀察各個演算法的特性。
## 開發環境
```shel
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 1
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-9700KF CPU @ 3.60GH
z
Stepping: 13
CPU MHz: 3600.000
CPU max MHz: 4900.0000
CPU min MHz: 800.0000
BogoMIPS: 7200.00
L1d cache: 256 KiB
L1i cache: 256 KiB
L2 cache: 2 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-7
```
## 實作佇列操作的程式碼
```c
#include "list.h"
```
:::danger
file 的翻譯是「檔案」，而非「文件」(document)
> 好的，已修正！
:::
我注意到 `queue.c` <s>文件</s> 檔案原先未包含 `list.h` 標頭檔，而 struct list_head 的宣告位於 `list.h` 中。為了解決這一問題，我在 `queue.c` 檔案開頭添加包含 `list.h` 的<s>指令</s> 敘述 (statement)。
### `q_new()`
> commit [3b96677](https://github.com/Lccgth/lab0-c/commit/3b966776436ae2aae7236e3f9087d9d6d764390d)
建立一個空的佇列，並且如果記憶體配置失敗就返回 NULL。
先配置記憶體空間給`head`，並檢查是否成功配置，接著使用函式 `INIT_LIST_HEAD()`將 `head->next` 和 `head->prev` 都指向 `head`。
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
```
:::danger
將「目標」和「實作」手法置於本段落前方。
> 好的，已修正！
:::
### `q_free()`
> commit [f3a5ab7](https://github.com/Lccgth/lab0-c/commit/f3a5ab76512ee45819e634fb980200474518b0f6), commit [33e05ca](https://github.com/Lccgth/lab0-c/commit/33e05ca64d024b94eb26e2bec5c5db2442a3e04b)
釋放所有佇列使用到的記憶體空間。
先檢查佇列（`head`）是否存在，接著逐一走訪佇列中的節點，紀錄每個節點的 entry，再從佇列中移除此節點、釋放`entry`。
```diff
list_for_each_safe (cur, temp, head) {
element_t *entry = list_entry(cur, element_t, list);
list_del(cur);
- free(entry->value);
- free(entry);
+ q_release_element(entry);
}
free(head);
```
### `q_insert_head()`
> commit [f4608c6](https://github.com/Lccgth/lab0-c/commit/f4608c6fb3ca332b416202e35a4302cc37ff3478)
在佇列的開頭處插入一個節點。
先檢查佇列（`head`）是否存在，和輸入的`s`字串是否有效。然後為新節點配置記憶體空間，並驗證配置是否成功。接著為字串配置記憶體並進行複製。如果配置失敗，則釋放已配置的節點記憶體。最後將新節點插入到佇列的開頭處。
```c
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
element->value = strdup(s);
if (!element->value) {
free(element);
return false;
}
list_add(&element->list, head);
```
### `q_insert_tail()`
> commit [7efac73](https://github.com/Lccgth/lab0-c/commit/7efac737b291fd18ca35c66c97be165cf45db930)
在佇列的尾部插入一個節點。
與`q_insert_head()`大致相同，只須將`list_add()`替換成`list_add_tail()`。
```diff
- list_add(&element->list, head);
+ list_add_tail(&element->list, head);
```
### `q_remove_head()`
> commit [6229a62](https://github.com/Lccgth/lab0-c/commit/6229a62e978ea1631044ee0e213a53ab4ab48f0d)
移除佇列開頭處的節點。
先檢查佇列（`head`）是否存在，和是否為空，接著將字串複製到`sp`中，最後將節點移除
```c
if (sp) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del_init(&entry->list);
```
### `q_remove_tail()`
> commit [cc82605](https://github.com/Lccgth/lab0-c/commit/cc826056ea0261126f2e8f825ead15bacef47155)
移除佇列尾部的節點。
與 `q_insert_head()` 大致相同，只須將`list_first_entry()`替換成 `list_last_entry()`。
```diff
- element_t *entry = list_first_entry(head, element_t, list);
+ element_t *entry = list_last_entry(head, element_t, list);
```
### `q_size()`
> commit [88d6c73](https://github.com/Lccgth/lab0-c/commit/88d6c73e2966fb73d76c70625cfa728f1d1ce337)
計算佇列的大小。
先處理`head`為空的情況，接著逐一走訪每個節點，由此計算佇列的大小。
```c
list_for_each (li, head)
len++;
```
### `q_delete_mid()`
> commit [39e784f](https://github.com/Lccgth/lab0-c/commit/39e784f729c02d50992233a9fcd15e8397d4be28)
刪除佇列裡中間的節點。
先檢查佇列（`head`）是否存在，和是否為空，接著使用快慢指標找到佇列中間的節點，最後將其刪除
```c
while (fast->next != head && fast->next->next != head) {
slow = slow->next;
fast = fast->next->next;
}
element_t *entry = list_entry(slow, element_t, list);
list_del(slow);
q_release_element(entry);
```
:::warning
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
> 了解，已進行修改！
:::
### `q_delete_dup()`
> commit [b215517](https://github.com/Lccgth/lab0-c/commit/b2155172b4b5637ec84f73a1f81fc294c22fb7c9)
刪除佇列中有重複字串的節點。
逐一走訪每個節點，若目前節點和下一個節點的字串相同，則刪除目前節點，如果不相同的話，利用 `dup` 標籤檢查此節點的字串有沒有出現過，是否要進行刪除。
```c
list_for_each_safe (node, safe, head) {
if (safe != head && !strcmp(node_entry->value, safe_entry->value)) {
dup = true;
list_del(node);
q_release_element(node_entry);
} else if (dup) {
dup = false;
list_del(node);
q_release_element(node_entry);
}
}
```
:::warning
TODO: 撰寫出更精簡的程式碼。
:::
### `q_swap()`
> commit [8226559](https://github.com/Lccgth/lab0-c/commit/82265591384a588f698ff13f492a3a1350df5c38), commit [f4c7aab](https://github.com/Lccgth/lab0-c/commit/f4c7aab4ed8535cb3bda98d4f05aebad76047a4e)
將每兩個相鄰節點交換。
先檢查佇列（`head`）是否存在，和是否為空，接著逐一走訪每兩個節點，每進行一組交換就要調整六個指標，分別是 `cur->prev` 的 `next`、 `cur` 與 `cur->next` 的 `prev` 和 `next`、`cur->next->next` 的 `prev`。
使用 `list_move()` 將 `cur` 移到 `cur->next` 後方，一樣可達成目標，且程式碼更加精簡。
```diff
while (cur != head && cur->next != head) {
- cur->next = temp->next;
- temp->next->prev = cur;
- temp->prev = cur->prev;
- temp->next = cur;
- cur->prev->next = temp;
- cur->prev = temp;
+ list_move(cur, temp);
cur = cur->next;
}
```
### `q_reverse()`
> commit [4e53342](https://github.com/Lccgth/lab0-c/commit/4e53342d0b04b7fa25f9125630a9d00c9c23e113), commit [ff94823](https://github.com/Lccgth/lab0-c/commit/ff94823821e8039818091e588e99c75c2e57f85c)
反轉佇列中的節點。
先檢查佇列（`head`）是否存在，和是否為空，接著逐一走訪每個節點，將 `prev` 和 `next` 交換。
只需要逐一走訪每個節點，並使用 `list_move()` 依序將其插入到佇列的開頭處即可。
```diff
- do {
- temp = cur->next;
- cur->next = cur->prev;
- cur->prev = temp;
- cur = temp;
- } while (cur != head);
+ list_for_each_safe (cur, safe, head)
+ list_move(cur, head);
```
### `q_reverseK()`
> commit [c954812](https://github.com/Lccgth/lab0-c/commit/c95481207a1714ce740af6c8ad08659e3c614ec3)
將佇列中的節點以 `k` 個為一組作反轉。
先檢查佇列（`head`）是否存在、是否為空、`size` 是否大於 `k`，接著依照 `k` 個為一組走訪，將其中的每個節點作反轉。
```c
do {
do {
temp = cur->next;
cur->next = cur->prev;
cur->prev = temp;
cur = temp;
} while (cur != head && count > 0);
cur->prev->prev = prev;
prev->next = cur->prev;
start->next = cur;
prev = start;
start = cur;
} while (size > k);
```
:::warning
善用 List API，撰寫出更精簡的程式碼
> 了解，我會依序檢查可以使用哪些 List API。
:::
### `q_sort()`
> commit [ae7aeba](https://github.com/Lccgth/lab0-c/commit/ae7aeba997abd28a74f3b5406666414ee645759d)
將佇列中的節點升序/降序排序。
若目前佇列的節點數大於二，則使用快慢指標找到目前佇列的中點，並依照終點將其切為兩條佇列，直到所有佇列的節點數都只剩下一個，再開始依序將兩兩一組佇列進行合併。
```c
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
list_cut_position(&left, head, slow);
list_splice_init(head, &right);
if (descend ? strcmp(left_entry->value, right_entry->value) >= 0
: strcmp(left_entry->value, right_entry->value) <= 0)
list_move(left->next, cur);
else
list_move(right->next, cur);
```
:::danger
1. 如果不使用遞迴呼叫，你該如何實作排序程式？
2. 你如何確保目前的測試已涵蓋排序演算法最差狀況？
3. 目前的測試如何檢查程式碼是否 stable (sorting)？
:::
### `q_ascend()`
> commit [1cb637d](https://github.com/Lccgth/lab0-c/commit/1cb637d7ca1285f3645f82096e2975f044c273f0), commit [b22c3f0](https://github.com/Lccgth/lab0-c/commit/b22c3f01a3b4e33eb4ef4d1a095d5709b0d1e205), commit [7bc72a1](https://github.com/Lccgth/lab0-c/commit/7bc72a1bf55a42d140f8f3f3eb2065dfaa669b43)
<s>刪除</s> 移走佇列中滿足條件的節點: 右方存在嚴格小於此節點的節點。
先檢查佇列（`head`）是否存在，和是否為空，接著反向逐一走訪每個節點，同時紀錄目前所觀察到的最小值，若目前走訪的節點大於最小值，就<s>刪除</s>移走目前節點，反之更新最小值，並紀錄佇列中剩下的節點數。
可以不用建立一個字元陣列紀錄目前的最小值，直接使用指標獲取目前觀察到的最小值。
```diff
while (cur != head) {
if (strcmp(entry->value, min->value) >= 0) {
- list_del(cur);
- q_release_element(entry);
+ list_del_init(cur);
} else {
- strncpy(min_value, entry->value, MAX_STRING_LENGTH - 1);
- min_value[MAX_STRING_LENGTH - 1] = '\0';
min = entry;
}
}
```
### `q_descend()`
> commit [a18d7ff](https://github.com/Lccgth/lab0-c/commit/a18d7ff0d417c86e5e0f7f99b9be4a9285f0e534), commit [b22c3f0](https://github.com/Lccgth/lab0-c/commit/b22c3f01a3b4e33eb4ef4d1a095d5709b0d1e205), commit [7bc72a1](https://github.com/Lccgth/lab0-c/commit/7bc72a1bf55a42d140f8f3f3eb2065dfaa669b43)
<s>刪除</s> 移走佇列中滿足條件的節點: 右方存在嚴格大於此節點的節點。
和 `q_ascend()` 大致相同，只須將紀錄最小值改成紀錄最大值。
```diff
- if (strcmp(entry->value, min->value) >= 0)
+ if (strcmp(entry->value, max->value) <= 0)
```
### `q_merge()`
> commit [abee78b](https://github.com/Lccgth/lab0-c/commit/abee78b163bc04cc72e9a73cad4cc745f5bab74e)
將所有佇列合併成一個升序/降序的佇列。
利用 `list_splice_init()` 將所有佇列先合併成一個佇列，並且同時紀錄目前佇列的大小，再使用 `q_sort()` 對其進行排序，最後回傳佇列的大小。
```c
list_for_each_entry (cur, head, chain) {
list_splice_init(cur->q, tar->q);
size += cur->size;
}
q_sort(tar->q, descend);
```
:::danger
你如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::
---
## 研讀論文 〈 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 〉
> [oreparaz/dudect](https://github.com/oreparaz/dudect)
此篇論文介紹了一個量測程式碼的方法 dudect，用以量測其是否能在常數時間 O(1) 內執行完畢。
### 實驗方法
對執行時間進行洩漏檢測，量測兩種不同輸入類別各自的執行時間，接著統計兩者在時間分佈上是否有差異。
### 實驗步驟
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
#### 量測執行時間
採用 fix-vs-random 的方法，將第一組輸入設定為固定值，而第二組輸入則會根據每次的量測隨機設定。
#### 後處理
在進行統計分析之前對於每次的量測結果進行後處理，大部分的量測值會集中在較小的執行時間，而有一小部份量測值會出現特別高的執行時間，導致時間分佈出現[正偏態](https://ithelp.ithome.com.tw/m/articles/10234743)，故須要對結果進行取捨。
#### 統計測試
使用 Welch 的 t 檢驗測試兩組數據的時間分佈是否相等，若結果顯示不相等，則意味著存在時間洩漏。
### [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution)
是一種機率分佈，用於依照小樣本來估計母體為常態分佈且標準差未知的期望值，由 v 值（自由度）控制其分佈的形狀，當 v 值越低，則出現極端值的概率較高，而 v 值越高，其分佈就越接近常態分佈。
### 修改 lab0-c
我觀察到 [oreparaz/dudect](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 程式碼中的 `prepare_percentiles()` 函式會根據不同百分位數計算出對應的 `percentile`，而它們會在 `update_statistics()` 函式中被用於進行比較，若量測的執行時間小於對應的 `percentile`，則將其用於統計分析中，大於就排除這些執行時間特別長的量測結果。
目前的 lab0-c 並未進行以上的檢查，會導致將一些執行時間異常的結果也納入統計中，導致程式碼的常數時間檢測會無法通過，當加入上述的檢查後，即可排除異常的結果。
:::danger
列出論文和程式碼實作的出入之處，並予以討論。
:::
論文與程式碼的主要差異有三，分別為：
`cmp()`: 比較兩個 64 位整數的大小，用來當作執行 `qsort()` 時的比較依據。
`percentile()`: 從一組測量值中找到特定百分位數的值。
`prepare_percentiles()`: 根據不同的百分位數設定不同的閥值，並透過這些閥值來篩選測量數據，可由此排除執行時間異常的數據。
## `qtest` 新增命令 `shuffle`
透過 [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法對佇列進行洗牌。
### Fisher-Yates shuffle
#### 步驟
走訪串列得知串列大小並設定 `last` 為最後一個節點。
從首節點到 `last` 節點中隨機取一個節點與 `last` 節點交換。
將 `last` 往前移一個節點。
重複步驟 2、3 直到 `last` 為首節點。
<s>
</s>
:::danger
以 Graphviz 重新製圖，並嵌入到 HackMD 筆記中。
:::
#### 示意流程圖
一開始先將 `last` 設為最後一個節點。
```graphviz
digraph G {
rankdir=LR;
label="Original List";
1 -> 2 -> 3 -> 4 -> "5(last)";
"5(last)" -> 4 -> 3 -> 2 -> 1;
}
```
隨機從首節點到 `last` 節點取一個和 `last` 節點交換，並將 `last` 向前移一個節點，這裡取節點 3 當範例。
```graphviz
digraph G {
rankdir=LR;
1 -> 2 -> 5 -> "4(last)" -> 3;
3 -> "4(last)" -> 5 -> 2 -> 1;
3 [color=green];
}
```
重複隨機取節點和 `last` 交換的步驟，這裡取節點 1 當範例。
```graphviz
digraph G {
rankdir=LR;
4 -> 2 -> "5(last)" -> 1 -> 3;
3 -> 1 -> "5(last)" -> 2 -> 4;
3, 1 [color=green];
}
```
重複隨機取節點和 `last` 交換的步驟，這裡取節點 5 當範例。
```graphviz
digraph G {
rankdir=LR;
4 -> "2(last)" -> 5 -> 1 -> 3;
3 -> 1 -> 5 -> "2(last)" -> 4;
3, 1, 5 [color=green];
}
```
重複隨機取節點和 `last` 交換的步驟，這裡取節點 4 當範例。
```graphviz
digraph G {
rankdir=LR;
"4(last)" -> 2 -> 5 -> 1 -> 3;
3 -> 1 -> 5 -> 2 -> "4(last)";
3, 1, 5, 2 [color=green];
}
```
當 `last` 指到首節點時結束，完成節點的洗牌。
```graphviz
digraph G {
rankdir=LR;
4 -> 2 -> 5 -> 1 -> 3;
3 -> 1 -> 5 -> 2 -> 4;
3, 1, 5, 2, 4 [color=green];
}
```
#### 實作
> commit [65c2bfc](https://github.com/sysprog21/lab0-c/commit/65c2bfc7a459d33ea35700414ab7e553c39e72af)
```c
while (last != head && --size) {
int index = rand() % size;
struct list_head *node = head->next, *temp = last->prev;
while (index--)
node = node->next;
list_move(last, node->prev);
if (node != temp)
list_move(node, temp);
last = node->prev;
}
```
### 加入到 `qtest` 中
:::danger
避免非必要的項目縮排 (即 `* `, `- ` 或數字)，以清晰、明確，且流暢的漢語書寫。
授課教師在大學教書十餘年，見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。為此，要求學員書寫開發紀錄，並隨時做好「當主管問起，就能清晰解釋自己的投入狀況」，是強調讓學員「翻身」的本課程在意的事。
濫用條列 (或說 bullet) 來展現，乍看很清爽，但在面試的場合中，就很難用流暢的話語說明。反之，若平日已有這方面的練習，則面試過程中，才可充分展現自己專業之處。
:::
首先在 `qtest.c` 中加入 `do_shuffle()` 函式，接著在 `console_init()` 中加入 shuffle 命令，最後在 `qtest` 中輸入 help 可看到 shuffle 命令已成功加入。
```
Commands:
# ... | Display comment
shuffle | Shuffle the order of nodes in the list
```
### 驗證
使用 [lab0 (D)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d) 提供之驗證程式碼進行驗證。
將初始串列設定為 [1, 2, 3, 4]，並使用 1000000 次 shuffle，將每次執行的結果記錄下來。
四個節點組成的串列共有 24 (4!) 種排列方式，當執行 1000000 次 shuffle，每一種排列方式平均會出現 41666 次。
```
Expectation: 41666
Observation: {'1234': 41375, '1243': 41683, '1324': 41545, '1342': 42180, '1423': 41396, '1432': 41561, '2134': 41821, '2143': 41784, '2314': 41315, '2341': 41531, '2413': 41805, '2431': 41480, '3124': 41586, '3142': 41432, '3214': 42248, '3241': 41822, '3412': 41855, '3421': 41530, '4123': 41623, '4132': 41984, '4213': 41449, '4231': 41620, '4312': 41601, '4321': 41774}
chi square sum: 31.861085777372438
```
由數據得知每種排列分式出現的次數都大約在 41666 次左右，符合離散均勻分佈的期望特徵。
## 引入 lib/list_sort.c 到 lab0-c 專案中
### 步驟
> commit [3893eb1](https://github.com/sysprog21/lab0-c/commit/3893eb1fea73e93fb0eb308fa7215cdcc6f57f25)
:::danger
避免非必要的項目縮排 (即 `* `, `- ` 或數字)，以清晰、明確，且流暢的漢語書寫。
授課教師在大學教書十餘年，見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。為此，要求學員書寫開發紀錄，並隨時做好「當主管問起，就能清晰解釋自己的投入狀況」，是強調讓學員「翻身」的本課程在意的事。
濫用條列 (或說 bullet) 來展現，乍看很清爽，但在面試的場合中，就很難用流暢的話語說明。反之，若平日已有這方面的練習，則面試過程中，才可充分展現自己專業之處。
:::
首先將 `list_sort.c` 和 `list_sort.h` 加入到 lab0-c 中，接著將 `list_sort.o` 加入到 `MakeFile` 的 OBJS 中，然後在 `qtest.c` 中加入 `do_list_sort()` 函式，且在 `console_init()` 中加入 list_sort 命令，最後在 `qtest` 中輸入 help 可看到 list_sort 命令已成功加入。
```
Commands:
# ... | Display comment
list_sort | Sort queue by linux list sort
```
### 和 q_sort 比較
測試用 shell script，可調整佇列大小。
```shell
echo -e "new\nit RAND 200000\ntime\nsort\ntime\nfree" | ./qtest
```
```shell
echo -e "new\nit RAND 200000\ntime\nlist_sort\ntime\nfree" | ./qtest
```
#### q_sort
| 佇列大小 | Round 1 | Round 2 | Round 3 | Round 4 | Round 5 | 平均 |
| -------- | ------- | ------- | ------- | ------- | ------- | ---- |
| 200k | 0.128 | 0.140 | 0.139 | 0.133 | 0.139 | 0.136 |
| 400k | 0.307 | 0.329 | 0.332 | 0.317 | 0.330 | 0.323 |
| 600k | 0.493 | 0.521 | 0.528 | 0.511 | 0.503 | 0.511 |
| 800k | 0.693 | 0.769 | 0.756 | 0.733 | 0.736 | 0.737 |
| 1M | 0.903 | 0.962 | 0.947 | 0.955 | 0.945 | 0.942 |
#### list_sort
| 佇列大小 | Round 1 | Round 2 | Round 3 | Round 4 | Round 5 | 平均 |
| -------- | ------- | ------- | ------- | ------- | ------- | ---- |
| 200k | 0.116 | 0.117 | 0.116 | 0.119 | 0.116 | 0.117 |
| 400k | 0.266 | 0.281 | 0.271 | 0.263 | 0.266 | 0.269 |
| 600k | 0.433 | 0.427 | 0.427 | 0.424 | 0.433 | 0.429 |
| 800k | 0.602 | 0.604 | 0.598 | 0.632 | 0.592 | 0.606 |
| 1M | 0.756 | 0.760 | 0.755 | 0.761 | 0.773 | 0.761 |
#### 比較圖
從資料與圖表可得知目前專案實作的 `q_sort` 略慢於 `list_sort`，須通過研讀 `list_sort` 程式碼得知具體差異為何。
#### 使用 perf 分析
在佇列大小為 200k ，執行 100 次來觀察。
```shell
Performance counter stats for './test_q_sort.sh' (100 runs):
1874,4031 cache-misses # 43.136 % of all cache refs ( +- 0.15% )
4332,7132 cache-references ( +- 0.05% )
9,7055,4711 instructions # 0.78 insn per cycle ( +- 0.01% )
12,4672,1225 cycles ( +- 0.11% )
0.258425 +- 0.000369 seconds time elapsed ( +- 0.14% )
```
```shell
Performance counter stats for './test_list_sort.sh' (100 runs):
1756,4224 cache-misses # 47.197 % of all cache refs ( +- 0.54% )
3733,7572 cache-references ( +- 0.05% )
9,2544,3885 instructions # 0.78 insn per cycle ( +- 0.01% )
11,6991,3859 cycles ( +- 0.30% )
0.25129 +- 0.00104 seconds time elapsed ( +- 0.41% )
```
cache-misses : 表示程式執行期間無法在快取中找到所需資料而導致的快取未命中次數。
cache-references : 表示程式執行期間對快取的總參考次數。
instructions : 表示程式執行期間執行的指令數量。
cycles : 表示程式執行期間花費的 CPU 週期數。
觀察兩筆資料發現 `list_sort` 在 cache-misses、cache-references、instructions、cycles 中都小於 `q_sort`，但在 cache-misses 的比例比 `q_sort` 要高，須通過研讀比較兩者程式的差異。
### 研讀 list_sort
#### `merge()`
將兩個已經排序好的串列 (`a`、`b`) 合併為一個串列，並將合併後的串列返回。
利用 `cmp()` 比較 `a`、`b` 當前節點的大小，若 `a` 節點小於或等於 `b` 節點，就通過間接指標將 `a` 節點接在新串列後方，反之則將 `b` 節點接在新串列後方，在判斷 `a`、`b` 節點大小時若兩者相等則串接 `a` 節點可以保持 [stable](https://en.wikipedia.org/wiki/Category:Stable_sorts) 的特性，而使用間接指標可以避免不必要的記憶體空間分配，降低空間複雜度。
此函式只會維護 `next` 指標，而沒有維護 `prev` 指標。
#### `merge_final()`
當完成所有排序操作後，將最終兩個排序好的串列 (`a`、`b`) 合併為一個串列，並將此串列恢復成雙向環狀的鏈結串列。
在研讀此函式時對以下程式碼感到疑惑，為什麼 if 判斷式中要使用 `unlikely()`，且為什麼要比較 `b` 和 `b` 的大小?
```c
do {
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
```
##### 為什麼 if 判斷式中要使用 `unlikely()`
在 [linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 中 unlikely 定義如下:
```c
# define unlikely(x) __builtin_expect(!!(x), 0)
```
此巨集會先對 `x` 做兩次 not 運算，因為 `x` 可能不是 0 或 1 的整數，通過兩次 not 運算後可以將值限制在 0 或 1 之間。
我參照 [gcc 13.2 第 6.59 章](https://gcc.gnu.org/onlinedocs/gcc-13.2.0/gcc/Other-Builtins.html)說明的 `__builtin_expect()` 後了解此函式的功能為向編譯器提供分支的預測資訊，當 `__builtin_expect(x, 0)` 時預期 `x` 的值為 0，而 `__builtin_expect(x, 1)` 時則預期 `x` 為 1。
所以 `unlikely(!++count)` 此判斷式只有在當 `count` 值增加 1 後變成 0 (溢位) 時成立，這種情況非常罕見，所以這裡才用 `unlikely` 來提示編譯器此分支不常發生。
但我看到其中預設 `__builtin_expect` 為真的機率為 90%，不懂為什麼要以此機率當預設值。
> For the purposes of branch prediction optimizations, the probability that a __builtin_expect expression is true is controlled by GCC’s builtin-expect-probability parameter, which defaults to 90%.
##### 為什麼要比較 `b` 和 `b` 的大小
因為 `cmp()` 會根據傳入的比較函式不同而改變，因此我查看了 [lib/test_list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的比較函式，在其中發現比較時會呼叫 `check` 函式。
首先此函式會先使用 `KUNIT_EXPECT_LT_MSG` 巨集來檢查 `ela` 和 `ela` 的 `serial` 是否小於 `TEST_LIST_LEN`，確保他們的大小在特定範圍內。
```c
KUNIT_EXPECT_LT_MSG(test, ela->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");
KUNIT_EXPECT_LT_MSG(test, elb->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");
```
接著使用 `KUNIT_EXPECT_PTR_EQ_MSG` 巨集來比較 `elts` 中對應編號的元素是否和 `ela` 和 `elb` 匹配。
```c
KUNIT_EXPECT_PTR_EQ_MSG(test, elts[ela->serial], ela, "phantom element");
KUNIT_EXPECT_PTR_EQ_MSG(test, elts[elb->serial], elb, "phantom element");
```
最後使用 `KUNIT_EXPECT_EQ_MSG` 巨集來比較 `ela` 和 `elb` 的 `position1` 和 `position2` 是否和預設值相同，驗證內容沒有被意外修改。
```c
KUNIT_EXPECT_EQ_MSG(test, ela->poison1, TEST_POISON1, "bad poison");
KUNIT_EXPECT_EQ_MSG(test, ela->poison2, TEST_POISON2, "bad poison");
KUNIT_EXPECT_EQ_MSG(test, elb->poison1, TEST_POISON1, "bad poison");
KUNIT_EXPECT_EQ_MSG(test, elb->poison2, TEST_POISON2, "bad poison");
```
除此之外根據註解的說明，如果要合併的串列非常不平衡 (例如已經排序完畢)，會造成迴圈執行次數較大，此時可以在 `cmp()` 中定期呼叫 `cond_resched()`，此函式會根據當前行程已經占用的 CPU 時間和系統中其他行程的狀態判斷是否要讓出 CPU，使其他行程不會產生 [starvation](https://en.wikipedia.org/wiki/Starvation_(computer_science))。
#### `list_sort()`
通過呼叫 `merge()` 和 `merge_final()` 對串列進行排序。
其中最不理解的部分為迴圈內判斷是否該進行合併的程式碼。
```c
do {
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
} while (list);
```
首先 for 迴圈會通過位元運算來找到 `count` 最低位的 0，並同時更新 `tail` 指標，當 count 為 2 的冪加 1 時，就會執行一次合併，這樣是為了確保最多只有兩個子串列在等待合併。
Sign in with Wallet
Connect another wallet