Lab0 lib/list_sort.c 學習筆記

lib/list_sort.c

出於好奇，我會將這些 list_sort.c 的問題，對 ChatGPT 進行提問，並將對話附在下方，最後再做比較及總結

研讀過程

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)
{
    ...
}

這段程式可以從函式名稱得知用途是合併兩條鍊結串鍊，並且會使用函式指標 cmp 進行大小的比較，可以特別的看到前面使用了一個特別的巨集 __attribute__((nonnull(2,3,4))) 可以從Is attribute((nonnull)) standardized in C 知道它並不是 C 語言標準庫內的規範，而是特定於像是 GCC/Clang 這類的編譯器內的規範。我們可以透過 6.30 Declaring Attributes of Functions 得知他的定義為指定這個函是的參數應該要是非空指標 (non-null pointer)，當中的數字是用來指定第幾個參數要為非空指標，若是沒有參數的話，就是預設所有的參數都是非空指標

struct list_head *head, **tail = &head;

畢竟這邊是 linux kernel 的部份，不免俗的使用 indirect pointer ，來進行 list 的走訪，詳情請見 你所不知道的 C 語言: linked list 和非連續記憶體

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

上面的 for-loop 進行的是兩條鍊結串列中每個值的大小比較，可以發現假如 a 跟 b 所指向的值是相同的時候，會選擇將 a 排入，這麼做是為了排序是 stable sorting，並且當 a 或是 b 其中一方到達 tail 後，它會直接將另一條接在結束的那條鍊結串列後。

merge_final

__attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
			struct list_head *a, struct list_head *b)

merge_final 的實作原理與 merge 其實很像，只是他是在合併最後一個 list 的時候才會使用到的，因此它額外多了一個函式參數 struct list_head *head ，此時就是把所有比較後的東西都接在 head 的後面。

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

	/* And the final links to make a circular doubly-linked list */
	tail->next = head;
	head->prev = tail;

根據上面所述， linux kernel 開發者應該是認為剩下的 b 都是已經排序過的，因此不太需要在花時間比較 b 的值了，因此，才會使用一個 uint8_t count = 0 的變數來確定是否要進行比較，並且在之後使用運算子前置 ++ 來讓第一次是 unlikely 而若是有 ++count 的話，就會變成 !unlikely ，最後是把b 全數加入後，將頭尾相連形成環狀之後完成

# define likely(x)	__builtin_expect(!!(x), 1)
# define unlikely(x)	__builtin_expect(!!(x), 0)

__built_except() 是 GCC 編譯器所提供的函式，用來將 branch 的相關資訊提供給 Compiler ，告訴 Compler 開發者預期的結果，方便他們對程式碼改變分支預測的順序來進行優化。至於為何使用 !!(x) 這樣的語法，是因為透過兩次的 Not operator (!) 可以確定結果必定為 0 或是 1 。
至於會需要這樣的巨集與 Cache 有關，可以知道當 cache 未命中時會從 Memory 搬移一個區塊到 cache 中，而這樣會使得鄰近的程式碼也一起被搬移，進而增加 Cache 命中的機會。因此這個巨集就是將比較可能的部份往前移，比較不可能的部份往後面移動，此部份與老師的提示相吻合。

list_sort

首先先從註解理解程式

 * 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.

它首先解釋了合併以及未合併的個數比例要是2a:1a，並且每a條 sublist 的節點個數為

$2^k$ 個，所以就可以知道總數會是

$3\ast 2^k$ 個節點。這麼做的原因是他要將這些點都放進 L1 cache ，這麼做可以避免 cache thrashing。

 * 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 lists 中節點的數量，在 count 變 count + 1 後，可以觀察到第 k 個 bit 會改為 1，0 ~ k - 1 個 bit 會變 0，此時會將 2 個

$2^k$ 個節點合併，變成

$2^{k+1}$ 然後留下一個

$2^k$

 * This merge happens exactly when the count reaches an odd multiple of
 * 2^k, which is when we have 2^k elements pending in smaller lists,
 * so it's safe to merge away two lists of size 2^k.
 *
 * After this happens twice, we have created two lists of size 2^(k+1),
 * which will be merged into a list of size 2^(k+2) before we create
 * a third list of size 2^(k+1), so there are never more than two pending.

這邊的註解主要在說明上述的部分重複兩次後，就會有兩條

$2^{k+1}$ 可以合併成

$2^{k+2}$ ，如此一來就可以保持只有兩條 pending lists

 * The number of pending lists of size 2^k is determined by the
 * state of bit k of "count" plus two extra pieces of information:
 *
 * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
 * - Whether the higher-order bits are zero or non-zero (i.e.
 *   is count >= 2^(k+1)).

這邊主要也有不合併的情況，當 count + 1 後是

