Linux 核心專題: 改進 `lib/list_sort.c`

執行人: visitorckw
專題解說錄影

任務簡述

解釋 Linux 核心的 lib/list_sort.c 現有的 bottom-up merge sort 實作，並尋求效能改進，例如 hybrid sort 的引入。

TODO: 解釋 Linux 核心的 `lib/list_sort.c`

彙整〈你所不知道的 C 語言: linked list 和非連續記憶體〉、〈Linux 核心的鏈結串列排序〉，以及 Homework1 學員關於 lib/list_sort.c 的實作討論成果，在本頁面解釋各項設計和實作議題，應涵蓋以下:

commit b5c56e0 提及的論文和相關解讀
如何撰寫對 cache 友善的程式碼並評估其效益
提出合理的排序測試和效能評估機制

研讀 lib/list_sort.c

注意用語:

linked list 為「鏈結串列」，可簡稱為 list (串列)，但不可稱「链表」(不具備任何「表」的寓意，參見中華民國教育部重編國語辭典「表」)
a power of 2 是「2 的冪」，而非「2 的冪次方」，參見資訊科技詞彙翻譯
pseudocode 是「虛擬碼」，而非「偽代碼」
register 是「暫存器」，而非「寄存器」，參見詞彙對照表
區分「藉由」和「通過」，否則難以對應 "pass" 一詞

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

lib/list_sort.c 中實作的 merge sort 演算法採用 bottom-up 策略。它首先將給定的串列轉換為一個以空結尾的單向鏈結串列。該演算法維護一個稱為 "pending" 的數據結構，表示等待進一步合併的已排序子串列。

lib/list_sort.c 中 merge sort 演算法的特點如下：

DFS 順序：與傳統的 BFS 順序合併不同，使用 DFS 順序。
2 的冪子串列：該演算法確保每個已排序子串列的大小都是 2 的冪。
平衡合併：該演算法旨在保持平衡的合併過程。它在待合併的元素數量與它們的大小相等時進行兩個子串列的合併。這確保每個後續的最終合併的比例最差為 2:1。
快取使用效率高：這個實作中的 DFS 順序合併設計得對快取友善。通過深度優先演算法來合併子串列，它減少 cache trashing 現象，提高快取的利用率。

commit b5c56e0 和論文和相關解讀

George Spelvin 在 commit message 中附上的分析合併排序的論文：

排序測試和效能評估機制

為了評估和比較各個排序演算法，會關注以下三種數據:

Execution time
The number of comparisons
Cache miss ratio

Execution time

為了說明多種不同的排序演算法執行時間存在顯著差異並且希望不侷限某特定 CPU 硬體平台，我們可以引入統計學中的變異數分析的手法並搭配 F 分布來檢驗。其執行步驟如下:

測量執行時間:
參考論文〈Dude, is my code constant time?〉之中 Measure execution time 的方法。現代 CPU 提供週期計數器（例如 x86 系列中的 TSC 暫存器，或 Arm Cortex-M 可用的 systick 周邊硬體），可用於準確地獲取執行時間測量。並且重複進行多次反覆測量。
設立虛無假說:
- $H_{0}$ （虛無假說）:
  $μ_{1} = μ_{2} = . . . μ_{k}$
- $H_{1}$ （對立假說）:
  $N o t a l l m e a n s a r e e q u a l$
  (
  $μ_{i}$ 為每種排序演算法的平均執行時間)
計算 F 值
- 計算 mean square due to treatment，其公式如下:
  
  $M S T R = \frac{\sum_{j = 1}^{k} n_{j} (μ_{j} - μ)^{2}}{k - 1}$
- 計算 mean square error，其公式如下:
  
  $M S E = \frac{\sum_{j = 1}^{k} (n_{j} - 1) s_{j}^{2}}{n_{T} - k}$
  (其中
  $μ$ 為所有排序演算法的執行時間總平均，
  $n_{j}$ 為每種排序演算法的執行時間的數據個數，
  $s_{j}$ 為每種排序演算法的執行時間的組內變異數，
  $n_{T} = \sum_{j = 1}^{k} n_{j}$ )
- 計算 F 值，其公式如下:
  
  $F = \frac{M S T R}{M S E}$
