L01: lab0

主講人: jserv / 課程討論區: 2023 年系統軟體課程

返回「Linux 核心設計/實作」課程進度表

研讀 Linux 核心原始程式碼的 lib/list_sort.c

• 用 bottom up 實作 merge sort 對 cache 較友善，因為過程中就是一直合併，cache 被參照到的機會更大。
• 而 top down 是會先做 partition 再來 merge，但 partition 本身對 cache 不友善，在 cache 移進移出（內容不斷更新），導致 cache thrashing。

合併方式

合併方式是當有

$3\times 2^k$ 個節點時，合併前兩個

$2^k$ 變成

$2^{k+1}$，並留下一個

$2^k$ 不動，維持著合併：不合併為 2 : 1 的比例，因為只要

$3\ast 2^k$ 可以放得進 L1 cache，可以避免 cache thrashing。

count 為 pending list 中節點的數量，在 count 變 count + 1 後，可以觀察到第 k 個 bit 會改為 1，0 ~ k - 1 個 bit 會變 0，此時會將 2 個

$2^k$ 合併，並留下一個

$2^k$。

何時合併

每當 count + 1，可能會有兩種情況：

1. 當 count + 1 後為

$2^k$，就不合併（只有 leading 1 是 1，其餘都為 0）

• 例子：
  count = 1（
  ${0001}_2$）
  count + 1 = 2（
  ${0010}_2$）
  因為 count + 1 為 2 是 2 的冪，所以此種情況不合併。

2. 當 count + 1 後不為

$2^k$，就合併

• 例子：
  count = 2（
  ${0010}_2$）
  count + 1 = 3（
  ${0011}_2$）
  因為 count + 1 為 3 不是 2 的冪，所以此種情況要合併。
• 可以觀察到在 count 變 count + 1 後，第 k 個 bit 會改為 1，0 ~ k - 1 個 bit 會變 0。而這裡的 k 為 0，所以會將 2 個
  $2^0$ 合併，並留下一個
  $2^0$，也就是合併 2 個 1 為 2，留一個 1 不合併。

以下是 count 從 0 一直加到 16 merge 的狀況：
（括號內是當次被合併的節點加起來的節點數量，用加號來分隔尚未合併的節點，黃色底則是告知此次合併的是 1 + 1, 2 + 2 或 4 + 4 等。）

count 變化	count 二進位	merge	pending 上的節點
0 $\to$ 1	0000 $\to$ 0001	no（ $2^0$）	1
1 $\to$ 2	0001 $\to$ 0010	no（ $2^1$）	1 + 1
2 $\to$ 3	0010 $\to$ 0011	yes	(2) + 1
3 $\to$ 4	0011 $\to$ 0100	no（ $2^2$）	2 + 1 + 1
4 $\to$ 5	0100 $\to$ 0101	yes	2 + (2) + 1
5 $\to$ 6	0101 $\to$ 0110	yes	(4) + 1 + 1
6 $\to$ 7	0110 $\to$ 0111	yes	4 + (2) + 1
7 $\to$ 8	0111 $\to$ 1000	no（ $2^3$）	4 + 2 + 1 + 1
8 $\to$ 9	1000 $\to$ 1001	yes	4 + 2 + (2) + 1
9 $\to$ 10	1001 $\to$ 1010	yes	4 + (4) + 1 + 1
10 $\to$ 11	1010 $\to$ 1011	yes	4 + 4 + (2) + 1
11 $\to$ 12	1011 $\to$ 1100	yes	(8) + 2 + 1 + 1
12 $\to$ 13	1100 $\to$ 1101	yes	8 + 2 + (2) + 1
13 $\to$ 14	1101 $\to$ 1110	yes	8 + (4) + 1 + 1
14 $\to$ 15	1110 $\to$ 1111	yes	8 + 4 + (2) + 1
15 $\to$ 16	1111 $\to$ 10000	no（ $2^4$）	8 + 4 + 2 + 1 + 1

list_sort

__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
	struct list_head *list = head->next, *pending = NULL;
	size_t count = 0;	/* Count of pending */

	if (list == head->prev)	/* Zero or one elements */
		return;

	/* Convert to a null-terminated singly-linked list. */
	head->prev->next = NULL;

