2024q1 Homework1 (lab0)

contributed by < aa860630 >

Reviewed by `allenlial666`

避免中英混用，例如 function 應翻譯為函式。
q_swap 可以使用 list_move 簡化程式碼。

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
CPU op-mode(s):        32-bit, 64-bit
Address sizes:         39 bits physical, 48 bits virtual
Byte Order:            Little Endian
CPU(s):                  4
On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
Model name:            11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz
CPU family:          6
Model:               140
Thread(s) per core:  1
Core(s) per socket:  4

指定的佇列操作

`q_new`

在任何佇列操作前都需要一個 head 當作引數傳入，因此我們需要先 malloc 一個記憶體區塊並將其雙向鏈結(prev 和 next)都指向自己，用以之後操作空的佇列。

「空」(empty) 的佇列是指向有效結構，開頭 (head) 的值為 NULL。

在每次 malloc 時都須確認配置記憶體區塊是否成功，使用以下程式碼做確認。

struct list_head *head = malloc(sizeof(struct list_head));

+ if (!head)
+     return NULL;

輸入 ./qtest 後進行操作

cmd> new
l = []

`q_free`

commit 39ea8d0

填入自己帳號對應的 git commit 超連結，例如 https://github.com/aa860630/lab0-c/commit/c3fce364112666dac1d66cd916e040e29fa3b829

q_free()用以釋放佇列在記憶體的空間，包括 head 及每個 entry 的 value 跟 list，資料型別如下

typedef struct {
    char *value;
    struct list_head list;
} element_t;

在刪除每個節點的同時必須記得下一個刪除的物件，這裡透過 list_for_each_entry_safe (node, safe, l, list) 可以利用 safe 去記錄下一個被刪除的節點

留意資訊科技詞彙翻譯
改進你的漢語表達。

輸入./qtest後進行操作

l = [a b c]
cmd> free
l = NULL

q_insert_head() 和 q_insert_tail()

q_insert_head() 在佇列的第一個位置插入新的節點，在 malloc 一個 element_t 之後一樣要確認記憶體空間是否被創造，確認方法如下

element_t *new_node = malloc(sizeof(element_t))

+ if (!new_node) 
+     return false;

透過 list_add(&new_node->list, head) 可以直接將 new_node 插入在第一個位置，但由於其形態為 element_t，因此要將指標位置改為指向 new_node 的 list

兩個 function 的操作方法一致，差別只在於插入位置

避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。

輸入./qtest後進行操作

l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]

commit 8a8823c
commit fdc6218

q_remove_head() 和 q_remove_tail()

q_remove_head()用來 pop 佇列的第一個節點，可以透過 list_del_init()來移除 head 的下一個節點，但無法同時移除該節點的 value，因此需要以下程式碼來完整 pop 整個節點

if (sp) {
    strncpy(sp, node->value, bufsize);
    strcat(sp, "\0");
}

將 node->value的字串複製到由指標 sp 指向的空間，空間大小為 bufsize，記得在字串後方加入"\0"，才能知道字串結束位置

兩個 function 的操作方法一致，差別只在於 pop 節點的位置

輸入./qtest後進行操作

l = [a b c]
cmd> rh
Removed a from queue
l = [b c]
cmd> rh
Removed b from queue
l = [c]

q_delete_dup

用作刪除佇列中重複的字串，詳情見Remove Duplicates from sorted list II

段落中的程式碼標注，使用 1 個 backtick，而非 3 個。

利用 list_for_each_entry_safe (cur, safe, head, list) 去比較 cur 與 safe 是否一樣。若不一樣，則雙雙移至下個節點，若一樣，則將 cur 刪除，並將布林常數 cmp 改為 1，雙雙移至下個節點

改進你的漢語表達。
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

if (cmp == 1) {
    list_del_init(&cur->list);
    free(cur->value);
    free(cur);
}

由上述程式碼可知當cmp為 1 時，無論比較結果為何都需刪除當前節點，確保刪除連續重複字串的最後一個字串。

輸入./qtest後進行操作

l = [a b b c c c d]
cmd> dedup
l = [a d]

commit c3cef8f

q_swap

將佇列中兩兩節點進行反轉，詳情見 Swap Nodes in Pairs

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

輸入./qtest後進行操作

l = [b a d c e]
cmd> swap
l = [a b c d e]

commit a371b33

q_reverse

將整個佇列做反轉

輸入./qtest後進行操作

l = [a b c d e]
cmd> reverse
l = [e d c b a]

commit 72bd7b4

q_reverseK

佇列根據引數k為一個單位進行反轉，詳情見Reverse Node In K-Group