透過 F 值來得到 p-value 並決定是否拒絕
$H_{0}$ 假設
我們可以透過先前計算好的 F 值以及自由度
$d f_{1} = k - 1$ 和
$d f_{2} = n_{T} - k$ 來得到 p-value。其相關公式可參考 F-distribution。若 p-value 小於設定的
$α$ (顯著水準)，我們就可以拒絕
$H_{0}$ 假設並且得到至少有兩種排序演算法的執行時間存在顯著差異的結論。
假設已經得到拒絕虛無假說的結論，我可以用 Fisher least significant difference 來得知是哪幾個排序方法中存在顯著差異。
挑選要比較的兩種排序後，設立虛無假說:
- $H_{0}$ （虛無假說）:
  $μ_{i} = μ_{j}$
- $H_{1}$ （對立假說）:
  $μ_{i} \neq μ_{j}$
計算 t 值，其公式如下:

$t = \frac{m u_{i} - m u_{j}}{\sqrt{M S E (\frac{1}{n_{i}} + \frac{1}{n_{j}})}}$
接著透過 t 分佈以及自由度
$d f = n_{T} - k$ 來計算 p-value。若 p-value 小於設定的
$α$ (顯著水準)，我們就可以拒絕
$H_{0}$ 假設並且得到這兩種排序演算法的執行時間存在顯著差異的結論。

The number of comparisons
論文 Bottom-up Mergesort: A Detailed Analysis 當中使用 K 值來分析比較次數。論文中提及比較次數與排序的元素個數關係如下:

$C_{w, t d} (N) = N \lg N + N A (\lg N) + 1$
其中
$C_{w, t d}$ 代表 top down 方法中最差情況下比較次數的函數。而
$A$ 的公式如下：

$A (x) = 1 - {x} - 2^{1 - {x}}$
其中大括號
${}$ 是取小數的函數。函數
$A$ 是一個週期函數。
我們可以進一步將比較次數的函數總結成以下式子:

$C (N) = N \lg N - N K (\lg N) + O (1)$
由於
$K$ 具有週期的性質，參考 kdnvt 的共筆所使用的方法，在設計實驗計算
$K$ 的平均值時，將鏈結串列長度為
$N \in [N_{1}, N_{2}]$ 都計算一次比較次數並推估出每次的
$K$ 值後取其平均。其中
$N_{1}$ 為 2 的冪並且
$N_{2} = 2 N_{1} - 1$ 。以下程式碼示意:
```
double average_K(int size)
{
   double sum_k = 0;
   for (int n = size; n < end; n++) {
       ptr *list = new_list();
       for (int i = 0; i < n; i++) {
           insert_tail(list, random());
       }
       int cmp_count = sort(list);
       sum_k += log2(n) - (double) (cmp_count-1) / n;
   }
   return sum_k / size;
}
```
Cache miss ratio

可用 valgrind 之中的 cachegrind 工具分析 cache miss ratio，其用法如下:

$ valgrind --tool=cachegrind ./executable_file

TODO: 引入 Timsort 及其變形

延續〈Timsort 研究與對 Linux 核心貢獻嘗試〉的成果，著重於以下:

討論 Timsort 對 Mergesort 的改善
原本的 Timsort 並非 in-place 演算法，但考慮到 lib/list_sort.c 的應用場景，必須做到最低的堆疊使用開銷，因此需要從演算法層面調整 Timsort，使其得以達到 in-place (或最低的記憶體開銷)
引入 Adaptive Shivers Sort 及相關的 Timsort 變形，探討其效益，並予以實作

涉及排序演算法和現代處理器的議題，可對照閱讀以下:

Timsort 對 Mergesort 的改善

改善比較次數
在尚未排序的序列中，已經排序好的子序列會被加入到同一個 runs 之中，以減低額外排序的開銷。這個特性使得 Timsort 在處理具有部分有序性質的序列時表現更好。
插入排序優化
Timsort 中的一個關鍵改進是對小規模子陣列採用插入排序。相比之下，Mergesort 在處理小規模陣列時仍然使用歸併操作。插入排序對於小規模陣列的排序效率更高，這使得 Timsort 在實際應用中具有更好的性能。
Cache Miss 改善
相比於傳統遞迴版本的 Mergesort 採用廣度優先的合併順序，Timsort 類似於 Linux 核心 Mergesort 的作法採用深度優先的合併順序。這樣做的好處是，趁元素才剛存取過仍在快取時，就進行合併，從而降低 cache miss 的機率。

