# Linux 核心專題: `lib/sort.c`
> 執行人: kart81604
> [專題解說錄影](https://youtu.be/ECGinZ1t5U4)
## 任務描述
解釋 Linux 核心的 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 現有的 bottom-up heap sort 實作，並尋求效能改進，例如 hybrid sort 的引入。
參照 [2021 年作業: sort](https://hackmd.io/@sysprog/linux2021-sort) 及對應[學員成果](https://hackmd.io/@sysprog/linux2021-homework5)。
## TODO: 解釋現有 Linux 核心的 `lib/sort.c` 的實作
參見 [Bottom-up Heapsort](https://hackmd.io/@Uduru0522/bottomup-heapsort-analyze)，對照 git log 提及的論文，解釋其原理，包含數學推導。藉由 perf 一類的效能分析工具，探討 Linux 核心 `lib/sort.c` 實作的效益。
### 〈[BOTTOM-UP-HEAPSORT](https://www.sciencedirect.com/science/article/pii/030439759390364Y)〉論文研讀
先來複習資料結構學到的 heap sort ，利用 [heap](https://en.wikipedia.org/wiki/Heap_(data_structure)) 的性質，資料量為 n 的陣列 `a`，先將此陣列利用 **reheap** (部分資料結構參考書將此稱為 `heapify` ) 調整為符合 min-heap (此論文都以 min-heap 來討論) 結構，再將 $a[1]$ 的值跟 $a[n]$ 交換，再對 $a[1]$ ~ $a[n-1]$ 進行 **reheap**。(論文內陣列從 $a[1]$ 開始存值，而不是 $a[0]$)
:::info
***HEAPSORT(a)***
1) /* heap creation phase */
2) for ( **i** from **$\lfloor \frac{n}{2} \rfloor$** downto **1** ) begin
3)  ***reheap*** **(n, i)**
4) end
6) /* select phase */
7) for ( **m** from **n** downto **2** ) begin
8)  **interchange** **a[1]** and **a[m]**
9)  if **m** $\neq$ 2 then ***reheap*** **(m - 1, 1)**
10) end
:::
:::info
***reheap(m, i)***
1) if (**i** > **$\frac{m}{2}$**) exit
2) if (**i** < **$\frac{m}{2}$**) **MIN** = min( **a[i]**, **a[2 * i]**, **a[2 * i + 1]** ) with 2 comparisons
3) if (**i** = **$\frac{m}{2}$**) **MIN** = min( **a[i]**, **a[2 * i]** ) with 1 comparison
4) if ( **MIN** = **a[i]** ) exit
5) else if ( **MIN** = **a[2 * i]** ) begin
6)  **interchange** **a[i]** and **a[2 * i]**
7)  ***reheap*** **(m, 2 * i)**
8) end
9) else if ( **MIN** = **a[2 * i + 1]** ) begin
10)  **interchange** **a[i]** and **a[2 * i + 1]**
11)  ***reheap*** **(m, 2 * i + 1)**
12) end
:::
在進行 **reheap** 時，第一個參數 $m$，總是會放該陣列的最後一筆資料，因 heap 為 complete binary tree ，因此 $a[\frac{m}{2}]$ 指的是 $a[m]$ 的 parent 。找出 `i` 以及 `i` 的 child 之中最小的為 `MIN` ，如果 `MIN` 就是 $a[i]$ ，則終止，反之將最小的那 index 設為新 `i` ，重複這個做法，直到第 1 行或是第 5 行的中止條件成立。是由上而下的進行 interchange ，來將樹調整成 min-heap 。
考慮 heap 高度為 d (root 所在的高度為 0)，上述的 **reheap** 最多會執行 $2 \times d$ 次的 comparisons ，以及 d 次的 interchange ，然而，因為在執行 **heap-sort** 時，每一輪會把 heap 中最後一個值 $a[m]$ (考慮儲存最後一個值的 index 為 $m$) 放到 root ，在進行 **reheap** 會將 $a[m]$ 放置合適的位置，但這個位置會傾向靠近於 leaves，因此論文提到一個新的方法來找出代替 reheap 找出合適的位置，且有較少的 comparison 次數以及 interchange 次數。
搭配圖片解說，以下方的 heap 作為示範。($n = 13$，$n$ 為資料量)，原文演算法的描述排版會做點修改，但執行順序以及方式不會做改變。
:::danger
:warning: 陣列初始位置的 index 為 $1$ 而非 $0$
:::
```graphviz
graph heap{
4 -- 7 4 -- 8
7 -- 23 7 -- 21
8 -- 14 8 -- 10
23 -- 31 23 -- 29
21 -- 24 21 -- 25
14 -- 15 14 -- 17
}
```
因為要討論的 **reheap** 的執行方式，那我們就要先進行第一次的 **heapsort** ，也就是將最後一個位置的值與 root 的值交換，接著要對這棵樹進行 **reheap** 。(不會動到已排序好的值，此例為從 root 移到最後一個位置的 4)
```graphviz
graph heap1{
17 -- 7 17 -- 8
7 -- 23 7 -- 21
8 -- 14 8 -- 10
23 -- 31 23 -- 29
21 -- 24 21 -- 25
14 -- 15
sorted[label = 4, color = gray]
14 -- sorted
}
```
首先是 **leaf-search**，目的是要找出 **special leaf** ， **special leaf** 為從 root 開始，找出目前節點中的 childs 較小的那個，再指向該點，直到指到最後一層，也就是這個 heap 的 leaf ，該點就是 **special leaf** 。
:::info
***leaf-search(m, i)***
1) **j = i**
2) while ( **2 * j < m** ) begin
3)  if ( **a[2 * j]** < **a[2 * j + 1]** ) **j = 2 * j**
4)  else **j = 2 * j + 1**
5) end
6) if ( **2 * j = m** ) **j = m**
7) return **j**
:::
橘色節點的 $24$ 為 **special leaf** ，而走訪的路徑(紅色節點的部分與橘色節點)為 **special path** 。
下圖執行 ***leaf-search(12, 1)*** 會回傳 $10$，其為 **special leaf** 的 index 。
```graphviz
graph heap2{
17[label = 17, color = red]
17 -- 7 17 -- 8
7[label = 7, color = red]
7 -- 23
21[label = 21, color = red]
7 -- 21
8 -- 14 8 -- 10
23 -- 31 23 -- 29
24[label = 24, color = orange]
21 -- 24 21 -- 25
14 -- 15
sorted[label = 4, color = gray]
14 -- sorted
}
```
**bottom-up-search** 為找出應該放 $a[m]$ 的合適位置。
透過 **leaf-search** 找出 special leaf ，再由這個 leaf ，再拿 $a[m]$ 從這點往上比較，找出適合放入的位置，該位置稱為 **special object**。
:::info
***bottom-up-search(i, j)***
/* **j** is the output of ***leaf-search(m, i)*** */
1) while ( **a[i] < a[j]** ) **j = $\lfloor \frac{j}{2} \rfloor$**
2) return **j**
:::
從 **special leaf** 往上找，直到找到比 root 還要小的值。(紫色節點)
下圖執行 ***bottom-up-search(1 , 10)*** 會回傳 $2$，其為 `reheap` 後， root 要換過去的位置。
```graphviz
graph heap3{
7[label = 7, color = purple]
17 -- 7 17 -- 8
7 -- 23 7 -- 21
8 -- 14 8 -- 10
23 -- 31 23 -- 29
24[label = 24, color = orange]
21 -- 24 21 -- 25
14 -- 15
sorted[label = 4, color = gray]
14 -- sorted
}
```
**interchange-1** 為 root 移至指定位置，且 root 到指定位置上的節點往上移動。
:::info
***interchange-1(i, j)***
/* **j** is the output of ***bottom-up-search(i, j)*** */
1) **l** = **$\lfloor log(\frac{j}{i}) \rfloor$**
2) **x** = **a[i]**
3) for ( **k** from **l - 1** downto **0** ) **a[$\lfloor\frac{j}{2^{k+1}}\rfloor$] = a[$\lfloor \frac{j}{2^k} \rfloor$]**
4) **a[j]** = **x**
:::
下圖為執行 ***interchange-1(1, 2)*** 後的結果，滿足 heap 的性質。(不考慮最後一個已排序的節點)
(root 移至 $a[2]$，原本 $a[2]$ 的值往其親代節點移動，因此移到 root)
```graphviz
graph heap4{
17[label = 17, color = purple]
7 -- 17 7 -- 8
17 -- 23 17 -- 21
8 -- 14 8 -- 10
23 -- 31 23 -- 29
24[label = 24, color = orange]
21 -- 24 21 -- 25
14 -- 15
sorted[label = 4, color = gray]
14 -- sorted
}
```
因此原本的 **reheap** 可以被修改成 bottom-up 形式，為
:::info
***bottom-up-reheap(m, i)***
1) **j** = **leaf-search(m, i)**
2) **j** = **bottom-up-search(i, j)**
3) **interchange-1(i, j)**
:::
考慮任一個值任意排序的陣列(每個值都相異)，對其做 **HEAPSORT** ，首先要先將陣列調整為 heap，需要做 **reheap($n, \lfloor \frac{n}{2} \rfloor$)**, **reheap($n, \lfloor \frac{n}{2} \rfloor-1$)**, ..., **reheap($n, 1$)**，因上述透過 bottom-up的方式改良，因此上述函式會呼叫 **leaf-search($n, \lfloor \frac{n}{2} \rfloor$)**、**leaf-search($n, \lfloor \frac{n}{2} \rfloor-1$)**、...、**leaf-search($n, 1$)**，而這些 **leaf-search** 最少會執行 $n - \lceil \log{(n+1)} \rceil - \lceil \log{(n)} \rceil + 1$ 次 comparisons，最多會執行 $n - 2$ 次 comparisons。(論文中的 lemma 4.1)
:::spoiler 證明(點我展開)
先考慮 $n = 2^{k}-1$ 的情況，也就是 full binary tree (共 $k$ 層，第 $0$ 層至第 $k-1$ 層)，第 $0$ 層的節點 (root) 要找到 **special leaf** 要進行 $k - 1$ 次的 comparisons，第 $1$ 層則是 $k - 2$ 次的 comparisons，第 $k - 2$ 層則是 $1$ 次，因為第 $i$ 層有 $2^i$ 個節點，因此總共會進行
$$
\begin{split}\sum_{i = 0}^{k-2}2^i(k-1-i) & = 2^0(k-1)+2^1(k-2)+...+2^{k-2}(1) \\ & =(2^0+2^1+...+2^{k-2})+(2^0+2^1+...+2^{k-3})+...+(2^0+2^1)+2^0 \\ & =(2^{k-1}-1)+(2^{k-2}-1)+...+(2^2-1)+(2^1-1) \\ & = (2^{k-1}+2^{k-2}+...+2^1)-(k-1)\times 1 \\ & = (2^{k-1}+2^{k-2}+...+2^1+2^0)-2^0-(k-1)\times 1 \\ & =(2^k-1)-k \\ & =n - \lceil\log{(n+1)} \rceil
\end{split}
$$
次的 comparisons。
接著考慮不為 full binary tree 的情況，在第 $k$ 層加入 $i$ 個節點。 $i$ 為偶數，才會增加 worst-case 下 comparison 次數，也就是說 $i=0$ 與 $i=1$ 在 worst-case 增加comparison 次數是一樣的，$i=2$ 與 $i=3$ 在 worst-case 增加的 comparison次數是一樣的，...，以此類推，在第 $k$ 層增加 $i$ 個節點，會影響第 $k-1$ 層中的前 $\lceil\frac{(i-1)}{2}\rceil$ 個節點，在 worst-case 下，他們會多做一次的 comparison，而第 $k-2$ 層中前 $\lceil\frac{(i-1)}{2^2}\rceil$ 個節點也要多做一次的 comparison，...，第 $0$ 層則會有 $\lceil\frac{i-1}{2^{k}}\rceil$ 個節點要多做一次 comparison ，因此共要多做 $\begin{split}\sum_{j=1}^{k}\lceil\frac{(i-1)}{2^j} \rceil\end{split}$ 次。
$\begin{split}\sum_{j=1}^{k}\lceil\frac{(i-1)}{2^j} \rceil\end{split}$ 的 upper bound 為 $i-2+k$，證明如下:
$$
\begin{split}\sum_{j=1}^{k}\lceil\frac{(i-1)}{2^j} \rceil & = \sum_{j=1}^{k}\frac{(i-1)}{2^j}+(\sum_{j=1}^{k}\lceil\frac{(i-1)}{2^j} \rceil-\sum_{j=1}^{k}\frac{(i-1)}{2^j})\\ &\leq(i-1)(1-\frac{1}{2^k})+\sum_{j=1}^{k}(1-\frac{1}{2^j}) \\ & =i-1-\frac{i}{2^k}+\frac{1}{2^k}+k-(1-\frac{1}{2^k})\\ & =i-2+k+\frac{2-i}{2^k}\\ & \leq i-2+k \ \ \ (\text{for}\ i \geq 2)
\end{split}
$$
因為 $i<2$ 不會增加 comparison 次數，所以只考慮 $i\geq 2$ 的情況。
因此對於非 full binary tree 來說， worst-case 下，comparison 最多會做
$\begin{split}\underbrace{(2^k-1-k)}_{\text{full binary tree}}+(i-2+k) &= (2^k-1+i)-2 =n-2 \ 次。\end{split}$
對於非 full binary tree 的 best-case ，就是 root 到第 $n$ 個節點的路徑上的所有點，在進行 comparison 時，都指向右子節點，遠離第 $n$ 個節點，這樣這些點進行 **leaf-search** 都會少一個 comparison ，而這路徑上的點(不包含 leaf)共有 $\lceil\log n\rceil-1$ 個，因此 best-case 下，comparison的次數至少會是
$n-\lceil\log(n+1)\rceil-(\lceil\log n\rceil - 1)=n-\lceil\log(n+1)\rceil-\lceil\log n\rceil + 1$ 次。
best-case 發生在 $n = 2$。
:::
\
雖然分析出 best-case 與 worst-case 情況下的 comparison 次數，但實際上在調整至 heap 的過程，不管是在 best-case 還是 worst-case ，comparison 次數其實是差不多的，平均 comparison 次數就還是以 $n+\Theta(\log n)$ 考慮。
接著來討論 **bottom-up-search** 在陣列調整至 heap 時的執行次數，考慮透過 **leaf-search** 時找出的 **special path** ，將這個 path(不包含 root ) 用 $b(1),b(2),...b(d)$ 表示，$b(0) = -\infty,b(d+1) = \infty$ ， $x$ 為要執行 **reheap** 的 root， 目的就是要找出滿足 $b(j)<x<b(j+1)$ 的 $j$，接著 **HEAPSORT** 以及 **bottom-up-search** 的 comparison 次數為以下表格。
| | $j<d$ | $j=d$ |
|:--------------------:| :------: |:-----:|
| **HEAPSORT** | $2(j+1)$ | $2d$ |
| **bottom-up-search** | $d-j+1$ | $d$ |
:::info
**HEAPSORT** 每一層在做 comparison 時，會做 $2$ 次比較，因此要乘上 $2$ 。
:::
用 $l_{\text{HS}}$ 表示 **HEAPSORT** 的 comparison 次數的==一半==，以及 $l_{\text{BUS}}$ 表示 **bottom-up-search** 的 comparison 次數。
再藉由上述表格，可以得到以下結論 :
| | $l_{\text{HS}}+l_{\text{BUS}}$ |
|:---------------------:|:------------------------------:|
| $0<j<d$ | $d+2$ |
| $j=0 \text{ or } j=d$ | $d+1$ |
接著透過〈[An average case analysis of Floyd’s algorithm to construct heaps](https://www.sciencedirect.com/science/article/pii/S0019995884800534)〉的結論，**HEAPSORT** 平均 comparison 次數為 $(\alpha_1+2\alpha_2-2)n+\Theta(\log n)$ 次，以及平均 interchange 次數為 $(\alpha_1+\alpha_2-2)n+\Theta(\log n)$ 次，其中 $\alpha_1=1.6066951...,\alpha_2=1.1373387...,$
$\alpha_i$ 的公式為 $\begin{split}\alpha_i=\sum_{j=1}^{\infty}(2^j-1)^{-i}\end{split}$ 。(論文中的 Thm 4.2)
因為在調整 heap 的過程中， **bottom-up-reheap** 會呼叫 $\lfloor\frac{n}{2}\rfloor$ 次，因此其中的 **bottom-up-search** 也同樣會執行 $\lfloor\frac{n}{2}\rfloor$ 次，以 $L_{\text{BUS}},L_{\text{HS}},D$ 作為隨機變數，分別代表的是 $l_{\text{BUS}},l_{\text{HS}},d$ 的總和，目標是要求出 $E(L_{\text{BUS}})$ ，也就是在調整至 heap 的過程，執行 **bottom-up-search** 的次數的期望值。
藉由上述的 lemma 4.1 跟 Thm 4.2 ，可以得出
$$
E(D)=n+\Theta(\log n)、E(L_{\text{HS}})=(\alpha_1/2+\alpha_2-1)n+\Theta(\log n)
$$
用 $T$ 來表示呼叫 **bottom-up-search** 且 $l_{\text{HS}}+l_{\text{BUS}}=d+1$ 的次數，則 $\lfloor\frac{n}{2}\rfloor-T$ 則為呼叫 **bottom-up-search** 且 $l_{\text{HS}}+l_{\text{BUS}}=d+2$ 的次數。
因此
$$
\begin{split}
E(L_{\text{BUS}}) &= E(T)\cdot(E(d)+1-E({l_{\text{HS}}}))+(\lfloor\frac{n}{2}\rfloor-E(T))\cdot(E(d)+2-E(l_{\text{HS}})) \\ &=\lfloor\frac{n}{2}\rfloor E(d)+2\lfloor\frac{n}{2}\rfloor-\lfloor\frac{n}{2}\rfloor E(l_{\text{HS}})-E(T) \\ &=E(D)+2\lfloor\frac{n}{2}\rfloor-E(L_{\text{HS}})-E(T) \\ &=n+2\lfloor\frac{n}{2}\rfloor-(\alpha_1/2+\alpha_2-1)n-E(T)+\Theta(\log n) \\ &=(3-\alpha_1/2-\alpha_2)n-E(T)+\Theta(\log n)
\end{split}
$$
處理 $E(L_{\text{BUS}})$ 中的 $E(T)$，考慮 $j=0$ 的情況，也就是 **special object** 恰巧就為該子樹的 root ，如果該子樹有 r 個節點，則發生 $j=0$ 的機率為 $\frac{1}{j}$，考慮 full binary tree ，總高度為 $h$ ，在允許 $\Theta(\log n)$ 的誤差，第 $0$ 層有 $1$ 個子樹且該樹的節點為 $n$ 個，第 $1$ 層有 $2$ 個子樹且該樹的節點大致為 $\frac{n}{2}$ 個，...，第 $h-2$ 層有 $2^{h-2}$ 個子樹且該樹節點大致為 $\frac{2}{2^{h-2}}$，因此 $j=0$ 的狀況發生在各個非 leaf 的節點上的機率為
$$
\begin{split}
\beta=\sum_{h=2}^{\infty}[2^h(2^h-1)]^{-1} = 0.1066952
\end{split}
$$
因此發生在 $j=0$ 的情況下的期望值為 $\beta n+\Theta(\log n)$ 。
接著是 $j=d$ 的情況，在處理前，先說明一個等式，$c$ 為在執行 **reheap** 時的 comparison 次數，$i$ 為 interchange 次數，$s$ 為 **special object** 的子代節點的個數，則以下等式成立 :
$c=2\times i+s$
考慮 $C、I、S$ 分別為 $c、i、s$ 在調整 heap 的總和，由上述等式可得 :
$$
E(C)=2\times E(I)+E(S) \Rightarrow E(S)=E(C)-2\times E(I)
$$
因為二元樹的關係，$s$ 只有三個可能性，也就是 $s\in \{0,1,2\}$，$s=1$ 的情況，也就是 **special object** 為第 $\frac{n}{2}$ 個節點，且 $n$ 為偶數，這情況最多只會發生 $\log n$ 次( root 到最後一個節點這路徑上的節點才有可能會發生)，當 $n$ 很大時， $s=1$ 發生次數少到可以不用考慮，所以我們可以改成 $s\in \{0,2\}$，設 $p_{s=0}、p_{s=2}$ 分別為 $s=0, s=2$ 發生的機率，可得
$$
\begin{align}
&E(s)=0\times p_{s=0}+2\times p_{s=2}\\
\Rightarrow &E(s)=2\times p_{s=2}\\
\Rightarrow &\lfloor\frac{n}{2}\rfloor E(s)=\lfloor\frac{n}{2}\rfloor\times 2\times p_{s=2} \\
\Rightarrow &E(S)=\lfloor\frac{n}{2}\rfloor\times 2\times p_{s=2}\\
\Rightarrow &p_{s=2}=(E(S)/\lfloor\frac{n}{2}\rfloor)/2=2-\alpha_1+\Theta(n^{-1}\log n)
\end{align}
$$
則 $s=0$ 就能求出， $p_{s=0}=1-p_{s=2}=\alpha_1-1+\Theta(n^{-1}\log n)。$
再回來看要處理 $j=d$ 的情況，也就是 **special object** 為 leaf 的情況，剛好就是 $s=0$ 的意思，因此發生在 $j=d$ 的情況下的期望值為
$$
\lfloor\frac{n}{2}\rfloor p_{s=0}=\lfloor\frac{n}{2}\rfloor(\alpha_1-1+\Theta(n^{-1}\log n))=(\alpha_{1}/2-1/2)n+\Theta(\log n)
$$
求出 $j=0、j=d$ 的期望值後，$E(T)$ 為這兩者之和，因此
$E(T)=(\alpha_1/2-1/2+\beta)n+\Theta(\log n)$，帶回 $E(L_{\text{BUS
}})$ 中，可得 :
$$
\begin{split}E(L_{\text{BUS}})&=(3-\alpha_1/2-\alpha_2)n-(\alpha_1/2-1/2+\beta)n+\Theta(\log n)\\ &=(7/2-\alpha_1-\alpha_2+\beta)n+\Theta(\log n)\end{split}
$$
因此得到以下結論，在進行 **bottom-up-HEAPSORT** 一開始 heap creation phase 時 comparison 平均花費次數為
$$
\begin{split}
&\underbrace{n+\Theta(\log n)}_{\text{leaf-search}}+\underbrace{(7/2-\alpha_1-\alpha_2+\beta)n+\Theta(\log n)}_{\text{bottom-up-search}} \\
= &(9/2-\alpha_1-\alpha_2+\beta)n+\Theta(\log n)\\
\approx &1.649271n
\end{split}
$$
接著分析 select phase 的 comparison ，會進行 **leaf-search(n-1,1)、leaf-search(n-2,1)、...、leaf-search(2,1)** ，在執行 **leaf-search(i,1)** 的 worst-case 下，共會執行 $\lfloor\log(i-1)\rfloor$ 次的 comparisons，worst-case 下， 全部 **leaf-search** 的 comparisons 次數為
$$
\begin{split}
\sum_{i=2}^{n-1}\lfloor\log(i-1) \rfloor &= \sum_{i=1}^{n-2}\lfloor\log i\rfloor \\
&=\sum_{i=1}^{\lfloor\log(n-2)\rfloor-1}i2^i+\lfloor\log(n-2)\rfloor(n-2^{\lfloor\log(n-2)\rfloor}-1)\\
&= n\lfloor\log (n-2)\rfloor-2\cdot2^{\lfloor\log(n-2)\rfloor}-\lfloor\log(n-2)\rfloor+2
\end{split}
$$
將以上調整至 $n\log n-c(n)n$ 的形式，則
$$
c(n)=(\log n-\lfloor\log(n-2)\rfloor)+2\cdot2^{\lfloor\log(n-2)\rfloor}/n
$$
$c(n)$ 在 $n\approx 1.386\cdot 2^k$ 時為最大值，此時 $c(n)\approx 1.91393$ 。 worst-case 下，**leaf-search** 會執行 $n\log n-1.91393n$ 次 comparisons。但這是在 worst-case 下，並不是每次找到的 **special path** 總會是最長的，也是有可能找到較短的 **special path**，其長度為 $\lfloor\log (n-1)\rfloor-1$ ，在論文的實驗下，在 $n\approx1.4\cdot2^k$ 約會有 $0.519$ 的機率找到的 **special path** 不是最長的。綜上所述，**leaf search** 平均下會執行 $n\log n -1.91393n-0.519n=n\log n -2.43293n$ 次 comparisons。
**bottom-up-search** 也會做 comparison，因為每次 **bottom-up-search** 至少會做一次的 comparison，且大部分作的次數都會很少(因為在做 heap sort 要將最後一個值 x 與 root 交換，再使 x 下沉至 x 應該在的位子，因 x 為 heap 的葉子，預期其值會相當大，因此 x 新的位子也會相當靠近最後一層)，論文實驗分析，會執行 $1.17n$ 次的 comparisons。
那執行整體 **bottom-up-HEAPSORT** 預計共會花
$$
\begin{split}
\underbrace{1.649271n}_{\text{heap creation phase}}+\underbrace{n\log n-2.43293n}_{\text{select phase leaf-search}}+\underbrace{1.17n}_{\text{select phase bottom-up-search}}=n\log n+0.386341n
\end{split}
$$
而論文中則是用猜想的方式，以 $n\log n+d(n)n$ 為執行 comparison 次數之期望值，來進行實驗，得到以下結果(部分節錄)
| n | 1000 | 2000 | 3000 | 4000 | ... | 27000 | 28000 | 29000 | 30000 |
| ------ | ----- |:-----:|:-----:|:-----:|:---:|:-----:|:-----:|:-----:|:-----:|
| $d(n)$ | 0.345 | 0.349 | 0.383 | 0.358 | ... | 0.381 | 0.378 | 0.373 | 0.371 |
透過實驗結果，這可以解釋 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 中，開頭的
> This performs n\*log2(n) + 0.37\*n + o(n) comparisons on average
考慮 $o(n)$ 為容許的誤差，實驗結果也與分析出來的 $n\log n+0.386341n$ 相當接近。
> and 1.5\*n\*log2(n) + O(n) in the (very contrived) worst case.
也可從論文中 Thm 5.1 中得出。
### 建立相關實驗環境
[commit f8f230a](https://github.com/kart81604/linux2023_final/commit/f8f230acbd6f8b8ef794407fd806ceb0084677ac)
目前建立一個陽春簡單的 driver 可以使用 linux kernel 中的 sort 排序，以及建立 client 的 user space 來讀取相關資料。
[commit 0fcbe0f](https://github.com/kart81604/linux2023_final/commit/0fcbe0f6521bb678dbc305c90b4362c4d16f7a2c)
考慮原本未排序資料過於固定，會影響實驗結果，參考 [2021年作業-ksort](https://hackmd.io/@sysprog/linux2021-sort) 後，引入 [xoroshiro128+](https://en.wikipedia.org/wiki/Xoroshiro128%2B) 這個 [Pseudorandom number generator](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)，以下為引入後的時間表現圖。
利用 perf stat 來查看資源利用。
```
Performance counter stats for './client':
9,396.16 msec task-clock # 1.000 CPUs utilized
40 context-switches # 4.257 /sec
1 cpu-migrations # 0.106 /sec
60 page-faults # 6.386 /sec
31,746,894,265 cycles # 3.379 GHz
23,920,611,236 instructions # 0.75 insn per cycle
3,855,864,140 branches # 410.366 M/sec
658,348,492 branch-misses # 17.07% of all branches
9.396961274 seconds time elapsed
0.011975000 seconds user
9.364692000 seconds sys
```
利用 perf record 來查看熱點(僅列出與 sort 有關的函式)。
```
49.76% client [kernel.kallsyms] [k] cmpint64
37.61% client [kernel.kallsyms] [k] sort_heap
10.00% client [kernel.kallsyms] [k] do_swap
0.88% client [kernel.kallsyms] [k] sort_read
```
不意外的，花最多時間 comparison 上。
[commit 2751912](https://github.com/kart81604/linux2023_final/commit/27519128b5b7302f359e853cb5bf57210fe1bca8)
將每次執行 comparison 次數與論文中的 $n\log(n)+0.37n$ 做比較，結果兩者高度接近！
## TODO: 參照[學員成果](https://hackmd.io/@sysprog/linux2021-homework5)，引入 hybrid sort
需要強化排序測試和效能評估，程式碼應實作於 Linux 核心中
延伸閱讀: (涉及排序演算法和現代處理器的關聯)
* [Hoare’s Rebuttal and Bubble Sort’s Comeback](https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html)
* [Lomuto’s Comeback](https://dlang.org/blog/2020/05/14/lomutos-comeback/)
[commit fd5f87b](https://github.com/kart81604/linux2023_final/commit/fd5f87b9a437d035e5cd403064ca999fd0cd070a)
參考 [hankluo6/ksort](https://github.com/hankluo6/ksort) 的成果，引入 introsort。
透過 perf stat 來查看 introsort 的資源利用。
```
Performance counter stats for './client':
6,553.87 msec task-clock # 0.999 CPUs utilized
223 context-switches # 34.026 /sec
3 cpu-migrations # 0.458 /sec
60 page-faults # 9.155 /sec
22,107,043,269 cycles # 3.373 GHz
13,762,687,088 instructions # 0.62 insn per cycle
2,719,459,349 branches # 414.939 M/sec
617,936,408 branch-misses # 22.72% of all branches
6.559289342 seconds time elapsed
0.011913000 seconds user
6.492720000 seconds sys
```
以及 perf record (僅列出與 sort 有關的函式)。
```
63.88% client [kernel.kallsyms] [k] cmpint64
32.18% client [kernel.kallsyms] [k] sort_intro
1.35% client [kernel.kallsyms] [k] sort_read
```
並與 bottom-up heapsort 比較，這次紀錄方法使用 `printk` 印出兩者的執行時間，再透過 `dmesg` 將資料印出，接著做成圖表。因為 dmesg 的 ring buffer 為 8000+ 個，因此資料量從 10000 調整至 8000。比較成果如下圖所示。
```shell
sudo dmesg -t > ttest.txt
```
如果 dmesg 已經有其他的系統訊息，可以先用以下命令清除。
```shell
sudo dmesg -C
```
Sign in with Wallet
Connect another wallet