使用q_size可知佇列長度，比較 len 與 k 的大小，若 len >= k 就進行反轉(呼叫副函式 q_reverse())，否則不做任何操作，在反轉後都會將 len - k，直到 len < k

len = q_size(head);
while (len >= k) {
    ...
    len = len - k;
}

輸入./qtest後進行操作

l = [a b c d e f g]
cmd> reverseK 2
l = [b a d c f e g]
cmd> reverseK 3
l = [d a b e f c g]

commit c3cef8f

q_sort

將佇列做排序，在嘗試過 Bubble Sort 後，由於其時間複雜度為 O(n²)，不符合系統預計時間，因此以下使用時間複雜度為 O(n\log{n})的 Merge Sort

將 Merge Sort 分為兩個步驟

mergeSortList :利用 slow 指標與 fast指標將佇列拆成兩個等長的佇列，用地回呼叫的方式反覆執行上述動作直至佇列無法再被分割

while (fast != head && fast->next != head) {
    slow = slow->next;
    fast = fast->next->next;
}

merge :兩兩佇列利用strcmp去比較字串大小並由小排到大，反覆執行直至合併成原先佇列大小

~~![image](https://hackmd.io/_uploads/r1YvylzpT.png)~~

使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記中。

參考文件來自Linked List Sort

在做合併的同時，由於每個佇列已排序，因此當其中一個佇列為空時，只要把另一個佇列剩餘部分接回正在合併的佇列即可

if (t1->next == t1) {
    list_splice_tail(&tmp2, &new_queue);
} else if (t2->next == t2) {
    list_splice_tail(&tmp1, &new_queue);

輸入./qtest後進行操作

cmd> ih RAND  4
l = [ndqavs pmdkzpsti dmectanx coowpn]
cmd> sort
l = [coowpn dmectanx ndqavs pmdkzpsti]

commit a96cac6

你如何確保目前的測試已涵蓋排序演算法的最差狀況？

q_ascend 和 q_descend

q_descend的功能為在不移動節點的情況下將佇列從最大排到小，過程中勢必會刪除掉一些節點，並回傳佇列剩餘節點數，詳情見Remove Nodes From Linked List

兩個 function 的操作方法一致，差別只在於由小到大或由大到小

輸入./qtest後進行操作

l = [f c d a b]
cmd> descend
l = [f d b]

commit c3fce36
commit bf41ea4

q_merge

將不同佇列，按照順序合併回一個佇列，詳情見Merge k Sorted Lists

特別需要注意的是，此處使用的資料型別為queue_contex_t

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

commit e759807

Shuffle

在qtest.c裡並沒有可執行 "shuffle" 的指令，為此我們可以新增一個名為 "shuffle" 的命令，同時附上指令說明

ADD_COMMAND(shuffle, "Shuffle the queue","");

在同個檔案下新增一個名為do_shuffle的 function，在使用者輸入shuffle命令的同時呼叫do_shuffle

Fisher–Yates shuffle

利用 Fisher–Yates shuffle 演算法來實作洗牌（shuffle）

for (tail = head->prev; tail != head; tail = tail->prev, len--) {
    rnd = head->next;
    int j = rand() % (len);  
    for (int k = 0; k < j; k++) {
        rnd = rnd->next;
    }
    if (tail == rnd) {
        continue;
    }
    tmp = rnd->prev;
    list_move(rnd, tail);
    list_move(tail, tmp);
    tail = rnd;
}

執行 lab0-d 提供的腳本後，輸出結果如下：

$ ./scripts/shuffle.py 

Expectation:  41666
Observation:  {'1234': 41525, '1243': 41663,'1324': 41579,
'1342': 41841, '1423': 41658,'1432': 41388,'2134': 41665,
'2143': 41717,'2314': 41754, '2341': 41622, '2413': 41814,
'2431': 41890, '3124': 41731, '3142': 41295, '3214': 41560,
'3241': 41845, '3412': 41551, '3421': 41440, '4123': 41516,
'4132': 41858, '4213': 41659, '4231': 41712, '4312': 41493,
'4321': 42224}
chi square sum:  20.929774876398024

為了測試洗牌是否足夠隨機，我們透過使用佇列中的4個節點 (l = [1 2 3 4]) 去做測試。在做了

10^{6}

次發牌，由於出現的可能為

4!

，因此可得期望值

E = 41666 (= 10^{6} / 24)

，chi square sum

X^{2} = 20.929774

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

在list_sort函示開始前可見一行指令__attribute__((nonnull(2,3)))，避免參數head或cmp為NULL指標。__attribute__其實是GCC的一種編譯器指令，當其設定為函數屬性時，可以使編譯器在錯誤檢查方面增強

參考自GNU GCC compiler()

__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp){}

將head->prev的next指向NULL，也就是最後一個節點指向NULL，若只觀察next方向的串列，從原先的環狀鏈結串列變成了單向鏈結串列

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

list sort 在做合併時，兩個要被合併的 sublist必須是

2^{k + 1}

：

2^{k}

( 2 : 1 ) 的平衡狀態，並使用二進制的count作為合併與否的依據

count = 1(
$0001_{2}$ ) |
$2^{0}$
count = 2(
$0010_{2}$ ) |
$2^{0}$ +
$2^{0}$ (
$2$ 的冪，不合併 )
count = 3(
$0011_{2}$ ) |
$2^{0}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{1}$ +
$2^{0}$
count = 4(
$0100_{2}$ ) |
$2^{1}$ +
$2^{0}$ +
$2^{0}$ (
$2$ 的冪，不合併 )
count = 5(
$0101_{2}$ ) |
$2^{1}$ +
$2^{0}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{1}$ +
$2^{1}$ +
$2^{0}$
count = 6(
$0110_{2}$ ) |
$2^{1}$ +
$2^{1}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{2}$ +
$2^{0}$ +
$2^{0}$
count = 7(
$0111_{2}$ ) |
$2^{2}$ +
$2^{0}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{2}$ +
$2^{1}$ +
$2^{0}$

上述例子來自 yinghuaxia

在 while 迴圈裡看到的 for 迴圈用來尋找count中的least-significant clear bit，藉此將tail移到待合併的位置上，當bits不為 0 時，sublist 進行排序合併

if (likely(bits)) {}用以判斷count是否為2的冪，若為2的冪，則bits早在 for 迴圈時就被改成0，不會進行合併; 若不為2的冪，bits不為0，則會進行排序合併

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

其中likely與unlikely用在提升程式碼運行效率，這兩個巨集被定義在 /include/linux/compiler.h ，按照__builtin_expect的定義，要用第一個參數和第二個參數比較，它期望的值是true。第二個值是1。這裏的!!(x)就是為了保證當x本身作為邏輯值為true的時候，其!!(x)值為1

# ifndef likely
#  define likely(x)	(__branch_check__(x, 1, __builtin_constant_p(x)))
# endif

#define __branch_check__(x, expect, is_constant) ({			\
			long ______r;					\
			static struct ftrace_likely_data		\
				__aligned(4)				\
				__section("_ftrace_annotated_branch")	\
				______f = {				\
				.data.func = __func__,			\
				.data.file = __FILE__,			\
				.data.line = __LINE__,			\
			};						\
			______r = __builtin_expect(!!(x), expect);	\
			ftrace_likely_update(&______f, ______r,		\
					     expect, is_constant);	\
			______r;					\
		})

