Try   HackMD

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 去記錄下一個被刪除的節點

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

輸入./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) 去比較 cursafe 是否一樣。若不一樣,則雙雙移至下個節點,若一樣,則將 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(n2),不符合系統預計時間,因此以下使用時間複雜度為 O(n\log{n})的 Merge Sort

將 Merge Sort 分為兩個步驟

  1. mergeSortList :利用 slow 指標與 fast指標將佇列拆成兩個等長的佇列,用地回呼叫的方式反覆執行上述動作直至佇列無法再被分割
while (fast != head && fast->next != head) {
    slow = slow->next;
    fast = fast->next->next;
}
  1. 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\)

image

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

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

參考自GNU GCC compiler()

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

head->prevnext指向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\) \(\Longrightarrow\) \(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\) \(\Longrightarrow\) \(2^1\) + \(2^1\) + \(2^0\)
  • count = 6(\(0110_2\)) | \(2^1\) + \(2^1\) + \(2^0\) + \(2^0\) \(\Longrightarrow\) \(2^2\) + \(2^0\) + \(2^0\)
  • count = 7(\(0111_2\)) | \(2^2\) + \(2^0\) + \(2^0\) + \(2^0\) \(\Longrightarrow\) \(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);

其中likelyunlikely用在提升程式碼運行效率,這兩個巨集被定義在 /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_sortlist_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_sortlist_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