owned this note
owned this note
Published
Linked with GitHub
# 2024q1 Homework1 (lab0)
contributed by < [`padaray`](https://github.com/padaray) >
## 開發環境
```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): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 14
Socket(s): 1
Stepping: 3
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 5376.00
```
## 佇列實作和程式碼改進
### `q_new`
> [commit f6ae25f](https://github.com/padaray/lab0-c/commit/f6ae25f50b5df3da9fcb8356888a076edca7d072)
建立新的「空」佇列
我們需要用 `malloc` 配置 `list_head` 空間，並且使用 `list.h` 檔案的 `INIT_LIST_HEAD` 函式，讓 head 指向 head 本身
```shell
$ ./qtest
cmd> new
l = []
```
:::danger
避免非必要的項目縮排 (即 `* `)，用清晰、明確，和流暢的漢語書寫。
:::
### `q_free`
> [commit 28b833e](https://github.com/padaray/lab0-c/commit/28b833e65558c5a879a53f5d54c1982d6f30a469)
釋放佇列所佔用的記憶體
使用 `list.h` 中的 `list_for_each_safe` 函式，在 for 迴圈中呼叫 `list_entry` 取得完整 `element_t` ，當 `entry->value` 不為空則 free，接下來 free 整個 `element_t` 。for 迴圈結束時 free head
```shell
$ ./qtest
cmd> new
l = []
cmd> ih p
l = [p]
cmd> ih l
l = [l p]
cmd> free
l = NULL
```
程式碼改進：
```shell
$ make check
...
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated
make: *** [Makefile:57: check] Error 1
```
:::danger
command 的翻譯是「命令」，而非「指令」(instruction)
:::
執行 make check 命令時回報以上錯誤，原因是在初始化 `list_for_each_safe` 函式的參數時，事先分配空間，造成不必要的記憶體空間配置，程式碼修改如下：
```diff
if (!head)
return;
- struct list_head *node, *safe = malloc(sizeof(struct list_head));
+ struct list_head *node, *safe = NULL;
```
### `q_insert_head`
> [commit b03e585](https://github.com/padaray/lab0-c/commit/b03e5852d7af82f726df7de13b223c5c5a152b76)
在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
`malloc` 一個 `element_t` 大小的空間給新加入的節點 `new_node` ，使用 `strdup` 函式複製一個參數 char s 的副本給 `new_node->value` ，最後呼叫 `list.h` 中的 `list_add` 函式傳入 `new_node`
```shell
$ ./qtest
cmd> new
l = []
cmd> ih r
l = [r]
cmd> ih s
l = [s r]
```
程式碼改進：
```shell
cmd> new
l = []
cmd> ih r
ERROR: Need to allocate and copy string for new queue element
l = [r]
cmd> ih a
ERROR: Need to allocate and copy string for new queue element
l = [a ��!\]
```
最一開始沒有為傳入參數s建立副本，直接使用造成重複存取錯誤，因此修改為以下版本：
```c
new_node->value = malloc(strlen(s) + 1);
if (!new_node->value) {
return false;
}
strcpy(new_node->value, s);
```
最後發現使用 `strdup` 即可完成上述須求，因此修改為以下版本：
```c
new_node->value = strdup(s);
```
### `q_insert_tail`
> [commit a3f913b](https://github.com/padaray/lab0-c/commit/a3f913b7c2ffba94c13a0af0a59dcfaa311c1878)
在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
與 `q_insert_head` 的做法大致相同，差別在於呼叫 `list.h` 中的 `list_add_tail` 函式傳入 `new_node`
```shell
$ ./qtest
cmd> new
l = []
cmd> it e
l = [e]
cmd> it q
l = [e q]
```
### `q_remove_head`
> [commit 5c444e8](https://github.com/padaray/lab0-c/commit/5c444e8a0bbd362bf86e2bdd841a3afd6f650f1f)
在佇列開頭 (head) 移去 (remove) 給定的節點
使用 `list.h` 中的 `list_first_entry` 函式回傳第一個節點的完整 `element_t`，呼叫 `list_del` 函式，斷開第一個節點與佇列，使用 `strncpy` 函式複製 `element_t->value` 到參數 `sp` ，回傳 `element_t`
```shell
l = [s e q]
cmd> ih o
l = [o s e q]
cmd> rh
Removed o from queue
l = [s e q]
```
### `q_remove_tail`
> [commit e83f301](https://github.com/padaray/lab0-c/commit/e83f30154227295ac23f01ac331e47db35bd424e)
在佇列尾端 (tail) 移去 (remove) 給定的節點
與 `q_remove_head` 的做法大致相同，差別在於呼叫 `list.h` 中的 `list_last_entry` 取得最後一個節點
```shell
cmd> ih y
l = [y u i o]
cmd> rt
Removed o from queue
l = [y u i]
```
:::warning
TODO: 提高程式碼的可重用程度。
:::
### `q_size`
> [commit d74b2f4](https://github.com/padaray/lab0-c/commit/d74b2f4c4dc4cfb59ceb9f9a1a35c21a575e64a7)
計算目前佇列的節點總量
初始化 `count` 變數為 0，呼叫 `list.h` 中的 `list_for_each` 函式，在 for 迴圈中執行 `count++` ，最後回傳變數 `count`
```shell
l = [a b c d e f g h]
cmd> size
Queue size = 8
l = [a b c d e f g h]
```
### `q_delete_mid`
> [commit 208b6c5](https://github.com/padaray/lab0-c/commit/208b6c59bfef865aa18b1abffc50c3b46cdc73df)
移走佇列中間的節點。[Leetcode 2095](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
:::danger
- [ ] traverse (動詞) 和 traversal (名詞)
根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse
): (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)
* to pass or move over, along, or through.
* to go to and fro over or along.
其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。
當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。
還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。
在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。
遍歷 (Ergodic) 源於以下二個希臘詞：
* ergon (對應英語的 work)
* odos (對應英語的 path 或 way)
最初這是由奧地利物理學家波茲曼 ([Ludwig Boltzmann](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。
因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
宣告兩個 `list_head` 指標 `front` 和 `back` ，指標 `front` 從第一個節點向後<s>遍歷</s>，指標 `back` 從最後一個節點向前遍歷，當兩個指標指向同一個節點，或是指標 `front` 的前一個節點是指標 `back` 所指向的節點，跳出 while 迴圈，呼叫 `list_del` 將 `front` 所指向的節點從佇列中刪除
```shell
l = [a c e g i]
cmd> dm
l = [a c g i]
cmd> dm
l = [a c i]
cmd> dm
l = [a i]
cmd> dm
l = [a]
```
### `q_delete_dup`
> [commit - 38e85db](https://github.com/padaray/lab0-c/commit/38e85db5eca0d3a6f0a56dbd3180e2683ad8141a)
在已經排序的狀況，移走佇列中具備重複內容的節點。[Leetcode 82](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/)
初始化 `flag` 變數為 false，使用 `list.h` 中的 `list_for_each_entry_safe` 函式，逐一走訪每個節點，確認當前節點的 `value` 是否和下一個節點的 `value` 相同，若是相同則 free 當前節點，同時修改 `flag` 為 true，最後一個重複節點雖和下個節點不相同，仍然會因 `flag` 為 true 刪除節點
```shell
l = [a a a b b c]
cmd> dedup
l = [c]
```
### `q_swap`
> [commit - 76ba3ff](https://github.com/padaray/lab0-c/commit/76ba3ff411fec83a71c913f32ccc29d1010e13a5)
交換佇列中鄰近的節點。[Leetcode 24](https://leetcode.com/problems/swap-nodes-in-pairs/)
呼叫 `q_reverseK` 函式傳入參數 2
```shell
l = [a b c d e f]
cmd> swap
l = [b a d c f e]
```
### `q_reverse`
> [commit - 0e5cf75](https://github.com/padaray/lab0-c/commit/0e5cf756e3a5c5b44e1c61c94182dd1e82da1210)
以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
使用 `list_for_each_safe` 函式，逐一走訪每個節點，對當前的節點使用 `list_move` 函式，使其到佇列的最前方，走訪完後即可完成 reverse
```shell
l = [a b c d e f]
cmd> reverse
l = [f e d c b a]
```
### `q_reverseK`
> [commit - 0025287](https://github.com/padaray/lab0-c/commit/0025287587c557c4a749b16aef1c3b15cc683b11)
類似 `q_reverse`，但指定每 k 個節點為一組，進行反向順序排列。[Leetcode 25](https://leetcode.com/problems/reverse-nodes-in-k-group/description/)
新增兩個暫存佇列 `tmp`、`tmp_rev`，`tmp` 儲存 k 個變數後，執行 `q_reverse` 函式，將儲存的變數反向重新排列，呼叫 `list_splice_tail_init` 函式將佇列 `tmp` 插入 `tmp_rev` 尾端，若剩餘的節點少於 k ，呼叫 `list_splice` 函式，將佇列 `tmp_rev` 插入 head 前方
```shell
l = [1 2 3 4 5 6]
cmd> reverseK 2
l = [2 1 4 3 6 5]
cmd> reverseK 6
l = [5 6 3 4 1 2]
```
程式碼改進：
```diff
- if (count % k == 0) {
- list_cut_position(&tmp, head, cur);
- q_reverse(&tmp);
- list_splice_tail_init(&tmp, &tmp_rev);
- if (cur->next == head)
- list_splice(&tmp_rev, head);
- } else if (cur->next == head) {
- list_splice(&tmp_rev, head);
- }
+ if (count % k == 0 && cur->next == head) {
+ list_cut_position(&tmp, head, cur);
+ q_reverse(&tmp);
+ list_splice_tail_init(&tmp, &tmp_rev);
+ list_splice(&tmp_rev, head);
+ } else if (count % k == 0) {
+ list_cut_position(&tmp, head, cur);
+ q_reverse(&tmp);
+ list_splice_tail_init(&tmp, &tmp_rev);
+ } else if (cur->next == head) {
+ list_splice(&tmp_rev, head);
+ }
```
:::warning
使用精準的詞彙。
:::
雖然兩種撰寫方式是<s>同義的</s>，但是若使用刪掉部份的程式碼，測試時會讓佇列清空，目前還沒找到原因
```shell
l = [a b c d e f]
cmd> reverseK 2
l = []
```
### `q_sort`
> [commit - be368c1](https://github.com/padaray/lab0-c/commit/be368c19a876871e377366252bec36f41876dbbb)
以遞增順序來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法
排序演算法選擇 Merge Sort，使用快慢指標的方式，讓兩個指標 `slow` 和 `fast` 分別指向中間的節點和最後的節點，呼叫 `list_cut_position` 函式，將佇列分為 head 到 slow，slow->next 到 fast，達成將佇列切成兩段的效果
以遞迴的方式呼叫 `q_sort` 函式，當每個佇列剩下一個節點，使用 `q_merge_two_list` 函式，將每個佇列排序且合併
```shell
l = [8 4 9 5 2 1 3]
cmd> sort
l = [1 2 3 4 5 8 9]
```
### `q_ascend`
> [commit f611f5f](https://github.com/padaray/lab0-c/commit/f611f5f49922538b8bc29d4de896612f66e70edf)
參閱 [Leetcode 2487](https://leetcode.com/problems/remove-nodes-from-linked-list/description/)
呼叫 `list_last_entry` 函式取得佇列最後一個 entry ，比較最後一個 entry `cur_entry` 和倒數第二個 entry `comp_entry`
條件一：
    若 comp_entry 小於 cur_entry ，刪除 comp_entry
條件二：
    若 comp_entry 大於 cur_entry ，cur_entry = comp_entry
```shell
l = [2 1 3 6 5 8 9]
cmd> ascend
l = [1 3 5 8 9]
```
### `q_descend`
> [commit - 38368ab](https://github.com/padaray/lab0-c/commit/38368ab0b08d7236e0c48d82dfd19863839c481b)
:::danger
Chris Beams 在 [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/) 一文 (繁體中文翻譯: [如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)) 提出，好的 Git commit message 應符合七條規則:
1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. 標題開頭要大寫
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how
你沒有依循上述規範，請詳讀作業說明，以 `git rebase -i` 改正。
:::
參閱 [Leetcode - 2487](https://leetcode.com/problems/remove-nodes-from-linked-list/description/)
呼叫 `list_last_entry` 函式取得佇列最後一個 entry ，比較最後一個 entry `cur_entry` 和倒數第二個 entry `comp_entry`
條件一：
    若 comp_entry 大於 cur_entry ，刪除 comp_entry
條件二：
    若 comp_entry 小於 cur_entry ，cur_entry = comp_entry
```shell
l = [7 9 4 5 3 2 1]
cmd> descend
l = [9 5 3 2 1]
```
### `q_merge`
合併所有已排序的佇列，並合而為一個新的已排序佇列。[LeetCode 23](https://leetcode.com/problems/merge-k-sorted-lists/description/)
實作方式：
```shell
l = [2 4 5]
cmd> new
l = []
cmd> ih 3
l = [3]
cmd> ih 1
l = [1 3]
cmd> merge
l = [1 2 3 4 5]
```
</br></br>
## 在 qtest 提供新的命令 `shuffle`
以 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 的方式實作洗牌演算法，以下為程式碼實作：
> [commit - 19971b1](https://github.com/padaray/lab0-c/commit/19971b1fd5ec3cd4103db176728c0ea20fe95abf)
### 撰寫 `shuffle` 測試檔
1. 創建一個 `testShuffle.py` 檔，複製教材所提供的 [測試程式碼](https://hackmd.io/@sysprog/linux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)
2. 修改 `qtest.c` 程式碼
```c=29
extern void q_shuffle(struct list_head *head);
```
```c=1015
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current || !current->q) {
report(3, "Warning: Calling shuffle on null queue");
return false;
}
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
q_show(3);
return !error_check();
}
```
```c=1038
ADD_COMMAND(shuffle, "Shuffle all nodes in the list", "");
```
3. 執行`testShuffle.py` 檔
```cmd
python3 ./scripts/testShuffle.py
```
</br>
### 驗證 `shuffle`
> [commit - 19971b1](https://github.com/padaray/lab0-c/commit/19971b1fd5ec3cd4103db176728c0ea20fe95abf)
**1. 計算 Chi-square test statistic $X^2 = \Sigma_{i=1}^n \frac{(O_i - E_i)^2}{E_i}$**
[測試程式碼](https://hackmd.io/@sysprog/linux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) 中的串列有四個節點，共有 4！種排列組合，以亂數打亂 1000000 次後，每種排列的出現次數期望次數為 41666，Chi-square 是18.113。以下為結果：
```shell
ray@ray:~/linux2024/lab0-c$ python3 ./scripts/testShuffle.py
Expectation: 41666
Observation: {
'1234': 41456, '1243': 41703, '1324': 41676,
'1342': 41873, '1423': 41882, '1432': 41708,
'2134': 41708, '2143': 41375, '2314': 41695,
'2341': 41946, '2413': 41477, '2431': 41719,
'3124': 41287, '3142': 41524, '3214': 41680,
'3241': 41479, '3412': 41482, '3421': 41840,
'4123': 41591, '4132': 41793, '4213': 41849,
'4231': 41768, '4312': 41554, '4321': 41935
}
chi square sum: 18.113281812508998
```
**2. 決定自由度**
自由度的計算為 N 個隨機樣本減去 1，四個節點的隨機樣本數是 24，因此自由度為 23
**3. 選擇顯著水準**
顯著水準 α 代表在虛無假說為真下，型一錯誤發生之機率。
α = P(拒絕 | 為真)，α 設定為 0.05
透過卡方分布表知道自由度 23，chi-square 18.113，P value 介於 0.25 和 0.5 之間
**4. 統計檢定的結果不拒絕虛無假說**
P value 大於 α，因此無法推翻虛無假說「shuffle 的結果發生的機率相同，遵守 Uniform distribution」
</br></br>
## 以 [Massif](https://valgrind.org/docs/manual/ms-manual.html) 分析記憶體使用量
1. 使用以下 valgrind 命令 `--tool=massif` 產生 massif 檔
```cmd
valgrind --tool=massif ./qtest -f traces/trace-15-perf.cmd
```
2. 執行命令後可在 lab0-c 資料夾中產生 `massif.out.xxxx` 檔
3. 安裝 massif-visualizer 插件，以視覺化工具查看記憶體使用狀況
```cmd
sudo apt install massif-visualizer
```
4. 用 massif-visualizer 執行 `massif.out.xxxx` 檔
```cmd
massif-visualizer massif.out.3445
```
5. 產生以下視覺化圖像
</br></br></br>
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
### 程式碼
list_sort.c 所實作的排序演算法為 merge sort，程式碼分為三個函式，以下個別進行講解：
#### 1. merge
此函式的功能為將串列 a，b 進行合併。合併的方式為若 a 的節點 <= b 的節點，則將 a 的節點放入串列 head 內; 若 a 的節點 > b 的節點，則將 b 的節點放入串列 head 內，最後回傳串列 head。
```
/*
* Returns a list organized in an intermediate format suited
* to chaining of merge() calls: null-terminated, no reserved or
* sentinel head node, "prev" links not maintained.
*/
```
透過註解了解，此函式用在 merge sort 兩兩合併時所用，但並不是用來在生成最終 merge sort 的結果，因此不用實作 "prev" 來變成雙向鏈結串列
**圖解實作方式如下：**
```graphviz
digraph{
rankdir=LR
NULL [shape=none,color=black]
head [shape=none,label=head]
tail [shape=none,label=tail]
tail -> head -> NULL
}
```
若 a <= b：
```graphviz
digraph{
rankdir=LR
head [shape=none,label=head]
tail [shape=none,label=tail]
a [shape=none,label=a]
a_next [shape=none,label=a_next]
head -> a
tail -> a -> a_next
}
```
**程式碼理解**
```c=19
struct list_head *head, **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
...
```
第 19 行宣告一個指標的指標 `tail`，並將其指向 `head`，原因是可以透過更新 `tail` 指向的位址，增加鏈節串列 `head` 的節點，使 `head` 指向的位址不用更動，最後直接回傳此串列即可。
第 23 行的 <= 為此實作方式是 stable sort 的原因，因為 = 代表 a，b 兩個串列內的值相同，若是值相同的情況下，會將 a 的節點放入 `head` 中，而不是 b 的節點，以此達到 stable
#### 2. merge_final
此函式的功能是，當剩下最後兩個串列要進行合併時，才會使用此函式，並且會將串列恢復成雙向鏈節串列。註解中提到，實作兩個 merge 函式的原因是，在合併過程中不用維護 prev 會讓程式執行更快
**圖解實作方式如下：**
```graphviz
digraph{
rankdir=LR
head_next [shape=none,color=black]
head [shape=none,label=head]
tail [shape=none,label=tail]
head -> head_next
tail -> head_next
}
```
若 a <= b：
```graphviz
digraph{
rankdir=LR
node [shape=none,color=black]
tail -> a -> tail
head -> a
}
```
tail = a:
```graphviz
digraph{
rankdir=LR
node [shape=none,color=black]
head -> tail
}
```
重複以上操作
</br>
**程式碼理解**
```c=79
/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
...
```
這段程式碼是當合併兩個串列時，其中一個串列已經為空，將剩下的串列直接放入 `head` 內，並且讓該串列變回雙向鍊結串列
**unlikely函式**
第89行 `likely` 和 `unlikely` 函式為 linux kernel 的巨集，被定義在 /include/linux/compiler.h 中，程式碼如下：
```c
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
```
`_built_expect` 是gcc的內建function，`__builtin_expect((x),1)` 的意思是 x 為真的機率較大，反之為假的機率較大。兩個 ! 運算符號的原因是，將輸入的參數 x 變為 0 或 1，因為本來 x 可以為非 0 整數。總結來說，使用 `likely` 函式 assembly code 會提前執行發生機率較大的程式碼
[資料來源](https://meetonfriday.com/posts/cecba4ef/)
#### 3. list_sort（ 主程式 ）
```c=128
/**
* This mergesort is as eager as possible while always performing at least
* 2:1 balanced merges. Given two pending sublists of size 2^k, they are
* merged to a size-2^(k+1) list as soon as we have 2^k following elements.
*
* Thus, it will avoid cache thrashing as long as 3*2^k elements can
* fit into the cache. Not quite as good as a fully-eager bottom-up
* mergesort, but it does use 0.2*n fewer comparisons, so is faster in
* the common case that everything fits into L1.
```
這段註解描述，要進行合併的兩個 sublists，至少要維持著 2 ：1 的大小比例，才能讓效能比較好，我們只需要注意 cache 大小是否低於 $3 * 2^k$，即可避免發生 cache thrashing*，
[cache thrashing](https://en.wikipedia.org/wiki/Thrashing_(computer_science)) 解釋：在低關聯度的 cache 中，若有兩個以上要取得的記憶體位置，它們需要用到的 cache line 相同，在輪流存取的過程中，就會一直發生 cache miss
**合併機制**
```c=138
/**
* The merging is controlled by "count", the number of elements in the
* pending lists. This is beautifully simple code, but rather subtle.
*
* 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`，當 `pending` 中的節點數增加，`count + 1`，當 `count` 是 $2^k$ 時不進行合併，反之則合併
</br>
**程式碼理解**
```c=214
do {
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;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
第 219 行的 for 迴圈是為了找到 `count` 的 least significant clear bit，第 222 行判斷 bit 是否為 1，如果是的話進行 merge，之後將 list 的節點移到 pending 中。重複上述動作直到 list 清空。
```c=239
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
```
上面的程式碼在做的是將 pending 中的節點放到 list 中，並且做合併。
總結就是 214～237 行是將單個節點合併成部分排序的子串列，239～251 行是將這些子串列進一步合併成最後排序好的鏈結串列。
</br>
Sign in with Wallet