在一些明確的條件下，我們比編譯器更了解哪個分支更有可能發生，gcc 在編譯時會在程式引導下調整 if 分支內程式碼的位置，如果是likely修飾過的就調整到前面，因此可以節省跳轉指令帶來的時間開銷

用 perf 進行效能比較

使用 perf 進行效能比較，參考至GNU/Linux 開發工具

perf stat --repeat 5 -e instructions,cycles ./qtest -f traces/trace-sort.cmd

定義測資

option fail 0
option malloc 0
new
ih RAND 500000
time
<sort>
time

比較 q_sort 與 list_sort 這兩個排序的 system time(s)，測試資料筆數分別為10萬筆、50萬筆、100萬筆跟500萬筆資料，如下表所示 :

資料數	q_sort	list_sort
100,000	0.035	0.027
500,000	0.111	0.116
1,000,000	0.226	0.240
5,000,000	0.654	0.653

比較 q_sort 與 list_sort 這兩個排序的效能差別，測試資料筆數為10 萬筆

項目	q_sort	list_sort
cache-misses	78,5773	78,9353
cache-references	114,0532	114,5490
% of all caches refs	68.90%	68.91%
instructions	3,7345,3621	3,7352,0238
cycles	1,8751,4000	1,8724,0725
insn per cycle	1.99	1.99
duration time	0.035 s	0.027 s

2024q1 Homework1 (lab0)

Reviewed by allenlial666

開發環境

指定的佇列操作

q_new

q_free

q_insert_head() 和 q_insert_tail()

q_remove_head() 和 q_remove_tail()

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend 和 q_descend

q_merge

Shuffle

Fisher–Yates shuffle

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

用 perf 進行效能比較

Read more

透過 Netfilter 自動過濾廣告

2024q1 Homework5 (assessment)

2024q1 Homework6 (integration)

2024q1 Homework4 (quiz3+4)

Reviewed by `allenlial666`

`q_new`

`q_free`