---
tags: linux2024
---
# 2024q1 Homework1 (lab0)
contributed by < `randyuncle` >
## Reviewed by `SHChang-Anderson`
* 鏈結串列的~~遍歷~~應更改為走訪。
* 透過 [perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 或其他工具分析 `list_sort.c` 與專案實作的排序方式效能差異。
## Reviewed by `Shawn531`
* `list_sort.c` 使用 perf 分析，並放上分析結果。
## 開發環境
```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: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i9-12900H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 14
Socket(s): 1
Stepping: 3
CPU max MHz: 5000.0000
CPU min MHz: 400.0000
BogoMIPS: 5836.80
Caches (sum of all):
L1d: 544 KiB (14 instances)
L1i: 704 KiB (14 instances)
L2: 11.5 MiB (8 instances)
L3: 24 MiB (1 instance)
```
## 指定佇列的操作
### `q_new`
首先以 `malloc` 來配置 `struct list_head` 大小的記憶體空間給最初的節點，之後再將其以 `list.h` 的內部 function `INIT_LIST_HEAD` 把該節點的內容初始化。
除此之外，為了防止 `malloc` 無法配置記憶體空間的問題，所以加了一個 if-statement 判斷此節點是否為 NULL，以防在做 `INIT_LIST_HEAD` 的初始化時出錯。
### `q_free`
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list)、「佇列」(queue)，和「函式」(function，端視情境而定)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
> 已做初步的改動。
:::
以 `list.h` 中的巨集 `list_for_each_entry_safe` 對輸入進來的 `struct list_head *head` 做迭代。
其中，將所有經過的節點的 :
* `struct list_head list` : 以 `list.h` 的函式 `list_del` 刪掉。
```c
list_del(&iterator->list);
```
* `char *value` : 以 `queue.h` 的函式 `q_release_element` 釋放掉。
```c
q_release_element(iterator);
```
除此之外，為了防止輸入進來的 `struct list_head *head` 是 NULL，所以多加了一個 if-statement 判斷其是否為 NULL。
### `q_insert_head` / `q_insert_tail`
這兩個函式的<s>實做</s> 實作是大同小異的，都是先新增一個 `element_t` 型態的節點，將輸入進函式的兩個變數－`struct list_head *head`、`char *s` －儲存。
```c
element_t *new = (element_t *) malloc(sizeof(element_t));
int s_len = strlen(s) + 1;
new->value = (char *) malloc(s_len * sizeof(char));
```
之後，再使用 `list.h` 的函式將 `element_t` 內的 `list` 加入到佇列之中。其中，`q_insert_head` 用的是 `list_add` ; `q_insert_tail` 使用 `list_add_tail`。
```c
/* depends on where `element_t *new` inserts in a queue */
list_add(&new->list, head); // insert in the head of queue
list_add_tail(&new->list, head); // insert in the tail of queue
```
### `q_size`
採用 `list.h` 的函式 `list_for_each` 做鏈結串列的<s>遍歷</s> ，達成佇列長度的計算。
```c
struct list_head *p;
list_for_each (p, head)
size++;
```
### `q_remove_head` / `q_remove_tail`
這兩個函式的實作方式是大同小異的。差別在於 `q_remove_head` 是用 `list.h` 中的 `list_first_entry` 去找到要被移走的頭部節點 ; 而相反的，`q_remove_tail` 是用 `list.h` 中的 `list_last_entry` 去找到要被移走的尾部節點。以下程式碼為上述描述的參考。
```c
/* depends on which node you want to remove */
/* remove head node */
element_t *remove = list_first_entry(head, element_t, list);
/* remove tail node */
element_t *remove = list_last_entry(head, element_t, list);
```
> [commit 03a14a2](https://github.com/randyuncle/lab0-c/commit/03a14a2e51baa387a568613ee8130a1ed35afc6d)
根據 Valgrind 的初步檢查，此兩個函式的實作有潛在的 `Invalid Memory Access` 的問題，因此做了以下的改動改善相關的問題。
```diff
- memcpy(sp, remove->value, bufsize);
+ size_t q = bufsize > strlen(remove->value) + 1
+ ? strlen(remove->value) + 1
+ : bufsize;
+ memcpy(sp, remove->value, q);
```
### `q_delete_mid`
在尋找中間節點的實作當中，一開始是參考了 [Floyd’s Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection) 的理論，運用快慢指標的方式找到中間節點。
但是，由於此程式的佇列是用 circular double 鏈結串列的形式所構成，所以就稍微改變了一下實作的方式成以下：
1. 令兩個 `struct list_head` 的指標 `foreward` 和 `backward` 。前者的作用是從佇列的開頭往後跑一個節點 ; 後者的作用是從佇列的尾端往前跑一個節點。
```c
struct list_head *foreward = head->next, *backward = head->prev;
```
2. 當兩個指標指到同一個節點時，或者是 `foreward` 指標的下一個節點是 `backward` 時，則 `foreward` 指標指到的節點為該佇列的中間節點。
```c
for (; foreward != backward && foreward->next != backward;
foreward = foreward->next, backward = backward->prev)
;
```
### `q_delete_dup`
運用到了 `list.h` 中的巨集 `list_for_each_entry_safe` 來遍歷以 `element_t` 做為節點的資料型態的鏈結串列 `list` 。其中，以 `element_t *iterator` 當作該巨集中的 `entry` 參數，`element_t *next` 當作該巨集中的 `safe` 參數。
```c
list_for_each_entry_safe (iterator, next, head, list)
```
並且，根據每次的迭代，會有以下判斷的方式判斷是否有重複的字串：
* 當 `next != head` 且 `next->value` == `iteration->value` 時：
* 進入 do-while 迴圈中，把 `next` 指標指到的節點刪除，並將 `next` 指標移到他的下一個節點上，以相通得判斷式判斷該節點的 `value` 是否也為該重複的字串。
```c
do {
element_t *next_to_safe =
list_entry(next->list.next, element_t, list);
list_del(&next->list);
q_release_element(next);
next = next_to_safe;
} while (&next->list != head &&
!strcmp(iterator->value, next->value));
```
* 迴圈結束後，把當前 `iterator` 指標指到的節點刪除，回去 `list_for_each_entry_safe` 巨集做迭代。
### `q_swap`
使用兩個指標 `struct list_head *curr` 和 `struct list_head *next` ，分別代表兩個要被互相交換的節點，以及一個 for 迴圈做 `struct list_head` structure 的鏈結串列遍歷。
```c
struct list_head *curr = head->next, *next = curr->next;
for (; curr != head && next != head; curr = curr->next, next = curr->next)
list_move(curr, next);
```
其中，`curr` 和 `next` 任兩個指標在未到達 `struct list_head *head` 的情況下，會先以 `list.h` 中的函式 -- `list_move` -- 將 `curr` 和 `next` 指標指向的節點做交換。之後，再將 `curr` 指向當前位置的下一個節點，以及 `next` 指標指向 `curr` 指標目前指到的節點的下一個節點，避免有交換到已經做過交換的節點。
### `q_reverse`
使用 `list.h` 的巨集 `list_for_each_safe` 去遍歷所有的 `struct list_head` structure 的鏈結串列，並將每一個遍歷到的節點都使用 `list.h` 的函式 `list_move` 搬到整個佇列的頭部，也就是成為 `struct list_head *head` 的後一個節點。
```c
/*move each item the iterator points to to the
* head*/
list_for_each_safe (iterator, next, head)
list_move(iterator, head);
```
### `q_reverse_k`
目前使用的方法是用 `list.h` 的巨集`list_for_each_safe` 去遍歷所有的 `struct list_head` structure 的鏈結串列
```c
list_for_each_safe (iterator, next, head)
```
並在其中加入一個計數器來計是否已經經過 k 個節點。
```c
i++; /* The counter */
if (i < k)
continue;
```
如果已經經過 k 個節點，則會用前一個實作函式 `q_reverse` 去把該 k 個節點反轉。
```c
/*`dummy` is a `struct list_head` type pointer that is the linked-list
* which is composed of the orgin linked-list with k specific nodes*/
q_reverse(&dummy);
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
> 收到！已做初步的改動。
:::
### `q_sort`
在本程式中的 `q_sort` 我採用的是 merge sort 。其中，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 實作。也因此，我把 `q_sort` 拆成了三個函式 -- `q_sort` 、`divide`、`merge_two_list` 。接下來，將針對以上提及的三個函式做說明。
#### `q_sort`
此函式旨在作為外部程式進行佇列排序時所呼叫的函式。
在開始進行遞迴排序前，由於輸入進來的佇列是 doubly circular 鏈結串列，如果我們要進行 merge sort 中的拆分步驟的話，會需要多額外考慮到每個拆分的佇列需要有 `struct list_head *head` 的問題。因此，在這一個函式中，會先將 doubly circular 鏈結串列轉換成沒有 `struct list_head *head` 的 doubly 鏈結串列，簡化排序程式實作的難度。以下程式碼為上述描述的參考。
```c
struct list_head *end = head->prev;
// make the list no longer be circular
end->next = NULL;
head->next->prev = NULL;
```
:::warning
TODO: 考慮 Timsort 的整合，應提出對應的測試計畫，不只有亂數產生的資料序列。
:::
> commit [2074559](https://github.com/randyuncle/lab0-c/commit/2074559056f1ddf923074b7f480b8b01e30f8e8d)
為了考慮到 Timsort 整合的測試計畫，我在 commit [2074559](https://github.com/randyuncle/lab0-c/commit/2074559056f1ddf923074b7f480b8b01e30f8e8d) 調整了 `divide()`、`merge_two_list()` 的引數內容。在參照 `lib/list_sort.c` 的程式碼後，我在這兩個函式增加了 `void *priv` 和 `list_cmp_func_t cmp` 兩個引數，使它們擁有接收自定義比較函式的能力。
除此之外，我也為此，仿製 `lib/list_sort.c` 的 `list_sort()` 函式的定義，在 `queue.[ch]` 新增了一個命名為 `sort()` 的函式，專門用來給後續的測試程式使用。
#### `divide`
在 `q_sort` 使佇列失去 circular 鏈結串列的特性後，會先呼叫 `divide` 進行遞迴拆分 。
`divide` 函式的主要目的是找到一個鏈結串列的中間節點，將其拆分為兩個鏈結串列，然後分別對這兩個串列進行遞迴調用 `divide`。當鏈結串列被拆分成只有一個節點時，將兩個相鄰的鏈結串列使用 `merge_two_list` 函式合併成已排序的鏈結串列，然後依次將結果回傳給前一次的函式呼叫。
在尋找中間節點的過程中，使用了之前實現的 `q_delete_mid` 函式的方法。該方法宣告了兩個指標，分別指向鏈結串列的頭部和尾部，在一個 for 迴圈中相互逼近。
#### `merge_two_list`
做法源自於[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)的一個片段 -- `從 Linux 核心的藝術談起 — 案例探討: LeetCode 21. Merge Two Sorted Lists` ，也就是利用間接指標的概念將要合併的節點一個一個串起來。
其中，判斷要選擇哪個節點進行合併的 if 判斷條件受到 `bool descend` 的影響，決定最終排序結果是升冪還是降冪。
```c
if ((!descend && strcmp(l->value, r->value) < 0) ||
(descend && strcmp(l->value, r->value) > 0))
```
### `q_ascend` / `q_descend`
由於這兩個函式的操作都非常的相似，因此合併做撰寫。
#### `q_descend`
根據 [Leetcode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/description/) 的例子可以看出，`q_descend` 運行完以後的已排序鏈結串列會呈降冪排列。
:::warning
給定的鏈結串列已是環狀，何謂「逆向」？需要明確的定義。
:::
因此，此部分的實作就以兩個 `element_t` 型態的指標：`*p`, `*c_max` 配合一個 for 迴圈對佇列<s>逆向</s> <s>遍歷</s>從尾端節點向前（`head->prev`），依次走訪到開頭節點。
:::danger
使用清晰的表達，例如「從開頭向後，逐次走訪到尾端」和「從尾端向前，逐次走訪到開頭」，寧可用更多話，不要存在語意的模糊。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
```c
struct list_head *curr = head->prev;
```
就 `q_descend` 函式的角度來看，當指標 `*p` 指向的節點的 `value` 比起 `*c_max` 指到的來得小的話，就會將其抹除 ; 若否，則將 `*c_max` 更新為 `*p` 指到的節點。
```c
strcmp(p->value, c_max->value) < 0
```
#### `q_ascend`
另一方面，`q_ascend` 函式移除節點的標準正好為 `q_descend` 函式的相反，因此，此函式的變數選擇將和 `q_descend` 一樣，且其 for 迴圈走訪的方向與 `q_descend` 相反；亦即，從開頭節點向後（`head->next`），依次走訪到尾端節點。
```c
struct list_head *curr = head->next;
```
就 `q_ascend` 函式的角度來看，由於 for 迴圈走訪的方向和 `q_descend` 函式相反。因此，其判斷是否移除節點的 if 判斷條件和 `q_descend` 函式一樣，並不會有變化。
```c
strcmp(p->value, c_max->value) < 0
```
### `q_merge`
將 `queue_contex_t` structure 各個分段的佇列以 `list.h` 的函式 `list_splice_init` 接在以 `queue_contex_t *main_q` 的佇列之中。
```c
queue_contex_t *c = list_entry(curr, queue_contex_t, chain);
list_splice_init(c->q, main_q->q);
```
之後，再使用前面寫的 `q_sort` 函式將 `queue_contex_t *main_q` 佇列做重新排列。
```c
q_sort(main_q->q, descend);
```
## 目前指定佇列操作的自動測試結果
### `make test`：靜態分析結果
目前評分：95/100
未通過的測試：`trace-17-complexity`
`q_insert_head`, `q_insert_tail`, `q_remove_head` 皆有以下的錯誤訊息。
> ERROR: Probably not constant time or wrong implementation
`q_remove_tail` 的結果為：
> Probably constant time
### `make valgrind`：動態分析結果
* 目前評分：48/100
* 未通過的測試：
```shell
trace-01-ops
trace-02-ops
trace-03-ops
trace-04-ops
trace-05-ops
trace-06-ops
trace-07-string
trace-09-robust
trace-17-complexity
```
其中，測試資料 01，02，03，04，05，06，07，09 在做靜態評分的話。因此，接下來，我們將針對動態評分 ( Valgrind ) 的結果，檢討程式潛在的記憶體分配問題。
#### 從測試資料 `trace-01-ops` 探討潛在記憶體分配問題
首先，我們先從 `trace-01-ops` -- 主要是做 `insert_head` 以及 `remove_head` 的測試 -- 遇到的問題做排查。
以下是使用 Valgrind 做 `trace-01-ops` 測試後得到的結果節錄：
```shell
==13519== Invalid read of size 8
==13519== at 0x4852AF8: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==13519== by 0x10F8DE: memcpy (string_fortified.h:29)
==13519== by 0x10F8DE: q_remove_head (queue.c:85)
==13519== by 0x10C714: queue_remove (qtest.c:353)
==13519== by 0x10C8BC: do_rh (qtest.c:410)
==13519== by 0x10DFD1: interpret_cmda (console.c:181)
==13519== by 0x10E586: interpret_cmd (console.c:201)
==13519== by 0x10E987: cmd_select (console.c:610)
==13519== by 0x10F273: run_console (console.c:705)
==13519== by 0x10D3C3: main (qtest.c:1258)
==13519== Address 0x4b85448 is 8 bytes before a block of size 2,049 alloc'd
==13519== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==13519== by 0x10C4B3: queue_remove (qtest.c:318)
==13519== by 0x10C8BC: do_rh (qtest.c:410)
==13519== by 0x10DFD1: interpret_cmda (console.c:181)
==13519== by 0x10E586: interpret_cmd (console.c:201)
==13519== by 0x10E987: cmd_select (console.c:610)
==13519== by 0x10F273: run_console (console.c:705)
==13519== by 0x10D3C3: main (qtest.c:1258)
==13519==
```
從上面的結果節錄中，配合 [lab0 作業說明 -- 以 Valgrind 分析記憶體問題](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-b#Valgrind-%E4%BD%BF%E7%94%A8%E6%A1%88%E4%BE%8B)輔助解讀，觀察到問題是 `Invalid Memory Access`，並且問題源於佇列操作函式 `q_remove_head` 中對 `memcpy()` 的 C 語言函式使用。
因此，以下將相關的實作片段擷取出來檢查：
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
...
if (sp) {
memcpy(sp, remove->value, bufsize);
sp[bufsize - 1] = '\0';
}
...
}
```
經過對比後，可以發現到輸入參數 `bufsize` 的大小是 1025，和測試字串參數 `*sp` 長度為 8 是不相符的，代表說不能完全依賴輸入的 `bufsize` 資訊去做記憶體內容複製。
所以，根據上述的發現，將上述程式碼做以下改動：
```diff
- memcpy(sp, remove->value, bufsize);
+ size_t q = bufsize > strlen(remove->value) + 1
+ ? strlen(remove->value) + 1
+ : bufsize;
+ memcpy(sp, remove->value, q);
```
:::spoiler
```shell
# Test of insert_head and remove_head
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
Removed dolphin from queue
l = [bear gerbil]
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
Freeing queue
```
:::
再做一次 Valgrind 測試，可看到之前 Valgrind 偵測到的 `Invalid Memory Access` 問題已被解決。
不過，由於我在 `q_remove_tail` 的函式實作有和 `q_remove_head` 一樣的操作，導致其也產生了一樣的問題。因此，在 [commit 03a14a2](https://github.com/randyuncle/lab0-c/commit/03a14a2e51baa387a568613ee8130a1ed35afc6d) 中一同更新。
最後，在修改了 `q_remove_tail` 和 `q_remove_head` 後，得到以下的 `make Valgrind` 動態分析結果：除了 `trace-17-complexity` 測試以外，其他皆通過，也就是 95/100。
---
## Linux 核心原始程式碼 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 研讀及引入
TODO:
- [X] Documenting my insights into the functionality of lib/list_sort as implemented in the Linux kernel.
- [x] Incorporate and integrate the list_sort.[ch] files into lab0-c, and update the corresponding git commit.
1. - [x] Introduce the related files and work into lab0-c repository.
2. - [x] Test if it works well.
- [X] Apply an experiment
- [X] Implement the command `shuffle`
- [X] Introduce Tim sort to `queue.c`
### [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 研讀紀錄
Linux 核心的鏈接串列排序採用 bottom up merge sort 方法，主要原因是，相比於比較次數更少的 top down 方法而言，它對於 cache 的利用更加友好。這樣做不太可能引起快取的頻繁內容移進、移出和更新。除此之外，`list_sort.c` 使用了 depth-first merge order，從而降低及避免 [cache thrashing](https://en.wikipedia.org/wiki/Thrashing_(computer_science)) 的機率發生。
在閱覽程式碼及註解時，有一個疑惑是為何需要寫明鏈接串列的大小比例需遵守 $2:1$ 的原則。直到閱讀 [Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e#%E4%BD%95%E6%99%82%E5%90%88%E4%BD%B5)的表格、圖解、以及下方的相關證明，以及嘗試閱讀了貢獻者附的三篇論文，才有些明白其中的原因。
#### The Queue-mergesort
<!--Note
三篇論文的數學證明內容都不是看得很懂，所以只能以比較白話的方式，撰寫論文中的證明結論或部分證明邏輯。
若能搞清楚大概得方向，就可以得知作者修改得程式碼的邏輯。
-->
[Queue-mergesort](https://doi.org/10.1016/0020-0190(93)90088-q) 的概念在 1993 年發表於 Information Processing Letters, 48(5) 的同名論文標題中，被證明其相比於 top-down 以及 bottom-up 的方法來說，在 worst case 的情況下，有著最優的比較次數。換句話說，這篇論文表示 Queue-mergesort 是一個最優的合併排序演算法。
在這篇論文中，假設每條佇列中只有一個元素，Queue-mergesort 的運作方式可表示為以下的樹狀結構 ( 以 5 條佇列為例 )：
原本的佇列狀態為以下（節點中的數字為本佇列的元素數量）
```graphviz
digraph queue_1 {
rankdir=TD; # 順序由左至右(上下是"TD"
# node
A[label = "1", shape=box]
B[label = "1", shape=box]
C[label = "1", shape=box]
D[label = "1", shape=box]
E[label = "1", shape=box]
}
```
第一次合併最左邊的兩個佇列（1 + 1 = 2），並更新於整條串列的最右邊
```graphviz
digraph queue_2 {
rankdir=TD; # 順序由左至右(上下是"TD"
# node
A[label = "1", shape=box]
B[label = "1", shape=box]
C[label = "1", shape=box]
D[label = "2", shape=box]
}
```
第二次合併的方式和上一步同理
```graphviz
digraph queue_2 {
rankdir=TD; # 順序由左至右(上下是"TD"
# node
A[label = "1", shape=box]
B[label = "2", shape=box]
C[label = "2", shape=box]
}
```
第三次合併最左邊的兩個佇列（2 + 3 = 5），並更新於整條串列的最右邊
```graphviz
digraph queue_3 {
rankdir=TD; # 順序由左至右(上下是"TD"
# node
A[label = "2", shape=box]
B[label = "3", shape=box]
}
```
第四次合併，將剩餘的兩條佇列合併及結束
```graphviz
digraph queue_3 {
rankdir=TD; # 順序由左至右(上下是"TD"
# node
A[label = "5", shape=box]
}
```
這樣的樹狀結構，如果將其看做是一個由下而上的組成，亦即，以葉節點向根節點逐步合併、組合的話，則可視為[霍夫曼編碼 ( Huffman encoding )](https://en.wikipedia.org/wiki/Huffman_coding) 所形成的二元樹。霍夫曼編碼的方式為尋找欲編碼的內容中，兩兩出現頻率最低的字元進行合併至一個親代節點，直到所有出現的字元都被編碼為止。而上面的 Queue-mergesort 形成的 merge tree，也做和霍夫曼編碼同樣的方式，將頻率最低的佇列兩兩合併，直到只剩一個佇列為止。又因為霍夫曼編碼是一個最優 prefix-free 二元樹[（Algorithms -- Section 4.4, by Jeff Erickson）](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf)，故 Queue-mergesort 是一個最優合併排序演算法。只不過，從以上的圖示來看，因為它是 get front、push back 的操作，所以它是 [unstable 的排序演算法](https://doi.org/10.1016/0020-0190(93)90088-q)，此特性和其它的 merge sort 演算法是不同的。
以上對於 Queue-mergesort 的簡單描述以及圖形演示中，可以看出，此演算法是相當適合實作於鏈接串列結構的佇列。在 `lib/list_sort` 中使用的 `list.h` API 中，其鏈接串列一個節點只存取一個對應的 key（`value`），符合論文中的情境。
#### 實作於 kernel 的方法 -- Bottom-up (原做法) + Queue-mergesort ([優化](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09))
如果我們閱讀 [commit b5c56e0](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 中的 git commit message 以及觀察下方的 git diff 標示的話，可以發現 `lib/list_sort` 原本是一個 bottom-up 合併排序的實作，且 cahce-friendly 的問題也在當時就獲得重視，使得當時的 bottom-up 合併排序也用 depth-first merge order 的實作手法。
但是，原本的實作方法，會有不平衡合併的問題出現。根據論文 [Bottom-Up Mergesort - A Detailed Analysis](https://doi.org/10.1007/BF01294131) 中第 346 頁對 worst case 的理論分析結論，當元素總數 `N` 為 2 的冪時，bottom-up 合併排序有最佳的表現；但若元素總數 `N` 為 2^m^ + 1，則表現最差。另一方面，在同篇論文第 344 頁中對 best case 的理論分析結論，當元素總數 `N` 為 2 的冪時，bottom-up 合併排序有最差的表現；但若元素總數 `N` 接近 2^m^/3，則表現最佳。我們假設有一條元素總數 `N` 為 1028 佇列，一個 `N` 大於 2 的冪的佇列，到最後的合併階段，程式會面臨分別為 1024- 和 4- 節點數的鏈接串列合併，可能會需要平均比較約 4/5 的串列長度的次數，使得效能浪費於不停的比較中。
因此，作者於 [commit b5c56e0](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 中，提出以 $2:1$ 的 depth-first merge order 合併實作取代原本的做法：從 lst 為起點掃描每輪變數 `count` 的二位數值，直到碰到 least significant clear bit 之前，都會進行合併。但整體的結構還是保持 bottom-up merge sort 演算法。
#### 比例限制 $2:1$ 的由來
在 [The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules](https://doi.org/10.1006/jagm.1998.0986) 這篇論文中，它對 Queue-mergesort 有以下的敘述：
> $\tau(n) = 2^{\lfloor log_2 2n/3 \rfloor}$ (balanced power-of-2 rule) in queue-mergesort.
以及
> Note that $2^{\lfloor log_2 2n/3 \rfloor}$ is unique power-of-2 lying between $n/3$ and $2n/3$ and that of the choice of retionals other than $2/3$ is not more balanced.
> （不過根據 [lab0-(E)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e) 的敘述，這裡應該寫成 $n/3 < 2^{\lfloor log_2 2n/3 \rfloor} \le 2n/3$ 比較恰當）
代表說 Queue-mergesort 可以找到最接近 $n/2$ 的 2 的冪，這也是為什麼它會稱呼 Queue-mergesort 是 balanced power-of-2 rule。
除此之外，它也舉了以下例子：
> For example, if $\tau(n) = 2^{\lfloor log_2 n/2 \rfloor}$ and $\tau(n) = 2^{\lfloor log_2 5n/9 \rfloor}$, then the sizes of two subproblems are $(2, 5)$ for $n = 7$, while the balanced power-of-2 gives $(3, 4)$
論文舉的是 $1:1$ 以及 $5:4$ 的比例，代入 $n=7$ 的場合，都會得到 $2$，但是最接近 $7/2$ 的 2 的冪卻是 $4$，因此在做合併的過程會出現像原本的 `lib/list_sort` 實作一樣的問題 -- 會出現極度不平衡的合併狀況。另一方面，如果使用 $2:1$ 的比例的話，代入 $n=7$ 可得到 $4$，是最接近 $7/2$ 的 2 的冪。
故因此有 $2:1$ 的合併比例限制存在。
#### 如何實作比例限制 $2:1$
<!--### Note
以下都是我的思考過程。
-->
首先，先看到它合併的規則：
> The merging is controlled by "count", the number of elements in the pending lists.
主要是透過一個 `size_t` 型態的變數 `count` 來控制合併操作的時機。
```c
size_t count = 0; /* Count of pending */
```
> Each time we increment "count", we set one bit (bit k) and clear bits k-1 .. 0. Each time this happens (except the very first time for each bit, when count increments to 2^k), we merge two lists of size 2^k into one list of size 2^(k+1).
每當變數 `count` 計算到非 2 的冪時，就對目前兩個等同大小 $2 * 2^k$ 的節點執行合併，得到新的 $2^{k+1}$，留下剩餘的一個 $2^k$。
以下列舉[表格](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e#%E4%BD%95%E6%99%82%E5%90%88%E4%BD%B5)中的幾個例子的細部操作：
- [ ] 例子一
令目前的變數 `count` 為 5~10~ = 0101~2~，其 pending list 上的節點大小為 2 <- 2 <- 1。
當 `count + 1` 時，變數 `count` 更新為 6~10~ = 0110~2~。若沒有達成合併條件的話，pending list 上的新增一個一單位大小的節點，使得其成為 2 <- 2 <- 1 <- 1。
由於二進位數 01==1==0~2~ 並非 2 的冪，因此，需要進行合併。這裡我們將 2 個 $2^1$ 節點合併，得到一個 $2^2$ 的合併節點。至此，pending list 成為 ==4== <- 1 <- 1。
- [ ] 例子二
令目前的變數 `count` 為 6~10~ = 0110~2~，其 pending list 上的節點大小為 4 <- 1 <- 1。
當 `count + 1` 時，變數 `count` 更新為 7~10~ = 0111~2~。若沒有達成合併條件的話，pending list 上的新增一個一單位大小的節點，使得其成為 4 <- 1 <- 1 <- 1。
由於二進位數值 011==1==~2~ 並非 2 的冪，因此，需要進行合併。這裡我們將 3 個 $2^0$ 節點中的 2 個 $2^0$ 節點合併，得到一個 $2^1$ 的合併節點，以及 1 個 $2^0$ 節點。至此，pending list 成為 4 <- ==2== <- 1。
- [ ] 例子三
令目前的變數 `count` 為 11~10~ = 1011~2~，其 pending list 上的節點大小為 4 <- 4 <- 2 <- 1。
當 `count + 1` 時，變數 `count` 更新為 12~10~ = 1100~2~。若沒有達成合併條件的話，pending list 上的新增一個一單位大小的節點，使得其成為 4 <- 4 <- 2 <- 1 <- 1。
由於二進位數 1==1==00~2~ 並非 2 的冪，因此，需要進行合併。這裡我們將 2 個 $2^2$ 節點合併，得到一個 $2^3$ 的合併節點。至此，pending list 成為 ==8== <- 2 <- 1 <- 1。
從以上的三個例子中，可以看出，lib/list_sort 的 bottom up merge sort 實作及理論和二補數的二位數運算有關。不過，其在程式中的實作方式，就要說到此程式對於變數 `count` 的使用。
```c
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
根據註解，此段程式的用意是找到本次迭代中，變數 `count` 的[最低有效 ( least-significant ) ](https://terms.naer.edu.tw/detail/981936df1ed6a485bde1f43ce8462ba3/?startswith=zh)0 位元位。同時，也同步更新 `tail` 指標的指標對 pending list `*pending` 的定位。
每一次 `count` 值加一，就會有一個位元從 0 變成 1。該位元就會是我們要在這想要得到的 least significant clear bit。而求到 least significant clear bit 後的變數 `bits` 則會由後續的 if 條件，判斷其是否需要進行合併。
至於為何要找變數 `count` 的最低有效 0 位元位，作者在 `lib/list_sort.c` 的註解中寫下以下描述：
> The number of pending lists of size 2^k is determined by the state of bit k of "count" plus two extra pieces of information:
`-` The state of bit k-1 (when k == 0, consider bit -1 always set), and
`-` Whether the higher-order bits are zero or non-zero (i.e. is count >= 2^(k+1)).
> 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)
這裡是將 `count` 的值分成六種種類，來探討 pending list 的狀態，以及是否進行合併。其中，左邊的 0/1 代表的是第 k 個 bit，右邊的 0/1 則是代表第 k - 1 個 bit。因此，可以知道最右邊的 x 至多會是第 k - 2 個 bit，也就是其最大值是 $2^{k-1} - 1$。
<!--至於這個 k 值的由來，就要看到 [The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules](https://doi.org/10.1006/jagm.1998.0986) 論文中對 Queue-Mergesort 的 heap recurrence 的證明。(待確認，又或是指 bottom-up mergesort -- A detailed analysis 那篇)-->
在 `lib/list_sort.c` 中，作者的實作在意的是第 k 個 bit 以及第 k - 1 個 bit 的狀態和變化，判斷目前長度為 $2^k$ 的鏈接串列的數量。
`0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k`
有 $x$ 個數量的節點在長度小於 $2^k$ 的子串列。
`1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k`
有 $2^{k-1} + x$ 個數量的節點在長度小於 $2^k$ 的子串列。
`2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k`
有 $2^k + x$ 個數量的節點在長度小於 $2^k$ 的子串列。
雖然說已出現可以合併的子串列，但是由於要保持 $2:1$ 的比例合併，所以在狀態 2 時不會進行合併。
`3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k`
有一個 $2^k$ 個數量節點的子串列，且另外有 $2^{k-1} + x$ 個數量的節點在長度小於 $2^k$ 的子串列中。
在狀態 3 中，沒有合併前應該會是 $3*2^{k-1} + x$ 個數量的節點在長度小於 $2^k$ 的子串列中。為了保持 $2:1$ 的比例合併，會將其中的兩個 $2^{k-1}$ 個數量節點的子串列合併為 $2^k$ 個數量節點的子串列，即可得到比例 $2^k : 2^{k-1} = 2:1$。
`4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k`
有一個 $2^k$ 個數量節點的子串列，且另外有 $2^k + x$ 個數量的節點在長度小於 $2^k$ 的子串列中。
狀態 4 和狀態 2 是差不多的狀態，為了比例限制 $2:1$ 而不對 $2*2^{k-1}$ 個數量節點的子串列做合併。
`5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k`
有兩個 $2^k$ 個數量節點的子串列，且另外有 $2^{k-1} + x$ 個數量的節點在長度小於 $2^k$ 的子串列中。
在狀態 5 中，和狀態 3 是一樣的，由於出現 $3*2^{k-1}$ 個數量節點的子串列，因此會將其中的兩個 $2^{k-1}$ 個數量節點的子串列合併成 $2^k$。不過，為了 $2^{k+1} : 2^k = 2:1$ 的比例限制，在 $2*2^k$ 個數量節點的長度 $2^k$ 子串列不會合併，直到後續出現新的 $2^k$ 個數量節點的子串列，形成 $3*2^k$ 的狀態，才會進行合併，並將第 k 個 bit 以及第 k - 1 個 bit 的狀態會回到狀態 2，重複這樣的循環。
藉由 for 迴圈，將處理過後的變數 `bits`，會交由到以下 if 條件判斷決定是否 merge：
```c
/* Do the indicated merge */
if (likely(bits))
```
搭配前面提到的[表格](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e#%E4%BD%95%E6%99%82%E5%90%88%E4%BD%B5)中的例子做說明。以例子一來說，原本的 `count` 是 0101~2~，在 for 迴圈中遇到的 least significant clear bit 為從 lst 數來的第二個位元，對應的 pending list 狀態是 2<-2<-1，為有兩個 $2^{k=1}$ 個數量節點的子串列，以及 $2^{(k=1)-1} + 0$ 個數量的節點在長度小於 $2^k$ 的子串列中，在作者的六個狀態欄中屬於狀態 5 的情形。
在 `count` + 1 後，理論上會變成 0110~2~，位元的變化符合上一段中的 least significant clear bit 的偵測。所以，此迭代中，經過 for 迴圈的變數 `bits` 會被更新為 010~2~。在這個情況，得到目前的第 (k = 1) - 1 個 bit 為 1（lst 數來第一個位元），第 (k = 1) 個 bit 為 0（lst 數來第二個位元），從這個角度來看， `count` 為 0101~2~ 確實符合狀態 5 的描述。
到 if 條件判斷後，由於變數 `bits` 是一個大於 0 的值，符合 if 條件，因此判斷需要進行合併，也就觸發以下的合併程序：
```c
/* pointer to pointer `**tail` had been pointed to address of pending list `&pending` */
struct list_head *a = *tail, *b = a->prev;
a = merge(cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
```
主要是將 `tail` 指標的指標指到的 pending list 位置 `a` 以及其前一個節點（或串列）`b` 做合併，並將結果回傳到 `a` 指標中。以例子一來看，這個步驟就會將兩個長度為 2 的節點做合併，得到更新後 pending list 為 4<-1。
在合併且更新完後，將新的節點接入 pending list 中，最後再把 `count` + 1
```c
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
會得到 0110~2~ 的 pending list 狀態：4<-1<-1，將第 k 個 bit 以及第 k - 1 個 bit 的狀態退到狀態 2 做起點。在下一次的迭代，也就是 0110~2~ 轉到 0111~2~ 的階段，就會將狀態從狀態 2 往後推到狀態 3，判斷是否要合併。
以此類推，當 least significant clear bit 得到的結果是新的 2 的冪時，即在迭代中沒有遇到過的 2 的冪時，就不會進行合併。這個結論也可以得到，如果輸入的鏈接串列節點數量愈多，那它就相對有越大的機會在每輪的 `count` 迭代中需要進行合併。假設輸入的是 1028 個節點，那它就會需要做 1018 次的合併，比例是 1018/1028 = 0.99027...。因此，在原程式中，對於 `bits` 是否為大於零的合併 if 條件判斷，加入了 `likely()` 巨集，對編譯器表示說，這個 if 條件有極大的機率會命中。
### `lib/list_sort.c` 引入紀錄
> commit [06233a2](https://github.com/randyuncle/lab0-c/commit/06233a2a0f2ed98813b1a3b4949af677ffb840bc)
> The commit message has been refined by ChatGPT.
在本次的引入中，為了能將 list_sort 整合進 `queue.c` 中，我做了以下的改動:
#### likely/unlikely
> commit [815080f](https://github.com/randyuncle/lab0-c/commit/815080f46b932c3244b29f5606d6cb05051da4aa)
在一開始我將程式片段引入的時候，有先參考了標頭檔 [`<linux/compiler.h>`](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 中對 `likely()` 和 `unlikely()` 函式的定義，並將其引入進 `queue.c` 中。
但是，在編譯的過程中，它產生了以下的錯誤訊息：
> implicit declaration of function `__branch_check__`
在跳出此編譯錯誤後，我才發現到原來在 `<linux/compiler.h>` 中，對 `likely()` 和 `unlikely()` 巨集有兩種定義：
```c
/*
* Using __builtin_constant_p(x) to ignore cases where the return
* value is always the same. This idea is taken from a similar patch
* written by Daniel Walker.
*/
# ifndef likely
# define likely(x) (__branch_check__(x, 1, __builtin_constant_p(x)))
# endif
# ifndef unlikely
# define unlikely(x) (__branch_check__(x, 0, __builtin_constant_p(x)))
# endif
#ifdef CONFIG_PROFILE_ALL_BRANCHES
...
#endif /* CONFIG_PROFILE_ALL_BRANCHES */
#else
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
從錯誤訊息中可以發現，我原本所引入的是帶有 `__branch_check__` 的巨集。然而，`__branch_check__` 本身是一個定義在標頭檔 `<linux/compiler.h>` 裡的巨集，從而產生編譯錯誤。
:::danger
原本的 `__branch_check__` 有何作用？使用 git log 和 git blame 命令去追蹤。
:::
- [ ] `__branch_check__`
我根據老師給予之建議，使用 `git log` 以及 `git blame` 指令，於 `linux/include/linux/compiler.h` 資料路徑，尋找我原本引入的 `likely()` / `unlikely()` 巨集中的 `__branch_check__` 究竟是什麼。
根據 git 文件的說明，`git blame` 指令的用途為：
> `git-blame` - Show what revision and author last modified each line of a file.
主要是用來找某文件中的每行程式碼的最後修改資訊以及作者。因此，我先使用了此項命令嘗試尋找些蛛絲馬跡。在輸入了指定的資料路徑以及指定行數後，得到了以下的結果：
:::spoiler
```shell
d45ae1f7041ac (Steven Rostedt (VMware) 2017-01-17 12:29:35 -0500 22) #define __branch_check__(x, expect, is_constant) ({ \
2026d35741f2c (Mikulas Patocka 2018-05-30 08:19:22 -0400 23) long ______r; \
134e6a034cb00 (Steven Rostedt (VMware) 2017-01-19 08:57:14 -0500 24) static struct ftrace_likely_data \
e04462fb82f8d (Miguel Ojeda 2018-09-03 19:17:50 +0200 25) __aligned(4) \
33def8498fdde (Joe Perches 2020-10-21 19:36:07 -0700 26) __section("_ftrace_annotated_branch") \
1f0d69a9fc815 (Steven Rostedt 2008-11-12 00:14:39 -0500 27) ______f = { \
134e6a034cb00 (Steven Rostedt (VMware) 2017-01-19 08:57:14 -0500 28) .data.func = __func__, \
134e6a034cb00 (Steven Rostedt (VMware) 2017-01-19 08:57:14 -0500 29) .data.file = __FILE__, \
134e6a034cb00 (Steven Rostedt (VMware) 2017-01-19 08:57:14 -0500 30) .data.line = __LINE__, \
1f0d69a9fc815 (Steven Rostedt 2008-11-12 00:14:39 -0500 31) }; \
d45ae1f7041ac (Steven Rostedt (VMware) 2017-01-17 12:29:35 -0500 32) ______r = __builtin_expect(!!(x), expect); \
d45ae1f7041ac (Steven Rostedt (VMware) 2017-01-17 12:29:35 -0500 33) ftrace_likely_update(&______f, ______r, \
d45ae1f7041ac (Steven Rostedt (VMware) 2017-01-17 12:29:35 -0500 34) expect, is_constant); \
1f0d69a9fc815 (Steven Rostedt 2008-11-12 00:14:39 -0500 35) ______r; \
1f0d69a9fc815 (Steven Rostedt 2008-11-12 00:14:39 -0500 36) })
```
:::
第一列的 16 進位碼代表的是該行程式改動的 commit 編號。可發現到這小小的片段經歷了不少的改動，最早也可以朔源到 2008 年。
從 `git blame` 得到的資訊，我之後使用 `git log` 指令，去追蹤那個 2008 年的 commit，確認了它確實是 `__branch_check__` 巨集最早被引入進 Linux 核心的時間點。
在 commit 1f0d69a9fc815 中，首次出現 `__branch_check__` 相關的巨集內容，作者為 Steven Rostedt。但是，它原本不是叫 `__branch_check__`，而是被命名為 `likely_check(x)` / `unlikely_check(x)` 這兩個巨集名稱，但程式碼內容有非常多的相似之處。也因此，原作者於 commit 2ed84eeb8808c 以及 commit 45b797492a075 做了些許修正，其中後者就是將巨集命名改成 `__branch_check__` 的 commit。
根據作者的提交內容，此巨集的創建旨在實現**在 kernel 中分析 `likely()` / `unlikely()` 巨集運作**的目標。當配置了帶有此巨集的 `likely()` / `unlikely()` 時，理論上所有的 `likely()` / `unlikely()` 巨集都會附帶一個計數器，用於**追蹤它們的命中和未命中次數**。在觀察的任務運行結束後，可以在 `/debugfs/tracing/profile_likely` 和 `/debugfs/tracing/profile_unlikely` 兩個檔案中獲得 likely / unlikely 的數據。
作者也有在 commit 中附上了幾個使用此巨集的測試結果，以下節錄其中的部份結果。
```shell
$ cat /debug/tracing/profile_likely | awk '{ if ($3 > 25) print $0; }'
correct incorrect % Function File Line
------- --------- - -------- ---- ----
39900 36577 47 pick_next_task sched.c 4397
20824 15233 42 switch_mm mmu_context_64.h 18
0 7 100 __cancel_work_timer workqueue.c 560
617 66484 99 clocksource_adjust timekeeping.c 456
0 346340 100 audit_syscall_exit auditsc.c 1570
...
$ cat /debug/tracing/profile_unlikely | \
awk '{ if ($3 > 25) print $0; }' |head -20
44963 35259 43 __switch_to process_64.c 624
12762 67454 84 __switch_to process_64.c 594
12762 67447 84 __switch_to process_64.c 590
1478 595 28 syscall_get_error syscall.h 51
0 2821 100 syscall_trace_leave ptrace.c 1567
...
```
可以發現在 2008 年的當下，有部份 Linux 系統程式的 likely / unlikely 使用需要做調整，也證明了此巨集存在的重要性。
經過 9 年後，原作者 Steven Rostedt 提交了 commit [d45ae1f7041ac](https://github.com/torvalds/linux/commit/d45ae1f7041ac52ade6c5ec76d96bbed765d67aa)，主要是對 `__branch_check__` 巨集增加一個 `is_constant` 引數，使此巨集可以接收編譯器編譯成 `constant` 的值。
之所以需要此修改，是因為作者在使用 likely / unlikely 分析器，測到 `link_path_walk()` 函式的 `unlikely()` 時，總是顯示 100% incorrect，但在加入 `trace_printk()` 後，變成了 80% correct。造成這個原因是因為在 GCC 編譯器中，把 `link_path_walk()` 函式中帶有 `unlikely()` 的 if 條件分成兩條 path：一條使 if 條件變成 `constant`，另一條是變成 `variable`。其中變成 `variable` 的 `unlikely` 一直是命中的狀態 ; 反之，變成 `constant` 的那條會被 branch profiler 忽略，導致它被編譯器忽略。因此，作者在`__branch_check__` 巨集中增加了 `is_constant` 引數去解決此問題。
後續在 commit [134e6a0](https://github.com/torvalds/linux/commit/134e6a034cb004ed5acd3048792de70ced1c6cf5) 更新了可以顯示在 likely/unlikely 解析器中追蹤到的 `constants` 數量，以決定是否需要忽略掉它。
- [ ] `__builtin_expect`
至於下方的 `likely()` 和 `unlikely()` 巨集，則是用到 GNU GCC 的內建函式 -- `__builtin_expect`。
根據 GNU GCC 手冊第 [6.61 Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 章節中，`__builtin_expect` 的定義為：
> `long __builtin_expect (long exp, long c)`
> You may use `__builtin_expect` to provide the compiler with branch prediction information. In general, you should prefer to use actual profile feedback for this (`-fprofile-arcs`), as programmers are notoriously bad at predicting how their programs actually perform. However, there are applications in which this data is hard to collect.
> The return value is the value of `exp`, which should be an integral expression. The semantics of the built-in are that it is expected that `exp` == `c`.
從上述描述中可以得知，`__builtin_expect` 是一個用來向編譯器提供特定程式區塊的分支預測資訊的內建函式。對於這個函式而言，它的作用是告訴編譯器這個程式區塊的分支預測結果引數 `c` 的機率較高，以便編譯器優化程式的執行。此內建函式通常的用法是使用在 if 條件判斷中，給予編譯器此 if 條件是否被觸發的預測，讓編譯器去做處理。
<!--
可能可以考慮結合計組學到的東西做說明？
-->
至於這個內建函式如何提供分支預測的機率，在該 GNU GCC 手冊章節中也有說明：
> 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%.
> You can also use `__builtin_expect_with_probability` to explicitly assign a probability value to individual expressions. If the built-in is used in a loop construct, the provided probability will influence the expected number of iterations made by loop optimizations.
基本上，機率的部份是由一個變數 `builtin-expect-probability` 所定義，且預設值為 90%。如果想要對機率的部份做自定義的話，可以改為使用另一個 GCC 內建函式 `__builtin_expect_with_probability`，但本程式的原作者並沒有想採用此條函式。
在經過引入及測試該項定義後，即可通過編譯，因此在 commit [815080f](https://github.com/randyuncle/lab0-c/commit/815080f46b932c3244b29f5606d6cb05051da4aa) 改採用帶有 `__builtin_expect` 內建函式的巨集定義。
不過，在一開始編譯錯誤後我所使用的替代方案，也就是 commit [06233a2](https://github.com/randyuncle/lab0-c/commit/06233a2a0f2ed98813b1a3b4949af677ffb840bc) 中，我有意外發現到 `__gibc` 也有一組和 commit [815080f](https://github.com/randyuncle/lab0-c/commit/815080f46b932c3244b29f5606d6cb05051da4aa) 中相似的內建函式 -- `__gibc_likely`/`__gibc_unlikely`。但是，它們的定義和 `<linux/compiler.h>` 中似乎有些些的不同。
```c
/* From `__glibc` */
#define __glibc_likely(cond) __builtin_expect ((cond), 1)
#define __glibc_unlikely(cond) __builtin_expect ((cond), 0)
```
（為了方便撰寫，以下我將 `__glibc` 的引數輸入 `cond` 轉為 `x`。）
在引數 `long exp` 的選擇中，`__glibc` 用的是 `x`，而 `<linux/compiler.h>` 中用的是 `!!(x)`。我之所以在 commit [815080f](https://github.com/randyuncle/lab0-c/commit/815080f46b932c3244b29f5606d6cb05051da4aa) 改用 `<linux/compiler.h>` 的定義，是因為輸入 `likely()` 和 `unlikely()` 巨集中的引數 `x` 有可能不是 0 或 1，這樣的實作更能保證最後輸出的是二元結果 -- 0 或 1，更有可能貼合預設的分支預測結果。
#### Data type `u8`:
根據標頭檔 [`<linux/types.h>`](https://github.com/torvalds/linux/blob/master/include/linux/types.h) 中，其對 `u8` 的定義為：
```c
#ifndef __BIT_TYPES_DEFINED__
#define __BIT_TYPES_DEFINED__
typedef u8 u_int8_t;
...
#endif /* !(__BIT_TYPES_DEFINED__) */
typedef u8 uint8_t;
```
這裡我採用 `<stdint>` 就有的 `uint8_t` 去做更換。
#### 抹除函式中的 `void *priv`：
- [ ] initial thought
在 [`lib/list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的註解中，對 `list_sort()` 函式的引數 `void *priv` 定義為下
> `@priv`: private data, opaque to list_sort(), passed to @cmp
這裡的 `@cmp` 指的是排序過程中使用的比較函式，它用於比較兩個給定節點的值，以確定哪個節點的值更大或更小。
不過，在標頭檔 [`linux/list_sort.h`](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 裡，對 `list_sort()` 函式的定義中
```c
__attribute__((nonnull(2, 3))) void list_sort(void *priv,
struct list_head *head,
list_cmp_func_t cmp);
```
多了以下 type attributes 描述
```c
__attribute__((nonnull(2,3)))
```
根據 GNU GCC 手冊第 [5.24 Declaring Attributes of Functions](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Function-Attributes.html) 章節中，對 `nonnull()` attribute 的定義為：
> `nonnull (arg-index, ...)`
> The nonnull attribute specifies that some function parameters should be non-null pointers.
結合手冊中對 `__attribute__` 的說明，`nonnull()` attribute 用來使編譯器檢查函式中的特定位置的指標引數是否為非零。
因此，我們可以得知，位列在函式第一個引數的 `void *priv` 並不在檢查範圍內，代表這個指標引數是可以為零的。
我們這裡再從標頭檔 [`linux/list_sort.h`](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 裡，引述裡面對 `list_sort()` 的比較函式定義做確認：
```c
typedef int
__attribute__((nonnull(2, 3))) (*list_cmp_func_t)(void *,
const struct list_head *,
const struct list_head *);
```
可以看到，比較函式的第一個引數是可以為零的。
故在此次的程式引入中，我將 `lib/list_sort.c` 所有函式中的指標引數 `void *priv` 抹除。
- [ ] current thought
在 [2024q1 第 1 週測驗題 -- 測驗二](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)的 `main.c` 以及 `timsort.c` 程式中，觀察到在 `void *priv` 引數的地方，可用來紀錄該輸入鏈接串列在排序所需要做的比較次數。因此，在後續會嘗試將此引數加回我所引入的 `lib/list_sort.c`，以盼能知道 `q_sort`、`lib/list_sort`、以及 `timsort` 在不同測試資料之間的比較次數區別。
> commit [0fa3a5f](https://github.com/randyuncle/lab0-c/commit/0fa3a5fd9ec23f6d431c3b855f5e519a809c675f)
在 commit [0fa3a5f](https://github.com/randyuncle/lab0-c/commit/0fa3a5fd9ec23f6d431c3b855f5e519a809c675f) 中，我已將引數 `void *priv` 加回去程式 `listsort.[ch]` 中，做為紀錄比較次數的引數。
### `list_sort.c` 和自己寫的 sort 的效能差異
確認引入的 `lib/list_sort` 可以正常運作後，為了比較我所寫的 `q_sort` 和 Linux核心的 `lib/list_sort.c` 的效能差異，我進行了相關的實驗。在實驗工具的選擇上，我依照 [SHChang-Anderson](https://hackmd.io/@ShchangAnderson/ryWsAyUna) 給予的建議，使用 [perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 做測試。
#### Random test
我的實驗設計如下：
1. **設置測試命令檔**：我總共設置了 5 個測試命令檔，檔案的內容都類似於以下
```shell
# sort-test-1.cmd
new
ih RAND 10000 # this number is differently between files to files
time
sort
time
free
quit
```
5 個檔案唯一不同的地方只有在插入隨機的字元（`ih RAND [num]`）這條命令。目前我測試的插入數目 `[num]` 分別為：10000, 10240, 100000, 102400, 409600。
2. **新增 target `make sort_exp` 進 Makefile**：避免需要輸入複數次相同的命令。以下是我在該 target 底下所寫的參考命令：
```shell
# There is a for loop in the outer layer to handle parameter $$number
perf stat --repeat 10 ./$< -f test/sort-test-$$number.cmd
```
從以上命令也可以看出，我在此次的 perf 實驗，是讓它重複跑 10 次後的結果。
在 `perf stat` 跑完後，可以得到以下的結果：
| random-data | task-clock (ms) | page-faults | cycles | instructions | branches | branch-misses | L1-dcache-load-misses (%) |
|:---------------:|:---------------:|:-----------:|:------------:|:------------:|:-----------:|:-------------:|:-------------------------:|
| **10^4^_self** | 5.94 | 431 | 2627,7813 | 4651,4367 | 672,0676 | 14,5790 | 2.82 % |
| **10^4^_ls** | 6.73 | 431 | 2432,7449 | 4599,5319 | 646,8690 | 14,4914 | 2.63 % |
| **10240_self** | 5.82 | 439 | 2736,7706 | 4965,9477 | 697,5064 | 13,9878 | 2.46 % |
| **10240_ls** | 5.37 | 439 | 2497,2495 | 4705,2724 | 661,8641 | 14,9050 | 2.58 % |
| **10^5^_self** | 77.95 | 3595 | 3,6472,3756 | 4,5976,9012 | 6736,1092 | 161,6404 | 3.84 % |
| **10^5^_ls** | 61.32 | 3595 | 6420,4313 | 4,5354,5050 | 6420,4313 | 160,7681 | 3.41 % |
| **102400_self** | 78.29 | 3679 | 3,6711,4848 | 4,7604,9928 | 6923,9861 | 162,6362 | 3.61 % |
| **102400_ls** | 63.86 | 3679 | 2,9624,4223 | 4,6453,3986 | 6577,0879 | 164,7908 | 3.54 % |
| **409600_self** | 544.54 | 1,4479 | 22,9314,7304 | 19,0703,5300 | 2,8309,7057 | 725,9745 | 3.98 % |
| **409600_ls** | 458.29 | 1,4478 | 19,1964,1807 | 18,8643,3948 | 2,6995,2082 | 722,6618 | 4.00 % |
#### Worst case test
<!--
設計最差測資的實驗。
-->
我的實驗設計如下：
1. 使 `qtest.c` 中的命令 `ih`、`it` 可辨別的新引數輸入 `WORST`
2. 編寫自動生成合併排序最差輸入的程式碼
<!--思考有沒有傳統 top-down 以外的實作-->
- [ ] `WORST` 引數實作
> commit [5adba97](https://github.com/randyuncle/lab0-c/commit/5adba9754765f43f4ec9021d3404560d7c5652d7)
> 目前的實作，等待後續實驗 => comparison 差距
> 需排除的問題：運行時間比同節點數的 RAND 還少
commit [5adba97](https://github.com/randyuncle/lab0-c/commit/5adba9754765f43f4ec9021d3404560d7c5652d7) 是目前的實作結果。程式的構成是參考了以下兩個來自 stack overflow 的提問：
1. [When will the worst case of Merge Sort occur?](https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur)
2. [Merge sort worst case running time for lexicographic sorting?](https://stackoverflow.com/questions/9276163/merge-sort-worst-case-running-time-for-lexicographic-sorting)
第一個 stack overflow 中的回覆描述了 merge sort 的最差情況是進行最大程度的比較。換句話說，比較次數越多，merge sort 的效能就會相對越差。在這篇的最高評價的回覆中，它使用的是將一個已排序過得陣列，以奇數元素位和偶數元素位分成兩個子陣列，之後對子陣列持續做此操作，直到每個子陣列都剩兩個或以下的元素數。當碰到子陣列只剩兩個或以下的元素數時，就將子陣列的元素交換（ 此步驟也可以不做 ），最後把所有的子陣列連接起來。
我將第一個 stack overflow 的想法轉換成 `worst_merge_split()` 以及 `worst_merge_join()` 兩個函式，以 bottom-up recursive call 的方式實現。
第二個 stack overflow 則是表示，進行 lexicographic order merge sort 的最差情況是需要比較到最後一個字串長度才能決定誰大誰小。因此，藉由此論述，我撰寫了 `fill_cont_string()` 這個函式，作為生成已排序過的鏈接串列的主要函式。
在經過初步的實驗，如果對直譯器 qtest 下以下的命令
:::spoiler
```shell
# In this experiment, I test them with list_sort
# from Linux kernel
# test with `WORST` argument
new
it WORST 1048576
time
sort
time
free
# test with `RAND` argument
new
ih RAND 1048576
time
sort。
time
free
quit
```
:::
可以得到以下的結果：
:::spoiler
```shell
# test with `WORST` argument
l = []
l = [aaaaaaaaaa aaaaabdvoy aaaaaaoxum aaaaabstjk aaaaaahlxg aaaaablhme aaaaaawjrs aaaaacafgq aaaaaadsyq aaaaabhono aaaaaasqtc aaaaabwmia aaaaaalevw aaaaabpaku aaaaabacqi aaaaacdyfg aaaaaabwmi aaaaabfsbg aaaaaaqugu aaaaabupvs aaaaaajijo aaaaabndym aaaaaaygea aaaaaccbsy aaaaaafpky aaaaabjkzw aaaaaaunfk aaaaabyiui aaaaaanbie aaaaabqwxc ... ]
Elapsed time = 1.524, Delta time = 1.524
l = [aaaaaaaaaa aaaaaaaaab aaaaaaaaac aaaaaaaaad aaaaaaaaae aaaaaaaaaf aaaaaaaaag aaaaaaaaah aaaaaaaaai aaaaaaaaaj aaaaaaaaak aaaaaaaaal aaaaaaaaam aaaaaaaaan aaaaaaaaao aaaaaaaaap aaaaaaaaaq aaaaaaaaar aaaaaaaaas aaaaaaaaat aaaaaaaaau aaaaaaaaav aaaaaaaaaw aaaaaaaaax aaaaaaaaay aaaaaaaaaz aaaaaaaaba aaaaaaaabb aaaaaaaabc aaaaaaaabd ... ]
Elapsed time = 2.047, Delta time = 0.523
l = NULL
# test with `RAND` argument
l = []
l = [nmviuxsht zeoxc xllbvm fmxwv qhcpku ywhplln hvxjjhf jaxbycx yoyhihc uywcvy chghui clbqvrhpz vmbzz pbgofvyfg efwwnl eolnjuoim ycvge ftdwe ogwjfupma tfaywzq cxmkxwkx ataawrzx ctodtt qqsmtrfe oighnl yaupd vhxjqcgds vbuejgv qqrkrc ruaseibqj ... ]
Elapsed time = 2.389, Delta time = 0.342
l = [aaaarwl aaabj aaabl aaabuo aaabvp aaabxpuz aaackbwb aaackxm aaacxysqm aaadfmng aaadof aaaefue aaaetlox aaafle aaagbj aaagokkqu aaagtstme aaagzfack aaahhm aaahwd aaahwhqs aaaietc aaailqbm aaaipf aaaiwo aaajgh aaajgxoc aaajhhgnd aaajrvjzj aaake ... ]
Elapsed time = 3.317, Delta time = 0.928
l = NULL
Freeing queue
```
:::
`WORST` 引數生成的資料的排序時間居然比 `RAND` 引數隨機生成的資料要短很多。代表 commit [5adba97](https://github.com/randyuncle/lab0-c/commit/5adba9754765f43f4ec9021d3404560d7c5652d7) 的實作從根本就有著問題。
<!--不過根據 [Bottom-up Mergesort -- a Detailed Analysis](https://doi.org/10.1007/BF01294131) 於第一節 Introduction 的說明，worst case time 只會比 average time 要多 $O(n)$ 的時間複雜度。-->
<!--#### 比較次數的差別
#### cache misses
-->
### 整合 Tim sort 進 `queue.c`
<!--### Tim sort 的移入和比較
* 此 section 配合 quiz1 的測驗二一同撰寫
- Tim sort 的研讀
- 想辦法將程式引入 `queue.c` 並跑成功（函式名稱 qsort 轉給 tim sort 就可以看跑不跑得了）
-->
> commit [0fa3a5f](https://github.com/randyuncle/lab0-c/commit/0fa3a5fd9ec23f6d431c3b855f5e519a809c675f)
在 commit [0fa3a5f](https://github.com/randyuncle/lab0-c/commit/0fa3a5fd9ec23f6d431c3b855f5e519a809c675f) 中，我將[第一週測驗之測驗二](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)之 `timsort.c` 整合進 `lab0-c` 中。也為此，我在直譯器 `qtest` 中新增一個命令 `tsort`，並且也將部份測驗題中的 `main.c` 程式碼引入進對應的 `do_tsort` 函式。
### Tim sort 和 lib/list_sort 的比較
<!--### Tim sort 的移入和比較
* 此 section 可以配合 quiz1 的測驗二一同撰寫
- 在此之前把 shuffle 命令實作出來
- 使用 Valgrind、perf、massif 工具做量測
- gnuplot 製圖
-->
#### 測試程式的製作
> commit [2074559](https://github.com/randyuncle/lab0-c/commit/2074559056f1ddf923074b7f480b8b01e30f8e8d)
> 調整各個排序演算法的呼叫方式，以及移動部份函式到其應當在的程式檔。
> commit [0c48f63](https://github.com/randyuncle/lab0-c/commit/0c48f63b8e99203e6b8229a2e54eb23e9065faa4)
> 引入針對 lab0-c 中的排序演算法所調整的測試程式。
在 commit [0c48f63](https://github.com/randyuncle/lab0-c/commit/0c48f63b8e99203e6b8229a2e54eb23e9065faa4) 中，我針對 lab0-c 的鏈接串列結構體和排序呼叫方式，以 quiz 1 測驗二的 `main.c` 為基礎，撰寫了對應的測試程式 `sort_test.c`，並且在直譯器 `qtest.c` 中新增呼叫此測試程式的命令 `stest`。
`sort_test.c` 主要測試目標有以下兩點：
- 排序函式的穩定性和正確性。
- 了解指定的排序演算法對不同的資料組成方式的比較次數和時間。
其中，排序的穩定性和正確性在 quiz 1 測驗二的 `main.c` 中已有實作，因此我只有將其從比較數值，變為比較字串。
另一方面，在測試資料生成的部分，就是我在 `qtest.c` 中，為命令 `ih` 和 `it` 實現的額外資料分佈引數的程式碼。以下將針對此部分做分段敘述。
- [ ] 字串生成方式
此程式的字串生成的方式有兩種 -- 隨機字串（`fill_random_string()`）、以及連續字串（`fill_full_cont_string()`）。隨機字串，只會在如果此資料分布需要有隨機數值存在時，才會被呼叫。大多數的情況，則都會呼叫到連續字串生成函式。隨機字串函式（`fill_random_string()`）和原本於直譯器 `qtest.c` 中的實作是一模一樣的。
而連續字串生成函式（`fill_full_cont_string()`），主要依靠輸入的數值，來生成並回傳該數值對應的字串。此函式生成的字串長度固定為 10，以 `aaaaaaaaaa` 為數值 0 對應的字串為起點，依照正整數的升冪順序做對應的生成。在一開始的實作中，我的生成順序從 0 開始往正整數升冪，資料會呈以下方式生成出來：
```
["aaaaaaaaaa", "aaaaaaaaab", "aaaaaaaaac", "aaaaaaaaad", ...]
```
但這樣做會有一個問題 -- 如果在碰到升冪資料中夾雜隨機資料的資料分佈中，不就會使其有很大部分的隨機元素需要被排序到最後一個節點中？因此，我增加了一個函式 `set_bias()`，專門計算本次資料生成的最大數值之字串的 "prefix `a`" 數量並回傳，以利生成的字元可以越靠向 mst 越好。經由這方法改良的生成函式，以最大數值（`count`） 1000 為例，會得到以下的分佈：
```
for `count = 1000`, we get
["aaaaaaaaaa", "aabaaaaaaa", "aacaaaaaaa", "aadaaaaaaa", ..., "bmlaaaaaaa"]
```
雖然可能還是會有隨機元素需要被排序到最後一個節點的問題，但是這問題會根據數值的不同而有所差異，比起舊的生成方式來說，一定會更早出現第 mst 的字元是 `b`~`z` 的情況，減少部分包含隨機資料的連續字串分布測試排到串列的尾端的問題。
- [ ] 在升冪資料中，隨機決定部份資料換成隨機資料
在此種資料分佈的生成方式都很相似：先初始化一個陣列 `exch[100000]`，之後以 for 迴圈隨機生成一個非負整數值，代表當生成資料的迴圈迭代到此數字時，該節點從連續資料改為為其生成隨機資料。在 for 迴圈每次的迭代結束時，會以另一個 for 迴圈檢查有沒有重複的數值，若有的話就重新再隨機一個數字。在該迴圈結束後，再將其排序，以配合資料生成迴圈做使用。
- [ ] 在升冪資料中，最後十個資料換成隨機資料
這種資料分佈就很容易生成：除了資料生成迴圈的最後十次迭代以外，前面的資料都是連續資料生成函式所生成的資料。
- [ ] 有多個重複的資料
此資料分佈以隨機資料生成函式做為唯一生成函式。和隨機資料分佈的差別在於，它在生成時，會由亂數隨機決定當前的資料是否成為重複資料。如果是的話，接下來再隨機一個 1 ~ 100 的數值，決定往後的幾次迭代需要延用該筆資料，之後的操作以此類推。
在鏈結串列生成結束後，若節點數在 25000 或以下（目前的實作中，若節點數超過此數字，會需要運作很長的時間），則會使用 Fisher-Yates shuffle 將鏈結串列洗牌，打亂節點的順序。
- [ ] worst case scenario
參考了兩篇來自 stackoverflow 的討論
1. [When will the worst case of Merge Sort occur?](https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur)
2. [Merge sort worst case running time for lexicographic sorting?](https://stackoverflow.com/questions/9276163/merge-sort-worst-case-running-time-for-lexicographic-sorting)
以及[課堂討論](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ?view#%E5%95%8F%E9%A1%8C%E4%B8%80-merge-sort-%E6%9C%80%E4%BD%B3%E6%9C%80%E5%B7%AE%E7%8B%80%E6%B3%81)的內容做設計。我目前於 `sort_test.c` 的使用的製作方式和 commit [5adba97](https://github.com/randyuncle/lab0-c/commit/5adba9754765f43f4ec9021d3404560d7c5652d7) 的實作是相似的，差別只在於連續資料生成的方式不一樣。
根據[課堂討論](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ?view#%E5%95%8F%E9%A1%8C%E4%B8%80-merge-sort-%E6%9C%80%E4%BD%B3%E6%9C%80%E5%B7%AE%E7%8B%80%E6%B3%81)，以及 [When will the worst case of Merge Sort occur?](https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur) 討論中的敘述，merge sort 的最差情況是在每一次子序列的排序中，都會交錯比較到兩個子序列的最後一個節點。也由此，這兩個討論共提出了四種構造法。截至目前為止，我只復現了[課堂討論](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ?view#%E5%95%8F%E9%A1%8C%E4%B8%80-merge-sort-%E6%9C%80%E4%BD%B3%E6%9C%80%E5%B7%AE%E7%8B%80%E6%B3%81)中的構造法一和構造法二，[課堂討論](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ?view#%E5%95%8F%E9%A1%8C%E4%B8%80-merge-sort-%E6%9C%80%E4%BD%B3%E6%9C%80%E5%B7%AE%E7%8B%80%E6%B3%81)中提供的 bottom-up 遞迴生成範例程式碼還沒想到如何在鏈結串列結構中實現。以下將針對 merge sort worst case 的構造法一和構造法二做討論。
##### 構造法一
首先先看構造法一，構造法一的資料分佈和 [When will the worst case of Merge Sort occur?](https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur) 討論中提出的方法一致 -- 將已排序序列的奇數項分割成一條子序列，偶數項分割成另一條子序列，往後再對分割完的子序列做一樣的操作，直到每個子序列都剩一個節點。
構造法一的程式實作可見 commit [0c48f63](https://github.com/randyuncle/lab0-c/commit/0c48f63b8e99203e6b8229a2e54eb23e9065faa4) 的 `sort_test_impl.c` 中。在我的實作中，分成了三個函式：`worst_case_generator()`、`worst_merge_split()`、以及 `worst_merge_join()`。
* `worst_case_generator()` 是提供外部程式呼叫的函式，將輸入的鏈結串列的 circular 特性取除，並啟動 `worst_merge_split()` 的遞迴呼叫。
* `worst_merge_split()`、以及 `worst_merge_join()` 皆以指標的指標的方法處理鏈結串列，分別將串列的節點以奇偶項做遞迴分割，最後再分別遞迴合併。
由此方法重構的鏈結串列，若指定要 `stest.c` 生成 1000 個節點的 worst case 的話，鏈結串列的資料從頭部節點開始呈以下的分佈（節錄）：
```
[aaaaaaaaaa, atsaaaaaaa, ajwaaaaaaa, bdoaaaaaaa, aeyaaaaaaa, ayqaaaaaaa, aouaaaaaaa, bimaaaaaaa, ...]
```
在給 merge sort 排序演算法（`qsort` 和 `lib/list_sort.c`）排序來自 `worst_case_generator()` 重構後的 1048580 節點的鏈結串列，可得到以下的比較次數結果：
| sort \ comparisons | worst | random |
|:------------------:|:--------:|:--------:|
| lib/list_sort | 19922983 | 19643758 |
| q_sort | 19923029 | 19643532 |
可以看到，`worst_case_generator()` 重構的鏈結串列，比起隨機生成資料的鏈接串列，要多出將近 27 ~ 28 萬的比較次數。
至於這兩種資料分佈之間的運作時間差距，留待後續做說明。
##### 構造法二
接下來，來看到[課堂討論](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ?view#%E5%95%8F%E9%A1%8C%E4%B8%80-merge-sort-%E6%9C%80%E4%BD%B3%E6%9C%80%E5%B7%AE%E7%8B%80%E6%B3%81)中提及的構造法二。構造法二的目標是將鏈結串列變為：最大和最小項、次大和次小項、... ，以次類推的組成。
具體的程式碼實作可以參考 commit [0c48f63](https://github.com/randyuncle/lab0-c/commit/0c48f63b8e99203e6b8229a2e54eb23e9065faa4) 的 `sort_test_impl.c` 中，**被註解掉**的 `worst_case_generator` 函式。此資料分佈的實作對鏈結串列來說相對容易，分成以下幾個步驟：
* 首先，以 0 和鏈結串列的總長度為兩個數值 `x` 和 `y`，以以下的位元和布林操作，去取得此串列的中間節點和頭部節點的距離。
```c
int middle = (x & y) + ((x ^ y) >> 1);
```
* 以上一小點得到的數值 `middle`，從頭部節點開始迭代走訪串列，直到迭代了 `middle` 次，將結果存給 `iterator` 指標。
* 將 `iterator` 和 `head->prev` 節點連接成一個 circular doubly 鏈結串列，以可用實作於 `queue.c` 中的 `q_reverse()` 函式將整個串列反轉。之後，更新 `iterator` 指標指向此串列中最大值所在的節點，也就是以下程式碼的目的。
```c
/* update the head of the latter half of the list */
head->prev = iterator;
iterator = iterator->next;
```
* 去除 `iterator` 指標指向的鏈結串列的 circular 特性，並將其和 `head` 指標指向的鏈結串列以 `merge_list()` 函式執行合併。`merge_list()` 是一個在 `sort_test_impl.c` 的函式，用來做兩個串列的交錯合併。
* 最後，將串列變回 circular doubly 鏈結串列。
經由以上操作後，若指定要 `stest.c` 生成 1000 個節點的 worst case 的話，鏈結串列的資料從頭部節點開始呈以下的分佈（節錄）：
```
[bmlaaaaaaa, aaaaaaaaaa, bmkaaaaaaa, aabaaaaaaa, bmjaaaaaaa, aacaaaaaaa, ...]
```
將此資料分佈給 merge sort 排序演算法（`q_sort` 和 `lib/list_sort.c`）排序來自此 `worst_case_generator()` 重構後的 1048580 節點的鏈結串列，可得到以下的比較次數結果：
| sort \ comparisons | worst（構造法一） | worst（構造法二） | random |
|:------------------:|:-----------------:|:-----------------:|:--------:|
| lib/list_sort | 19922983 | 15466577 | 19643758 |
| q_sort | 19923029 | 15466543 | 19643532 |
從以上的表格，可以發現到，構造法二所創造的 worst case 的比較次數，遠比構造法一來的小，甚至還比隨機資料分佈要小。
若我們看到排序時間的比較，則會有更加明顯的結果：
| sort \ durations(ms) | worst（構造法一） | worst（構造法二） |
|:--------------------:|:-----------------:|:-----------------:|
| lib/list_sort | 0.611 | 0.221 |
| q_sort | 0.972 | 0.194 |
總結而言，構造法二不符合 worst case of merge sort 的命題。因此，在測試程式，以及 `qtest.c` 中對於 WORST 引數的實作，我皆採用構造法一。
- [ ] 字串組成和排序時間的關聯
這一段是個比較有趣的話題，也是我在 [list_sort.c 和自己寫的 sort 的效能差異](https://hackmd.io/jX0N-0D4S_yxXipGlRRBIg?both#list_sortc-%E5%92%8C%E8%87%AA%E5%B7%B1%E5%AF%AB%E7%9A%84-sort-%E7%9A%84%E6%95%88%E8%83%BD%E5%B7%AE%E7%95%B0) 段落中的 WORST 引數實作的運作時間，比 RAND 引數生成的資料分佈要快的原因。
先回顧一下我在 [list_sort.c 和自己寫的 sort 的效能差異](https://hackmd.io/jX0N-0D4S_yxXipGlRRBIg?both#list_sortc-%E5%92%8C%E8%87%AA%E5%B7%B1%E5%AF%AB%E7%9A%84-sort-%E7%9A%84%E6%95%88%E8%83%BD%E5%B7%AE%E7%95%B0)裡的 WORST 引數的字串生成方式，該生成的方式參考的是 [Merge sort worst case running time for lexicographic sorting?](https://stackoverflow.com/questions/9276163/merge-sort-worst-case-running-time-for-lexicographic-sorting) 討論所提出的一個說法：字串比較的最差情況就是都幾乎比較到最後一個字元。所以我就寫下了以下的連續字串生成函式：
```c
/**
* A function to generate the continious strings.
* Start from `aaaaaaaaaa` to maximum of the given string length [num].
*/
static void fill_cont_full_string(char *buf, size_t buf_size, int counter)
{
for (size_t i = 0; i < buf_size; i++) {
buf[i] = charset[0];
}
int num = counter + 1;
size_t index = buf_size - 1;
do {
if ((num - 1) % 26 >= 0 && index != (buf_size - 1))
num++;
buf[index--] = charset[(num - 1) % 26];
num = (num - 1) / 26;
} while (num != 0);
}
```
所生成的字串如同前面提過得，會呈現以下的分佈：
```
["aaaaaaaaaa", "aaaaaaaaab", "aaaaaaaaac", "aaaaaaaaad", ...]
```
理想的情況下，在做字串比較時，都會比較到倒數的幾個字元，才會知道結果，運行時間應該會比較長才對。
但是，如果將以上程式碼生成的資料分佈（令其為 align with lst）的排序時間，和我在 commit [2074559](https://github.com/randyuncle/lab0-c/commit/2074559056f1ddf923074b7f480b8b01e30f8e8d) 更新的連續字串程式碼生成的資料分佈（令其為 align with mst）的排序時間做比較的話，以 1048580 節點的生成串列，各重複排序 10 次，去掉兩個極端值並取平均後，可以得到以下的結果：
| sort \ mean durations(ms) | align with lst | align with mst |
|:-------------------------:|:--------------:|:--------------:|
| lib/list_sort | 0.642 | 0.6396 |
| q_sort | 0.9925 | 1.004 |
可以發現到它們之間的時間差距並不明顯。
但如果把它們的排序運行時間，和隨機資料分佈的排序運行時間做比較的話，則會出現以下的結果：
| sort \ mean durations(ms) | align with lst | align with mst | random |
|:-------------------------:|:--------------:|:--------------:|:------:|
| lib/list_sort | 0.642 | 0.6396 | 1.453 |
| q_sort | 0.9925 | 1.004 | 1.259 |
縱然在前一段對 worst case scenario 的討論中，構造法一的資料分佈所擁有的比較次數比 random 要來的多。但是，在排序時間方面，我所生成的連續字串，居然比隨機的字串要來的快。
那如果，改變連續字串分佈樣式會有什麼樣的結果？
抱持著這樣的想法，我在某一次的測試中，對字串的生成以上面的程式碼為基礎，做了以下的更動：
```diff
-size_t index = buf_size - 1;
+size_t index = 0;
```
這改動也有包含在 commit [0c48f63](https://github.com/randyuncle/lab0-c/commit/0c48f63b8e99203e6b8229a2e54eb23e9065faa4) `qtest.c` 裡的 `fill_cont_full_string()` 函式中，但已被註解化。
由此方式生成的連續字串分佈會呈以下的分佈：
```
["aaaaaaaaaa", "baaaaaaaaa", "caaaaaaaaa", ..., "abaaaaaaaa", ..., "bbaaaaaaaa", ...]
```
但是，這種方法生成的字串並非升冪的資料，如果將其輸入排序函式，以 1048580 個節點的鏈結串列為例，可以得到以下的分佈：
```
["aaaaaaaaaa", "aaaabaaaaa", "aaaacaaaaa", "aaabaaaaaa", "aaabbaaaaa", ...]
```
側面顯示了改動的生成程式碼並非生成升冪的資料，也是我後續不採用此程式碼生成連續資料的原因。
如果將上面重新排好的升冪資料（令其為 alt process），經過構造法一演算法重構後，再輸入進 merge sort 進行排序，同樣以 1048580 個節點的鏈結串列為例，各重複排序 10 次，去掉兩個極端值並取平均後，可以更新表格為以下：
| sort \ mean durations(ms) | align with lst | align with mst | alt process | random |
|:-------------------------:|:--------------:|:--------------:|:-----------:|:------:|
| lib/list_sort | 0.642 | 0.6396 | 1.3834 | 1.453 |
| q_sort | 0.9925 | 1.004 | 1.5185 | 1.259 |
（因為使用相同的重構演算法，所以各個資料生成函式在 worst case of merge sort 的比較次數對兩個 merge sort 演算法來說，都是一樣的，就不額外再列表）
可以發現到，新的連續資料分佈函式（alt process），在其資料變為升冪資料並重構為 worst case 後，其所需要的排序時間遠比舊的生成方式要多約 1.5 ~ 2 倍，甚至在 `q_sort` 演算法中，其會比隨機分佈的資料要慢。
從以上的小實驗，可以得知，[Merge sort worst case running time for lexicographic sorting?](https://stackoverflow.com/questions/9276163/merge-sort-worst-case-running-time-for-lexicographic-sorting) 討論中的說法，在 lab0-c 鏈結串列結構體的排序中，並不成立。除此之外，也可以得知，**不同字串資料的組成，以相同的資料分佈做排序，對於排序時間的影響是很大的**。
---
## 實現 shuffle 命令
<!--
shuffle 可以用來做實驗，所以要先寫
-->
> commit [35af251](https://github.com/randyuncle/lab0-c/commit/35af251d8cc58d3ce8559472fb99903f12955593)
<!--> 目前的問題：shuffle 的 node 數量多於約 26000 節點數的 linked-list 會需要很長的時間，導致使用 exception_setup() 時會報錯。-->
在 commit [35af251](https://github.com/randyuncle/lab0-c/commit/35af251d8cc58d3ce8559472fb99903f12955593) 中，是我於目前實作的 `shuffle` 命令內容，以實現 Fisher–Yates shuffle 演算法來實作洗牌作為此命令存在的目的。
此實作是參考了 Fisher–Yates shuffle 演算法的[虛擬碼](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm)，從頭部節點開始，在每一次的迭代中隨機出一個介於 `0 ~ (串列長度 - 1)` 的數字，將此數字所在的節點與現行迭代到的節點做交換，直到走訪整個鏈接串列的迭代運行完為止。其中，走訪鏈接串列的迴圈參考了 [Linux Kernel List Management API](https://www.kernel.org/doc/html/v4.19/core-api/kernel-api.html) 的 `list_for_each_entry_safe(entry, safe, head, member)` 巨集，主要是看上其在迭代的過程中允許節點的刪除、修改的特性。
除此之外，在做節點的交換時，也參考了同 List API 的 `list_swap()` 以及 `list_replace()` 函式，並將其引入進 `qtest` 直譯器中，命名為 `list_swap()` 函式。不過，為了減少 `qtest.c` 中函式的數量，這裡暫時先將 List API 中 `list_replace()` 的實作融入進 `list_swap()` 中。如果後續有需要，會再做重新引入。
在做隨機函數的選擇中，原本想要使用 C 語言中的 `srand(time(NULL));` 函式及種子去實作。但是，在之前想要實作 `WORST` 引數時，觀察 `queue_insert()` 函式以及 `RAND` 引數的配套函式 `fill_rand_string()` ，卻發現在 `qtest.c` 中已有定義隨機的種子：
```c
/* A better seed can be obtained by combining getpid() and its parent ID
* with the Unix time.
*/
srand(os_random(getpid() ^ getppid()));
```
此種子使用的是 `qtest.c` 中內建的 `os_random` 函式，以及 `getpid()` 及其親代 ID 的 XOR 運算。
如果使用此隨機種子呼叫隨機函式 `rand()` 來定位欲交換的節點的話，經過 [lab0 (D)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d) 所附的統計檢定程式的運作後，會呈現以下的結果：
```shell
Expectation: 41666
Observation: {'1234': 41821, '1243': 41425, '1324': 41775, '1342': 41594, '1423': 42069, '1432': 41457, '2134': 41388, '2143': 41528, '2314': 41516, '2341': 41788, '2413': 41796, '2431': 41674, '3124': 41486, '3142': 41805, '3214': 41764, '3241': 41859, '3412': 41674, '3421': 41613, '4123': 41823, '4132': 41779, '4213': 41631, '4231': 41594, '4312': 41395, '4321': 41746}
chi square sum: 16.34550952815245
```
以及以下機率分佈圖：
[lab0 (D)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d) 的統計檢定程式 shuffle 4 個數字，因此會有 24 個隨機樣本，也因而有 24 - 1 = 23 的決定自由度。如果以決定自由度 v = 23, 以及 chi-square 值約 16.34551 去做 chi-square distribution 的查表，會得到 p 值約為 0.90 ~ 0.80 之間。設定顯著水準 $\alpha$ 值為 0.05，則 p = (0.90 ~ 0.80) > $\alpha$ = (0.05)，統計檢定的結果不拒絕虛無假說（$H_0$）。
---
## PRNG -- 偽亂數產生器
### [熵](https://en.wikipedia.org/wiki/Entropy_(information_theory))與亂度
在理解亂數產生器之前，要先知道如何說明亂數的亂度，也就是熵（Entropy）的概念。
在資訊理論中，一組亂數的熵指的是
### 藉由 [`drivers/char/random.c`](https://github.com/torvalds/linux/blob/master/drivers/char/random.c) 理解 CSPRNG
### [Xorshift](https://arxiv.org/pdf/1805.01407)
### 統計分析不同 PRNG 實作的品質
---
## Dude, is my code constant time?
<!--
1. trace-17-complexity 跑失敗的主因 (如果看那個來自 git action 的紅色 X 不爽可以考慮先讀這塊)
2. 論文內容也可以做實驗
-->
### 論文研讀筆記
### lab0-c 的 simulation mode
### student's t-test 的原理及作業中的實作
### 引入原論文 source code 的 percnetile 處理
---
## 整合 tiny-web-server
Sign in with Wallet
Connect another wallet