2023q1 Homework1 (lab0)

--- tags: linux kernel class --- # 2023q1 Homework1 (lab0) contributed by < [`willwillhi1`](https://github.com/willwillhi1) > ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 Copyright (C) 2019 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 39 bits physical, 48 bits virtual CPU(s): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 142 Model name: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz Stepping: 12 CPU MHz: 2100.000 CPU max MHz: 4200.0000 CPU min MHz: 400.0000 BogoMIPS: 4199.88 Virtualization: VT-x L1d cache: 128 KiB L1i cache: 128 KiB L2 cache: 1 MiB L3 cache: 6 MiB NUMA node0 CPU(s): 0-7 ``` ## 開發過程先閱讀[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) ![](https://i.imgur.com/vBvOdJ0.png) 可以發現程式中的 ```head``` 為上圖的 Head Node0,1,2... 為 ```element_t``` ### 完成 queue.c #### q_new 利用 ```malloc``` 一個 ```list_head``` 並命名為 ```head```，接著判斷是否成功執行 ```malloc``` 後用 ```INIT_LIST_HEAD``` 來對 ```head``` 初始化，也就是把 ```head->next```,```head->prev``` 指向 ```head``` ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); if (head == NULL) return NULL; INIT_LIST_HEAD(head); return head; } ``` #### q_free 用迴圈走訪整個佇列，並且 free 掉走過的點。 :::warning 改進上述漢語表達 :notes: jserv ::: ```c void q_free(struct list_head *l) { if (l) return; struct list_head *next = l->next; while (l != next) { //list_del(next); element_t *node = list_entry(next, element_t, list); next = next->next; free(node->value); free(node); } free(l); } ``` #### q_insert_head ```malloc``` 一個 ```element_t``` 物件叫做 ```node```，然後用 ```strdup``` 配置空間給 ```node->value``` 後將 ```s``` 複製過去，最後用 ```list_add``` 把 ```node``` 插入到佇列的開頭 ```c bool q_insert_head(struct list_head *head, char *s) { if (head == NULL) return false; element_t *node = malloc(sizeof(struct element_t)); if (node == NULL) return false; node->value = strdup(s); if (node->value == NULL) { free(node); return false; } list_add(&node->list, head); return true; } ``` #### q_insert_tail 與 ```q_insert_head``` 相似，把 ```list_add``` 改成 ```list_add_tail``` ```c bool q_insert_tail(struct list_head *head, char *s) { if (head == NULL) return false; element_t *node = malloc(sizeof(struct element_t)); if (node == NULL) return false; node->value = strdup(s); if (node->value == NULL) { free(node); return false; } list_add_tail(&node->list, head); return true; } ``` #### q_remove_head 去除佇列的第一個元素，```sp``` 為一個已配置空間的字元陣列，```bufsize``` 為其長度。先用 ```list_del``` 去除第一個元素，再用 ```strncpy``` 把去除元素的 ```value``` 複製到 ```sp``` 中。 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (head == NULL || list_empty(head)) return NULL; element_t *node = list_entry(head->next, element_t, list); list_del(head->next); if (sp != NULL) { strncpy(sp, node->value, bufsize-1); sp[bufsize-1] = '\0'; } return node; } ``` #### q_remove_tail 與 ```q_remove_head``` 相似，把 ```head->next``` 改成 ```head->prev``` ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (head == NULL || list_empty(head)) return NULL; element_t *node = list_entry(head->prev, element_t, list); list_del(head->prev); if (sp != NULL) { strncpy(sp, node->value, bufsize-1); sp[bufsize-1] = '\0'; } return node; } ``` #### q_size 如果佇列為空或只有 ```head``` 就回傳 0，之後用 ```list_for_each``` 走訪整個佇列計算 node 數量 ```c int q_size(struct list_head *head) { if (head == NULL || list_empty(head)) return 0; int size = 0; struct list_head *l; list_for_each(l, head) size++; return size; } ``` #### q_delete_mid 宣告 ```first``` 為 ```head->next```, ```second``` 為 ```head->prev```，用 ```while``` 迴圈判斷 ```first``` 和 ```second``` 是否相遇，若還沒則兩個各走一步，直到相遇時 ```first``` 代表中間點，之後便用 ```list_del``` 把其從佇列中去除，然後再 ```free``` 掉該 ```node``` ```c bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (head == NULL || list_empty(head)) return false; struct list_head *first = head->next; struct list_head *second = head->prev; while ((first != second) && (first->next != second)) { first = first->next; second = second->prev; } list_del(first); element_t *node = list_entry(first, element_t, list); free(node->value); free(node); return true; } ``` #### q_delete_dup 先確認佇列是否為空。宣告兩個 ```element_t``` 指標 ```N1```,```N2```，```N1``` 代表目前沒有重複的最後一個點，```N2``` 代表目前重複的數的第一個點 ```graphviz digraph del_mid { { node [shape=circle] rankdir=LR //rank=same node0[label="head"] node1[label="1"] node2[label="2"] node3[label="2"] node4[label="3"] // backbone node0 -> node1 -> node2 -> node3 -> node4 // mark N1 [shape=plaintext;label="N1"] N1 -> node1[] N2 [shape=plaintext;label="N2"] N2 -> node2[] {rank=same node0 node1 node2 node3 node4} } } ``` 接著就是判斷 ```N2->value``` 是否等於 ```N2->next->value```，若是則刪除 ```N2->next``` 直到不相同為止，最後再把重複的 ```N2``` 刪除 ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) return false; element_t *N1 = list_entry(head, element_t, list); element_t *N2 = list_entry(head->next, element_t, list); while (&N2->list != head) { char *value = list_entry(N2->list.next, element_t, list)->value; if (N2->list.next != head && strcmp(N2->value, value) == 0) { while (N2->list.next != head && strcmp(N2->value, value) == 0) { element_t *node = list_entry(N2->list.next, element_t, list); list_del(N2->list.next); q_release_element(node); value = list_entry(N2->list.next, element_t, list)->value; } list_del(&N2->list); element_t *node = list_entry(&N2->list, element_t, list); q_release_element(node); N2 = list_entry(N1->list.next, element_t, list); } else { N1 = list_entry(N1->list.next, element_t, list); N2 = list_entry(N2->list.next, element_t, list); } } return true; } ``` :::warning 1. 留意程式碼風格，`N1` 和 `N2` 並非恰當的命名。 2. 將 `if (head == NULL)` 改為更簡短的 `if (!head)` 3. 將 `strcmp(..) == 0` 改為更剪短的 `!strcmp(...)` 4. 縮減迴圈內的分支指令數量 :notes: jserv ::: * 改進後的版本額外使用 ```isdup``` 判斷是否需要刪除目前的節點 ```first``` 下圖可以看到因為 ```first->value``` 等於 ```second->value``` 所以把 ```first``` 刪除以及把 ```isdup``` 設成 ```true``` ```graphviz digraph del_mid { { node [shape=circle] rankdir=LR //rank=same node0[label="head"] node1[label="1"] node2[label="1"] node3[label="2"] node4[label="3"] // backbone node0 -> node1 -> node2 -> node3 -> node4 // mark first [shape=plaintext;label="first"] first -> node1[] second [shape=plaintext;label="second"] second -> node2[] {rank=same node0 node1 node2 node3 node4} } } ``` 接著來因為 ```isdup``` 等於 ```true```，所以把 ```first``` 刪除後，再把 ```isdup``` 改回 ```false``` ```graphviz digraph del_mid { { node [shape=circle] rankdir=LR //rank=same node0[label="head"] node1[label="1"] node2[label="2"] node3[label="3"] // backbone node0 -> node1 -> node2 -> node3 // mark first [shape=plaintext;label="first"] first -> node1[] second [shape=plaintext;label="second"] second -> node2[] {rank=same node0 node1 node2 node3} } } ``` ```c= bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) return false; element_t *first; element_t *second; bool isdup = false; list_for_each_entry_safe(first, second, head, list) { if (&second->list != head \ && !strcmp(first->value, second->value)) { list_del(&first->list); q_release_element(first); isdup = true; } else if (isdup) { list_del(&first->list); q_release_element(first); isdup = false; } } return true; } ``` #### q_swap 確認 ```head``` 是否為 ```NULL``` 或佇列是否為空，用 ```first```,```second``` 代表要交換的一組 ```node```，下方第 9 到 14 行進行交換，接著就把 ```first```,```second``` 指到下一組 ```node```，直到 ```first``` 或 ```second``` 等於 ```head``` 為止 ```c= void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if (head == NULL || list_empty(head)) return; struct list_head *first = head->next; struct list_head *second = head->next->next; while (first != head && second != head) { first->prev->next = second; first->next = second->next; second->prev = first->prev; first->prev = second; second->next->prev = first; second->next = first; first = first->next; second = first->next; } } ``` #### q_reverse 確認 ```head``` 是否為 ```NULL``` 或佇列是否為空。初始化 ```first = head```,```second = head->next```，接著互換 ```first``` 的 ```prev``` 和 ```next```(8, 9 行)，最後 11, 12 行是跳到下兩個節點，直到 ```first != head```，也就是佇列裡的 ```prev```,```next``` 都被換過 ```c= void q_reverse(struct list_head *head) { if (head == NULL || list_empty(head)) return; struct list_head *first = head; struct list_head *second = head->next; do { first->next = first->prev; first->prev = second; first = second; second = first->next; } while (first != head); } ``` #### q_reverseK 最初的想法是用之前實作的 ```q_reverse``` 來寫，也就是把整個佇列分成每次以 ```k``` 個點為單位進行反轉。首先利用 ```q_size``` 找出佇列的長度，然後除以 ```k``` 得到 ```times``` 代表共要做幾次 ```q_reverse```。在每次的反轉裡，都會從原佇列切出來長度為 ```k＋1``` 的佇列，```first```,```last``` 代表該切割出來的佇列的頭尾節點。```front```,```end``` 用來記錄該切割下來的佇列在原本佇列的前後節點，用來把反轉後的佇列接回去原佇列。以下圖為例假設 k = 3，且要反轉點 ```1```,```2```,```3```，所以 ```first``` 會在 ```head``` 上，```last``` 在 ```3```，```front```,```end``` 分別記錄該切割下來的佇列的前後點是 ```6``` 跟 ```4```。 ```graphviz digraph del_mid { { node [shape=circle] rankdir=LR node0[label="head"] node1[label="1"] node2[label="2"] node3[label="3"] node4[label="4"] node5[label="5"] node6[label="6"] // backbone node0 -> node1 node1 -> node2 node2 -> node3 node3 -> node4 node4 -> node5 node5 -> node6 node6 -> node0[dir="both"] // mark first [shape=plaintext;label="first"] first -> node0[] last [shape=plaintext;label="last"] last -> node3[] end [shape=plaintext;label="end"] end -> node4[] front [shape=plaintext;label="front"] front -> node6[] //{rank=max N1 N2} {rank=same node0 node1 node2 node3 node4 node5 node6} } } ``` :::warning 改進你的漢語表達 :notes: jserv ::: ```c void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (head == NULL) return; struct list_head *front = head; struct list_head *end = head; struct list_head *first = head; struct list_head *last = head; int times = q_size(head)/k; for (int i = 0; i < times; ++i) { for (int j = 0; j < k; ++j) last = last->next; front = first->prev; end = last->next; last->next = first; first->prev = last; q_reverse(first); first->prev->next = end; end->prev = first->prev; first->prev = front; // update first, last first = end->prev; last = first; } } ``` * 改進後的版本先宣告和初始化兩個 ```head_list```: ```tmp``` 和 ```result```，本來想用 ```malloc```，但是這次作業好像禁止用，所以改用 ```LIST_HEAD```。接著與前一個實作想法相同一次對 ```k``` 個節點作反轉，只不過這次會先透過 ```list_cut_position``` 把這 ```k``` 個節點移到 ```tmp``` 上，反轉後把 ```tmp``` 用 ```list_splice_tail_init``` 接到 ```result``` 的尾端且初始化 ```tmp```。最後把 ```result``` 用 ```list_splice_init``` 接到 ```head``` 開頭。 ```c= void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head) return; struct list_head *last = head->next; int times = q_size(head)/k; LIST_HEAD(tmp); LIST_HEAD(result); for (int i = 0; i < times; ++i) { for (int j = 0; j < k; ++j) last = last->next; list_cut_position(&tmp, head, last->prev); q_reverse(&tmp); list_splice_tail_init(&tmp, &result); } list_splice_init(&result, head); } ``` #### q_sort 參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 的 ```merge sort``` 的實做。實作共三個函式 ```q_sort```,```mergesort```,```mergelist``` 對 ```mergesort``` 輸入的佇列如果只有一個節點或空則直接回傳，接著把輸入的佇列分成兩半，然後對這兩個佇列做 ```mergesort```，```mergesort``` 會把這兩個佇列排序。 ```c= struct list_head *mergesort(struct list_head *l) { if (l == NULL || l->next == NULL) return l; struct list_head *fast = l; struct list_head *slow = l; while (fast->next != NULL && fast->next->next != NULL) { fast = fast->next->next; slow = slow->next; } struct list_head *l1 = l; struct list_head *l2 = slow->next; slow->next = NULL; return mergelist(mergesort(l1), mergesort(l2)); } ``` 最後對這兩個已排序的佇列用 ```mergelist``` 合併。 ```mergelist``` 用 ```pointer to pointer``` 的概念來做合併，縮短程式碼長度。 ```c= struct list_head *mergelist(struct list_head *l1, struct list_head *l2) { struct list_head *head = NULL; struct list_head **cur = &head; while (l1 && l2) { element_t *e1 = list_entry(l1, element_t, list); element_t *e2 = list_entry(l2, element_t, list); if (strcmp(e1->value, e2->value) >= 0) { *cur = l2; l2 = l2->next; } else { *cur = l1; l1 = l1->next; } cur = &(*cur)->next; } *cur = (struct list_head *) ((u_int64_t)l1 | (u_int64_t)l2); return head; } ``` :::warning 避免張貼過長的程式碼，畢竟 HackMD 是紀錄和討論的協作環境，你應該摘錄關鍵程式碼。實作後應提出改進事項。善用 `qtest` 內建的 `time` 命令，觀察你撰寫程式的行為。 `node` 的翻譯是「節點」，而非「點」 :notes: jserv ::: `q_sort` 將原本被拆開的節點重新連結起來 ```c= void q_sort(struct list_head *head) { if (head == NULL || list_empty(head)) return; head->prev->next = NULL; head->next = mergesort(head->next); struct list_head *cur = head; struct list_head *next = head->next; while (next) { next->prev = cur; cur = next; next = next->next; } cur->next = head; head->prev = cur; } ``` 再這之後我利用雙向鏈結串列的特性，改寫 ```mergesort``` 用快慢指標找中間節點的作法，改成從頭尾開始去找，這樣便可以從共需要走訪 `1.5` 次佇列到只需要 `1` 次即可。 ```c= struct list_head *mergesort(struct list_head *l) { if (!l || !l->next) return l; struct list_head *first = l; struct list_head *last = l->prev; while (first != last && first->next != last) { first = first->next; last = last->prev; } struct list_head *l1 = l; struct list_head *l2 = first->next; l2->prev = l->prev; l1->prev = first; first->next = NULL; return mergelist(mergesort(l1), mergesort(l2)); } ``` 接下來我用 `qtest time` 去作效能測試，可以發現效能有明顯的提高 | | 改進前 | 改進後 | | -------- | -------- | -------- | | 100000 筆 | 1.140 | 0.123 | | 200000 筆 | 0.288 | 0.277 | | 300000 筆 | 0.472 | 0.449 | | 400000 筆 | 0.652 | 0.622 | | 500000 筆 | 0.824 | 0.797 | | 600000 筆 | 1.024 | 0.968 | | 700000 筆 | 1.219 | 1.189 | | 800000 筆 | 1.409 | 1.351 | #### q_descend 如果點 a 的右邊有比它的值還大的點就要把點 a 移除。關於 ```q_descend``` 的回傳值可以去 ```qtest.c``` 找，在 ```do_descend``` 裡可以看到這行 ```c if (exception_setup(true)) current->size = q_descend(current->q); ``` 表示 ```q_descend``` 要回傳佇列的長度。因為是雙向鏈結串列，所以可以從尾端開始走訪，在走訪的過程中若發現下一個點的值小於等於當前的點的值就移除。用 ```make test``` 進行測試時，發現之前的實作有誤，移除的點還要用 ```q_release_element``` 釋放空間。 :::warning 改進漢語表達 :notes: jserv ::: ```c= int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (head == NULL || list_empty(head)) return 0; element_t *first = list_entry(head->prev, element_t, list); element_t *second = list_entry(head->prev->prev, element_t, list); while (&second->list != head) { if (strcmp(first->value, second->value) < 0) { second = list_entry(second->list.prev, element_t, list); first = list_entry(first->list.prev, element_t, list); } else { list_del(&second->list); q_release_element(second); second = list_entry(first->list.prev, element_t, list); } } return q_size(head); } ``` #### q_merge ```queue_contex_t``` 是用來管理與其他佇列連接的結構，這邊的輸入 ```list_head *head``` 代表 ```list_head chain``` 的 ```head```。實作程式的想法是參考[你所不知道的 C 語言: linked list 和非連續記憶體: 案例探討: LeetCode 21. Merge Two Sorted Lists](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 的 Merge k Sorted Lists 的部分。因為在文中有提到直觀的想法是用第一條佇列接上剩下的佇列，這樣會導致第一條佇列愈來愈長，立即會遇到的問題是：多數的情況下合併速度會愈來愈慢。所以我採用的方法是分段合併 ```graphviz digraph G { { node[shape=none,label="interval = 1"]; i1 node[shape=none,label="interval = 2"]; i2 node[shape=none,label="interval = 4"]; i4 node[shape=none,label="interval = 8"]; i8 } interval1[label="<f0>L0|<f1>L1|<f2>L2|<f3>L3|<f4>L4|<f5>L5|<f6>L6|<f7>L7", shape=record, fixedsize=false,width=6] interval2[label="<f0>L01|<f1>|<f2>L23|<f3>|<f4>L45|<f5>|<f6>L67|<f7>", shape=record, fixedsize=false,width=6] interval4[label="<f0>L0123|<f1>|<f2>|<f3>|<f4>L4567|<f5>|<f6>|<f7>", shape=record, fixedsize=false,width=6] interval8[label="<f0>result|<f1>|<f2>|<f3>|<f4>|<f5>|<f6>|<f7>", shape=record, fixedsize=false,width=6] i1->i2[style=invis] i2->i4[style=invis] i4->i8[style=invis] interval1:f0 -> interval2:f0 interval1:f1 -> interval2:f0 interval1:f2 -> interval2:f2 interval1:f3 -> interval2:f2 interval1:f4 -> interval2:f4 interval1:f5 -> interval2:f4 interval1:f6 -> interval2:f6 interval1:f7 -> interval2:f6 interval1:f7 -> interval2:f7[style=invis] interval2:f0 -> interval4:f0 interval2:f2 -> interval4:f0 interval2:f4 -> interval4:f4 interval2:f6 -> interval4:f4 interval2:f7 -> interval4:f7[style=invis] interval4:f0 -> interval8:f0 interval4:f4 -> interval8:f0 interval4:f7 -> interval8:f7[style=invis] } ``` 第一層 ```for``` 迴圈數等同 $\lceil qsize(head)/2 \rceil$，裡面的 while 迴圈裡則是做兩兩合併的操作，```first``` 是第一個要合併的佇列，```second``` 是第二個要合併的佇列，```merge_two_list``` 會把兩個佇列合併，然後把結果存到 ```first``` 並回傳合併後佇列的長度，接下來把 ```NULL``` 賦值給空的 ```second``` 然後移到 ```head``` 的尾端，用來當作 ```while``` 迴圈的中止條件，最後 ```first``` 和 ```second``` 往下移一個節點繼續做合併。 ```c= int q_merge(struct list_head *head) { // https://leetcode.com/problems/merge-k-sorted-lists/ if (!head || list_empty(head)) return 0; else if (list_is_singular(head)) return q_size(list_first_entry(head, queue_contex_t, chain)->q); int size = q_size(head); int count = (size%2) ? size/2+1 : size/2; int queue_size = 0; for (int i = 0; i < count; ++i) { queue_contex_t *first = list_first_entry(head, queue_contex_t, chain); queue_contex_t *second = list_entry(first->chain.next, queue_contex_t, chain); while (first->q && second->q) { queue_size = merge_two_list(first->q, second->q); second->q = NULL; list_move_tail(&second->chain, head); first = list_entry(first->chain.next, queue_contex_t, chain); second = list_entry(first->chain.next, queue_contex_t, chain); } } return queue_size; } ``` 更新實作：因為 `second->q = NULL` 會造成 `memory leak` 所以改寫 `q_merge` 的 `while` 迴圈 ```c= while (!list_empty(first->q) && !list_empty(second->q)) { queue_size = merge_two_list(first->q, second->q); list_move_tail(&second->chain, head); first = list_entry(first->chain.next, queue_contex_t, chain); second = list_entry(first->chain.next, queue_contex_t, chain); } ``` 以及把 `merge_two_list` 函式裡面的 ```c= list_splice_tail(second, &temp_head) ``` 改成 ```c= list_splice_tail_init(second, &temp_head); ``` ### 在 qtest 新增 shuffle 命令在 `console.h` 可以發現以下 ```c= /* Add a new command */ void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter); #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) ``` `add_cmd` 會在命令列表中添加新命令，要新增一條新命令 `shuffle` 則要實作 `do_shuffle`，並在`qtest.c` 的 `console_init()` 替新命令加上 `ADD_COMMAND`。 ```c= ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", ""); ``` `qtest` 裡的 `do_shuffle` : 目前只有檢查輸入的佇列是否為空或只有一個節點 `q_shuffle` 要去 `queue.h` 新增 ```c= static bool do_shuffle(int argc, char *argv[]) { if (!current || !current->q) report(3, "Warning: Calling shuffle on null queue"); error_check(); if (q_size(current->q) < 2) report(3, "Warning: Calling shuffle on single queue"); error_check(); if (exception_setup(true)) q_shuffle(current->q); q_show(3); return !error_check(); } ``` shuffle 的實作分成兩個函式: `q_shuffle` 和 `swap` 在實作 `swap` 時要注意 : 1. ```node_1``` 總是在 ```node_2``` 之後 2. 當兩個要交換的節點是相鄰時不要做 ```list_move(node_2, node_1_prev)```，因為 `node_1_prev` 等於 `node_2`，如果做了 ```list_move(node_2, node_1_prev)``` 會把 `node_2` 這個節點移除。 ```c= static inline void swap(struct list_head *node_1, struct list_head *node_2) { if (node_1 == node_2) return; struct list_head *node_1_prev = node_1->prev; struct list_head *node_2_prev = node_2->prev; if (node_1->prev != node_2) list_move(node_2, node_1_prev); list_move(node_1, node_2_prev); } ``` 我的 `q_shuffle` 的想法是按照 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 提供的演算法： `new = last->prev` 是最後一個未被抽到的節點， `old` 是 `random` 出來的節點，將 `old` 和 `new` 交換，再將 `size` 減一，直到 `size` 變為零為止。 ```c= void q_shuffle(struct list_head *head) { if (!head || list_is_singular(head)) return; struct list_head *last = head; int size = q_size(head); while (size > 0) { int index = rand() % size; struct list_head *new = last->prev; struct list_head *old = new; while (index--) old = old->prev; swap(new, old); last = last->prev; size--; } return; } ``` 接下來利用腳本去測試對 `[1, 2, 3]` 執行 `shuffle` 的結果 ```c= Expectation: 166666 Observation: {'123': 166945, '132': 167113, '213': 166658, '231': 165775, '312': 166737, '321': 166772} ``` 可以從結果看到 `shuffle` 的結果分佈大致上是 `Uniform distribution`。 ### 研讀 Linux 核心原始程式碼的 lib/list_sort.c 先看到函式宣告的部分 ```c= /** * list_sort - sort a list * @priv: private data, opaque to list_sort(), passed to @cmp * @head: the list to sort * @cmp: the elements comparison function */ __attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp) ``` * [```__attribute__((nonnull()))```](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Function-Attributes.html): `compiler` 提供的 `attribute function`，可以指定該函式傳入第幾個變數必須是 `non-null`，否則會發出警告。 * `prev`: `private data`，`cmp` 的參數。 * `head`: 整個 `list` 的 `head`。 * `cmp`: `compare function`，用來決定 `sorting order`，是 `function pointer` 的型態。 `list_sort` 函式註解的部分跟[老師的筆記](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-e)大致相同 ``` * 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. ``` 主要是在做 `merge` 時，會將走訪過的節點維持在 `2:1` 的比例，其中 `2` 代表兩個已經排序過的佇列， `1` 代表新進來尚未排序的節點，也就是走訪到 `3∗2^k` 個 node 時才合併前面的兩個 `2^k` `sub-list`。這種作法在 `3∗2^k` 個節點能夠完全放進 `cache` 中的情況下能夠避免 `cache thrashing` 的發生。接下來就是程式碼的部分: 先把整個 `list` 的最後一個點的 `next` 指向 `NULL`: ```c= head->prev->next = NULL; ``` `count` 從零開始，代表 `pending list` 節點個數，每次加入一個節點到 `pending list` 就加一。配合前面的 `merge` 時機，只要該次迴圈的`count` 到 `count+1` 時，若 `count+1` 為 2^k^ 就不做 `merge`，反之則要做 `merge`。舉例來說: 1. count(二進位) 變化為 ```0011 -> 0100```，不做 `merge`。 2. count(二進位) 變化為 ```0010 -> 0011```，做 `merge`。由上述可以歸納出(以 0 ~ 16 為例)只要 `count` = `0000, 0001, 0011, 0111, 1111` 都不做 `merge`。接下來的程式用圖來舉例說明: * `pending`: 為 head of pending lists ，而 pending lists 是用於暫存待合併的 sub-list of lists，每一個 sub-list 的 size 都為 power of 2 的倍數，並且各個 sub-list 以 prev 連結。 * `tail`: 指標的指標，會指向 pending 裡準備要合併的 sub-list，要合併的 sub-list 是由 count 決定。 * `list`: 目前走訪到的 node。 ```c= 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); ``` 這邊舉個例子，由於不熟 `grapgviz`，所以先用 `drawio` 畫圖，之後有空會補。以實際例子來說，如果要排序一個佇列(4->1->2->3)，可以邊對照下方表格邊看圖解。 | count 變化 | count 二進位 | merge | pending 上的節點| | -------- | -------- | -------- | -------- | | 0 -> 1 | 0000 -> 0001 | no（$2^0$） | 1 | | 1 -> 2 | 0001 -> 0010 | no（$2^1$） | 1 + 1 | | 2 -> 3 | 0010 -> 0011 | yes | (2) + 1 | | 3 -> 4 | 0011 -> 0100 | no（$2^2$） | 2 + 1 + 1 | * 初始化 `count` 為零，所以第一個迴圈的 `count` 變化為 `0 -> 1`，看表可以知道不用做 `merge`，把 `pending` 和 `list` 往後讀一個節點。下圖為此次迴圈做到最後的結果。 ![](https://i.imgur.com/rAE2WU1.png) * 此次 `count` 變化為 `1 -> 2`，所以也不用做 `merge`，所以 `pending` 和 `list` 往後讀一個節點。最後整個佇列會如下圖: ![](https://i.imgur.com/8bueA7E.png) * `count` 變化為 `2 -> 3`，要做 `merge`。這邊的 `tail` 會指向 `pending` 的 address， ```c= struct list_head **tail = &pending; ``` 所以在執行下程式時 `a` 會在==上一張圖==的在 `1`，`b` 在 `4`，之後便是做 `merge`。然後 `merge` 會回傳合併之後的 `head` 並指派給 `a`，在本例中就是==下圖==的 `1`。在 `a->prev = b->prev` 中 `b->prev` 就是指向下一個 `sub-list` 的 `head`，本例中因為這就是第一個了所以是 `NULL`。最後 `*tail = a` 就是把 `pending` 指到 `a`，也就是 `1`。 ```c= 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; } ``` 此時的 `list` 指向下圖的 `2`，`pending` 指向下圖的 `1`，經過以下的運算可以得到下圖: ```c= list->prev = pending pending = list; list = list->next; pending->next = NULL; count++; ``` ![](https://i.imgur.com/5Hr0mLf.png) * `count` 的變化為 `3 -> 4`，不做 `merge`，所以跟前幾個相同，`pending` 和 `list` 往後讀一個節點。 ![](https://i.imgur.com/H8rihtv.png) * 由於 `list` 等於 `NULL`，所以跳出迴圈 `list` 指到與 `pending` 相同的節點後， `pending` 往前移一個節點。 ```c= list = pending; pending = pending->prev; ``` ![](https://i.imgur.com/kWz5EmT.png) * 進入 `for` 迴圈，`next` 指到 `pending->prev` 也就是下一個 `sub-list` 的 `head`，如果 `next != NULL` 就做對 `pending` 和 `list` 做 `merge`，然後 `pending` 指到 `next` 所指的節點也就是下一個 `sub-list` 的 `head`。 ![](https://i.imgur.com/bzzvC2I.png) * 下一次進入 `for` 迴圈因為 `next` 等於 `NULL`，所以跳出迴圈，對 `pending` 和 `list` 做 `merge_final`，此函式會先把最後的兩個佇列合併後，再把 `prev` 重建回來。 ![](https://i.imgur.com/94dOLFf.png) * 最後就可以得到整個排序的佇列了! ![](https://i.imgur.com/T6zcqi3.png) ### 比較 list_sort.c 與自己的 sort.c 效能差異先在 `qtest.c` 用 `add_param` 新增 `parameter` ```c= add_param("linux_sort", &enable_linux_list_sort, "Enable linux list sort", NULL); ``` `enable_linux_list_sort` 是在 `qtest` 宣告的全域變數 ```c= static int enable_linux_list_sort = 0; ``` 接下來修改部份 `do_sort` 程式： ```c= if (current && exception_setup(true)) { if (enable_linux_list_sort) list_sort(NULL, current->q, compare); else q_sort(current->q); } ``` 這樣就可以透過以下命令來切換要用哪個 `sort` ```c= option linux_sort 0 option linux_sort 1 ``` 接下來先修改 `queue.h` 其中 `likely 和 unlikely` 可以在 [compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 找到 ```c= # define likely(x) __builtin_expect(!!(x), 1) # define unlikely(x) __builtin_expect(!!(x), 0) typedef uint8_t u8; typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(); /** * list_sort - use linux list sort * @priv: private data, opaque to list_sort(), passed to @cmp * @head: the list to sort * @cmp: the elements comparison function */ void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp); /** * Compare - this function must return > 0 if @a should sort after * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should * sort before @b. */ int compare(void* priv, struct list_head *a, struct list_head *b); ``` 接下來是 `queue.c` 中的 `compare` 函式 ```c= int compare(void* priv, struct list_head *a, struct list_head *b) { element_t *ele_a = list_entry(a, element_t, list); element_t *ele_b = list_entry(b, element_t, list); return strcmp(ele_a->value, ele_b->value); } ``` 接下來比較的方式用 `perf` 來做測試參考 [blueskyson](https://hackmd.io/@blueskyson/linux2022-lab0#%E6%B8%AC%E8%A9%A6%E8%85%B3%E6%9C%AC) 的方式在 `lab0-c` 新增 `perf-traces` 目錄，裡面放了: ``` 100000.cmd 200000.cmd 300000.cmd 400000.cmd 500000.cmd ``` 前面的數字代表要幾個隨機字串，以 `100000.cmd` 為例 ```c= # sort 100000 random strings option linux_sort 0 new it RAND 100000 sort free ``` 以下是我的實驗結果: * 100000 筆 ```c= /* my merge sort */ Performance counter stats for './qtest -v 0 -f perf-traces/100000.cmd' (10 runs): 5,465,689 cache-misses # 42.893 % of all cache refs ( +- 3.47% ) 12,923,171 cache-references ( +- 1.43% ) 430,796,599 instructions # 1.26 insn per cycle ( +- 0.05% ) 350,214,286 cycles ( +- 1.42% ) 0.21634 +- 0.00417 seconds time elapsed ( +- 1.93% ) ---------------------------------------------------------------------------------------------------- /* linux list sort */ Performance counter stats for './qtest -v 0 -f perf-traces/100000.cmd' (10 runs): 4,715,115 cache-misses # 43.500 % of all cache refs ( +- 0.66% ) 10,830,099 cache-references ( +- 0.75% ) 434,026,705 instructions # 1.42 insn per cycle ( +- 0.02% ) 303,486,799 cycles ( +- 0.16% ) 0.193264 +- 0.000793 seconds time elapsed ( +- 0.41% ) ``` * 200000 筆 ```c= /* my merge sort */ Performance counter stats for './qtest -v 0 -f perf-traces/200000.cmd' (10 runs): 14,711,476 cache-misses # 50.953 % of all cache refs ( +- 0.54% ) 28,758,512 cache-references ( +- 0.16% ) 866,082,498 instructions # 1.23 insn per cycle ( +- 0.01% ) 703,121,988 cycles ( +- 0.16% ) 0.442772 +- 0.000732 seconds time elapsed ( +- 0.17% ) ---------------------------------------------------------------------------------------------------- /* linux list sort */ Performance counter stats for './qtest -v 0 -f perf-traces/200000.cmd' (10 runs): 12,785,220 cache-misses # 52.422 % of all cache refs ( +- 0.66% ) 24,082,873 cache-references ( +- 0.40% ) 876,536,039 instructions # 1.33 insn per cycle ( +- 0.06% ) 651,662,599 cycles ( +- 0.96% ) 0.41534 +- 0.00510 seconds time elapsed ( +- 1.23% ) ``` * 300000 筆 ```c= /* my merge sort */ Performance counter stats for './qtest -v 0 -f perf-traces/300000.cmd' (10 runs): 25,176,158 cache-misses # 53.992 % of all cache refs ( +- 0.40% ) 46,354,816 cache-references ( +- 0.14% ) 1,306,457,419 instructions # 1.18 insn per cycle ( +- 0.01% ) 1,099,759,769 cycles ( +- 0.14% ) 0.69770 +- 0.00257 seconds time elapsed ( +- 0.37% ) ---------------------------------------------------------------------------------------------------- /* linux list sort */ Performance counter stats for './qtest -v 0 -f perf-traces/300000.cmd' (10 runs): 21,191,601 cache-misses # 53.300 % of all cache refs ( +- 2.69% ) 38,848,369 cache-references ( +- 0.91% ) 1,322,133,992 instructions # 1.23 insn per cycle ( +- 0.03% ) 1,016,682,373 cycles ( +- 1.69% ) 0.6824 +- 0.0115 seconds time elapsed ( +- 1.69% ) ``` * 400000 筆 ```c= /* my merge sort */ Performance counter stats for './qtest -v 0 -f perf-traces/400000.cmd' (10 runs): 36,354,050 cache-misses # 56.179 % of all cache refs ( +- 0.36% ) 64,409,386 cache-references ( +- 0.20% ) 1,747,604,644 instructions # 1.16 insn per cycle ( +- 0.01% ) 1,498,409,395 cycles ( +- 0.13% ) 0.94878 +- 0.00400 seconds time elapsed ( +- 0.42% ) ---------------------------------------------------------------------------------------------------- /* linux list sort */ Performance counter stats for './qtest -v 0 -f perf-traces/400000.cmd' (10 runs): 30,814,049 cache-misses # 57.978 % of all cache refs ( +- 0.11% ) 53,256,480 cache-references ( +- 0.07% ) 1,771,579,815 instructions # 1.29 insn per cycle ( +- 0.00% ) 1,373,081,425 cycles ( +- 0.12% ) 0.86360 +- 0.00113 seconds time elapsed ( +- 0.13% ) ``` * 500000 筆 ```c= /* my merge sort */ Performance counter stats for './qtest -v 0 -f perf-traces/500000.cmd' (10 runs): 47,344,165 cache-misses # 56.546 % of all cache refs ( +- 0.18% ) 83,221,177 cache-references ( +- 0.18% ) 2,190,772,850 instructions # 1.14 insn per cycle ( +- 0.01% ) 1,905,805,048 cycles ( +- 0.13% ) 1.20848 +- 0.00371 seconds time elapsed ( +- 0.31% ) ---------------------------------------------------------------------------------------------------- /* linux list sort */ Performance counter stats for './qtest -v 0 -f perf-traces/500000.cmd' (10 runs): 40,109,266 cache-misses # 58.315 % of all cache refs ( +- 0.27% ) 68,806,922 cache-references ( +- 0.18% ) 2,219,682,272 instructions # 1.27 insn per cycle ( +- 0.00% ) 1,747,506,164 cycles ( +- 0.38% ) 1.09820 +- 0.00412 seconds time elapsed ( +- 0.37% ) ``` * 可以發現 `linux list sort` 的效能因為 `cache miss` 的次數明顯低於我實作的 `merge sort`，所以執行時間也比較快。 ### Valgrind 排除 qtest 執行時的記憶體錯誤發現在使用兩次以上的 `new` 後再做 `free` 會進入無限迴圈。利用 GDB+pwndbg 作測試，可以發現程式在 `is_circular` 這個函式無限迴圈 ```c= pwndbg> run Starting program: /home/will/linux2023/lab0-c/qtest cmd> new l = [] cmd> new l = [] cmd> free ^C Program received signal SIGINT, Interrupt. is_circular () at qtest.c:856 856 while (cur != current->q) { ``` 繼續往下看可以發現是在做 `do_free` 裡的 `q_show` 的 `is_circular` 進入無限迴圈的 ```c= ► f 0 0x555555556acc q_show+67 f 1 0x555555556acc q_show+67 f 2 0x5555555572a2 do_free+252 f 3 0x55555555a055 interpret_cmda+128 f 4 0x55555555a625 interpret_cmd+353 f 5 0x55555555b2e3 run_console+174 f 6 0x5555555593e2 main+1601 f 7 0x7ffff7c97083 __libc_start_main+243 ``` 最後仔細檢查可以發現 `q_free` 裡的 ```c= if (chain.size > 1) { qnext = ((uintptr_t) &current->chain.next == (uintptr_t) &chain.head) ? chain.head.next : current->chain.next; } ``` ```&current->chain.next``` 不用加 `&` 結果發現 sysprog/lab0-c 已經修正該錯誤了。 * trace-03-ops 的錯誤 ```c= +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, remove_head, reverse and merge ERROR: Freed queue, but 2 blocks are still allocated ==7825== 112 bytes in 2 blocks are still reachable in loss record 1 of 1 ==7825== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so) ==7825== by 0x10F3F4: test_malloc (harness.c:133) ==7825== by 0x10F8A0: q_new (queue.c:18) ==7825== by 0x10CD91: do_new (qtest.c:151) ==7825== by 0x10E066: interpret_cmda (console.c:181) ==7825== by 0x10E636: interpret_cmd (console.c:201) ==7825== by 0x10EA73: cmd_select (console.c:610) ==7825== by 0x10F37E: run_console (console.c:705) ==7825== by 0x10D3F3: main (qtest.c:1246) ==7825== --- trace-03-ops 0/6 ``` 實際去對 `trace-03-ops` 的每個指令去作測試，發現在對兩個 `new` 出來的佇列做 `merge` 時會跳出上述的問題，因此我推測是 `merge` 有什麼地方寫錯，後來發現 `q_merge` 裡的 `while` 迴圈的 `second->q = NULL` 是不對的。預期的輸出是若有兩個佇列 `a` 和 `b` 要和併到 `a`，把 `b` 的所有節點移到 `a` 時也要把 `b` 做初始化的動作，也就是要保留 `second->q`，所以如果直接做 `second->q ＝ NULL` 會造成 `memory leak` 的問題。重新修改程式後順利排除記憶體的所有問題 ```c= will@will:~/linux2023/lab0-c$ make valgrind # Explicitly disable sanitizer(s) make clean SANITIZER=0 qtest make[1]: Entering directory '/home/will/linux2023/lab0-c' rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.* rm -rf .dudect rm -rf *.dSYM (cd traces; rm -f *~) CC qtest.o CC report.o CC console.o CC harness.o CC queue.o CC random.o CC dudect/constant.o CC dudect/fixture.o CC dudect/ttest.o CC shannon_entropy.o CC linenoise.o CC web.o LD qtest make[1]: Leaving directory '/home/will/linux2023/lab0-c' cp qtest /tmp/qtest.5cWFNg chmod u+x /tmp/qtest.5cWFNg sed -i "s/alarm/isnan/g" /tmp/qtest.5cWFNg scripts/driver.py -p /tmp/qtest.5cWFNg --valgrind --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 5/5 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, remove_head, reverse and merge --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, swap, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort --- trace-05-ops 6/6 +++ TESTING trace trace-06-ops: # Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK --- trace-06-ops 6/6 +++ TESTING trace trace-07-string: # Test of truncated strings --- trace-07-string 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 +++ TESTING trace trace-10-robust: # Test operations on NULL queue --- trace-10-robust 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on insert_head --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on insert_tail --- trace-12-malloc 6/6 +++ TESTING trace trace-13-malloc: # Test of malloc failure on new --- trace-13-malloc 6/6 +++ TESTING trace trace-14-perf: # Test performance of insert_tail, reverse, and sort --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: # Test performance of sort with random and descending orders # 10000: all correct sorting algorithms are expected pass # 50000: sorting algorithms with O(n^2) time complexity are expected failed # 100000: sorting algorithms with O(nlogn) time complexity are expected pass --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of insert_tail --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant Probably constant time Probably constant time Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 100/100 ``` ### 論文閱讀：Dude, is my code constant time? [論文連結](https://eprint.iacr.org/2016/1123.pdf) [dudect Github](https://github.com/oreparaz/dudect) [參考](https://hackmd.io/E8DJnIryRwCo48uVQnuNDA?view) 這篇論文的貢獻是，透過自己開發的 dudect，一個透過統計分析的程式判斷程式是否是 constant-time 在給定的平台之下。實作可分為以下步驟: * A. Step 1: Measure execution time - a) `Classes definition`: 給定兩種不同類別的輸入資料，重複對方法進行測量，最常見的就是 fix-vs-random tests - b) `Cycle counters`: 現今的 CPU 提供的 cycle counters 可以很精準的獲得執行的時間。 - c) `Environmental conditions`: 為了減少環境的差異，每次測量都會對應隨機的輸入類別。 * B. Step 2: Apply post-processing - a) `Cropping`: 剪裁掉一些超過 threshold 的測量結果 - b) `Higher-order preprocessing`: Depending on the statistical test applied, it may be beneficial to apply some higherorder pre-processing * C. Step 3: Apply statistical test - a) `t-test`: Welch’s t-test，測試兩個平均數是否相同 - b) `Non-parametric tests`:(無母數統計分析): Kolmogorov-Smirnov ### dudect * 跟據作業說明：「在 [oreparaz/dudect](https://github.com/oreparaz/dudect) 的程式碼具備 `percentile` 的處理，但在 `lab0-c` 則無。」。所以我去對照發現 `lab0-c` 的 `fixture.c` 確實沒有實作，造成極端值沒有被去除，導致判斷結果出錯。 * 將 [oreparaz/dudect](https://github.com/oreparaz/dudect) 處理 `percentile` 的部分加入 `lab0-c` 的 `fixture.c` 後便可以正確分析 `insert_head`, `insert_tail`, `remove_head`, `remove_tail` 的執行時間。 ```c= static int cmp(const int64_t *a, const int64_t *b) { return (int) (*a - *b); } static int64_t percentile(int64_t *a, double which, size_t size) { qsort(a, size, sizeof(int64_t), (int (*)(const void *, const void *)) cmp); size_t array_position = (size_t)((double) size * (double) which); assert(array_position >= 0); assert(array_position < size); return a[array_position]; } /* set different thresholds for cropping measurements. the exponential tendency is meant to approximately match the measurements distribution, but there's not more science than that. */ static void prepare_percentiles(int64_t *percentiles, int64_t *exec_times) { for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) { percentiles[i] = percentile( exec_times, 1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)), N_MEASURES); } } ``` ### 引入 treesort [筆記連結](https://hackmd.io/@willwillhi/treesort)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.