• priv: 從 merge 函式可以看到 priv 會被當作 cmp 的參數傳入，在其他地方不會用到。
• head: 傳入指向 struct list_head 的指標，和原本自己寫的 q_sort 傳入的參數一樣
• cmp: compare function，以 function pointer 的型別傳入
  cmp 參數有考慮到通用性，但會增加 function call 的成本。

list 指向 head 的第一個節點，pending 指向 NULL，先檢查是否沒有任何元素或只有一個元素，然後將 head 前一個節點指向的下一個位置指向 NULL，將雙向 linked list 變成單向。

    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);

在 while 迴圈中，會先讓 tail 往前移動到待 merge 的節點，然後在 if 判斷是否需要 merge，最後移動 pending 和 list 的位置，直到 list 沒有節點。pending 從沒有節點，然後一次次將節點從 list 中搬到 pending，等到 list 沒有節點就代表現階段結束了。

    ...
    /* 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);
}
EXPORT_SYMBOL(list_sort);

merge

__attribute__((nonnull(2, 3, 4))) static struct list_head *
merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b)
{
    // cppcheck-suppress unassignedVariable
    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 {
            *tail = b;
            tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

當 cmp(priv, a, b) <= 0 表示 a 的值小於 b，因為由小排序到大，所以先接 a 再接 b，cmp(priv, a, b) > 0 表示 a 的值大於 b，則是先接 b 再接 a。
其中 head 會在排序過 list 的最前面，並回傳回去。

排序過程圖示

以 4, 3, 2, 1 的 list 為例做 list_sort 排序，隨著 count 增加，pending 內節點數量漸漸增加，而 list 內的節點數量漸漸減少：

count = 0 -> count = 1

• list 指向 head->next：

• 因為 bits 為 0，不需 merge。list->prev = pending 因為 pending 為 NULL，所以 list->prev 也指向 NULL：

• pending 節點數量 + 1，list 節點數量 - 1，count + 1，pending->next = NULL：

count = 1 -> count = 2

count = 2 -> count = 3

count = 3 -> count = 4

count = 4

Linux 核心排序實作的演進

探討 lib/list_sort.c 相關實作時，除了觀察程式碼，，也該理解為何 Linux 核心開發者採用這段程式碼，也就是推敲開發是如何思考及進行取捨。我們可參見 github commit history，lib/list_sort.c 最近一次演算法上的改動是 May 15, 2019, commit b5c56e0c, lib/list_sort: optimize number of calls to comparison function 引入，其中引用三篇論文：

1. Bottom-up Mergesort: A Detailed Analysis
   Wolfgang Panny, Helmut Prodinger
   Algorithmica 14(4):340–354, October 1995
   https://doi.org/10.1007/BF01294131
   https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5260
2. The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules
   Wei-Mei Chen, Hsien-Kuei Hwang, Gen-Huey Chen
   Journal of Algorithms 30(2); Pages 423–448, February 1999
   https://doi.org/10.1006/jagm.1998.0986
   https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.5380
3. Queue-Mergesort
   Mordecai J. Golin, Robert Sedgewick
   Information Processing Letters, 48(5):253–259, 10 December 1993
   https://doi.org/10.1016/0020-0190(93)90088-q
   https://sci-hub.tw/10.1016/0020-0190(93)90088-Q

對於比較次數的探討，我們可寫成以下形式：

$$\begin{array}{c}nlo{g}_{2}n-Kn+O(1)\end{array}$$

其中，以下 merge sort 的變形 (variants)，領導係數 (leading coefficient) 皆為

$lo{g}_2(n!)$，探討的著重點在於一次項係數 K。

開發者探討了 merge sort 的三種實作方式，分別為 top-down mergesort、bottom-up mergesort 和 queue-mergesort，以及開發者提出的方式，以下簡述不同的實作方式：

1. Top-down mergesort

• 有最少的 average case、worst case 的 comparison 次數。
• 需要使用遞迴或是額外空間作為 user stack。
• 需要事先知道整個 list 的大小。

下圖例子是 balanced power-of-2 rule dividing strategy:

2. Bottom-up mergesort

• 在這幾種變形中需要最多的 comparison 次數。

3. Queue-mergesort

• 特別適合用於鏈結串列的排序。
• queue-mergesort comparison 的次數少於 bottom-up mergesort，略高於 top-down mergesort。
• 可以以 top-down 或是 bottom-up 的方式實作。
• 透過 get front、put back 操作，因此排序完的結果會是 unstable。

根據 [3] 的演算法，虛擬碼如下

queue-mergesort(Q):
    while (Q.size != 1) do
        Q.put(Merge(Q.get, Q.get))

4. lib/list_sort.c

如果查看更之前的版本 commit 043b3f7b 會發現是用 bottom-up mergesort 實作。

證明

前提：所有子串列其長度皆為 2 的冪，所有合併皆為同大小串列。

設

$t_i$ 為目前長度小於

$2^i$ 的所有子串列的節點數總和。

$i$ 為正整數。

第一點：
證明當

$t_i$ 從

$3\times 2^{i-1}-1$ 加一變成

$3\times 2^{i-1}$ 時，不存在正整數

$j\ne i$ 使得

$t_j$ =

$3\times 2^{j-1}$ 。

假設存在

$j>i$ 且

$t_j$ =

$3\times 2^{j-1}$ 。則有一個正整數

$l$ 使得

$3\times 2^{i-1}+l=3\times 2^{j-1}$ 。因為長度小於

$2^i$ 的所有子串列的節點數總和都包含在

$t_i$ 裡面了，所以

$l$ 都在長度大於等於

$2^i$ 的串列裡。因此可以把

$l$ 寫成

$A\times 2^i$ 。其中 A 等於任意正整數。

$3\times 2^{i-1}+A\times 2^i=3\times 2^{j-1}$

$(3+2A)\times 2^{i-1}=3\times 2^{j-1}$

${\displaystyle \frac{(3+2A)}{3}}=2^{j-i}$

$1+{\displaystyle \frac{2A}{3}}=2^{j-i}$ 令

$A=3B$ 代入，

$B$ 為任意正整數。

$1+2B=2^{j-i}$ 因為

$j>i$ ，所以

$2^{j-i}$ 必為偶數，不存在任何正整數

$B$ 使得

$1+2B$ 等於偶數，假設不成立，因此不存在

$j>i$ 且

$t_j$ =

$3\times 2^j$ 。

假設存在

$j<i$ 且

$t_j$ =

$3\times 2^{j-1}$ 。則有一個正整數

$l$ 使得

$3\times 2^{i-1}=3\times 2^{j-1}+l$ 。因為長度小於

$2^j$ 的所有子串列的節點數總和都包含在

$t_j$ 裡面了，所以

$l$ 都在長度大於等於

$2^j$ 的串列裡。因此可以把

$l$ 寫成

$A\times 2^j$ 。其中 A 等於任意正整數。

$3\times 2^{i-1}=3\times 2^{j-1}+A\times 2^j$

$3\times 2^{i-1}=(3+2A)\times 2^{j-1}$

${\displaystyle \frac{(3+2A)}{3}}=2^{i-j}$

$1+{\displaystyle \frac{2A}{3}}=2^{i-j}$ 令

$A=3B$ 代入，

$B$ 為任意正整數。

$1+2B=2^{i-j}$ 因為

$j<i$ ，所以

$2^{i-j}$ 必為偶數，不存在任正整數

$B$ 使得

$1+2B$ 等於偶數，假設不成立，因此不存在

$j<i$ 且

$t_j$ =

$3\times 2^j$ 。

總和上述兩點，可得證。

第二點：
證明在 "能保持差異最大

$2:1$ 的情況下，能合併則合併。" 的條件下，當

$t_{n+1}$ 從

$3\times 2^n-1$ 增加到

$3\times 2^n$ 時，一定存在兩個長度為

$2^n$ 的子串列可供合併。

當

$n=0$，因為長度最短為 1，

$3\times 2^0$ = 3，長度分別為 1,1,1 ，因此可以合併，成立。

設當

$n=k$ 時成立，則當 n = k+1 時，必須證明當

$t_{k+2}$ 增加到

$3\times 2^{k+1}$ 時，一定存在兩個長度為

$2^{k+1}$ 的子串列可合併。
第一個

$2^{k+1}$ 子串列在

$t_{k+1}$來到

$3\times 2^k$ 時根據假設誕生。此時

$t_{k+2}$ 也等於

$3\times 2^k$ ，合併後

$t_{k+2}$ =

$3\times 2^k$，

$t_{k+1}$ =

$2^k$ 。
第二個

$2^{k+1}$ 子串列在

$t_{k+1}$再次來到

$3\times 2^k$ 時根據假設誕生，此時

$t_{k+2}$ 來到

$5\times 2^k$ 。
由上述兩點可知，在

$t_{k+2}$ 從 0 增加到

$3\times 2^{k+1}$ 的過程中，一定會經過

$3\times 2^k$ 以及

$5\times 2^k$ ，並在這兩時刻產生出長度為

$2^{k+1}$ 的串列。所以當

$t_{k+2}$ 增加到

$6\times 2^k=3\times 2^{k+1}$ 時，一定存在兩個長度為

$2^{k+1}$ 的子串列可供合併，根據數學歸納法得證。

第三點：
證明

$2^i$ 長度串列的合併(兩個

$2^{i-1}$ 合併成

$2^i$)只會發生在

$t_i$ 變成

$3\times 2^{i-1}$ 。

由第二點可知，對所有自然數

$i$ ，

$t_i$ 不會超過

$3\times 2^{i-1}$ ，因為只要等於

$3\times 2^{i-1}$ 就會合併串列並變回

$2^{i-1}$ 。所以合併不會發生在

$t_i>3\times 2^{i-1}$ 。

當

$t_i<3\times 2^{i-1}$ ，此時合併成

$2^i$ 串列無法保證兩條串列比例差異不會超過

$2:1$ ，所以不會合併。

故合併只會發生在

$t_i=3\times 2^{i-1}$ 得證。

綜合上述三點，可得出當 count 增加到 count+1 ，最多只會存在一正整數

$i$ 使得

$t_i$ 為

$3\times 2^{i-1}$ 。若此

$i$ 存在，則一定可合併成長度為

$2^i$ 的串列，且此串列為此時合併的唯一串列。

每次 count 遞增所合併的串列也不會造成更長串列的連鎖合併，因為合併成

$2^i$ 只會改變

$t_i$ 的值，不會改變其他的

$t$ 值，所以不會有其他

$t_j$ 增加成

$3\times 2^{j-1}$ 而造成合併。

為什麼 list_sort 中串列大小的比例差距限制是二比一

因為目的是為了避免合併差距過大，因此使用二比一而不是更大三比一、四比一很合理。需要考慮的是為什麼不用三比二或四比三這種比例。

先簡述一下 list_sort 的演算法：

第一階段：
將節點一個一個讀取，如果確定合併的大小不會超過整體的特定比例，就將之前的串列合併。因為本質還是 bottom up merge sort ，所以此階段的合併都是同大小，所有子串列也都會是二的冪。

第二階段：
當所有節點都讀進並盡可能的同大小合併後，就來到必須合併不同大小的階段。這個階段會將子串列由小大到一個接一個合併。

從以上兩階段可以看出，因為第一階段都是二的冪，在維持

$2m:2m+1$ 比例的情況下，第一階段結束時最大的子串列就是

$2^{\lfloor lo{g}_{2}2mn/(2m+1)\rfloor }$ 。

論文〈The cost distribution of queue-mergesort, optimal mergesorts, and
power-of-two rules〉提及:

Note that

$2^{\lfloor lo{g}_{2}2n/3\rfloor }$ is the unique power of two lying between

$n/3$ and

$2n/3$ and that the choice of rationals other than

$2/3$ will not be more balanced. For example, if

$2^{\lfloor lo{g}_{2}n/2\rfloor }$ or

$2^{\lfloor lo{g}_{2}5n/9\rfloor }$ then the sizes of two subproblems are

$(2,5)$ for

$n=7$ while the balanced power-of-two gives

$(3,4)$.

這段話其實不精準，因為當

$n=3\times 2^k$ 時， 在包括的情況下介於

$n/3$ 以及

$2n/3$ 的二的冪會有兩個，再不包括的情況下卻又會不存在。如果是寫成

$n/3<2^{\lfloor lo{g}_{2}2n/3\rfloor }\le 2n/3$

就符合這段話的描述。
而這段敘述講述了一件事，

$2^{\lfloor lo{g}_{2}2n/3\rfloor }$ 可以找到最接近

$n/2$ 的二的冪。

如果今天是用

$2^{\lfloor lo{g}_{2}3n/5\rfloor }$ 去求

$2^k$ ，則當

$n=13$ 時，

$2^{\lfloor lo{g}_{2}3n/5\rfloor }=4$，而最接近

$13/2$ 的二的冪卻是

$8$ 。
這代表如果在第一階段用

$3:2$ 的比例去限制，在第二階段合併中，最後一次合併會是

$9:4$ ，這個比例差距已經超過第一階段的

$3:2$ ，而同樣的反例在

$2m:2m+1,m>2$ 中也都會發生。因此這樣的演算法只能用在

$2:1$ 的情況。

證明 list_sort 的演算法是 optimal mergesort

optimal merge sort 定義：在最差的情況下，比較次數小於等於所有其他 mergesort 。

對所有 mergesort ，都可以繪製出一個 merge tree 來表示其合併的順序及長度，每一個節點的權重代表當下的串列長度。方形的是 external node (leaf) ，圓形的是 internal node 。如下圖所示：

graphviz參考連結

internal node 的數量為 leaf 數減一。在最差的情況下，合併 (x,y) 的次數為 x+y-1 ，因此最差情況下總共的比較次數就是

$\sum _v^T(w(v)-1)=\sum _v^{T}w(v)-(n-1)$
其中

$n$ 為這次排序的節點總數，也是 leaf 的總數。而

$v$ 為所有的 internal node 。

$w(v)$ 為該 internal node 的權重（也就是長度）。在這邊因為對所有 合併排序 n - 1 都是固定的，所以只要看

$\sum _v^{T}w(v)$ 就好。

論文〈Queue-Mergesort〉提及:

We use the fact that the weight of a merge tree is equal to its external path length. The height h(f) of a node I in a tree is the distance of a path from 1 to the root. The external path length of a tree T’ is the sum E(T’) =

$\sum _{laleafof{T}^{\prime }}h(l)$

及以下：

Thus a merge tree T describes an optimal merge-sort on n items if and only if T has minimum external path length

$\sum _{laleaf}h(l)$. It is known that this occurs if and only if the following condition is satisfied: all of T’s leaves are located on its bottom two levels.

因此可知，只要證明 list_sort 的 merge tree 符合所有 leaf 都在最下面兩層這個條件，就可以證明它是 optimal merge sort 。

分析 list_sort 的演算法，可以得出以下兩點：

1. 在合併的過程中，最多只有一個子串列不是 2 的冪（第二階段排最後的子串列）。
2. 在合併的過程中，兩者差異不大於兩倍。

證明合併過程中對所有長度 n 的子串列，其 merge tree 的所有 leaf 都在最下面兩層。

證明過程：

第一階段所有合併皆為 2 的冪，符合命題。

用數學歸納法證明第二階段：

最小端的子串列只可能是 (1,1) 或 (1,2)，兩者合併都符合命題。

對第二階段過程中的任意合併，假設其兩個子串列都符合命題。

則合併的過程中，由第一點可知，其中一個子串列一定為二的冪，因此其 merge tree 為 full binary tree ，所有 leaf 都在最底層。另其長度為

$2^{k_1}$ ，則 merge tree 的高度為

$k_1$ 。

當另一個子串列如果也是二的冪，因為第二點中兩者差異不大於兩倍，因此其大小只可能是

$2^{k_1-1}$ 或

$2^{k_1+1}$ 。 merge tree 的高度

$k_2=k_1\pm 1$，符合命題。

當第二的子串列不為二的冪，那根據假設，此串列的 merge tree 所有 leaf 都在最下面兩層，而其中一層就是

$k_1$ ，否則會違反第二點兩者差異不大於兩倍的描述，因此也符合命題。

根據數學歸納法，對第二階段過程中的任意合併，其 merge tree 的所有 leaf 都在最下面兩層。所以可以得出最後一次合併所產生的 merge tree 也符合命題。

根據論文中所述，可得知 list_sort 中的演算法也是 optimal merge sort 。