$2^k$ 的時候(也就是轉成二進制時最高位數是1，其他的位數都是 0 的情況)，就不會合併

接著開始探討程式碼的部分

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;

可以看到可以看到他先檢查了鏈結串列的狀況，以及將其變成非環狀的鏈結串列

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;

可以從註解看到他要找到的是 count 中最低位的 clear bit ，並且從 for-loop 的迭代 bits >>= 1 驗證是在找二進制的最低位數

/* 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;
}

這邊使用到了上面所出現過的 likely 巨集，應該也是為了減少 branch penalty 所做的優化，如果 bits 在上一個步驟的結尾變成了 0 的話，就不會進行合併，而如果是 1 的話，就會進到這個 if 敘述句並且合併

/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;

先從註解看起，可以知道他是要將一個節點從 input list 移動到 pending list 中，所以他是把 list 接到 pending 的後面，並且 list 迭代一個，再把 count++

/* 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 lists 合併在一起，最後再使用 merge_final 將頭尾連結在一起。

TODO
用 graphviz 可視化上述的過程

ChatGPT 版本

與 chatgpt 的對話會是對話式的，

代表的是我，而我會將 chatgpt 的回答用 ">" 這個引用記號來標記

---

請你詳細說明一下下面這段程式碼 (貼上 list_sort.c)

這段程式碼是 Linux kernel 內建的 list_sort() 函式，目的是對單向鏈結串列進行排序，使用的演算法為合併排序（mergesort）。

程式碼中包含下列函式：

static struct list_head *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b)
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, struct list_head *a, struct list_head *b)
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
其中，merge() 函式是將兩個子串列按照給定的比較函式進行合併排序的核心函式。而 merge_final() 函式是在 merge() 函式的基礎上，將排序後的結果恢復為標準的雙向鏈結串列。

最終，list_sort() 函式就是對於單向鏈結串列，使用 merge() 和 merge_final() 函式進行排序的對外公開接口。該函式需要三個參數，分別是：

priv：私有數據，不透明的對於 list_sort() 函式，會傳遞到比較函式 cmp 中使用。
head：指向待排序的單向鏈結串列的頭節點（不包含實際的數據節點）。
cmp：比較函式，該函式定義了如何比較兩個串列節點，以確定它們的順序。
list_sort() 函式使用的排序算法是合併排序，該算法的主要思想是將一個序列分成兩個子序列，分別對其進行排序，然後將排好序的兩個子序列合併成一個有序的序列。merge() 函式實現了合併的過程，而 merge_final() 函式則負責在合併完成後將結果恢復成標準的雙向鏈結串列。

值得注意的是，該函式在排序的過程中並不會改變節點之間的相對位置，也就是說，如果兩個節點在排序前是相鄰的，那麼在排序後它們還是相鄰的。這保證了該排序算法的穩定性，即排序後相等的元素之間的相對位置不變。

那請你說明一下上述程式碼中為何使用 likely 與 unlikely 巨集

在上述程式碼中，likely 和 unlikely 是 GCC 中的兩個內建巨集。這些巨集通常用於優化代碼中的條件分支，以提高代碼的效率。

當使用 likely 巨集時，表示該條件應該是非常可能成立的，因此編譯器會將該條件的代碼生成成優化的機器碼。相反地，使用 unlikely 巨集表示該條件應該是非常不可能成立的，編譯器會避免在生成機器碼時使用昂貴的分支預測機制，從而提高代碼的效率。

簡而言之，likely 和 unlikely 巨集通常用於幫助編譯器優化條件分支，以提高代碼的效率和性能。

請解釋上述程式碼對於 cache 有何特別設計用意

這是 Linux kernel 中的一個程式碼，負責排序鏈表。這個程式碼中的排序演算法是一個合併排序 (Merge Sort)，而此排序演算法會使用到 cache，這個程式碼特別設計用意是為了儘可能地使用 cache，讓排序效率更高。

程式碼中使用的排序演算法是合併排序，並採用 "cache-aware" 的設計。由於 CPU 的 L1、L2、L3 快取記憶體相對於主記憶體有較低的存取延遲，因此程式碼會儘量讓排序的資料保持在快取中以減少記憶體存取次數，以達到更好的排序效率。合併排序的特性也很適合 cache-aware 的實作，合併排序是個分治法 (Divide and Conquer)，將輸入的鏈表分成兩半，然後對每個子鏈表遞迴地排序，最後合併成一個排序好的鏈表。因為合併排序是遞迴的，因此能夠快取中保持較長時間，而且由於快取有一定的大小限制，程式碼設計上也有控制遞迴深度的限制，避免 cache miss 發生的頻率過高。

---

參考

• lib/list_sort.c
• Sorting a Linux/list.h linked list with list_sort
• likely和unlikely
• chatgpt