# 2024q1 Homework1 (lab0)
contributed by < [`pao0626`](https://github.com/pao0626) >
## 開發環境
```bash
$ 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: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 5800X 8-Core Processor
CPU family: 25
Model: 33
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 2
Frequency boost: enabled
CPU max MHz: 4850.1948
CPU min MHz: 2200.0000
BogoMIPS: 7585.52
```
## 針對佇列的操作
### 前置作業
:::danger
注意書名號的使用。
> 收到
:::
1. 閱讀〈[How to Write a Git Commit Message](https://cbea.ms/git-commit/)〉後，我新增了一個名為 `commitMsg` 的檔案，並將其設置為 `.gitconfig` 中的 `commit.template` 參數。
2. 查閱了 `queue.h` 每個函式的說明及要求，得知`queue_context_t` 負責追蹤所有的佇列，每個佇列由 `list_head` 開始，然後以鏈結串列的形式接續 `element_t` 。
3. 檢視了 `list.h` 中每個已定義好的巨集，以便後續進行使用。
### `q_new`
使用 `malloc` 配置 `list_head` 所需記憶體後，再用 `INIT_LIST_HEAD` 來初始化 `list_head` 的 `*next` 和 `*prev` 指標。
### `q_free`
:::danger
- [ ] traverse (動詞) 和 traversal (名詞)
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
> 已更改
:::
使用 `list_for_each_entry_safe` 走訪整個佇列。藉由其提供的 `list_entry` 巨集取得指向 `element_t` 的指標，再使用 `q_release_element` 函式釋放結構體中 `*value` 和 `list` 所佔用的記憶體資源。處理完佇列所有的 `element_t` 之後，最後釋放佇列頭部的 `list_head` 記憶體空間。
> 閱讀〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉裡 `container_of` 的介紹，理解此處 `list_for_each_entry_safe` 第四個參數放 `list` 的原因。
需注意 `element_t` 是經過 `typedef` 定義，與 `list_head` 的呼叫方式不同。
### `q_insert_head` 和 `q_insert_tail`
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
> 已刪除不必要程式碼
:::
確認佇列非空， 並成功配置 `element_t` 的記憶體空間後，使用 `strdup` 為字串配置記憶體空間，如果配置失敗需釋放先前配置給 `element_t` 的記憶體空間。反之若配置成功，則使用 `list_add` 或 `list_add_tail` 將新建立的節點插入至佇列的頭或尾。
### `q_remove_head` 和 `q_remove_tail`
>依據〈[CERN](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)〉建議，使用 strncpy 來複製字串
先排除佇列不存在或者為空的情形。用 `list_first_entry` 或 `list_last_entry` 取得佇列節點，並用 `list_del` 將其與佇列斷開連接，在 `sp` 指標不是 NULL 的情況下用 `strncpy` 複製預移除節點的字串內容至 `sp` ，需注意 `strncpy` 並不保證以 ``'\0'`` 結尾，因此需要額外處理。
### `q_size`
作業要求中給的範例，走訪整個佇列並用 `list_for_each` 紀錄經過的節點個數即為所求。
### `q_delete_mid`
考慮節點總數為奇數或偶數的兩種情況。使用兩個指標從佇列首尾兩側朝中間走訪，當符合相等或相鄰兩種情況時即找到中點，用 `list_del` 將中點從佇列移除，再用 `q_release_element` 釋放記憶體達到刪除效果。
### `q_delete_dup`
使用 `list_for_each_entry_safe` 走訪佇列，如果當前節點 `elemnet` 和下個節點 `safe` 的`value` 相等就刪除。需要更改 `list_for_each_entry_safe` 迴圈的中止條件以避免存取不存在的變數。此外，重複節點全部都要刪除，所以我用一個布爾值 `dup` 來紀錄是否正在處理重複節點。舉例來說：考慮 $[a,a,a,b]$ 的情形，當我兩兩一對判定至 a,b 時，雖然兩者不重複，但我仍可藉由 `dup` 變數判斷我該刪除節點 a 。
### `q_swap`
使用 `list_for_each` 走訪佇列，在不是最後一個節點的情況下，將當前節點用 `list_move` 移至其下個節點之後，即完成兩兩交換的目的。交換後當前節點的下個節點正好是下個處理的目標。
### `q_reverse`
使用 `list_for_each_safe` 走訪佇列，將當前節點依序移至列首即可達成反轉，與 `q_swap` 不同處是使用 `safe` 紀錄當前處理節點的下個節點，以避免將當前節點移至列首後無法繼續處理。
### `q_reverseK`
每走訪 k 個節點就做一次 `q_reverse`的操作。使用 `list_cut_position` 將要反轉的部份切割出來，反轉後再用 `list_splice_init` 接回原本鍊結串列。 `*cut` 指標紀錄每次處理的開始位置， `*tmp_head` 指標暫存切割出來的鍊結串列。
### `q_sort`
使用 top down 的 `merge_sort` 作法，因此需要新增 `q_merge_two` 函式，詳細實作內容請看 [`q_merge_two`](#q_merge_two) 介紹。
### `q_merge_two`
藉由 `strcmp` 比較 `first` 和 `second` 兩個串列中所有節點的字串大小，依序取出比較過程中的較小值，暫存在 `list_head` `tmp` 鍊結串列。
最後將 `tmp` 的合併結果移回 `second` 的佇列頭，因為我在 `q_sort` 呼叫 `q_merge_two` 函式時是將 `head` 放在第二個參數，也就是 `q_merge_two` 中的 `second` 佇列頭。
### `q_ascend 和 q_descend`
> `queue.h` 中只要求 remove 而非 delete ，但實測後發現需釋放記憶體
:::warning
使用 git rebase 以最新的 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) 作為根基，裡頭已澄清二者的操作。
:::
以下將兩個函式差異用（ ）表示。
從佇列後方開始走訪，紀錄當前最小（大）值，依序進行比較，只要當前節點大（小）於目前最小（大）值就刪除，否則更新最小（大）值，並將 `count` 加一。
完成後發現程式碼可以<s>優化</s> 改良，只有極值更動時 `*cur` 才會更新，所以不需要使用變數紀錄極值。
:::danger
某些濫用「優化」的語境，根本與「改良」和「改善」無異，那為何不直接講「改良」和「改善」呢？
> 已改進
:::
```diff
@@ -267,6 +258,7 @@ int q_descend(struct list_head *head)
element_t *cur = list_entry(head->prev, element_t, list);
int count = 1;
- char *min_val = list_entry(head->prev, element_t, list)->value;
while (cur->list.prev != head) {
- if (strcmp(prev->value, min_val) <= 0) {
+ if (strcmp(prev->value, cur_value) <= 0) {
count++;
- min_val = prev->value;
cur = prev;
}
```
### `q_merge`
將每個佇列藉由前面寫好的 `q_merge_two` 依序合併進第一個佇列。
兩兩合併也是可行的方法，但時間複雜度不一定更好，寫法卻複雜許多，因此暫不考慮。
> TODO: C++ 中藉由維護最小或最大堆積來處理會更快，但 C 不確定，未來可以設計實驗測試。
這裡碰到一個問題，當我使用 `list_for_each_entry` <s>遍歷</s> 走訪 所有`queue_contex_t` 時，編譯和執行沒問題，但在 git comment 時會出現以下錯誤：
```shell
error: Uninitialized variable: element->id [uninitvar]
if (element->id == first->id)
```
改成用 `list_for_each` <s>遍歷</s> 走訪就沒有問題了，目前還不知道原因。
```diff
@@ -307,13 +307,14 @@ int q_merge(struct list_head *head, bool descend)
if (!head || list_empty(head) || list_is_singular(head))
return 0;
queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
- queue_contex_t *element;
+ struct list_head *element;
int ret = first->size;
- list_for_each_entry (element, head, chain) {
- if (element->id == first->id)
+ list_for_each (element, head) {
+ if (list_entry(element, queue_contex_t, chain)->id == first->id)
continue;
- ret += element->size;
- q_merge_two(element->q, first->q, descend);
+ ret += list_entry(element, queue_contex_t, chain)->size;
+ q_merge_two(list_entry(element, queue_contex_t, chain)->q, first->q,
+ descend);
}
return ret;
}
```
到這為止 `make test` 分數為 $95/100$。
分析結果，發現在執行測試項目 `trace-17` <s>測資</s> 時會有以下錯誤：
:::danger
這裡是「測試項目」(item)，而非「測試資料」(data)，查閱辭典以理解二者的差異。
> 已改進
:::
```shell
ERROR: Probably not constant time or wrong implementation
```
觀察 `trace-17` 使用了 `option simulation 1` 開啟 `simulation` 模式。
並在作業要求中發現需先研讀 〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉論文。
:::danger
改進你的漢語表達。
> <s>已重頭改進</s>
> 沒有顯著改進，嘗試用 ChatGPT 一類的工具，讓機器告訴你該如何說話。
> 上面內容已再次改進
:::
**待解決問題：**
`git push` 後進行 CI 步驟時，執行至 `Run webfactory/ssh-agent@v0.7.0` 會遇到以下錯誤：
```
Error: The ssh-private-key argument is empty.
Maybe the secret has not been configured,
or you are using a wrong secret name in your workflow file.
```
> 參考 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-lab0) 的「貢獻與程式改進記錄」敘述，有此錯誤應屬正常情形。
---
## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
### 實驗原理
**步驟一. Measure execution time**
建立兩種類別的資料，分別重複測量其作為輸入資料時的執行時間。
- 固定資料（包含特殊的極端狀況）
- 隨機資料
**步驟二. Post-processing**
統計分析前，對每個測量值進行一些處理。
- Cropping：測量時會被作業系統或其他無關活動打斷，導致測量結果的執行時間比預期更長，所以要裁剪測量值。
- Higher-order preprocessing：應用一些高階預處，還無法理解其方法和原理。
**步驟三. Apply statistical test**
應用統計檢定來嘗試反駁「兩個時序分佈相等」的原假設。成功反駁即證明此原假設錯誤，說明程式並非以常數時間運行。
- t-test：為 `dudect` 所使用的 Welch's t-test。
- Non-parametric tests：優點是這些測試通常依賴關於基本分佈的較少假設，缺點是它們可能收斂速度較慢並且需要更多樣本（目前無法理解這些分析含意）。
**論文內實驗結果重點整理**
- 進行上述的Post-processing，將大於 p percentile 的測試值丟棄，來達到 Cropping 的目的，因為上尾部可能受到資料無關雜訊的影響。
- 使用 Welch's t-test 進行統計檢定。
### 改善 `lab0-c` 中對 percentile 的處理
> commit [09548f9](https://github.com/pao0626/lab0-c/commit/09548f9641a5a7a6207a1f992c3445fc88312864)
跟據作業說明，得知 lab0-c 程式碼相比 [oreparaz/dudect](https://github.com/oreparaz/dudect) 程式碼少了 percentile 的處理。而閱讀完〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉論文後知道 percentile 是用於 cropping 過大測量值的標準。
**lab0-c 程式碼重點整理：**
- `ttest.c` 實作 Welch's t-test。
- `constant.c` 維護了不同於 `qtest.c` 的佇列操作，避免測試時影響主程式，重點函式如下：
- `prepare_inputs` 將測資分配成固定資料和隨機資料。
- `measure` 針對不同模式（ih, it, rh, rt）進行不同操作，並計算兩種不同類別資料各自的執行時間。
- `fixture.c` 測量的主要程式檔，重點函式如下：
- `differentiate` 計算不同類別執行時間的差值。
- `update_statistics` 進行 Welch's t-test
- `report` 對 Welch's t-test 結果進行判斷
- `doit` 逐一執行上述所有函式。
了解大致架構後，將 [oreparaz/dudect](https://github.com/oreparaz/dudect) 中與 percentile 有關的函式移植至 `lab0-c/dudect/fixture.c` 中，更改如下：
1. 新增三個函式
- `cmp`：sort 時所需。
- `percentile`：percentile 相關處理。
- `prepare_percentiles`：對 `differentiate` 函式中計算好的差值進行 percentile 處理。
2. `doit` 函式中裡，在 `differentiate` 和 `update_statistics` 中間插入 `prepare_percentiles` ，以進行 cropping 操作，符合我研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉的心得。
:::info
`oreparaz/dudect` 的實際作法更為複雜。它不僅定義了常數 `DUDECT_NUMBER_PERCENTILES` ，還利用 `int64_t *percentiles` 數組額外紀錄處理後的結果。這個結果被用於 `update_statistics` 函數中，用以決定是否進行百分位數處理。
這部份我實在<s>看不太懂</s> 看不懂，目前只能一知半解的改進 `lab0-c` 。
:::
:::danger
看不懂就說看不懂，沒有「不太懂」這回事，誠實面對自己。拿出你的教科書，重新學習！
:::
---
## Valgrind
執行 `make valgrind` ，目前的程式並沒有問題。
研讀 `valgrind` 中提供的 [`Massif`](https://valgrind.org/docs/manual/ms-manual.html) 使用者手冊，理解 `ms_print` 產生的圖片意義。
---
## 實作 shuffle 命令
> 參考 [Fisher–Yates Shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
分為以下兩種方法：
- Fisher 和 Yates 提出的傳統方法：每次選擇一個隨機數 k，從頭部開始，找到第 k 個元素後將其從陣列移除，放入另一個紀錄洗牌結果的陣列尾部。因為每次都有元素刪減，所以每次都需要從頭開始計算，且需要一個全新的陣列紀錄結果。
- Durstenfeld 提出的現代方法：每次隨機「敲擊」一個陣列元素後，與陣列尾端「未敲擊」的元素交換，達到線性時間複雜度和 in-place 的洗牌結果。
兩者差異在於後者無論時間/空間複雜度都有所降低。時間複雜度由 $O(n^2)$ 降為 $O(n)$，空間複雜度則由 $O(n)$ 降為 $O(1)$。
**需注意，以上的討論是建立在用陣列儲存的情形。**
以下嘗試實作第二種方法，同時也是[作業敘述方法](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d)。
### 實作方法介紹
> commit [65089f0](https://github.com/pao0626/lab0-c/commit/65089f060d2d6abd67a54dae6d18d95803de1443)
為了在 `qtest.c` 新增一個 shuffle 命令，我參考了概念相近的 `q_swap` 實作方法去進行修改。新增了 `do_shuffle` 函式，並理解了一些關鍵函式如： `set_noallocate_mode` 用於控管函式對於記憶體的操作，以及 `exception_setup` 我認為是用來確保同時段內只進行一個指令，相當於 Lock 的功能<s>（理解如果有錯歡迎糾正）</s>。
:::danger
關於 `exception_setup`，詳見作業說明，其作用並非「相當於 lock」，在電腦科學中，lock 通常是 mutex lock 的簡稱，本案例不涉及同步操作。
下次不用講「如果有錯歡迎糾正」，只要你言之有物，人們會願意跟你討論，反之，特別標示這句話，則無助於他人理解。
:notes: jserv
:::
接著在 `queue.c` 中實作 shuffle 的操作。每次使用 `rand() % len` 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。
此處共新增了 `q_shuffle` 和 `swap_values` 兩個函式。
> commit [d45a3f0](https://github.com/pao0626/lab0-c/commit/d45a3f0735aac4f861100c5ac715644f973faa0e)
1.修正呼叫錯誤變數名稱。
2.修正函式宣告順序。
3.`git commit` 時發現不能更改 `queue.h` ，經同學< [HotMercury](https://hackmd.io/@NeedSleep/linux2024-homework1#2024q1-Homework1-lab0) >指導，在 `do_shuffle` 函數前用 `extern void q_shuffle(struct list_head *head);` 宣告
取隨機數時使用了 rand() 函式和 chatGPT 輔助，後者提到一個隱憂如下:
> rand() 函式來生成一個 0 ~ RAND_MAX（包括 RAND_MAX）之間的隨機數。因為 RAND_MAX 不一定能被 len 整除，導致產生的隨機數有一定的偏差。
TODO: 思考其他取隨機數方法。
> 參見 [Fast Random Integer Generation in an Interval](https://arxiv.org/abs/1805.10941) :notes: jserv
### 統計方法驗證
> 使用[作業說明]((https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d))中提供的程式碼
運行 [scripts/shuffle.py]() Python 程式進行實驗，測試 shuffle 1000000 次，結果如下：
```shell
Expectation: 41666
Observation: {'1234': 41893, '1243': 41798, '1324': 41241, '1342': 41516, '1423': 41488, '1432': 41745, '2134': 41914, '2143': 41685, '2314': 41403, '2341': 41758, '2413': 41537, '2431': 41731, '3124': 42004, '3142': 41673, '3214': 41671, '3241': 41458, '3412': 41799, '3421': 41670, '4123': 41724, '4132': 41601, '4213': 41486, '4231': 42135, '4312': 41508, '4321': 41562}
chi square sum: 22.59357749723996
```
以上的輸出包含了:
- 期待的頻率：41666
- 24 種可能洗牌結果的實際頻率
- 計算的 chi-squared test statistic 結果總和：22.59
將其畫成以下圖表觀察，可以看出 sshuffle 的頻率是大致符合 Uniform distribution 的。
> TODO: 實際運用數學證明
---
## 研讀 Linux 核心原始程式碼的 lib/list_sort.c
### 核心概念
> 參考 lib/list_sort.c 修改紀錄 (即 commit [b5c56e](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09?branch=b5c56e0cdd62979dd538e5363b06be5bdf735a09&diff=split))
> 參考 [Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh)
目標是減少呼叫 cmp() 的次數，也就是減少 merge sort 過程中發生不平衡的合併造成額外的比較次數。而 merge sort 的比較次數可以用用公式 $n*log2(n) - K*n + O(1)$ 來表示，可以明顯看出當 $K$ 值越大，比較次數就越少，效能也就越好。
當 $K=1.4427$ 時會逼近理論的最佳極限值，而實際上最好的情況發生在 $n$ 是2的冪時，此時 $K=1.2645$ 。當 $n$ 不是2的冪時，不同的排序方法會產生差異，整理如下:
1. top-down 的作法會取得最好的結果，平均 $K=1.248$，但 top-down 需要完整走訪所有節點才能進行分配，這會導致 cache blocking，節點的資料不斷搬進搬出 cache 。
2. botton-up 的作法有別於教科書中的敘述，其實是以 depth-first 概念的 eager merge pattern 實作，在走訪整個串列之前，只要遇到大小相同就先合併，因此可以減少 cache miss 的問題。但如此一來就得面臨不平衡的合併問題，舉例來說，當 $n=1028$ 時，最終合併情況就會是 $1024:4$ ，平均需要走訪列表的 $\frac{4}{5}$ ，大約820次比較後才能完成合併（平均即是假設4個節點的大小等距散落在1024個節點中），此時的 $K\approx1$ 。
3. 針對以上 simple eager botton-up 的缺點，文獻提出 "worst-case optimal" 的變體作法，像是 queue-mergesort，但是其使用 breadth-first 概念的方法與 top-down 作法有相同缺陷，需要處理 cache blocking 問題。
4. 最後一種作法，就是由 George Spelvin 所提出的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 。藉由保證所有合併的過程最壞情況下都只會是 $2:1$ 的不平衡，這讓 $K=1.207$ ，達成與 queue-mergesort 相等的效能，雖然比不上 top-down ，但優於 botton-up 的效能而且充分運用 cache。
### 確保 2 : 1 的關鍵實作方法
使用變數 `count` 代表 pending list 節點數量並控制合併時機，確保不會有超過兩個相同大小的 pending list 需要處理。每次增加 `count` 都會設置第 $k$ bit ，此時如果 count 不為 2 的冪，則設置的第 $k$ bit 代表將兩個 $2^k$ 合併。過程很像小時候玩的 2048 遊戲，在數量很小的時候盡量合併。
藉由判斷 $k-1$ bit 和更高位的 bit 情況，來判斷大小為 $2^k$ 的 pending list 數量，分成六種情況( x, y 代表任意位的值， y 不能為0):
以下用 $k$ = 2 來舉例幫助說明:
1. `00x`：0 pending of size $2^k$; x pending of sizes < $2^k$
舉例： `0001`， 大小為 $2^2$ 的 pending list 是 0 個，比 $2^2$ 小的有 $2^0$ 個。
查表可以看到 pending 上的節點是 `1`，合理。
2. `01x`：0 pending of size $2^k$; $2^(k-1)$ + x pending of sizes < $2^k$
舉例： `0010`，大小為 $2^2$ 的 pending list 是 0 個，比 $2^2$ 小的有 $2^1$ + 0 個。
查表可以看到 pending 上的節點是 `1<-1`，合理。
3. `x10x`：0 pending of size $2^k$; $2^k$ + x pending of sizes < $2^k$
舉例： `0100`，大小為 $2^2$ 的 pending list 是 0 個，比 $2^2$ 小的有 $2^2$ + 0 個。
查表可以看到 pending 上的節點是 `2<-1<-1`，合理。
4. `x11x`：1 pending of size $2^k$; $2^(k-1)$ + x pending of sizes < $2^k$
舉例： `0110`，大小為 $2^2$ 的 pending list 是 1 個，比 $2^2$ 小的有 $2^1$ + 0 個。
查表可以看到 pending 上的節點是 `4<-1<-1`，合理。
5. `y00x`：1 pending of size $2^k$; $2^k$ + x pending of sizes < $2^k$
舉例： `1001`，大小為 $2^2$ 的 pending list 是 1 個，比 $2^2$ 小的有 $2^2$ + $2^0$ 個。
查表可以看到 pending 上的節點是 `4<-2<-2<-1`，合理。
6. `y01x`：2 pending of size $2^k$; $2^(k-1)$ + x pending of sizes < $2^k$
舉例： `1010`，大小為 $2^2$ 的 pending list 是 2 個，比 $2^2$ 小的有 $2^1$ + 0 個。
查表可以看到 pending 上的節點是 `4<-4<-2<-1`，合理。此時當有一個新的節點進入 pending list 時，兩個 $2^2$ 大小的 pending list 會合併成一個 $2^3$ 大小的 pending list，並且不合併的節點數為 $2^2$ 個，達到所要的`合併：不合併為 2 : 1 的比例`效果。並且循環至 state 3。
### 引入到 lab0-c 專案
> 參考 < [jimmylu890303](https://github.com/jimmylu890303/lab0-c) > 作法
將 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 程式碼同 lab0-c 中其他實作功能一樣採取分離設計，用 `list_sort.h` 和 `list_sort.c` 來維護，
由於環境因素，將 `list_sort.c` 使用的類型定義 `u8` 替換成 `unsigned char` 。
這段程式碼很有趣，在 `merge_final` 函數中使用 `u8 count` 的目的主要是作為一個局部計數器，來追蹤鍊結串列節點合併操作的次數，一旦 `count` 從 255 增加到 256，它會溢出並迴繞到 0，這時 if (unlikely(!++count)) 將為真。 在這種情況下，會再次呼叫 cmp 函數，儘管不需要比較元素，但這樣做可以觸發 cond_resched()，從而允許作業系統做出調度決策，防止當前進程過長時間佔用處理器。
```diff
-u8 count = 0;
+unsigned char count = 0;
tail->next = b;
do {
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
```
其中的`unlikely` 是一個宏，本來在 `<linux/compiler.h>` 中定義。提供編譯器分支預測的資訊。當在條件語句中使用 `unlikely` 宏，就是告訴編譯器這個條件是不太可能成立的。可以幫助編譯器進行更有效的程式碼最佳化，以提高程式運行的效率。
由於將程式碼從包含特定巨集定義的環境（如 Linux 核心原始碼）遷移到沒有這些定義的環境（我的普通 C 應用程式）。 因此我用 GCC 提供的內建函數重新定義。
```c
#define unlikely(x) __builtin_expect(!!(x), 0)
#define likely(x) __builtin_expect(!!(x), 1)
```
在原本的 `queue.c` 中引入 `list_sort` ，並善用 `*prev` 參數來判斷升降序，改寫如下：
```diff
+int cmp_function(void *priv, const struct list_head *a, const struct list_head *b)
+{
+ element_t *a_entry = list_entry(a, element_t, list);
+ element_t *b_entry = list_entry(b, element_t, list);
+ bool ascending = *(bool *)priv; // 将 void* 参数转换回 bool
+ if (ascending) {
+ return strcmp(a_entry->value, b_entry->value) > 0;
+ } else {
+ return strcmp(a_entry->value, b_entry->value) < 0;
+ }
+}
+
+/* Sort elements of queue in ascending/descending order */
+void q_linux_sort(struct list_head *head, bool ascending)
+{
+ if (!head || list_empty(head))
+ return;
+ list_sort(&ascending, head, cmp_function);
+}
```
#### 比較兩種排序方法
測試項目如下，其中 `"different sorting methods"` 需替換成預測試排序方法：
```cmd
option fail 0
option malloc 0
new
ih RAND 1000000
time "different sorting methods"
```
Linux list_sort結果：
```cmd
➜ lab0-c git:(master) ✗ ./qtest -v 3 -f my_config.cmd
l = []
l = [ydmcl nymdtm rkyxkrhcv jxadma brxgwwwt knbhglna tfkxjwf cqgalghx libqb tvutrqno yqewed nweddjl lncgsup scjwlpqt ahpbjmrlx gafdpbw yroeg rhaspxep nyvzgwaut pjnxlh rvdbrdf pjhosg nlgxugi gcxphzmqp fsljrf hwclhm ugixfri mjihzsgdh rkbeo ymgvvljxw ... ]
l = [aaaajn aaabd aaabgane aaabqos aaabvtdqq aaacfjr aaacke aaacmrfun aaacwkls aaadoc aaadsrra aaaduj aaaejjp aaaeoob aaaezc aaagc aaagdkmre aaaghsyaw aaagowho aaagycz aaahcrjca aaahe aaahuo aaaidr aaainbma aaaiql aaaivlm aaajr aaakbykuw aaakdg ... ]
Delta time = 0.742
Freeing queue
```
我寫的 top-down merge_sort 結果：
```cmd
➜ lab0-c git:(master) ✗ ./qtest -v 3 -f my_config.cmd
l = []
l = [xjnpwneon wwlaat yfmnywkdf xdalfzp rtrfsg xhdsdj sxxkmix chrcay mmbxkj jhldqvkq jucrx kexylgknk bvkakkax hscyakuhh lojkn glrmuldd arqqt wblde lyynwsgjh qzuwzt ubfqwvfwa jojafwkjd gwlsfnv acghtw bcioamla hwaap icmxa hixwuht lixrn luxke ... ]
l = [aaaaotxg aaabfuai aaabrnbed aaabugyh aaabxxt aaacdl aaacjj aaacy aaadgczb aaadyjwt aaadzlc aaadzyy aaaesqbjj aaaevzaqb aaaffvh aaafivdop aaaftiy aaaftjs aaafyrz aaagaa aaahbvpr aaahlmop aaahnwgs aaahoxqw aaaini aaaixnw aaajuid aaakisbkm aaakiwfp aaaktuoo ... ]
Delta time = 0.714
Freeing queue
```
整理如下（待分析，感覺不應該比較慢）：
| | top-down merge_sort | Linux list_sort |
| -------- | -------- | -------- |
| Time | 0.714 | 0.742 |
### 改進 lib/list_sort.c
引入 Timsort。
Sign in with Wallet
Connect another wallet