# 2024q1 Homework1 (lab0)
contributed by <[`hungyuhang`](https://github.com/hungyuhang)>
## 開發環境
```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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 12
CPU max MHz: 4200.0000
CPU min MHz: 400.0000
BogoMIPS: 4199.88
```
## 佇列操作的程式碼實作
### `q_insert_tail`
本專案引入了 [Git pre-commit hook](https://git-scm.com/book/en/v2/Customizing-Git-Git-Hooks) ，所以 git 會在每次 commit 之前去預先對要提交的程式碼做一些檢查，在實際寫程式時也可以感受到這個工具帶來的一些好處，以下是一個例子：
下面是我原來插入佇列的函式的實作方式：
```c=
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (element == NULL)
return false;
size_t len = strlen(s) + 1;
element->value = malloc(len);
if (element->value == NULL)
return false;
strncpy(element->value, s, len);
list_add_tail(&element->list, head);
return true;
}
```
程式碼可以通過編譯，並且執行 `$ make check` 命令時也不會有錯誤，但是當我試著用 Git 提交程式碼時， Git pre-commit hook 的靜態程式碼檢查卻報了以下的錯誤：
:::danger
「報了以下的錯誤」的主詞是什麼？
> 已加上主詞
:::
```shell
$ git commit
Following files need to be cleaned up:
queue.c
queue.c:36:9: error: Memory leak: element [memleak]
return false;
^
queue.c:55:9: error: Memory leak: element [memleak]
return false;
^
Fail to pass static analysis.
```
:::danger
「報錯」的主詞是什麼？
> 這邊是我用詞有誤，已修改
:::
閱讀錯誤資訊，可以觀察到如果我在第 11 行回傳 false 並且離開這個函式，那我在第 5 行所建立的記憶體位置就不會有人知道他在哪裡了（因為唯一指向他的指標 `element` 是區域變數，而區域變數的特點之一就是當離開函式之後，區域變數就會被消滅），這樣的現象也就是所謂的 memory leak 。
在發現問題之後，我將程式碼的第 10 行做了以下修改：
```diff
- if (element->value == NULL)
- return false;
+ if (element->value == NULL) {
+ free(element);
+ return false;
+ }
strncpy(element->value, s, len);
```
:::danger
使用 `git diff` 或 `diff -u` 來產生程式碼之間的變更列表。
:::
經過這次修改後，程式碼就可以被正確的提交了。
### `q_free`
要實作一個釋放佇列的函式，最直觀的想法就是逐一走訪每個節點，並且運用 `free()` 函式去釋放相對應的記憶體空間。
但是在走訪時會遇到一個問題，以下圖來看，當我在走訪節點的時候，我能得到的指標位置都是指向每個 element 的 `list` 物件，而非 element 本身。
```graphviz
digraph {
node [shape=record];
rankdir=LR;
subgraph cluster_element1 {
label="element";
list_head1 [label = "list"];
value1 [label = "value"];
}
subgraph cluster_element2 {
label="element";
list_head2 [label = "list"];
value2 [label = "value"];
}
subgraph cluster_element3 {
label="element";
list_head3 [label = "list"];
value3 [label = "value"];
}
list_head1 -> list_head2;
list_head2 -> list_head1;
list_head2 -> list_head3;
list_head3 -> list_head2;
}
```
:::warning
使用 Graphviz 一類的工具重新繪製，並嵌入到 HackMD
> <s>已更新</s>
> 你沒做到事，不要輕易說「已更新」，繼續改！
> 好的
:::
如果無法取得 element 的記憶體位置， element 所佔用的記憶體就無法被釋放掉。
#### `container_of` 的用法
在 `list.h` 裡面提供了一個叫做 `container_of` 的巨集，只要輸入指向 element 中 `list` 的指標， element 的型別，以及 `list` 在 element 型別中的名稱，這個巨集就可以回傳一個指向 element 本身的指標。
舉我實作的程式碼為例：
```c
element_t *temp = container_of(curr, element_t, list);
```
其中：
- `curr` 指向我目前的 element 的 list
- `element_t` 是 element 的型別名稱
- `list` 則是 `curr` 在 `element_t` 型別中的名稱
並且該巨集就會回傳一個指向 element 的指標。
### `q_remove_head`
以下是該函式在 `queue.h` 的宣告：
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize);
```
這個函式的功能是把第一個節點從佇列中移除，除此之外，還需要把欲移除的節點內容（也就是一個字串）複製到 `sp` 指向的記憶體空間裡面，而這個記憶體空間的大小是 `bufsize` 。
既然是複製記憶體空間，我們就需要告訴程式碼它要從來源複製多少 byte 的資料到目的地。在這個例子當中，我們可能就會很自然的選擇目標的記憶體空間大小（也就是 `bufsize`）當作要搬運的資料數量。
但考慮以下狀況：
- `element->value` 指向的字串長度是 2（含 `'\0'`）
- `bufsize` 的值是 100
當這種情況發生時，我們等於要把 `element->value` 後面的 98 個未知位元一起複製到 `bufsize` 指向的記憶體空間，我認為如果後面多出來的位元剛好包含了一些較為敏感的資訊的話，那這份程式碼就不是那麼的安全。以下是我複製字串的程式碼：
```c
strncpy(sp, temp->value, min(strlen(temp->value) + 1, bufsize));
```
可以看到，我在第三個參數的欄位，也就是要複製的長度，是取 `element->value` 的長度跟 `bufsize` 之間的最小值。
#### 程式碼改進
但是實際去看 `strncpy()` 在 [man page](https://man7.org/linux/man-pages/man3/stpncpy.3.html) 的說明：
> These functions copy the string pointed to by src into a null-padded character sequence at the fixed-width buffer pointed to by dst.
所以我在前面擔心發生的狀況其實是不存在的， `strncpy()` 會自動把多餘的位元都填入 `NULL` 。
以下是我修正過後的程式碼：
```c
strncpy(sp, temp->value, bufsize);
```
### `q_reverseK`
一開始在實作時，使用了較為直覺的寫法。
> [commit 2222798](https://github.com/hungyuhang/lab0-c/commit/222279845dad26639b307f05e73b877e5c1730c9)
程式的邏輯，就是 `rear` 跟 `front` 這兩個指標會在 for 迴圈迭代的過程中把長度為 `k` 的區域給圍起來，並且對裡面的指標做相對應的操作，讓區域內的節點順序可以被倒轉。
其實可以發現，上面這份程式碼因為沒有好好的利用 `list.h` 裡面所提供的工具函式，所以程式碼相當雜亂且難以理解。於是我決定用另一種寫法將函式重寫了一次。
> [commit 0ee7532](https://github.com/hungyuhang/lab0-c/commit/0ee7532eb77bac96e09bcc6b2f280e7bf314b91a)
:::danger
使用 `git diff` 或 `diff -u` 來產生程式碼之間的變更列表。
:::
改寫後程式的邏輯，是在迭代的過程中，將原本佇列裡面的節點依序取出，並且推入到堆疊裡面，當堆疊的長度到達 k 個的時候，再將堆疊內的節點一次全部推出，藉此改變這 k 個節點的順序。
相較於前一份程式碼，我認為這份程式碼是比較好理解而且簡潔的。
### `q_sort`
一開始選擇使用 insertion sort 來實作這個函式：
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head)
return;
if (q_size(head) < 2)
return;
struct list_head *dirty = head->next->next;
struct list_head *probe;
struct list_head *temp;
bool (*cmp_func)(struct list_head *, struct list_head *);
if (descend)
cmp_func = &issmaller;
else
cmp_func = &isbigger;
while (dirty != head) {
for (probe = dirty->prev; probe != head; probe = probe->prev) {
if (!cmp_func(probe, dirty))
break;
}
temp = dirty->next;
list_del(dirty);
list_add(dirty, probe);
dirty = temp;
}
return;
}
```
在 insertion sort 當中，我們可以把正在排序中的鏈結串列分成兩邊，一邊是前半段已經排序好的部份，另一邊則是後半段還沒排序好的部份。
在這份程式碼中：
- `dirty` 指向未排序部份的第一個節點，這個節點同時也要被插入到前半段已排序的部份當中。
- 為了找出適當的插入位置，我們會需要一個指標去尋找適當的插入點，而這也正是 `probe` 的功能。
- `issmaller` 跟 `isbigger` 是我另外實作的函式，目的是要比較兩個節點的字串大小。實作方式可以參考[GitHub](https://github.com/hungyuhang/lab0-c/blob/master/queue.c)
但是在實作後，我發現這個程式無法通過 `trace-15-perf` 的效能檢查，原因是因為 insertion sort 的時間複雜度是 $O(n^2)$ ，但是該效能檢查需要排序的時間複雜度不超過 $O(n \log{n})$ 才有辦法通過。
於是我將排序方式改為 merge sort ：
```c
void q_sort(struct list_head *head, bool descend)
{
/* handle special case */
if (!head)
return;
if (q_size(head) <= 1)
return;
/* seperate the unsorted list to two sublists */
struct list_head *slow = head->next;
struct list_head head_left;
for (struct list_head *fast = head->next;
fast != head && fast->next != head;
fast = fast->next->next, slow = slow->next) {
}
list_cut_position(&head_left, head, slow->prev);
/* sort two sublists */
q_sort(&head_left, descend);
q_sort(head, descend);
/* merge two sublists together */
struct list_head result;
bool (*cmp_func)(struct list_head *, struct list_head *);
if (descend)
cmp_func = &isbigger;
else
cmp_func = &issmaller;
INIT_LIST_HEAD(&result);
while (!list_empty(&head_left) && !list_empty(head)) {
if (cmp_func(head_left.next, head->next)) {
list_move_tail(head_left.next, &result);
} else {
list_move_tail(head->next, &result);
}
}
while (!list_empty(&head_left))
list_move_tail(head_left.next, &result);
while (!list_empty(head))
list_move_tail(head->next, &result);
list_splice(&result, head);
return;
}
```
:::danger
如何確認目前的測試方法已涵蓋排序演算法的最差狀況？
> 已將問題探討放在下方
:::
做了上面的修改後，程式已經可以成功通過 `trace-15-perf` 。
#### 現有測試方式探討
觀察現有的測試方法，測試程式碼會分別建立三個長度不同的鏈節串列，串列內的值皆為隨機產生，並進行以下操作：
1. 對隨機產生的鏈節串列進行降序排序
2. 使用 reverse 函式將排序後的串列轉換成一個升序排序的串列
3. 對升序排序的串列進行降序排序
可以看到，這個測試的測資涵蓋了隨機排序的串列以及排序順序為相反的串列。
以下是幾種常見排序演算法的最差狀況：
- Selection Sort: 無最差狀況
- Insertion Sort: 當串列的排序順序為相反時
- Merge Sort: 無最差狀況
- Quicksort: 如果取第一個節點為 pivot 的話，就是當串列的排序順序為相反時
- Heap Sort: 無最差狀況
以我目前的實作而言，我所實作的兩個排序法為 insertion sort 跟 merge sort ，並且皆為標準的實作方式。對這兩種排序法而言，現有的測資已經涵蓋了對演算法而言最糟的狀況。
### 改善 `q_insert_tail`, `q_insert_head`
在執行 `$ make test` 的時候， `trace-14-perf` 無法通過：
```shell
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-14-perf 0/6
```
比較跟 [jimmylu890303](https://github.com/jimmylu890303) 的[程式碼](https://github.com/jimmylu890303/lab0-c/blob/master/queue.c)差異，我發現當我建立儲存字串的記憶體的時候，我使用的是 `strlen()` ， `malloc()` 以及 `strncpy()` 這三個函式：
```c
size_t len = strlen(s) + 1;
element->value = malloc(len);
if (element->value == NULL) {
free(element);
return false;
}
strncpy(element->value, s, len);
```
但 [jimmylu890303](https://github.com/jimmylu890303) 在建立記憶體的時候，他只用了 `strdup()` 這個函式：
```c
new_node->value = strdup(s);
```
於是我嘗試將我的程式碼所呼叫的函式作修改：
```c
element->value = strdup(s);
if (element->value == NULL) {
free(element);
return false;
}
```
:::danger
原理是什麼？你如何確認同學的修改沒有副作用？
:::
修改之後就可以通過 `trace-14-perf` 的測試了。為了探討原因為何，我在下面做了一些分析。
#### 分析
為了解析 `strdup()` 這個函式，我使用 `$ objdump -d qtest` 命令來將 qtest 做反組譯：
```
0000000000007542 <test_strdup>:
7542: f3 0f 1e fa endbr64
7546: 55 push %rbp
7547: 53 push %rbx
7548: 48 83 ec 08 sub $0x8,%rsp
754c: 48 89 fb mov %rdi,%rbx
754f: e8 dc b0 ff ff call 2630 <strlen@plt>
7554: 48 8d 68 01 lea 0x1(%rax),%rbp
7558: 48 89 ef mov %rbp,%rdi
755b: e8 33 fd ff ff call 7293 <test_malloc>
7560: 48 85 c0 test %rax,%rax
7563: 74 0e je 7573 <test_strdup+0x31>
7565: 48 89 ea mov %rbp,%rdx
7568: 48 89 de mov %rbx,%rsi
756b: 48 89 c7 mov %rax,%rdi
756e: e8 2d b2 ff ff call 27a0 <memcpy@plt>
7573: 48 83 c4 08 add $0x8,%rsp
7577: 5b pop %rbx
7578: 5d pop %rbp
7579: c3 ret
```
可以看到 `strdup()` 函式的內部也一樣呼叫了 `strlen()` ， `malloc()` 以及 `memcpy()` 三個函式，因此我先初步推測兩個版本的程式碼效能應該是差不多的。
:::danger
強化你的論述，用 perf 一類的工具來佐證。工程人員說話要精準，數字呢？
> 已嘗試改善
:::
為了進一步驗證我的推測，我撰寫了一個簡單的 `qtest` 腳本並且用 `perf` 效能分析工具測試了兩個不同版本的程式碼。以下是 `qtest` 腳本：
```
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
```
在這裡我使用以下命令對程式碼執行 100 次測試，並且取平均數據作為最後測試結果：
```
$ sudo perf stat -r 100 ./qtest -v 1 -f ./traces/trace-eg.cmd
```
另外為了確保程式不會出錯，在編譯兩個版本的程式碼之前，都有先執行 `make clean` 將原本的 object file 給刪除。
以下是 `perf stat` 輸出的實驗結果：
- 使用 `strlen` ， `malloc` 以及 `strncpy` ：
```
Performance counter stats for './qtest -v 1 -f ./traces/trace-eg.cmd' (100 runs):
299.98 msec task-clock # 0.999 CPUs utilized ( +- 0.12% )
1 context-switches # 3.334 /sec ( +- 11.86% )
0 cpu-migrations # 0.000 /sec
7,0387 page-faults # 234.637 K/sec ( +- 0.00% )
11,4704,8153 cycles # 3.824 GHz ( +- 0.05% )
26,6151,3722 instructions # 2.32 insn per cycle ( +- 0.01% )
5,6264,6672 branches # 1.876 G/sec ( +- 0.00% )
56,9917 branch-misses # 0.10% of all branches ( +- 0.37% )
0.300362 +- 0.000346 seconds time elapsed ( +- 0.12% )
```
- 使用 `strdup` ：
```
Performance counter stats for './qtest -v 1 -f ./traces/trace-eg.cmd' (100 runs):
294.10 msec task-clock # 0.999 CPUs utilized ( +- 0.16% )
1 context-switches # 3.400 /sec ( +- 11.84% )
0 cpu-migrations # 0.000 /sec
7,0387 page-faults # 239.329 K/sec ( +- 0.00% )
11,2403,0589 cycles # 3.822 GHz ( +- 0.04% )
26,2538,1443 instructions # 2.34 insn per cycle ( +- 0.00% )
5,5525,2743 branches # 1.888 G/sec ( +- 0.00% )
59,4290 branch-misses # 0.11% of all branches ( +- 0.31% )
0.294498 +- 0.000468 seconds time elapsed ( +- 0.16% )
```
可以看到使用 `strdup` 的版本的執行時間平均下來快了大概 5 毫秒，跟原本的程式碼比起來大約快了 2% ，原因我推測是因為原本版本的程式碼需要執行比多指令，而使用 `strdup` 版本的程式碼執行的指令相對比較少，所以才會造成執行時間上的差異。
> 參考： [perf 教學](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) ， [Perf Tutorial](https://perf.wiki.kernel.org/index.php/Tutorial)
#### 無法理解之狀況
奇怪的事情是當我把程式碼又改回原來的版本並運行 `$ make test` ， `trace-14-perf` 卻仍然還是可以通過。一模一樣的程式碼理論上在運行 `$ make test` 的時候結果會是一樣的，但是在這個例子上顯然不是這樣。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
> 已修改
:::
目前的情況是，執行 `$ make clean` 後再執行 `$ make test` ，會導致 `trace-14-perf` 測試無法通過。在這種情況下，我們需要修改 `q_insert_head()` 和 `q_insert_tail()` ，然後再次執行 `$ make test` ，這樣才能確保 `trace-14-perf` 測試通過。
---
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
### 問題以及心得紀錄
在閱讀 [Linux 核心的鏈節串列排序](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e) 時，其實對以下的敘述是有疑問的：
> - 用 bottom up 實作 merge sort 對 cache 較友善，因為過程中就是一直合併，cache 被參照到的機會更大。
> - 而 top down 是會先做 partition 再來 merge，但 partition 本身對 cache 不友善，在 cache 移進移出（內容不斷更新，導致 cache thrashing。
對於 partition 部份的敘述，我的理解是 top down 演算法會為了找出串列的中心點而先把整個串列給走訪一遍，而當串列的長度大於 cache 的大小時，這樣的操作無疑會增加 cache 的負擔。
但從另一個角度來看， top down 在遞迴的過程當中，子串列的長度會被切的越來越小，而當子串列的長度小於 cache size 的時候， top down 方法理應能夠更好的利用 cache 。
因為相對於 top down ，雖然 bottom up 省去了 partition 的步驟，但是在每次迭代的過程當中，演算法都會需要走訪整個串列一次，那當串列的大小比 cache 還要大的時候，每次的走訪肯定都會伴隨著大量的 cache miss 。
為了釐清我的疑問，我用以下的設置對兩種方法的 merge sort 做了一次推演：
- cache size: 四個節點
- 使用 LRU 的方式來更新 cache 裡面的資料
> 演算法邏輯以 [geeksforgeeks](https://www.geeksforgeeks.org/iterative-merge-sort/) 的範例程式碼作為標準
在數字右邊的 (h) 或是 (m) 則是代表 cache hit 或是 cache miss 。
1. Top down merge sort
```graphviz
digraph G {
splines=line
node[shape=box, height=.1];sorted_1 sorted_2 sorted_3 sorted_4 sorted_5 sorted_6 sorted_7 sorted_8;
node[shape=record, height=.1];input result
divide_41 divide_42 divide_21 divide_22 divide_23 divide_24
merge_21 merge_22 merge_23 merge_24 merge_41 merge_42;
node[shape=none];merge_pad
input[label="<f0>2(m)|<f1>5(m)|<f2>4(m)|<f3>6(m)|<f4>8(m)|<f5>1(m)|<f6>7(m)|<f7>3(m)"]
result[label="<f0>1(h)|<f1>2(m)|<f2>3(m)|<f3>4(m)|<f4>5(m)|<f5>6(m)|<f6>7(m)|<f7>8(m)"]
divide_41[label="<f1>2(m)|<f2>5(m)|<f3>4(m)|<f4>6(m)"]
divide_42[label="<f1>8(m)|<f2>1(m)|<f3>7(m)|<f4>3(m)"]
divide_21[label="<f0>2(h)|<f1>5(h)"]
divide_22[label="<f0>4(h)|<f1>6(h)"]
divide_23[label="<f0>8(h)|<f1>1(h)"]
divide_24[label="<f0>7(h)|<f1>3(h)"]
sorted_1[label="1(h)"]
sorted_2[label="2(h)"]
sorted_3[label="3(h)"]
sorted_4[label="4(h)"]
sorted_5[label="5(h)"]
sorted_6[label="6(h)"]
sorted_7[label="7(h)"]
sorted_8[label="8(h)"]
merge_21[label="<f0>2(h)|<f1>5(h)"]
merge_22[label="<f0>4(h)|<f1>6(h)"]
merge_23[label="<f0>1(h)|<f1>8(h)"]
merge_24[label="<f0>3(h)|<f1>7(h)"]
merge_41[label="<f1>2(h)|<f2>4(h)|<f3>5(h)|<f4>6(h)"]
merge_42[label="<f1>1(h)|<f2>3(h)|<f3>7(h)|<f4>8(h)"]
merge_pad[label=""]
input -> divide_41
input -> divide_42
divide_41 -> divide_21
divide_41 -> divide_22
divide_42 -> divide_23
divide_42 -> divide_24
divide_21:f0 -> sorted_2
divide_21:f1 -> sorted_5
divide_22:f0 -> sorted_4
divide_22:f1 -> sorted_6
divide_23:f0 -> sorted_8
divide_23:f1 -> sorted_1
divide_24:f0 -> sorted_7
divide_24:f1 -> sorted_3
sorted_1;
sorted_2;
sorted_3;
sorted_4;
sorted_5;
sorted_6;
sorted_7;
sorted_8;
sorted_2 -> merge_21:f0
sorted_5 -> merge_21:f1
sorted_4 -> merge_22:f0
sorted_6 -> merge_22:f1
sorted_8 -> merge_23:f1
sorted_1 -> merge_23:f0
sorted_7 -> merge_24:f1
sorted_3 -> merge_24:f0
merge_22 -> merge_pad[style=invis]
merge_23 -> merge_pad[style=invis]
merge_pad -> result[style=invis]
merge_21 -> merge_41
merge_22 -> merge_41
merge_23 -> merge_42
merge_24 -> merge_42
merge_41 -> result
merge_42 -> result
}
```
2. Bottom up merge sort
```graphviz
digraph G {
splines=line
node[shape=record, height=.1];input result
merge_21 merge_22 merge_23 merge_24 merge_41 merge_42;
input[label="<f0>2(m)|<f1>5(m)|<f2>4(m)|<f3>6(m)|<f4>8(m)|<f5>1(m)|<f6>7(m)|<f7>3(m)"]
result[label="<f0>1(-)|<f1>2(-)|<f2>3(-)|<f3>4(-)|<f4>5(-)|<f5>6(-)|<f6>7(-)|<f7>8(-)"]
merge_21[label="<f0>2(m)|<f1>5(m)"]
merge_22[label="<f0>4(m)|<f1>6(m)"]
merge_23[label="<f0>1(m)|<f1>8(m)"]
merge_24[label="<f0>3(m)|<f1>7(m)"]
merge_41[label="<f1>2(m)|<f2>4(m)|<f3>5(m)|<f4>6(m)"]
merge_42[label="<f1>1(h)|<f2>3(m)|<f3>7(m)|<f4>8(m)"]
input:f0 -> merge_21:f0
input:f1 -> merge_21:f1:n
input:f2 -> merge_22:f0
input:f3 -> merge_22:f1
input:f4 -> merge_23:f1
input:f5 -> merge_23:f0
input:f6 -> merge_24:f1
input:f7 -> merge_24:f0:n
merge_21:f0 -> merge_41:f1
merge_21:f1 -> merge_41:f3
merge_22:f0 -> merge_41:f2
merge_22:f1 -> merge_41:f4
merge_23:f0 -> merge_42:f1
merge_23:f1 -> merge_42:f4
merge_24:f0 -> merge_42:f2
merge_24:f1 -> merge_42:f3
merge_41:f1 -> result:f1
merge_41:f2 -> result:f3
merge_41:f3 -> result:f4
merge_41:f4 -> result:f5
merge_42:f1 -> result:f0
merge_42:f2 -> result:f2
merge_42:f3 -> result:f6
merge_42:f4 -> result:f7
}
```
可以看到當 top down 所處理的子串列長度小於 cache size 的時候，cache miss 的數量就減少了。
但在這邊我意識到如果 bottom up 的 merge sort 如果不需要在每次迭代都走訪一次整個串列的話，那麼 cache miss 的數量是有辦法被降低的。在 list_sort.c [commit b5c56e0c](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 的提交訊息當中也有以下描述：
> While textbooks explain bottom-up mergesort as a succession of merging
passes, practical implementations do merging in depth-first order: as
soon as two lists of the same size are available, they are merged. This
allows as many merge passes as possible to fit into L1; only the final
few merges force cache misses.
可以看到在實務上， bottom up merge sort 的實作方法並不是像教科書寫的那樣，在每次的迭代都走訪一次整個串列。
### 進一步理解 list_sort
- **理解 `count` 的機制**
依照 list_sort.c 裡面的註解來看，我們可以用有限狀態機的方式去理解 `count` 是如何運作的：
```c
/* There are six states we distinguish. "x" represents some arbitrary
* bits, and "y" represents some arbitrary 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 sizes < 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
* (merge and loop back to state 2)
*/
```
為了理解上面註解的敘述，下面是我整理的範例：
| state | `count` | `pending` 所擁有的串列的性質 |
|--------|--------------|--------|
|2 |0==10==0 |0 個長度為 $2^2$ 的串列; 剩下串列的節點數量總和為 $2^2 + 0$ |
|2 |0==10==1 |0 個長度為 $2^2$ 的串列; 剩下串列的節點數量總和為 $2^2 + 1$ |
|3 |0==11==0 |1 個長度為 $2^2$ 的串列; 剩下串列的節點數量總和為 $2^{2-1} + 0$ |
|3 |0==11==1 |1 個長度為 $2^2$ 的串列; 剩下串列的節點數量總和為 $2^{2-1} + 1$ |
|4 |1==00==0|1 個長度為 $2^2$ 的串列; 剩下串列的節點數量總和為 $2^2 + 0$ |
|4 |1==00==1 |1 個長度為 $2^2$ 的串列; 剩下串列的節點數量總和為 $2^2 + 1$ |
|5 |1==01==0 |2 個長度為 $2^2$ 的串列; 剩下串列的節點數量總和為 $2^{2-1} + 0$ |
|5 |1==01==1 |2 個長度為 $2^2$ 的串列; 剩下串列的節點數量總和為 $2^{2-1} + 1$ |
並且以下程式碼：
```c
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
它表面上是要去找最右邊的 0 ，但實際上這也等價於「找到下次 count + 1 的時候會從 0 變成 1 的那個 bit 」。
舉一個例子，`011011` 最右邊的 0 是第二個位元，那當我們把這個數字加一的時候就會變成 `011100` ，可以注意到位元零跟一都從 1 變成 0 ，但是位元二卻從 0 變成了 1 ：
```
a == 011011 => 最右邊的 0 是第二個位元
a += 1
a == 011100 => 加一之後，可以觀察到第二個位元同時也是從 0 變成 1 的那個位元
```
- **閱讀 list sort 的演算法修改紀錄 [commit b5c56e0c](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09)**
由於呼叫 `cmp()` 函式會對效能造成負面影響，所以這次 commit 旨在於減少演算法中的比較次數。
在不同種類的 merge sort 當中，top down merge sort 可以達到最低的比較次數，但是當這個演算法在將串列分成兩個子串列的時候，它會需要先把整個串列都走訪一遍才能得到串列的中心點，而當串列的大小無法被 cache 容納時，「走訪整個串列」這件事情會造成 cache 不停的被更新（因為我們一直走訪不在 cache 裡面的節點），造成效能降低。
相對的， bottom up merge sort 不需要將串列分成兩個子串列，所以不存在上述問題。但是當串列的長度略大於 2 的冪時，bottom up merge sort 的效能會明顯的降低。以長度為 1025 （略大於 1024 ）的串列來說，當 bottom up merge sort 合併到最後一次的時候會剩下兩個子串列：
- 一個長度為 1024 的串列
- 一個長度為 1 的串列
這時候為了要將這兩個子串列合併在一起，我們會需要呼叫平均 512 次 `cmp()` 函式才能完成整個串列的排序，跟排序長度為 1024 的串列比較起來 bottom up merge sort 在排序長度為 1025 的串列的效能明顯是較低的。
會造成 top down 跟 bottom up 兩者之間的差異，我的觀察是因為 top down 的方法會在實際排序之前先取得串列的長度，那有了這樣的資訊，演算法就可以在選擇適當的斷點，將串列切割成子串列。而 bottom up 的方法在處理到串列中最一個節點之前，都無法得知整個串列的長度，少了整個串列的長度資訊，演算法就無法規劃出最有效率的分割方式。
### 效能比較
#### 執行時間比較
> 在這裡 `sort` 的實作方式是標準的 top down merge sort 。
參考 [kdnvt](https://hackmd.io/@sysprog/linux2022-sample-lab0#%E7%94%A8%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E5%B7%A5%E5%85%B7%E6%AF%94%E8%BC%83-list_sortc-%E5%8F%8A%E8%87%AA%E5%B7%B1%E5%AF%A6%E4%BD%9C%E7%9A%84%E6%8E%92%E5%BA%8F) ，我在 `qtest.c` 裡面新增了一個 `ksort` 指令，並且執行時會使用 `list_sort.c` 內的排序方法對鏈節串列做排序。
測試手法則是使用 `qtest` 內建的 `time` 命令，來測量排序所花的時間，測試方法如下：
使用以下腳本，並且執行 `$ make check`
```
cmd> new
cmd> ih RAND 100000
cmd> time sort
Delta time = 0.125
cmd> free
cmd> new
cmd> ih RAND 100000
cmd> time ksort
Delta time = 0.104
```
將串列長度增加到 1000000 再試一次：
```
cmd> new
cmd> ih RAND 1000000
cmd> time sort
Delta time = 1.601
cmd> free
cmd> new
cmd> ih RAND 1000000
cmd> time ksort
Delta time = 1.490
```
可以看到 `ksort` 的效能是優於原本的 `sort` 的。
> TODO: check cache miss of top down merge sort and list sort
> https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-b
> https://valgrind.org/docs/manual/cg-manual.html
> https://www.cs.cmu.edu/afs/cs.cmu.edu/project/cmt-40/Nice/RuleRefinement/bin/valgrind-3.2.0/docs/html/cg-manual.html
#### cache miss 比較
使用以下 qtest 腳本：
```
option fail 0
option malloc 0
new
ih RAND 500000
time ksort # 如果想要測試另一個演算法，則將 ksort 改成 sort
free
```
並且使用 `valgrind` 的 `cachegrind` 工具做測試：
```bash
# 執行測試並產出報告
$ valgrind --tool=cachegrind ./qtest -v 1 -f traces/trace-eg.cmd
```
該命令會產生一個叫做 `cachegrind.out.{pid}` 的報告檔，其中 `pid` 的值就是被測試的程式的 process id 。
產生報告檔後，就可以用下面的命令來查閱報告：
```bash
# 閱讀報告
$ cg_annotate cachegrind.out.{pid}
```
以下是兩個不同排序實作的實驗結果
- top down merge sort (使用 `sort` 命令)
```
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
--------------------------------------------------------------------------------
1,316,226,147 (100.0%) 1,883 (100.0%) 1,867 (100.0%) 333,574,023 (100.0%) 23,672,579 (100.0%) 9,595,756 (100.0%) 183,753,935 (100.0%) 7,817,164 (100.0%) 3,827,764 (100.0%) PROGRAM TOTALS
```
- list sort (使用 `ksort` 命令)
```
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
--------------------------------------------------------------------------------
1,139,560,405 (100.0%) 1,886 (100.0%) 1,870 (100.0%) 259,533,929 (100.0%) 18,497,711 (100.0%) 9,529,891 (100.0%) 132,075,742 (100.0%) 2,731,157 (100.0%) 2,551,728 (100.0%) PROGRAM TOTALS
```
可以看到跟 list sort 比較起來，原本的 top down merge sort 不管在 read miss 跟 write miss 的表現都是比較差的。
由於 `valgrind` 的 `cachegrind` 工具所產生的報告有包含每一行程式碼所造成的 read / write miss 的數量，所以可以利用這份報告來分析是程式碼的哪個部份造成 cache 的效率低下。
以下是我使用這份報告對我實作的 top down merge sort 的分析：
- **read miss 來源**：
```
Dr D1mr DLmr
0 0 0 for (struct list_head *fast = head->next;
4,783,216 ( 1.43%) 2,515,562 (10.63%) 745,274 ( 7.77%) fast != head && fast->next != head;
9,384,992 ( 2.81%) 4,637,747 (19.59%) 1,039,718 (10.84%) fast = fast->next->next, slow = slow->next) {
. . . }
```
這段程式碼的目的是走訪整個串列，並找出串列的中間點。可以看到這兩行程式雖然在 data read 的次數只佔了整個程式的 4% 左右，但是 data read miss 在整個程式的佔比卻高達 30% 。這裡可以看到「對整個串列做走訪」這件事情對效能是有影響的。
另外 `q_size` 的實作方式也是造成 cache miss 的來源之一：
```
Dr D1mr DLmr
. . . int q_size(struct list_head *head)
0 0 0 {
0 0 0 if (!head)
. . . return 0;
. . .
0 0 0 int len = 0;
. . . struct list_head *li;
. . .
11,475,712 ( 3.44%) 6,251,538 (26.41%) 2,515,738 (26.22%) list_for_each (li, head)
0 0 0 len++;
. . . return len;
1,000,000 ( 0.30%) 1,749 ( 0.01%) 18 ( 0.00%) }
```
這裡可以再次驗證，「走訪整個串列」這件事情對 cache 的效能是非常不友善的。
- **write miss 來源**：
```
Dw D1mw DLmw
. . . static inline void list_del(struct list_head *node)
. . . {
0 0 0 struct list_head *next = node->next;
0 0 0 struct list_head *prev = node->prev;
. . .
8,837,160 ( 4.81%) 5,556,265 (71.08%) 1,774,804 (46.37%) next->prev = prev;
8,837,160 ( 4.81%) 0 0 prev->next = next;
```
我實作的 merge sort 在將兩個串列合併的時候，會把兩個串列最前端比較小（或是比較大）的那個節點移到新的串列上，而當要把該節點從舊的串列移除的時候就會使用到 `list_del` 這個函式。
觀察 `list_del` 的程式碼邏輯，因為這個函式所操作的資料是雙向的環狀鏈節串列，所以為了刪除節點，程式碼需要做以下的操作：
- 改寫欲刪除節點的下一個節點的 `prev` 指標
- 改寫欲刪除節點的上一個節點的 `next` 指標
換句話說，每當刪除一個節點，我都要對另外兩個節點的內容（也就是 `prev` 跟 `next` ）做改寫，當所以當要改寫的節點不在 cache 裡面，就會造成 cache write miss 。
回到 merge sort 的程式碼，在程式碼中我刪除的都是第一個節點，而第一個節點的上一個節點永遠都會是 `head` 這個特殊節點，所以不太會出現 cache miss 的情況。但是第一個節點的下一個節點在每次進行刪除的時候都會是不一樣的，在這樣的情況下，如果我想更新下一個節點的 `prev` 指標的話，就很容易造成 cache write miss 。
相較於我實作的 merge sort ，list sort 在演算法內部所採用的串列型態是單向且非環狀的鏈節串列。所以在刪除節點時，程式碼只需要去改寫該節點上一個節點的 `next` 指標。跟雙向的環狀鏈節串列比起來，這種設計可以大幅降低 cache write miss 的次數。
### 其他問題
在將程式碼做 commit 的時候遇到了一些問題，下面是問題紀錄以及解決方法
為了將 `list_sort()` 導入到程式碼裡面，我另外新增了 `list_sort.c` 跟 `list_sort.h` 兩個檔案，並且把從 Linux kernel 修改的程式碼放在這兩個檔案裡面，並且與能夠直接編譯並正確執行。
但是當我試著把我的程式碼做 commit 的時候， git 一直出現下列錯誤訊息：
```shell
hungyuhang@hungyuhang-ZenBook-UX434FQ-UX434FQ:~/linux2024/lab0-c$ git commit
Following files need to be cleaned up:
list_sort.c
list_sort.h
qtest.c
list_sort.c:11:23: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
element_t *ele1 = container_of(node1, element_t, list);
^
list_sort.c:12:23: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
element_t *ele2 = container_of(node2, element_t, list);
^
list_sort.c:22:23: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
element_t *ele1 = container_of(node1, element_t, list);
^
list_sort.c:23:23: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
element_t *ele2 = container_of(node2, element_t, list);
^
Fail to pass static analysis.
```
但我確定相同的程式碼在 `queue.c` 並不會出現這樣的錯誤訊息。
所以我檢查程式專案內的 `pre-commit.hook` 腳本，發現在 `CPPCHECK_suppresses` 參數裡面有把 `queue.c` 加入白名單裡面：
```
--suppress=nullPointer:queue.c \
```
將 `list_sort.c` 加入到白名單之後，就可以順利 commit 了。
## 比較 Timsort 與 [list_sort](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 之間的效能差異
為了比較兩者之間的效能差異，我在 [commit 1ca5d00](https://github.com/hungyuhang/lab0-c/commit/1ca5d001ff777fb465a90c36adfce00529833752) 將 Timsort 整合進 `lab0-c` ，以便使用 `qtest` 進行測試。
> 為了防止 `qtest` 因為執行時間過長而回報 `ERROR: Time limit exceeded.` ，我暫時將 `harness.c` 裡面的 `time_limit` 變數從 1 改為 3 。
下面是實際比較的方式與結果：
1. **使用隨機排序的序列**
一開始使用隨機的測資對兩種排序方式進行測試，以下是測試腳本：
```
# for sorting randomly generated array
# == using list sort ==
new
ih RAND 500000
time ksort
free
# == using timsort ==
new
ih RAND 500000
time timsort
free
```
下面是實際試跑一次的結果：
```
# for sorting randomly generated array
# == using list sort ==
Delta time = 0.425
# == using timsort ==
Delta time = 0.738
```
可以看到 timsort 排序的時間明顯大於 list sort 。
2. **使用部份排序的數列**
由於 Timsort 的強項在於處理部分已排序的資料，所以在這裡我嘗試使用 `reverseK` 函式來模擬出部份已排序的資料，以下是部份測試腳本：
```
# for sorting partially sorted array
# == using list sort ==
new
ih RAND 500000
sort
reverseK 100
reverseK 70
reverseK 50
time ksort
free
```
先將序列排序之後，我透過用不同的 k 值來反覆反轉序列來做出一個部份排序的序列。下面是輸出的結果：
```
# for sorting partially sorted array
# == using list sort ==
Delta time = 0.615
# == using timsort ==
Delta time = 0.503
```
在這個情況下， Timsort 的執行速度反而是優於 list sort 的。
最後我將上述測驗重複執行五次並且取平均，以下是結果：
| 序列型態 | 排序演算法 | 執行時間（秒） |
|--------|--------------|--------|
|隨機序列 |list sort |**0.419** |
|隨機序列 |Timsort |0.691 |
|部份排序的序列|list sort |0.616 |
|部份排序的序列|Timsort |**0.514** |
## 在 `qtest` 加入新的命令 `shuffle`
作業中要求使用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 的方式來實作 `shuffle` 的功能，並且需要證明產生出來的結果符合 Uniform distribution 。
以下是我的 shuffle 實作：
```c
void q_shuffle(struct list_head *head)
{
int range = q_size(head);
struct list_head *tmp;
while (range) {
int cnt = rand() % range;
tmp = head->next;
while (cnt--) {
tmp = tmp->next;
}
list_move_tail(tmp, head);
range--;
}
return;
}
```
這個程式碼會從佇列最前面 `range` 個節點中隨機抓一個節點然後移到佇列的最後面（也就是 `head` 的上一個），因為 `range` 會越來越小，所以被移動到後面的節點就不會再次被移動到。
使用在 lab0-d 提供的[測試程式](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)對我實作的函式做測試，以下是輸出結果：
```
Expectation: 41666
Observation: {'1234': 41802, '1243': 41490, '1324': 41625, '1342': 41683,
'1423': 41378, '1432': 41741, '2134': 41539, '2143': 41859,
'2314': 41668, '2341': 41597, '2413': 41531, '2431': 41309,
'3124': 41711, '3142': 41734, '3214': 41643, '3241': 41679,
'3412': 41687, '3421': 41982, '4123': 41509, '4132': 41734,
'4213': 41721, '4231': 41378, '4312': 41693, '4321': 42307}
chi square sum: 23.48015168242692
```
將 Observation 裡面的數據做成分佈圖，可以看出雖然有一些差異，但是還是有大致上維持 Uniform distribution 的分佈：
## 論文閱讀 + 解析 lab0-c 的 "simulation" 模式
### 論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 以及其實作程式碼 [dudect](https://github.com/oreparaz/dudect)
這份論文是想要透過利用統計的方式來測量一段程式碼是否能在常數時間 $O(1)$ 內完成。
論文的方法如下：
1. 先準備兩組不同種類的資料
2. 將這兩組資料做為程式碼的輸入去執行，並且分別統計程式碼在這兩組資料上所耗費的時間分佈
3. 透過統計學去分析程式碼在這兩組資料上運行的時間分佈是否不同
4. 如果不同的話則代表該程式碼的時間複雜度並非 $O(1)$
以 `q_insert_head` 來舉例的話，如果我們實作的程式碼是 constant time 的話，那不管輸入的字串長度是兩個位元還是一萬個位元，程式碼的執行時間理論上都不應該會有顯著的差異。
### lab0-c 的 "simulation" 模式
simulation 模式可以透過 `qtest` 內的命令將其開啟或是關閉，由一個全域變數 `simulation` 來做控制。
舉 `q_insert_head()` 為例子，在 `qtest.c` 的程式碼中會去呼叫 `is_insert_head_const()` ：
```c
if (simulation) {
if (argc != 1) {
report(1, "%s does not need arguments in simulation mode", argv[0]);
return false;
}
bool ok =
pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const();
if (!ok) {
report(1,
"ERROR: Probably not constant time or wrong implementation");
return false;
}
report(1, "Probably constant time");
return ok;
}
```
然後經過一連串的追蹤，可以發現程式碼會去呼叫 `fixture.c` 內的 `test_const()` ，其中 `text` 內的文字是 `"insert_head"` ：
```c
static bool test_const(char *text, int mode)
{
bool result = false;
t = malloc(sizeof(t_context_t));
for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
init_once();
for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
++i)
result = doit(mode);
printf("\033[A\033[2K\033[A\033[2K");
if (result)
break;
}
free(t);
return result;
}
```
主要的測試程式碼都是在 `doit()` 函式內被執行。
#### 程式碼改寫
觀察跟 [dudect 原始碼](https://github.com/oreparaz/dudect/blob/master/src/dudect.h)之間的差異，主要有兩個部份：
1. lab0-c 內缺少了 `prepare_percentiles()` 這個函式
2. 在呼叫 `update_statistics()` 的時候，dudect 的程式碼會忽略前 10 筆資料，但是 lab0-c 的程式碼卻不會
[commit 91a81d9](https://github.com/hungyuhang/lab0-c/commit/91a81d94fe85cdb616f879ffff521cb684739e95) 可以通過 `trace-17-complexity` 測試了：
```
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
```
Sign in with Wallet
Connect another wallet