# Linux 核心專題: 針對鏈結串列的資料排序改進
> 執行人: randyuncle
> [解說錄影](https://youtu.be/D6mcttf1jKA)
:::danger
附上解說錄影
:::
### Reviewed by `164253`
Timsort 是建立在大部分靠近的資料都已經有序的前提上的，是不是可以判斷 run 太多切換成其他的排序方式。
回應：可以考慮這麼做。但可能需要其他方法測試 run 的數量和排序速度的關聯性，才能確定能否靠 run 的數量判斷是否切換排序演算法。
### Reviewed by `yenslife`
> 合併序列時，若 run 的數量等於或小於 2 的冪時，效率是最高的
這件事有辦法用數學證明嗎？
### Reviewed by `jujuegg`
請問合併時所使用的 Galloping merge 在 worst case 的表現會比起一般的 "one pair at a time" mode 還要差嗎?
回應：理論上來說，worst case of merge sort（注意，我說的不是 Timsort 的 worst case）的情況下，因為它的目的是讓合併排序在合併時會是兩個序列交叉取值得關係，所以很難達到 galloping mode 的啟動條件，也就是其合併時很難連續取同一個序列的元素的個數超過 `min_gallop` 次，其中 `min_gallop` 是一個指定的變數。但是，我寫說很難啟動，而不是不會啟動，代表它還是有機會啟動到 galloping mode。
我手邊有之前測的數據，這裡就把結果的 plot 出來。
| Number of Comparison | K value | Time (us) |
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
這裡使用的排序程式是 [`timsort_l_gallop.c`](https://github.com/randyuncle/linux2024_final_listsort/blob/master/timsort_l_gallop.c)、以及 [`timsort_linear.c`](https://github.com/randyuncle/linux2024_final_listsort/blob/master/timsort_linear.c)。兩者的差距在於也沒有實施 galloping mode。
在比較次數的分佈圖中，雖然很不明顯，但是在兩個排序程式在各自週期的最高點中，他們的排序次數其實有些微的差異，且 `timsort_l_gallop.c` 的比較次數會比 `timsort_linear.c`，這點必須得直接從數據看才會知道。另一方面，從時間來看，有 galloping mode 的排序明顯的更不適應 worst case of merge sort。除了有啟動 galloping mode 的因素外，我認為使它需要排比較長時間的主要原因是，需要額外計數、以及清零需不需要進入 galloping mode 的計數器，也是影響整體排序時間的關鍵。
### Reviewed by `youjiaw`
我想請問實驗的資料分佈為什麼有使用升冪資料，卻沒有降冪資料？
回應：測一整輪排序程式的時間實在太久了，所以只先實作了升冪資料的分佈。
## 任務描述
以第一週測驗二給定的 Timsort 為基礎，針對 Linux 核心風格的鏈結串列，提出資料排序的改進方案。
## 開發環境
```shell
$ 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
Virtualization features:
Virtualization: VT-x
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)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-19
$ uname -r
6.5.0-41-generic
```
## TODO: 探討 Timsort 原理並提出改進方案
### Timsort 的原理
Timsort 是一種混合排序演算法，由 Tim Peters 在 2002 年設計，並被用於 Python 的內建排序函數以及 Java 的 Arrays.sort() 方法。它結合了合併排序（Merge Sort）和插入排序（Insertion Sort）的優點，旨在高效處理真實世界中的數據。
Timsort 對於 Merge sort 的改進有以下幾點：
* 加速合併的速度及次數。
* 改善記憶體及使用 cache-friendly 的實作手法。
接下來將描述 Timsort 是用哪些做法來達成上面的兩點改善。
:::danger
闡述其主體想法。
:::
#### Run 的使用
考慮到以下的序列：$$12, 10, 7, 5, 7, 10, 14, 25, 36, 3, 5, 11, 14, 15, 21, 22, 20, 15, 10, 8, 5, 1$$
在開始排序前，Timsort 會先走訪一次給定的序列，將此序列分解成一條一條單調遞增或遞減的序列：
* $12, 10, 7, 5$
* $7, 10, 14, 25, 36$
* $3, 5, 11, 14, 15, 21, 22$
* $20, 15, 10, 8, 5, 1$
這些序列在這被稱為 runs。在這些序列當中，單調遞減的序列會在這個階段被反轉為單調遞增的序列。
這種將欲排序的序列降解為一條一條的 runs 的方法其實並非新穎的做法。在 < *The art of computer programming, 2th ed., Volume 3* > 中，作者 Knuth 有在裡面提到 NaturalMergeSort 演算法的策略，在這本書出版後的其他研究也都統稱帶有 runs 特性的合併演算法為 Natural Mergesort。
在 Timsort 中，當有一條 run 被分解出來後，會被加入進一條堆疊的最上層中。當堆疊的 run 序列達到一定的數量時，Timsort 就會啟動 `merge_collapse`，判斷目前堆疊中最上層的幾條 run 是否要執行合併，使得各個 run 的長度能趨近於等長。此做法主要是盡量讓 run 在較高層的 memory hierarchy 就可以合併，以 temporal locality 的想法來減少記憶體的開銷，達成 cache-friendly。這個特點和 Linux 核心中的 lib/list_sort.c 的實作手法是很相似的。
合併序列時，若 run 的數量等於或略小於 2 的冪時，效率是最高的；反之，若 run 的數量略大於 2 的冪時，效率則會特別低。因此，Tim Peters 設定了每一條 run 都有最小的長度限制 -- `minrun` ( <= 32 )，以能限制 run 序列的數量，以及堆疊的空間複雜度為 $O(log N)$。若有 run 的長度低於該值，就會使用 binary insertion sort（i.e. 使用 binary search 的方式搜尋欲插入的節點在序列的位置），將該條 run 後面的元素填補進去，直到長度為 `minrun` 為止。
讓我們將眼光回到前面提到的 `merge_collapse` 策略中。`merge_collapse` 策略的制定，對於能不能將各個 run 序列長度都能趨近於等長，是一個不少研究者都在研究的課題。從一開始對 [java 中 Timsort 實作的研究](http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf)，到後續對於 [stable merge sort](https://arxiv.org/pdf/1801.04641) 的研究，以及 [powersort](https://arxiv.org/pdf/1805.04154)、[adaptive shiverssort](https://arxiv.org/pdf/1809.08411) 的誕生，他們的研究目標都是如何改善 `merge_collapse` 策略，使其能夠在各個資料分布有更趨近於 optimal sorting 的特性。以下將對 Timsort 的 `merge_collapse` 策略做說明。
- [ ] 原始的 `merge_collapse`
檢查堆疊中最上 3 層的 run 序列 -- $X$, $Y$, $Z$ -- 是否滿足以下 invariant：
* $X$ 的長度大於 $Y$ 和 $Z$ 長度總和
* $Y$ 的長度大於 $Z$ 的長度
若以上 invariant 不滿足，則會開始以下判斷決定是否進行合併：
* 若未合併的 run 序列數量超過 3 條或以上，取堆疊最上層 3 條 run $X$, $Y$, $Z$，若 $len(X) >= len(Y) + len(Z)$，則 $Y$ 和 $X$ 或 $Z$ 當中最小的 run 合併。
* 若未合併的 run 序列數量超過兩個，且不合上一條規則的條件的話，取堆疊最上層 2 條 run $X$, $Y$，若 $len(X) >= len(Y)$，兩條 run 執行合併。
但是，這個版本合併策略，無法在任意場景使該 invariant 成立。
在 [Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it)](http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/) 文章中，提出了以下的堆疊分布做為反例：
```
120, 80, 25, 20, 30
```
在第一次判斷迴圈中，25 和 20 被合併（因為 25 < 20 + 30 以及 25 < 30）
```
120, 80, 45, 30
```
在第二次迴圈中，因為 80 > 45 + 30 以及 45 > 30，所以其會以符合 invariant 的原因而跳出 `merge_collapse` 函式。但是，如果以 [120, 80, 45] 三條 run 為一組，會因為 120 < 80 + 45，而發現到他們的分布是不符合 invariant 的
因此，文章的作者對 `merge_collapse` 提出了以下的改善機制。
- [ ] 改良版的 `merge_collapse`
在原本的合併判斷的基礎上，再加上以下的條件：
* 若當前的堆疊有 4 條 run 或以上，取堆疊最上層 4 條 run $X$, $Y$, $Z$, $W$ 為對象判斷，當出現 $X <= Y + Z$ 或 $Y <= Z + W$ 的場合，將 $Z$ 與 $Y$ 和 $W$ 中長度最小的 run 做合併。
加入這個條件後，以上一段文章作者的例子再進行一次分析，可以發現到在第二次判斷迴圈時，會因為 120 < 80 + 45 的條件（也就是 $X <= Y + Z$），而執行合併，堆疊的最終結果也變為以下：
```
120, 80, 75
```
#### 合併演算法 -- Galloping merge
在 Tim Peters 所撰寫的 [listsort.txt](https://github.com/python/cpython/blob/24e5ad4689de9adc8e4a7d8c08fe400dcea668e6/Objects/listsort.txt) 中，描述了他在 Timsort 的實作中是如何增進合併排序的合併操作，作者稱這個操作為 **Galloping**。
在傳統的合併排序中，他們的合併操作主要從兩個序列的開頭元素一對一的比較，哪一個元素存的值最小，該元素的值就更新到合併後的序列中，直到其中一個序列的元素被取完，而另一個序列剩下的元素就都接在該元素的後面。這個方法 Tim Peter 稱它為 "one pair at a time" mode。Linux 核心的 lib/list_sort.c 目前的合併操作是這樣實作的。
不過，Tim Peter 觀察到，在現實世界的資料中，並不是所有的資料都是隨機排列的資料，反絕大部分的資料都會是部份排序過得形式。因此，他決定在 Python list sort 的合併操作中實作 galloping strategy，以加速序列合併的過程。
在 galloping mode 中，總共可歸納為兩個部份：
* Exponential searching the boundaries.
* Binary searching within the identified boundaries.
假設有 $a, b$ 兩個序列，且 $len(a) < len(b)$。在第一個部份中，Tim sort 會先以 exponential search 的方法，在 $b$ 序列中，尋找當前 $a$ 序列的頭部元素可併入該序列的區間。此步驟也可稱為 "galloping"。
在 [listsort.txt](https://github.com/python/cpython/blob/main/Objects/listsort.txt#L211) 中，對 "galloping" 作法有以下的說明：
> In galloping mode, we first look for A[0] in B. We do this via "galloping", comparing A[0] in turn to B[0], B[1], B[3], B[7], ..., B[2**j - 1], ..., until finding the k such that B[2**(k-1) - 1] < A[0] <= B[2**k - 1]. This takes at most roughly lg(B) comparisons, and, unlike a straight binary search, favors finding the right spot early in B (more on that later).
在原描述的定義中，"galloping" 主要是以 0, 1, 3, 7, …, 2k+1 的節點定位去找到節點大略會插入的範圍。簡單來說，就是以 2 的冪次做為間距的搜尋，以求能在 $lg(B)$ 的比較次數就可以找到合適的合併區間。
在找到合併區間後，Tim sort 會使用和 minrun insertion 同樣的方法，使用 binary insertion sort 的方式，從找到的合併區間中，搜尋 $a$ 序列的頭部元素在 $b$ 序列的最佳合併點。
不過，由於不能直接假定所有的序列元素皆為部份排序過的序列。因此，Tim sort 並不直接對所有序列採用 galloping mode，而是還是默認以 "one pair at a time" mode 為優先使用的合併策略。至於是否對該序列的合併使用 galloping mode，則是額外實作了一個變數 `min_gallop`，定義在 "one pair at a time" mode 時，如果有連續 `min_gallop` 次的合併操作都取同一個序列時，就啟動 galloping mode 加速合併操作。
### 在 Linux 核心鏈結串列的資料排序實作 Timsort 的疑慮點
雖然根據以上的描述，Tim sort 對於合併排序的加速，不管是採用 run decomposition 策略，還是使用新型態的合併操作，從理論的描述來看，都是可以改進 lib/list_sort 的好策略。但是，[原本的 Timsort 實作](https://github.com/python/cpython/blob/24e5ad4689de9adc8e4a7d8c08fe400dcea668e6/Objects/listobject.c#L2180)是在陣列中完成，而非鏈結串列。
在 C 語言的鏈結串列中，若要取得指定位置（節點）的元素，必須從頭節點開始走訪序列，才能找到特定位置的元素。相反地，在陣列中，只要知道要取得的是第幾個元素，就可以直接從陣列中取得，而不需耗費走訪的時間。因此，在 Python 的實作中，可以輕鬆使用 binary insertion sort 進行 run 的填充，以及在合併序列的 galloping mode 中尋找合併點。所以，在鏈結串列中，實作 run 填充以及 galloping mode 的 binary insertion sort 是否會比 linear insertion sort 更有效率，是一個值得探討的問題。
### 當前基於 list API 的 Timsort 實作
我目前引入進測試的 [`timsort_merge.c`](https://github.com/randyuncle/linux2024_final_listsort/blob/master/timsort_merge.c) 程式檔，是源自於 [linux2024-quiz1-測驗二](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) 的 `timsort.c` 程式碼，兩者的區別在於 `timsort_merge.c` 使用的是 Linux 核心的函式庫，而 `timsort.c` 則是使用 user space 的函式庫。
不過，兩者的排序程式實作內容都是一樣的，主要是因為 `timsort.c` 的撰寫方式就是從 Linux 核心的 lib/list_sort.c 改寫而成，改變的地方是將原本對串列做 Bottom-up Queue Merge 的 do-while 迴圈改成做 run decomposition，以及將 Bottom-up Queue Merge 的節點串列合併策略，改成 Timsort 的 run 序列合併策略。因此，其本身就可在核心環境編譯及使用。
但是，在 `timsort_merge.c` 中，只有實作 Timsort 的 run decomposition 以及 run 合併策略，並沒有實作 minrun 限制，以及 galloping mode 機制，所以往後的可以嘗試引入這兩個實作，並觀察它們是否可以穩定 Timsort 的運行，或反而只是使鏈結串列的 Timsort 更加不穩定。
[`timsort_binary.c`](https://github.com/randyuncle/linux2024_final_listsort/blob/master/timsort_binary.c) 以及 [`timsort_linear.c`](https://github.com/randyuncle/linux2024_final_listsort/blob/master/timsort_linear.c) 是我在當前 Timsort 實作中增加 min run 限制的程式碼。這兩支程式主要的目的是，比較在較少的鏈結串列節點數的範圍中（在這裡，我設定的 min. run 上限是 32），究竟是 binary insertion sort 會比較快，還是 linear insertion sort。需要注意的是，這兩支程式目前不能排序帶有高頻率重複資料的資料分佈，因為它們的實作是 unstable 的，在相同的資料內容中，會有 sequence id 上的變動。
另一方面，[`timsort_b_gallop.c`](https://github.com/randyuncle/linux2024_final_listsort/blob/master/timsort_b_gallop.c) 和 [`timsort_l_gallop.c`](https://github.com/randyuncle/linux2024_final_listsort/blob/master/timsort_l_gallop.c) 是由上一段的程式碼，各自添加了 galloping mode 的版本。但是，這兩支程式後續會從測試程式中剔除，因為目前的 galloping mode 在大量資料的測試下，出現 segmentation fault 的問題。
### Timsort 的複雜度是 $O(n\log{n})$
<!-- "On compressing permutations and adaptive sorting"
"On the Worst-Case Complexity of Timsort" -->
Timsort 自 2002 年由 Tim Peter 於 cpython 實作並發表以來，並沒有相關的理論證明其確實為 $O(nlogn)$ 的排序演算法。直到 ["Merge Strategies: from Merge Sort to TimSort"](https://hal.science/hal-01212839v1/file/aunipi2016-merge-sorts.pdf) 論文中，才有記載 Timsort 為 $O(n\log{n})$ 的簡單證明。3 年後，同一研究團隊，聯合 Adaptive Shivers Sort 的發明者，共同發表 ["On the Worst-Case Complexity of TimSort"](https://arxiv.org/pdf/1805.08612)，對於 Timsort 的排序複雜度比起上一篇論文中，提供更為嚴謹的證明。
#### 分析的 Timsort 結構
我們先回到 Timsort 的排序結構。在 Python 3.6.5 版時，Timsort 的運作結構可以以下的 `Algorithm 1` 虛擬碼做呈現：
- [ ] Algorithm 1：
```
Input : A sequence S to sort
Result: The sequence S is sorted into a single run, which remains on the stack.
Note: The function `merge_force_collapse repeatedly` pops the last two runs on
the stack R, merges them and pushes the resulting run back on the stack.
runs ← a run decomposition of S
R ← an empty stack
while runs != ∅ do // main loop of TimSort
remove a run r from runs and push r onto R
merge_collapse(R)
if height(R) != 1 then // the height of R is its number of runs
merge_force_collapse(R)
```
另一方面，它的 `merge_collapse()` 函式也可以以下 `Algorithm 2` 虛擬碼做類比：
- [ ] Algorithm 2：
```
input : A stack of runs R
Result: The invariant of Equations (1) and (2) is established.
Note: The runs on the stack are denoted by R[1] . . . R[height(R)], from top
to bottom. The length of run R[i] is denoted by ri. The blue highlight
indicates that the condition was not present in the original version of
TimSort (this will be discussed in section 5).
while height(R) > 1 do
n ← height(R) − 2
if (n > 0 and r3 <= r2 + r1) or (n > 1 and r4 <= r3 + r2) then
if r3 < r1 then
merge runs R[2] and R[3] on the stack
else
merge runs R[1] and R[2] on the stack
else if r2 <= r1 then
merge runs R[1] and R[2] on the stack
else break
```
將以上兩個演算法做合併及轉換，可以得到以下 `Algorithm 3` 供證明的虛擬碼：
- [ ] Algorithm 3：
```
input : A sequence to S to sort
Result: The sequence S is sorted into a single run, which remains on the stack.
Note: At any time, we denote the height of the stack R by h and its ith
top-most run (for 1 <= i <= h) by Ri. The size of this run is denoted by ri.
runs ← the run decomposition of S
R ← an empty stack
while runs != ∅ do // main loop of TimSort
remove a run r from runs and push r onto R // #1
while true do
if h > 3 and r1 > r3 then merge the runs R2 and R3 // #2
else if h > 2 and r1 > r2 then merge the runs R1 and R2 // #3
else if h > 3 and r1 + r2 > r3 then merge the runs R1 and R2 // #4
else if h > 4 and r2 + r3 > r4 then merge the runs R1 and R2 // #5
else break
while h != 1 do merge the runs R1 and R2
```
其中，我們可以將 Timsort 的主要迴圈結構編號為以下：
* **#1**: remove a run r from runs and push r onto R
* **#2**: if h > 3 and r1 > r3 then merge the runs R2 and R3
* **#3**: else if h > 2 and r1 > r2 then merge the runs R1 and R2
* **#4**: else if h > 3 and r1 + r2 > r3 then merge the runs R1 and R2
* **#5**: else if h > 4 and r2 + r3 > r4 then merge the runs R1 and R2
在以下證明中，將會拋棄 Timsort 中所有的改善手段（min. run 限制、galloping mode 等），並只分析 merging two runs 的總體 merge cost，也就是 `merge_collapse()` 裡主要 while 迴圈的內容。
#### 理論
**理論一**：令 C 為長度為 n 的陣列的 class，且該陣列的 run decompositions 擁有 $\rho$ 條 monotonic runs。其中，該 $\rho$ 條 monotonic runs 可被表示為 $r_{1}, r_{2}, ..., r_{\rho}$。令 $H(p_{1}, ..., p_{\rho}) = -\sum^{\rho}_{i=1} p_{i}log_{2}(p_{i})$ 為 binary Shannon entropy，且 $\mathcal{H} = H(r_{1}/n, ..., r_{\rho}/n)$。則，
Timsort 在陣列的運行時間為 $O(n + n\mathcal{H})$。
若**理論一**成立，我們可以得到以下 Timsort 的複雜度界限。
**理論二**：Timsort 在長度為 n，且有 $\rho$ 條 monotonic runs 的陣列的運行時間為 $O(n + nlog(\rho))$。因此，其複雜度為 $O(nlogn)$。
*<證明>*：
$f:x \longmapsto xln(x)$ 函式在正實數區間中是凹函數，因為其二次微分為 $f^{\prime\prime} = -1/x$。因此，當 $p_{1}, ..., p_{\rho}$ 皆為正實數，且總和為 1，我們可得 $$H(p_{1}, ..., p_{\rho}) = -\sum^{\rho}_{i=1} f(p_{i})/ln(2) <= {\rho}f(1/\rho)/ln(2) = log_{2}(\rho)。$$ 這也代表著，$\mathcal{H} <= log_{2}(\rho)$。也因此， Timsort 的運行時間在 $O(n + nlog(\rho))$。由於 ${\rho} <= n$，我們可以說 $O(n + nlog(\rho)) \supseteq O(n + nlog(n)) = O(nlogn)$，證明理論二成立。
#### Compressing permutations and contigious monotone runs
<!-- 好多沒看過得東西... -->
在證明**理論一**成立與否之前，我們先來了解為什麼證明 Timsort 的複雜度還需要熵的參與。
在 ["On compressing permutations and adaptive sorting"](https://www.sciencedirect.com/science/article/pii/S0304397513007962) 論文中，作者提出一種 compressed data structure 可以將 permutations $\pi$ 編碼成 $$n(1 + \mathcal{H}(R)) = n + \sum^{nRuns}_{i=1} r_{i}log_{2}{n/r_{i}} <= n(1 + log_{2}\mathcal{nRuns})$$ 位元，且 $\pi()$ 以及 $\pi^{-1}()$ 的平均時間複雜度為 $O(\mathcal{H}(R)/log(log(n)))$，以及最差時間複雜度 $O(log(\mathcal{nRuns})/log(log(n)))$。
不過，這篇論文對於 Timsort 複雜度的證明來說，比較重要的是文中理論二的結論：
**理論二**：存在一排序演算法排序長度為 n，且包含 $\mathcal{nRuns}$ 條 contigious monotone runs 的陣列，需要 $O(n( 1 + \mathcal{H}(\mathcal{nRuns})))$ 的時間組成指定的 $\mathcal{vRuns}$ 向量。其中，此耗費的時間在 comparison model 中是 worst case optimal 的。
所以，以下我會先寫關於這條理論的說明。
- [ ] sorting and permutations
一個有限集合的 permutations $\pi$ 指的是將其元素排列成一行。之所以會在排序當中使用到 permutations，是因為它們可以當作為排序的序列，並且其能被用來計算導致某排序步驟被執行一定次數的 permutations 數量，以能研究不同排序方法的效率。不過 permutations 數量通常會很多，所以如何將其資料量壓縮，且同樣易於查詢，是一個從古至今都有人在研究的課題。例如說，在 2012 年的 Theoretical Computer Science 期刊中，["Succinct Representations of Permutations and Functions"](https://arxiv.org/pdf/1108.1983) 這篇論文提出了能夠在 $O(lg(n)/lg(lg(n)))$ 時間複雜度就可尋找指定的 $\pi$ 和它的 inverse $\pi^{-1}$ 的表示方式。
我們將目光看到 adaptive sorting 的議題。在 adaptive 演算法相關的議題中，其對於複雜度的研究，通常都以 fixed size 及 difficulty 為實例的 worst case，且每個分析對難度的定義各有不同。即使在 comparison model 中，對 n 個元素 permutations 的排序在 worst case 會需要 $O(nlog(n))$ 次的比較，但對於某些參數化的 permutations 類別，可以取得更好的結果。舉 [<The art of computer programming, Volume 3, Sorting and Searching>](https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming) 一書中的內容為例，作者 Knuth 在裡面提及 run (contigious ascending order) 的 permutations $\pi$，並計算 $\mathcal{nRuns} = 1 + |{i: 1 <= i < n, \pi(i + 1) < \pi(i)}|$
另一方面，在 ["Sorting and Searching in Multisets"](https://epubs.siam.org/doi/abs/10.1137/0205001?journalCode=smjcat) 論文中，探討不同排序演算法排序 multisets 的議題，其中有包含 MergeSort 的討論。在他們的討論中，顯示出演算法在對於不同的 multisets 中會有 $O(n(1 + \mathcal{H}(\langle m_{1}, ..., m_{r} \rangle)))$ 的時間複雜度，其中 $m_{i}$ 是 meltisets 中元素 $i$ 的出現次數。
不過，當前對於 comparison model 中的 adaptive sorting 演算法的研究，都會產生一種 permutations 的壓縮方案，但這樣定義的編碼不一定支持在不解壓整個 permutations 的場合下，對於單個元素應用 permutations，或應用其之 inverse permutations。
- [ ] succinct data structures
[succinct data structures](https://en.wikipedia.org/wiki/Succinct_data_structure) 是一種使用空間趨近於 information-theoretic 的下限，但依舊保留高效率的查詢（query）操作的資料結構。換言之，此資料結構的存在是為了知道如何以最少的 bit 數來表示一個資料結構，以及如何在壓縮後的資料進行高效率的查詢操作。
令 $S[1...n]$ 是一個由 alphabet $[1...r]$ 所組成的訊號序列。此序列在 $r = 2$ 的場合（在這裡，alphabet 序列會表示為 {0, 1}，而非 {1, 2}），會出現 bitmap 結構。後續會使用這樣的 succinct $S$ 來表示字串和二進位向量中的 `rank` 以及 `select` 操作：
* $rank_{c}(S, i)$： 給出 $c$ 在 $S[1...i]$ 中的出現次數。
* $select_{c}(S, j)$： 給出 $c$ 在 $S$ 中的第 $j$ 次出現的位置。
更多關於 sussinct data structures 的研究，有興趣的可以前往閱讀 ["Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets"](https://dl.acm.org/doi/10.1145/1290672.1290680)，以及 ["High-Order Entropy-Compressed Text Indexes"](https://dl.acm.org/doi/10.5555/644108.644250)。
- [ ] structure and construction of compressing permutations on contigious monotone runs
在這裡，我們考慮到由少許 monotone runs 所構成的 permutations。
**定義**：permutations $\pi$ 在 [1...r] 的一次 *down-step* 指的是由是一個位置 $1 ≤ i < n$，使得 $\pi(i + 1) < \pi(i)$。另一方面，permutations $\pi$ 裡的 ascending run 指的是不包含任何 *down-step* 的連續位置的最大範圍 $[i...j]$。令 $d_{1}, d_{2}, ..., d_{k}$ 為 permutations $\pi$ 的連續 *down-steps*。那 $\pi$ 的 ascending runs 的數量為 $\mathcal{nRuns} = k + 1$，且代表各 ascending runs 長度的序列為 $\mathcal{vRuns} = \langle n_{1}, n_{2}, ..., n_{\mathcal{nRuns}} \rangle$。其中，$n_{1} = d_{1}$、$n_{2} = d_{2} − d_{1}$、...、$n_{\mathcal{nRuns}−1} = d_{k} − d_{k−1}$、$n_{\mathcal{nRuns}} = n − d_{k}$。（如果 $k = 0$，則 $nRuns = 1$ 且 $vRuns = \langle n_{1} \rangle =\langle n \rangle$。）至於 *up step* 和 descending run 的定義跟以上的描述類似。
Fig. 2 是論文中附的 run-compressed data structure 的事例圖，對象是 permutations $\pi = (8, 9, 1, 4, 5, 6, 7, 2, 3)$ 序列。從**定義**來看的話，Fig. 2 的 $\pi$ 的 $nRuns = 3$、$vRuns = \langle 2, 5, 2 \rangle$。
首先先來講 Fig. 2 資料結構主體。我們考慮 MergeSort 演算法，其合併過程可以表示為高度為 $lgn$ 的平衡二元數。檢測 runs 以及將它們以 pairwise 和 hierarchically 的合併，能使得 MergeSort 針對 $nRuns$ 數量的 runs 適性化。由此，簡化的合併過程表示為高度為 $lg(nRuns)$ 的平衡二元數，且排序時間變為 $O(n + nlog(nRuns))$。除此之外，若每一步皆合併兩個最短的 run，除了可以提升 MergeSort 的效率，也使得其運行時間適應由向量 $vRuns$ 構成的熵：$O(n + \mathcal{H}(vRuns))$。以上的合併操作如果成立的話，就代表 $vRuns$ 的分佈構成一個和 Huffman tree 相同形狀的樹。
因此，如果要構成如 Fig. 2 的樹，要先找到所有 $\pi$ 的 *down-step*，並從求到的 $nRuns$ 推出 $vRuns$，就可以將對 $vRuns$ 的分佈應用 Huffman algorithms，建出一顆有 v 數量的葉節點的 huffman tree。在葉節點中，如 Fig. 2 所示，會存放以下的資訊：
*
- [ ] queries of compressing permutations on contigious monotone runs
- [ ] complexity of the comparisons in comparison model
#### 證明理論一成立
- [ ] complexity of the comparisons in comparison model
這部份要借助 ["On compressing permutations and adaptive sorting"](https://www.sciencedirect.com/science/article/pii/S0304397513007962) 論文中**理論二**的結論。
**特性三**：對於每個只做 pairs of elements 比較的演算法來說，在 class $C$ 中，存在一個需要做至少 $n\mathcal{H} - 3n$ 個元素比較的陣列。
*<證明>*：
在 comparison model 中，要排序 $C$ 中所有的陣列，至少需要 $log_{2}(|C|)$ 元素的比較。因此，以下證明 $log_{2}(|C|) >= n\mathcal{H} - 3n$。
令 $\pi = (\pi_{1}, ..., \pi_{\rho})$ 是集合 ${1, ..., n}$ 的 partition，使得該集合被分解成 $\rho$ 組 subsets，且這些 subsets 的大小為 $r_{1}, ..., r_{\rho}$。若對所有 $i <= {\rho} - 1$，$max{\rho_{i}} > min{\rho_{i+1}}$，我們說 $\pi$ 是 *nice*。讓我們再令 $\mathcal{P}$ 為 partitions $\pi$ 在 ${1, ..., n}$ 的集合，使得對所有 $i <= {\rho}$，$|\pi_{i}| = r_{i}$。並且，令 $\mathcal{N}$ 為 nice partitions 的集合。
接下來，讓我們以以下步驟，將每個 partition $\pi \in \mathcal{P}$ 轉換成 nice partitions。
- [ ] the main loop of the Timsort
- [ ] the starting sequence and ending sequence of Timsort
- [ ] the proof of starting sequence
- [ ] the proof of ending sequence
### Strategies for Stable Merge Sorting
["Strategies for Stable Merge Sorting (2019 v.3)"](https://arxiv.org/pdf/1801.04641) 是一篇和研究 natural merge sort 有關的論文。它除了證明了 Timsort 的 worst case merge cost 的 lower bound（附註：其之 upper bound，以及 Timsort 的複雜度是 $O(nlogn)$ 的證明，可參見 ["On the Worst-Case Complexity of Timsort"](https://arxiv.org/pdf/1805.08612) 論文中）、由 Timsort 延伸出來的其他 natural merge sort 的理論複雜度分析以外，也提出了一個作者自創的 stable natural merge sort 演算法：$2$-merge sort 以及 $\alpha$-merge sort。
在 ["Strategies for Stable Merge Sorting"](https://arxiv.org/pdf/1801.04641)、["On the Worst-Case Complexity of Timsort"](https://arxiv.org/pdf/1805.08612)、以及 ["Adaptive Shivers Sort: An Alternative Sorting Algorithm"](https://arxiv.org/pdf/1809.08411) 中，它們探討 Timsort，以及 natural merge sort 的方式，都只有研究他們的 merge strategies 的複雜度，而忽略 Timsort 中的 min. run 限制、galloping mode 等優化手段。不過，這方面的分析也正好可以呼應目前取來測試的 `timsort_merge.c` 程式碼，以及後續要測試的 Timsort 變體，因為它們當前的實作都是修改 lib/list_sort.c 的 Bottom-up Queue-Mergesort 的機制，而非完整的落實 Tim Peter 當初在 Python list sort 施行的優化策略。
這篇論文中，將其所分析的 natural merge sort 框架定義為以下的虛擬碼：
```
procedure MergeSortFramework(S, n)
R ← list of runs forming S
Q ← empty stack
while R 6 = ∅ or Q has > 1 member do
choose to do either (A) or (Bi) for some ℓ − k2 < i < ℓ, based on
whether R is empty and on the values |Qj | for ℓ − k1 < j ≤ ℓ
(A) Remove the next run R from R and push it onto Q.
This increments ℓ = |Q| by 1.
(Bi) Replace Qi and Qi+1 in Q with Merge(Qi, Qi+1).
This decrements ℓ = |Q| by 1.
end choose
end while
Return Q1 as the sorted version of S.
end procedure
```
其中，
> S is a sequence of integers of length n.
> R is the list of m runs formed from S.
> Q is a stack of ℓ runs, Q1, Q2, . . . , Qℓ. The top member of the stack Q is Qℓ.
> k1 and k2 are fixed (small) integers. The algorithm is (k1, k2)-aware.
> Upon termination, Q contains a single run Q1 which is the sorted version of S.
以上的框架被作者稱為 `(k1, k2)-aware`（`aware` 也有其他人稱之為 `degree`）。這樣稱呼的原因是，在 natural merge sort 中合併已被降解的 run 時，通常會取堆疊中的前 k1 條 run 來比較它們之間的大小，以決定該進行哪項合併；而每次執行合併時，都是取堆疊中的前 k2 條 run 來進行對應的合併。不過，通常來說，k1 和 k2 的值都是一樣的，以 Tim Peter 撰寫的 Timsort 為例，它決定合併的規則是根據堆疊中的頭 3 條 run 來決定的，且合併的 run 也是從堆疊中的頭 3 條 run 取得，因此，也可以稱 k1 = k2 的 natural merge sort 為 `k-aware`。由此架構，我們可以得知，修正過後的 Timsort 是一個 (4, 3)-aware 的 natural merge sort。
這個框架的出現，除了可以得知不同 `aware` 情況下的 natural merge sort 的特性，來自法國的研究者 Vincent Juge 使用此論文的 `(k1, k2)-aware` 架構，證明不同 k 值的 natural merge sort 的 unapproximately bounds 以及 approximately bounds，提供 [approximately optimal sorting algorithms 的證明方法](https://arxiv.org/pdf/1809.08411)。
不過，此證明，包括 "Strategies for Stable Merge Sorting"、和 "Adaptive Shivers Sort: An Alternative Sorting Algorithm" 中對於自己提出的，以及其他的 natural merge sort 演算法的數學分析，都會牽扯到 compressing permutations 對於 adaptive sorting 的影響，這方面的研究可以參見 ["On compressing permutations and adaptive sorting"](https://www.sciencedirect.com/science/article/pii/S0304397513007962) 論文中的討論。
### $\alpha$-merge sort
在論文 ["Strategies for Stable Merge Sorting"](https://arxiv.org/pdf/1801.04641) 中，作者提出了自己的 natural merge sort 演算法，它們稱其為 2-merge sort 以及 $\alpha$-merge sort，其中 $\alpha$ 的值被限定在 $golden ratio < \alpha < 2$ 的範圍中。這些排序演算法是 3-aware 的演算法，也就是其決定合併條件和合併的 run 都位於堆疊的頭 3 項。根據論文描述，此兩個 natural merge sort 相比於 Timsort 有比較好的 worst-case merge cost upper bound，且比 Timsort 要容易實作。
2-merge sort 和 $\alpha$-merge sort 的實作方式都和最早的 Timsort 的設計有相似之處 -- 都是取堆疊中的頭 3 條 run 來決定合併規則。只是，這兩個 natural merge sort 取用的條件有些不同。
首先看到 2-merge sort 的合併規則。假設最堆疊中頭 3 條 run 分別是 $X, Y, Z$，且 $Z$ 為頂部。則
* 若 $len(Y) < 2*len(Z)$ 的場合，且
* $len(X) < len(Z)$：合併 $X, Y$
* 反之：合併 $Y, Z$
另一方面，$\alpha$-merge sort 的合併規則就稍有不同。一樣假設最堆疊中頭 3 條 run 分別是 $X, Y, Z$，且 $Z$ 為頂部。則
* 若 $len(Y) < \alpha x len(Z)$ **或** $len(X) < \alpha * len(Y)$ 的場合，且
* $len(X) < len(Z)$：合併 $X, Y$
* 反之：合併 $Y, Z$
對於這兩個排序演算法，原作者有做了[簡單的實驗](https://github.com/alexanderknop/S4SMS/tree/master)。此實驗主要是比較 $\alpha$-merge sort 和其他資料排序的 normalized merge cost。原作者使用了以下三種資料分佈做實驗：
* The uniform distribution over numbers between 1 and 100,
* The power low distribution over numbers between 1 and 100 with the exponent 0.5 (note that the plots are almost identical),
* A mixture of the uniform distribution over integers between 1 and 100 and the uniform distribution over integers between 10000 and 100000, with mixture weights 0.95 and 0.05. This distribution was specially tailored to work better with 3-aware algorithms while still being formulated in a general way that avoids favoring any particular algorithm.
而在這三組實驗中，$\alpha = 1.62$ 的 $\alpha$-merge sort 的 merge cost 相比於其他的排序，有著較為穩定的上下限。也因此，我決定引入此排序，和 Timsort 的 merge run strategy 以及 lib/list_sort 做效能比較。
[alpha_merge.c](https://github.com/randyuncle/linux2024_final_listsort/blob/master/alpha_merge.c) 是一隻改變 Timsort 的 merge_collapse strategy 的排序程式。改變的方式為以下：
```diff
-if ((n >= 3 &&
- run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
- (n >= 4 && run_size(tp->prev->prev->prev) <=
- run_size(tp->prev->prev) + run_size(tp->prev))) {
- if (run_size(tp->prev->prev) < run_size(tp)) {
- tp->prev = merge_at(priv, cmp, tp->prev);
- } else {
- tp = merge_at(priv, cmp, tp);
- }
+int alpha = 162;
+size_t z = run_size(tp), y = run_size(tp->prev), x = run_size(tp->prev->prev);
+if ((n >= 3) && (y <= ((z * alpha) / 100) || x <= ((y * alpha) / 100))) {
+ if (x < z) {
+ tp->prev = merge_at(priv, cmp, tp->prev);
+ } else {
+ tp = merge_at(priv, cmp, tp);
+ }
```
其他的則維持不變。需要注意的是，Linux 核心不使用浮點數乘法，因此我使用 $((number) * 162) / 100$ 的寫法取代 $(number) \times 1.62$。
### Adaptive Shivers Sort
Adaptive Shivers Sort，是一個結合 Timsort 以及 Shivers Sort 優點的 3-aware natural merge sort。根據作者在[同名論文](https://arxiv.org/pdf/1809.08411)的證明中，雖然此 natural merge sort 演算法的 worst case 複雜度比 Powersort 還要差，但此演算法的 merge_collapse 相比於 Powersort 的來說，是非常容易從 Timsort 轉變到它的實作，且其享有比 Timsort 要好的 worst case 複雜度。
Adaptive Shivers Sort 的 merge_collapse 演算法，跟 $\alpha$-merge sort 一樣，都是取堆疊中的頭 3 條 run 來決定合併規則。假設最堆疊中頭 3 條 run 分別是 $X, Y, Z$，且 $Z$ 為頂部。則
* 若 $h >= 3$，且 $log(X) <= max\{log(Y), log(Z)\}$。將 $X, Y$ 合併。
作者在[同名論文的第六節](https://arxiv.org/pdf/1809.08411)，有說明此 merge_collapse 演算法的實作可以使用 bitwise operation，也就是我在 [shiverssort_merge.c](https://github.com/randyuncle/linux2024_final_listsort/blob/master/shiverssort_merge.c) 所運用的實作方式。此實作方式有參考及借鑒 [yanjiew1](https://github.com/yanjiew1/linux23q1-timsort/blob/main/shiverssort.c) 的成果，使用 `__builtin_clzl` 以及 bitwise operation 實作 Adaptive Shivers Sort 的 merge_collapse 演算法。
```diff
+static inline size_t run_size_cmp(struct list_head *h1, struct list_head *h2)
+{
+ size_t r1 = run_size(h1), r2 = run_size(h2);
+ return __builtin_clzl(r1 | r2);
+}
/* The code in the while loop in merge_collapse() are change to the
* following implementation */
+if (__builtin_clzl(run_size(tp->prev->prev)) < run_size_cmp(tp, tp->prev))
+ break;
+tp->prev = merge_at(priv, cmp, tp->prev);
```
## TODO: 建立資料排序的 Linux kernel module
## TODO: 建立測試程式的 Linux kernel module
1. 建立以數值比較為主的環境測試排序演算法，以呼應在 kernel module 測試
2. 了解亂數產生器並應用進測試中
> 參見 lab0, integration 作業描述
### 開發過程
> [commit 37b6cf3](https://github.com/randyuncle/linux2024_final_listsort/commit/37b6cf3cea45958df0d0c6d6cff5f67767745857)
> 第一版測試版本
[commit 37b6cf3](https://github.com/randyuncle/linux2024_final_listsort/commit/37b6cf3cea45958df0d0c6d6cff5f67767745857) 是第一版的排序測試核心模組。此思路借鑒於我在 lab0-c 作業中所實作的[測試程式](https://github.com/randyuncle/lab0-c/blob/master/sort_test.c)，只是當時的實作是在 user space，而本次是實作於核心模組中。
此測試程式可偵測兩個部份：排序時間、排序的比較次數。排序時間主要以 Linux 核心的計時器 ktime 所獲取 ; 而另一方面，比較次數以排序函式和比較函式中都有的 `priv` 引數，去做函式間的傳送和計數。
目前的實作存在著以下的問題：
1. 當排序到帶有亂數產生器 [xoroshiro128+](https://prng.di.unimi.it/) 生成的亂數的鏈結串列時，就算是使用 lib/list_sort 排序，還是有機會被 `check_list()` 函式判定此排序是失敗的。
2. 當前的實作中，若使該 Linux 核心模組跑稍微長一點的時間（約超過 5 秒），則會將整個主機死機。
第一個問題已於 [commit d289971](https://github.com/randyuncle/linux2024_final_listsort/commit/d289971cf13884341e4ffd509e5284fd6ea6f9fd) 中解決。
> [commit d289971](https://github.com/randyuncle/linux2024_final_listsort/commit/d289971cf13884341e4ffd509e5284fd6ea6f9fd)
> 第二版
在 [commit d289971](https://github.com/randyuncle/linux2024_final_listsort/commit/d289971cf13884341e4ffd509e5284fd6ea6f9fd) 中，最主要的改動是將亂數產生器 xoroshiro128+ 生成的亂數先被一個指定的常數取餘數，最後再賦值給 `int` 資料型態的變數。這個改動可以避免 C 語言整數賦值間的溢位問題。在此改動施行後，沒有出現 `check_list()` 函式判定此排序是失敗的問題。
但是，前一個 commit 中提到的第二個問題依舊存在，也就是此核心模組會使裝置死機，以致於後續的排序測試無法施行。目前還正在尋找造成此問題的來源。
> [commit 9347c93](https://github.com/randyuncle/linux2024_final_listsort/commit/9347c9368220564b69675d3eabea5ef1c63c7208)
> 修復使裝置死機的問題
在 [commit 9347c93](https://github.com/randyuncle/linux2024_final_listsort/commit/9347c9368220564b69675d3eabea5ef1c63c7208) 的修改中，我主要做了以下三個改動：用於 user space 和 kernel space 之間的資料傳輸方式、帶有隨機資料的資料分佈的生成方式，以及使用 kmalloc 獲取核心記憶體的方法。第一個和第三個改動都是為了排查導致程式死機的原因，而第三個改動才正式解決了這個問題。
在 user space 和 kernel space 之間的資料傳輸，我原先是使用兩個特定的 `struct` 去做資料的傳輸和接收：
```c
/* The structure for the device driver from `copy_from_user` */
typedef struct {
size_t nodes;
size_t case_id;
int test_case;
} st_dev;
/* The structure for the user space data from `copy_to_user` */
typedef struct {
unsigned long long int time;
size_t count;
} st_usr;
```
`st_dev` 是一個供 user space 傳送本次排序測試的細節給 kernel space 的結構體，傳送的資料有鏈結串列節點的數量、要做哪個資料分佈的測試、以及要測試的是什麼排序 ; 而 `st_usr` 結構是供 kernel space 傳送本次排序測試的結果給 user space 的結構體，內容包含排序了多長的時間，以及比較次數。
我將此資料傳輸轉換成一個我很熟悉，且[確定是沒問題](https://github.com/randyuncle/My-personal-bachelar-coding-experience/blob/main/Operating%20System/os_2022_hw2-randyuncle-main/My_proc.c)的方式 -- 以 `char` 陣列做為傳送和接收的媒介。
具體的方式是將所有的數值資料先透過各個空間的字串函式輸入到一個已宣告的 `char` 陣列，然後將該陣列傳送出去。接收端則使用相同大小的 `char` 陣列來接收資料，並透過各個空間的字串函式進行字串分割和將字串轉換為數值的工作，最後再根據格式進行分類和使用。以下的程式碼及為上述描述的示例：
```c
/* For user space program */
char buf_write[512];
sprintf(buf_write, "%d %d %d", num, case_id, sort_id);
/* write the properties of the current test case to device driver */
ssize_t w_sz = write(fd, buf_write, 512);
...
char buf_read[512];
/* read the output of the test from device driver */
ssize_t r_sz = read(fd, &buf_read, 512);
```
```c
/* For kernel space program */
char device_buf[512];
snprintf(device_buf, 512, "%llu %lu", kt_sort, count);
unsigned long len = copy_to_user(buf, device_buf, 512);
...
char device_buf[512];
unsigned long len = copy_from_user(device_buf, buf, size);
```
使用此方式後依舊會使得裝置死機。
但是，在某一次再度使用此測試程式後，在裝置死機的同時，得到了來自函式 `worst_case_generator()` 的 `segmentation fault` 的結果。由此，我推斷有可能是我的 `kmalloc()` 的使用方式有問題。
原本的核心模組實作中，我在對鏈結串列結構體 `element_t` 的空間求取和我在 user space 的實作中做了一樣的事情：一次求取固定節點數量的 `element_t` 結構體。
```diff
- element_t *samples = kmalloc(nodes * sizeof(element_t *), GFP_KERNEL);
```
我將實作方式轉換成：一次只求取一個結構體的空間。
```diff
+ element_t *sample = kmalloc(sizeof(element_t), GFP_KERNEL);
```
在使用新的實作方式後，kernel device 的啟動使得裝置死機的問題就解決了。也因此，我也將 copy_list() 函式所要複製的 `element_t` 結構體也以同樣的方式做生成，以避免裝置死機。
最後，關於帶有隨機資料的資料分佈的生成方式的改動，目的是要脫離為了定義隨機資料生成的節點位置所使用的 `int exch[MAX_LEN]` 陣列，減少核心模組所會使用到的額外記憶體空間。
```diff
- int exch[MAX_LEN] = {0};
- memset(exch, 0, sizeof(exch));
+ int random_section, random_index, random_count;
+ int dup[4];
```
`random_section` 變數是用來儲存需要每多少筆資料，才生成一個隨機資料 ; `random_index` 變數則是用來儲存在當下的資料區間中，第幾個資料需要被替換為隨機資料 ; 最後，`random_count` 是紀錄此資料分佈的生成共需要多少個資料室隨機資料。除此之外，由於我原本的實作中，在多種重複資料分佈的部份，會使用 `int exch[MAX_LEN]` 陣列儲存需要生成的重複資料，因此我額外宣告了 `int dup[4]` 陣列作為代替。
### `sort_test`: Linux kernel device driver for sort performance test
[sort_test_kernel.c](https://github.com/randyuncle/linux2024_final_listsort/blob/master/sort_test_kernel.c) 是一個我撰寫用來測試 merge sort 或 merge sort like 的鏈結串列排序的核心模組。其主要測試排序程式的兩個方面：
1. 排序各個指定資料分佈所需要的時間。
* 排序時間的量測和求取使用的是 Linux 核心的 `ktime_t`，以此來獲得小至 us 單位的高精度運行時間。
2. 每輪排序所需要的比較次數。
* 使用排序函式以及比較函式的 `void* priv` 引數來傳遞和紀錄每次進入比較函式的比較次數。需要注意的是，若兩個節點的數值是相同的，則不計入比較次數的計算中。
之所以選擇在 LKM 中測試排序程式，不僅因為能夠獲得每輪排序所需的高精度時間，還因為 LKM 可以通過以下方式避免 preemption 和中斷，使排序測試結果更具說服力。
```c
local_irq_disable();
get_cpu();
...
local_irq_enable();
put_cpu();
```
在 sort_test_kernel.c 被編譯後，會被編譯出 sort_test.ko 檔案。將其掛載進核心後，會在系統的 `/dev` 檔案目錄中，出現 `sort_test` device driver，以供後續來自 user space 的操作可以對該模組做讀寫，以及驅動 `sort_test` 開始測試排序程式。
### `client`: User space program for defining the formation of tests
[client.c](https://github.com/randyuncle/linux2024_final_listsort/blob/master/client.c) 是一個用來處理排序測試內容的 user space 程式。這支程式提供兩種測試：連續數量節點測試（`./client continuous`）、和單一節點個數測試（`./client single <int. number>`）。
在連續數量節點測試中，程式會測試並量測指定排序程式在 4 ~ 2^14^ + 10 個節點的鏈結串列之中的排序所需時間和比較次數，並計算該排序程式在每個節點的 k 值。需要注意的是，每一個節點數目會和每組資料分佈分別重複排序 100 次，且每次的結果都會紀錄並輸出到指定的檔案中，供後續做 gnuplot，或進行數據分析。另一方面，單一節點個數測試則會要求使用者輸入一個正整數，測試程式會針對該正整數和每組資料分佈分別做 100 次的重複排序。
在此程式中的 k 值計算，主要是參考 [kdnvt](https://hackmd.io/byNYeoGvQv-a9TNDc2CKFQ?view#comparison-%E6%AC%A1%E6%95%B8) 的方法。在此篇筆記中，作者參閱了 ["Bottom-up Mergesort: A Detailed Analysis"](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5260)，藉由裡面對於比較次數和排序序列的元素數量的關係，了解其中 K 值的意義，並以此關係寫出計算 average k 值的程式碼。不過，在本次的測試中，我沒有要計算 average k 值，因此只將 k 值的計算引入進測試程式之中。本次加入 k 值運算有一個好處 -- **能夠精確地觀察到每個節點數所對應的比較次數週期，以及比較的穩定性。**
### 實驗的資料分佈
實驗的資料分佈類型參考自 cpython 中，由 Tim Peter 撰寫的 [listsort.txt](https://github.com/python/cpython/blob/24e5ad4689de9adc8e4a7d8c08fe400dcea668e6/Objects/listsort.txt) 裡所做的測試類型。部份的資料分佈實作也參考 cpython 中的[`Tools/scripts/sortperf.py`](https://github.com/python/cpython/blob/0c7dc494f2a32494f8971a236ba59c0c35f48d94/Tools/scripts/sortperf.py#L10) 程式。
以下是本次實驗會用到的資料分佈：
* Worst case scenario for merge sort（file prefix：w）
* 關於本程式中所使用的 Worst case scenario for merge sort 可以參見 [lab0-c 針對生成 worst case scenario](https://hackmd.io/jX0N-0D4S_yxXipGlRRBIg?view#%E6%A7%8B%E9%80%A0%E6%B3%95%E4%B8%80) 的討論。雖然此頁面主要討論生成字串內容的資料分佈，但該演算法所需的排序比較次數對每個節點數來說都是相同的。因此，可以參考此頁面中關於不同生成方法在排序時所需比較次數的討論。
* 升冪資料，隨機 3 個資料換成隨機資料（file prefix：r3）
* 升冪資料，最後 10 個資料換成隨機資料（file prefix：rl10）
* 升冪資料，隨機 1% 個資料換成隨機資料（file prefix：r1p）
* 有多個重複的資料（file prefix：dup）
* 以 `int dup[4]` 陣列儲存指定的 4 個數值，接著使用 xoroshiro128+ 亂數產生器，以 `next() % 4` 的方式隨機決定每個節點存放的數值。
* 完全隨機的資料（file prefix：r）
### 使用的亂數產生器 (To be modified)
我於本次的實驗中，使用的是 [xoroshiro128+](https://arxiv.org/pdf/1805.01407) 亂數產生器，來產生帶有亂數的資料分佈的亂數資料內容和該亂數該取代的位置。
#### xoroshiro128+
- [ ] xoroshiro
- [ ] `+` scrambler
#### 和 `/dev/random` 及 `/dev/urandom` 的比較 (To be modified)
這裡的 xoroshiro128+ 亂數產生器取用本課程第六次作業 ksort 的 [`xoro_mod.c`](https://github.com/sysprog21/ksort/blob/master/test_xoro.c) 所生成的 `dev/xoro` 核心模組，做為和 `/dev/random` 及 `/dev/urandom` 比較的對象。（本測試有把 `xoro_mod.c` 中非輸出錯誤資訊的 printk() 註解化，以免把 root file system 的 `/var/log` 塞滿）
- [ ] `diehard`
* `/dev/random`
* `/dev/urandom`
* `/dev/xoro`
- [ ] 亂數生成時間
### 實驗方式及結果
#### 實驗方式
藉由[本課程作業 6 的作業描述](https://hackmd.io/@sysprog/linux2024-integration/%2F%40sysprog%2Flinux2024-integration-a#%E6%8E%92%E9%99%A4%E5%B9%B2%E6%93%BE%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E5%9B%A0%E7%B4%A0)，先進行以下步驟，排除干擾效能分析的因素：
* 抑制 address space layout randomization (ASLR)
```
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
* 設定 scaling_governor 為 performance。準備以下 shell script，檔名為 `performance.sh`:
```
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > ${i}
done
```
之後再用 `$ sudo sh performance.sh` 執行
* 針對 Intel 處理器，關閉 turbo mode
```
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
* 關閉 SMT
```
$ sudo sh -c "echo off > /sys/devices/system/cpu/smt/control"
```
將所需要測試的排序函式及名字加入 [sort_test_kernel.c 的 test[] 陣列中](https://github.com/randyuncle/linux2024_final_listsort/blob/master/sort_test_kernel.c#L206)，以及將對應的輸出 directory 名稱加入 [client.c 的 dir[] 陣列中](https://github.com/randyuncle/linux2024_final_listsort/blob/master/client.c#L34)。
在 Linux terminal 中輸入 `make all`，將程式都編譯。
完成後，再輸入 `make load`，將編譯出來的 `sort_test.ko` 掛載進 Linux device 中。
由於我目前所做的實驗都是連續節點個數的排序測試，因此，輸入 `sudo ./client continuous`，即可開始測試排序程式。
#### 連續節點個數排序測試
此項測試目前只測了 lib/list_sort，以及只改變 lib/list_sort 的 Bottom-up merge policy 的 Timsort、Adaptive Shivers Sort、以及 $\alpha$-merge sort。其中，$\alpha$-merge sort 設定常數 $\alpha = 1.62$，也就是原作者和其他排序演算法比較所設定的值。
> 圖示：
> 綠色 - lib/list_sort.c 的結果
> 紫色 - Timsort、Adaptive Shivers Sort、以及 $\alpha$-merge sort 的結果
- [ ] Worst case scenario for merge sort
* Number of Comparison:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* K value:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* Time (us):
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
- [ ] 升冪資料，隨機 3 個資料換成隨機資料
* Number of Comparison:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* K value:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* Time (us):
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
- [ ] 升冪資料，最後 10 個資料換成隨機資料
* Number of Comparison:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* K value:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* Time (us):
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
- [ ] 升冪資料，隨機 1% 個資料換成隨機資料
* Number of Comparison:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* K value:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* Time (us):
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
- [ ] 有多個重複的資料
* Number of Comparison:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* K value:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* Time (us):
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
- [ ] 完全隨機的資料
* Number of Comparison:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* K value:
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
* Time (us):
| lib/list_sort v.s. timsort | lib/list_sort v.s. Adaptive Shivers Sort | lib/list_sort v.s. $\alpha$-merge sort|
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
#### binary insertion sort 和 linear insertion sort
這個項目，主要是比較小型資料長度（<= 32 個節點）的 binary insertion sort，以及 linear insertion sort 之間的效能差距，以 `timsort_binary.c` 和 `timsort_linear.c` 的排序結果為比較的基準。其中，此項不會做「多個重複的資料」以及「完全隨機的資料」兩種資料不的實驗，因為這兩隻排序程式，無法保證同樣資料內容但不同節點於排序前後的順序是相同的。
> 圖示：
> 綠色 - `timsort_linear.c` 的結果
> 紫色 - `timsort_binary.c` 的結果
- [ ] Worst case scenario for merge sort
| Number of Comparison | K value | Time (us) |
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
- [ ] 升冪資料，隨機 3 個資料換成隨機資料
| Number of Comparison | K value | Time (us) |
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
- [ ] 升冪資料，最後 10 個資料換成隨機資料
| Number of Comparison | K value | Time (us) |
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
- [ ] 升冪資料，隨機 1% 個資料換成隨機資料
| Number of Comparison | K value | Time (us) |
| -------------------------- | ---------------------------------------- | ---------------------------------------- |
||||
### 實驗結論
#### 連續節點個數排序測試
從上面的分佈圖來看，在 worst case of merge sort 中，雖然在 Timsort 及其延伸變形的比較次數都比 lib/list_sort.c 多，但是在運行時間的部份，Adaptive Shivers Sort 以及 $\alpha$-merge sort 的排序時間都和 lib/list_sort 相差無幾，甚至 $\alpha$-merge sort 有機會比 lib/list_sort.c 的排序要快。
接下來看到帶有部份隨機資料的升冪資料的測試項目，基本上，Timsort 及其變形的排序，不管在比較次數或排序時間上，都比 lib/list_sort.c 都要少，顯示出 Timsort 及其變形的排序的在部份以排序資料的資料分佈中的優勢。
不過，當我們看到有多種重複資料的排序時，除了 Timsort 及其變形在比較次數沒有比 lib/list_sort.c 要少以外，在排序時間的部份，可以發現到除了 Adaptive Shivers Sort 以外，Timsort 及 $\alpha$-merge sort 都沒有比 lib/list_sort.c 快，或和 lib/list_sort.c 相當。這現象也可以在完全隨機資料分佈的分佈圖中發現。Timsort 及其變形無法在比較次數上比肩 lib/list_sort.c，且在排序時間中，除了 Adaptive Shivers Sort 以外，Timsort 及 $\alpha$-merge sort 都比 lib/list_sort.c 要慢。
所以，從以上的實驗中，顯示出 Adaptive Shivers Sort 在 Timsort 及其延伸的排序中，在我測試的這幾種資料分佈裡，雖然說在它不擅長的資料分佈裡的比較次數不及 lib/list_sort.c，但其運行時間最差是可以作到和 lib/list_sort.c 比肩的程度。因此，如果要改善 Linux 核心的 lib/list_sort.c，Adaptive Shivers Sort 是一個可以考慮的排序演算法實作。
#### binary insertion sort 和 linear insertion sort
在 worst case of merge sort 中，雖然帶有 binary insertion sort 的 Timsort 的比較次數比帶有 linear insertion sort 的 Timsort 的次數要少，但是如果看到運行時間的部份，linear insertion sort 明顯比 binary insertion sort 要快。
不過，當我們看到帶有隨機資料的升冪資料分佈中，有 binary insertion sort 的 Timsort 的排序速度要比帶有 linear insertion sort 的 Timsort 還要快，而且從分佈圖來看，這是非常明顯就可發覺到的現象。
所以，鏈結串列中的 Timsort min. run strategy 實作，在帶有隨機資料的資料分佈中，binary insertion sort 明顯的比 linear insertion sort 要好；但是在 worst case of merge sort 的資料分佈，linear insertion sort 就比 binary insertion sort 要好。
## 了解統計分析方法
> 參見 lab0-c 作業描述
Sign in with Wallet
Connect another wallet