排序執行時間與鏈結串列節點數量關係圖
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
比較次數與鏈結串列節點數量關係圖
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
ANOVA 分析
- N (鏈結串列節點數量) = 5
  - 執行時間 (p-value)
  list_sort timsort shiversort
  
  list_sort
  
  timsort 1.11022e-16
  
  shiversort 6.1281e-08 0.00254456
  - 比較次數 (p-value)
  list_sort timsort shiversort
  
  list_sort
  
  timsort 4.44089e-16
  
  shiversort 4.44089e-16 1.0
- N (鏈結串列節點數量) = 100000
  - 執行時間 (p-value)
  list_sort timsort shiversort
  
  list_sort
  
  timsort 1.11022e-16
  
  shiversort 1.11022e-16 6.11238e-10
  - 比較次數 (p-value)
  list_sort timsort shiversort
  
  list_sort
  
  timsort 1.11022e-16
  
  shiversort 1.11022e-16 1.11022e-16

	list_sort	timsort
list_sort
timsort	1.11022e-16
shiversort	6.1281e-08	0.00254456

	list_sort	timsort
list_sort
timsort	4.44089e-16
shiversort	4.44089e-16	1.0

	list_sort	timsort
list_sort
timsort	1.11022e-16
shiversort	1.11022e-16	6.11238e-10

	list_sort	timsort
list_sort
timsort	1.11022e-16
shiversort	1.11022e-16	1.11022e-16

In-place Timsort

GitHub

Timsort 需要一個 stack 來存放所有的 runs。由於排序時，會將待排序的鏈結串列當成單向鏈結串列。因此每個節點中的 prev 指標就可以被利用來儲存各種額外資訊。由於每個 runs 都保證最少會包含有兩個節點，因此我們可以用每個 runs 的第一個節點的 prev 指標來串接 stack ，而第二個節點的 prev 指標則用來儲存 runs 的大小。

首先實作用來取得 runs 大小的函式， runs 的大小存放在第 2 個節點的 prev 指標中。

size_t get_run_size(struct list_head *run_head)
{
    return run_head ? 0 : (size_t)(run_head)->next->prev;
}

接著我們需要一個函式用來合併兩個相鄰的 runs。

static struct list_head *merge_at(void *priv, list_cmp_func_t cmp, struct list_head *at)
{
    size_t len = get_run_size(at) + get_run_size(at->prev);
    struct list_head *prev = at->prev->prev;
    struct list_head *list = merge(priv, cmp, at->prev, at);
    list->prev = prev;
    list->next->prev = (struct list_head *) len;
    --stk_size;
    return list;
}

接著根據 runs 的大小實作合併策略。

static struct list_head *merge_collapse(void *priv, list_cmp_func_t cmp,
                                        struct list_head *tp)
{
    int n;
    while ((n = stk_size) >= 2) {
        if ((n >= 3 && get_run_size(tp->prev->prev) <= get_run_size(tp->prev) + get_run_size(tp)) ||
            (n >= 4 && get_run_size(tp->prev->prev->prev) <= get_run_size(tp->prev->prev) + get_run_size(tp->prev))) {
            if (get_run_size(tp->prev->prev) < get_run_size(tp)) {
                tp->prev = merge_at(priv, cmp, tp->prev);
            } else {
                tp = merge_at(priv, cmp, tp);
            }
        } else if (get_run_size(tp->prev) <= get_run_size(tp)) {
            tp = merge_at(priv, cmp, tp);
        } else {
            break;
        }
    }

    return tp;
}

最後則是 Timsort 的本體，不斷地找尋新的 runs 並且合併。

do {
    /* Find next run */
    struct pair result = find_run(priv, list, cmp);
    result.head->prev = tp;
    tp = result.head;
    list = result.next;
    stk_size++;
    tp = merge_collapse(priv, cmp, tp);
} while (list);

測試結果:

Ampere eMAG 8180

Implementation	Elapsed time	Comparisons
Linux	462341	20621567
shiverssort	269158	14339471
timsort	298119	1525486

Apple M1

Implementation	Elapsed time	Comparisons
Linux	170253	20573832
shiverssort	94199	14318621
timsort	95611	14906465

Intel E5-2650 v4

Implementation	Elapsed time	Comparisons
Linux	298097	20621567
shiverssort	183847	14339471
timsort	203153	15254864

TODO: 將改進的 Timsort 引入到 Linux 核心

利用第 7 週教材提到的 user-mode-linux 和 virtme，對改進的 lib/list_sort.c 進行正確性和效能測試，確保能在 Linux v6.1+ 運作。

隨後可準備作出 Linux 核心的程式碼貢獻

Linux 核心專題: 改進 lib/list_sort.c