# 2023q1 Homework1 (lab0) contributed by < `Korin777` > ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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): 20 On-line CPU(s) list: 0-19 Vendor ID: GenuineIntel Model name: 12th Gen Intel(R) Core(TM) i7-12700H CPU family: 6 Model: 154 Thread(s) per core: 2 Core(s) per socket: 14 Socket(s): 1 Stepping: 3 CPU max MHz: 4700.0000 CPU min MHz: 400.0000 BogoMIPS: 5376.00 Caches (sum of all): L1d: 544 KiB (14 instances) L1i: 704 KiB (14 instances) L2: 11.5 MiB (8 instances) L3: 24 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-19 ``` ## 開發過程 ### `q_new` ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` 建立一個新的佇列， 透過 `INIT_LIST_HEAD` 巨集來初始化佇列的 `head` ， 這個 `head` 不儲存值且在新增及移除時不會改變 ， 它用來對應到 `queue_contex_t` 的 `q` ### q_free ```c void q_free(struct list_head *l) { if (!l) return; element_t *itr, *safe; list_for_each_entry_safe (itr, safe, l, list) { q_release_element(itr); } free(l); } ``` * 透過 `list_for_each_entry_safe` 來走訪佇列並釋放 memory ， 最後在釋放 `head` * `list_for_each_entry_safe` 透過 `save` pointer 來事先存好要被釋放的 element 的下一個 element ， 讓我們可以釋放記憶體 ### q_insert_head ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *ele = malloc(sizeof(element_t)); if (!ele) return false; ele->value = strdup(s); if (!ele->value) { free(ele); return false; } list_add(&ele->list, head); return true; } ``` * 配置 `element_t` 及 `value` 的記憶體，透過 `list_add` 將它插入佇列的開頭(head->next) ### q_insert_tail ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *ele = malloc(sizeof(element_t)); if (!ele) return false; ele->value = strdup(s); if (!ele->value) { free(ele); return false; } list_add_tail(&ele->list, head); return true; } ``` * 配置 `element_t` 及 `value` 的記憶體，透過 `list_add_tail` 將它插入佇列的尾端(head->prev) ### q_remove_head ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *ele = list_first_entry(head, element_t, list); list_del(&ele->list); if (sp) { size_t n = strlen(ele->value) + 1; n = bufsize < n ? bufsize : n; strncpy(sp, ele->value, n); sp[n - 1] = '\0'; } return ele; } ``` * 透過 `list_first_entry` 取出開頭的值並複製到 `sp` ，在透過 `list_del` 移除開頭 * `n` 用來決定要複製多少字元，並確保包含結束字元 ### q_remove_tail ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *ele = list_last_entry(head, element_t, list); list_del(&ele->list); if (sp) { size_t n = strlen(ele->value) + 1; n = bufsize < n ? bufsize : n; strncpy(sp, ele->value, n); sp[n - 1] = '\0'; } return ele; } ``` * 與 `q_remove_head` 類似 ， 這裡用 `list_last_entry` 取出尾端 ### q_size ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; size_t n = 0; struct list_head *itr; list_for_each (itr, head) ++n; return n; } ``` * 走訪整個佇列來記錄經過的節點數 ### q_descend ```c int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head)) return 0; int count = 1; struct list_head *itr = head->prev, *safe; char *cur_max = list_entry(itr, element_t, list)->value; for (itr = itr->prev, safe = itr->prev; itr != head; itr = safe, safe = itr->prev) { char *tmp = list_entry(itr, element_t, list)->value; if (strcmp(tmp, cur_max) >= 0) { cur_max = tmp; ++count; } else { list_del(itr); q_release_element(list_entry(itr, element_t, list)); } } return count; } ``` * 透過 prev 從佇列尾端開始走訪，記下當前的最大值並把後續遇到比它小的節點刪除，確保佇列是遞減的 ### q_delete_mid ```c bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return false; struct list_head *ahead = head->next, *back = head->prev; while (ahead != back && ahead != back->prev) { ahead = ahead->next; back = back->prev; } list_del(ahead); element_t *ele = list_entry(ahead, element_t, list); q_release_element(ele); return true; } ``` * 透過一個從開頭一直往後走的 pointer 及從尾端一直往前走的 pointer 找出 middle node *節點數為奇數時 ， middle節點就是相遇的 node *節點數為偶數時 ， middle節點是在兩 pointer 相鄰時往前的 pointer ### q_merge :::warning 避免張貼完整程式碼，你只要列出值得討論以及後續可改進的部分即可。 :notes: jserv ::: ```c struct list_head *itr, *safe, *q_finalhead = list_entry(head->next,queue_contex_t,chain)->q; struct list_head *tmp = q_finalhead->next; while(head-> next != head->prev) { if(tmp != q_finalhead) { char *cur_min = list_entry(tmp,element_t,list)->value; struct list_head *cur_q = q_finalhead, *cur_chain = NULL; for (itr = head->next->next, safe = itr->next; itr != head; itr = safe, safe = itr->next) { struct list_head *q_head = list_entry(itr,queue_contex_t,chain)->q; char *q_min = list_entry(q_head->next,element_t,list)->value; if(strcmp(q_min,cur_min) < 0) { cur_min = q_min; cur_q = q_head; cur_chain = itr; } } if(q_finalhead != cur_q) { list_move(cur_q->next,tmp); if(list_empty(cur_q)) list_del(cur_chain); } else { tmp = tmp->next; } } else { char *cur_min = NULL; struct list_head *cur_q= NULL, *cur_chain = NULL; for (itr = head->next->next, safe = itr->next; itr != head; itr = safe, safe = itr->next) { struct list_head *q_head = list_entry(itr,queue_contex_t,chain)->q; char *q_min = list_entry(q_head->next,element_t,list)->value; if(!cur_min) { cur_min = q_min; cur_q = q_head; cur_chain = itr; } else if(strcmp(q_min,cur_min) < 0) { cur_min = q_min; cur_q = q_head; cur_chain = itr; } } list_move_tail(cur_q->next,tmp); if(list_empty(cur_q)) { list_del(cur_chain); } } } ``` * 每次找出所有佇列中最小值 `cur_min` ，若 `cur_min` 不再第一個佇列中，就把它所在的節點移到 `tmp(第一個佇列尚未 merge 完成的 node)` 前面，否則將 `tmp` 移動到下一個節點。當 `tmp` 回到開頭表示第一個佇列的值都 merge 完成，之後 `cur_min` 所在的節點都改為移到 `tmp` 的尾端。 * 測試時發現會因為 `queue_contex_t` 的 size 沒有被改到而產生錯誤，沒被改到的原因為我將第一個以外的佇列都移除，所以 chain 的 size 剩 1，導致 `do_merge` 無法更新 merge 後的 size 也無法釋放被我移除的佇列的 head 記憶體 ```c struct list_head *q_merge = list_entry(head->next, queue_contex_t, chain)->q; for (struct list_head *c_itr = head->next->next; c_itr != head; c_itr = c_itr->next) { struct list_head *q_itr, *safe, *q_other = list_entry(c_itr, queue_contex_t, chain)->q, *node_merge = q_merge->next; list_for_each_safe (q_itr, safe, q_other) { while (node_merge != q_merge) { if (strcmp(list_entry(q_itr, element_t, list)->value, list_entry(node_merge, element_t, list)->value) <= 0) { break; } else node_merge = node_merge->next; } list_add_tail(q_itr, node_merge); } INIT_LIST_HEAD(q_other); } ``` * 改為將其他的佇列依序跟第一個佇列merge，由於其他佇列的節點最後都會被移除，所以直接用 `INIT_LIST_HEAD` 來讓佇列不再與任何節點連接 ### q_sort ```c void q_sort(struct list_head *head) { if (!head || list_empty(head) || head->next == head->prev) return; struct list_head less, greater; INIT_LIST_HEAD(&less); INIT_LIST_HEAD(&greater); struct list_head *pivot = head->next; char *pivot_val = list_entry(pivot, element_t, list)->value; list_del(pivot); struct list_head *itr, *safe; list_for_each_safe (itr, safe, head) { if (strcmp(list_entry(itr, element_t, list)->value, pivot_val) <= 0) list_add(itr, &less); else list_add(itr, &greater); } q_sort(&less); q_sort(&greater); INIT_LIST_HEAD(head); list_add(pivot, head); list_splice(&less, head); list_splice_tail(&greater, head); } ``` * 參考[第 1 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz1)實作的 quick sort ， 將佇列的第一個節點當作 pivot ， 其餘的節點分別放入 `greater`(value 比 pivot 大)、`less`(value 比 pivot 小) 這兩個佇列， 遞迴去繼續將這兩個佇列分割直到佇列不超過一個節點，最後將 `less` 、 `pivot` 、 `greater` 接起來的佇列就會是排序好的 * 這裡使用到 `list_for_each_safe` 是由於 `list_add` 會更換 `itr` 的下一個節點， 所以先將它儲存在 `safe` 。在測驗題中最後連接排序好的佇列之前漏掉了 `INIT_LIST_HEAD` ， 由於 `head` 連接的節點已經被連接到排序好的 `less` 及 `greater` 中，所以要先斷開原本的連接。 * 這個實作在跑測試案例 `trace14` 、 `trace15` 會產生 `ERROR: Time limit exceeded` 。在 `trace14` 中，插入了許多相同的資料，因此在分割時會集中在其中一個 queue; 在 `trace15` 中，經過 sort 後資料就已經被排序完成， 因為這裡 pivot 固定選擇第一個節點， 所以資料也會集中在其中一個佇列。 當分割的資料幾乎都在其中一個佇列中，就使 quick sort 的時間複雜度從 $O(nlogn)$ 變成 $O(n^2)$ ```c void q_sort(struct list_head *head) { if (!head || list_empty(head) || head->next == head->prev) return; struct list_head less, greater, middle; INIT_LIST_HEAD(&less); INIT_LIST_HEAD(&greater); INIT_LIST_HEAD(&middle); struct list_head *pivot = head->next; char *pivot_val = list_entry(pivot, element_t, list)->value; list_del(pivot); struct list_head *itr, *safe; list_for_each_safe (itr, safe, head) { int result = strcmp(list_entry(itr, element_t, list)->value, pivot_val); if (result < 0) list_add(itr, &less); else if(result > 0) list_add(itr, &greater); else { list_add(itr,&middle); } } q_sort(&less); q_sort(&greater); INIT_LIST_HEAD(head); list_add(pivot, head); list_splice(&middle,head); list_splice(&less, head); list_splice_tail(&greater, head); } ``` * 為了解決大量相同資料的問題，新增一個佇列 `middle` 用來儲存與 pivot 相同的節點， middle 後續不在進行 quick sort ， 測試後可以通過 `trace14` ```c void q_sort(struct list_head *head) { if (!head || list_empty(head) || head->next == head->prev) return; struct list_head less, greater, middle; INIT_LIST_HEAD(&less); INIT_LIST_HEAD(&greater); INIT_LIST_HEAD(&middle); struct list_head *pivot = head->next; char *pivot_val = list_entry(pivot, element_t, list)->value; list_del(pivot); struct list_head *itr, *safe; bool less_change = true, greater_change = true; list_for_each_safe (itr, safe, head) { int result = strcmp(list_entry(itr, element_t, list)->value, pivot_val); if (result < 0) { if (less_change) list_add(itr, &less); else list_add_tail(itr, &less); less_change = !less_change; } else if (result > 0) { if (greater_change) list_add(itr, &greater); else list_add_tail(itr, &greater); greater_change = !greater_change; } else { list_add(itr, &middle); } } q_sort(&less); q_sort(&greater); INIT_LIST_HEAD(head); list_add(pivot, head); list_splice(&middle, head); list_splice(&less, head); list_splice_tail(&greater, head); } ``` * 因為選的 pivot 固定是第一個節點， 當佇列接近排序好的狀態(遞增或遞減) 就會使目前及後續的分割高度集中於其中一個 queue * 透過交互插入開頭及尾端的方式來打亂佇列中的節點， 使得下次選擇 pivot 時不會固定是佇列中最大或最小的來避來避免分割不平均的問題。測試後可以通過 `trace15` > [commit e7a6b70](https://github.com/Korin777/lab0-c/commit/e7a6b70cca766e02cf67b2d2c00dd2fba6d7bcd2) 參考 [linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)，新增 merge sort 的實作，並在 `qtest` 新增 `do_sortOption` 命令來切換排序的演算法 :::warning 若要改寫為非遞迴的排序，你打算如何進行？ :notes: jserv ::: #### 非遞迴 buttom-up mergesort [commit c44b1f4](https://github.com/Korin777/lab0-c/commit/c44b1f4daf1b7f64015ea41821be3d2add3ac895) 我的第一個想法是改用 buttom-up 去實作，去年[實作](https://hackmd.io/ae7DfZuiRW6wyn83y4UjNw?view#q_sort)的結果會因為 linked list 無法像陣列那樣直接取得某個位置的值，而產生許多不必要的走訪。 現在想想其實可以先不要將 `prev` 節點連接好，因為除了最後一次 merge ， 前面連接好的節點都可能會被重連 ， 所以可以等到最後再去重連 `prev` 節點 ， 有了 `prev` 節點我們就可以拿他來直接連到下一個要 merge 的區塊，來避免原本要經過多個節點才能到達下一個 merge 區塊 | bottom-up | time | cycles | instructions | cache-misses | cache-refrences | strcmp call | |--|--|--|--|--|--|--| | 改進前 |1.43996s|54,3498,5237|20,3342,1308|3180,7854|6983,8528|18715660| | 改進後 |1.09312s|43,7429,6136|17,7845,9395|2541,9759|4210,4296|18715660| 上面是排序一百萬資料的結果，執行時間降低了不少，但比遞迴 top-down merge sort 還慢 #### 非遞迴 top-down mergesort [commit fff99f4](https://github.com/Korin777/lab0-c/commit/fff99f4d2dab3c9b1764b7ce2722f17af7f93164) 這裡試著實現非遞迴的 top-down mergesort ， 想法也是跟上面一樣透過 `prev` 節點來連接合併好的區塊，並且額外在利用合併好的區塊的第二個節點的 `prev` 來紀錄這個區塊的大小，每次合併完就去看前面有沒有大小相同的區塊，有的話就繼續合併下去，主要是想模擬 top-down merge sort 會跟前一個區塊合併的行為 | top-down | time | cycles | instructions | cache-misses | cache-refrences | strcmp call | |--|--|--|--|--|--|--| | 遞迴 |0.71662s |29,7889,3727|18,9145,7316|1373,0805|3967,0762|18673584| | 非遞迴 |0.69153s|29,2025,8297|17,8725,7508|1306,4755|3145,8093|18715660| 可以觀察到 `strcmp` 的次數不一樣，想想當節點有奇數個時，這個方法最後一個孤立的節點會跟 buttom-up 一樣固定在最後，但 top-down 的位置卻不一定，顯然我的方法只是一個會額外先合併相同大小的 buttom-up merge sort ， 而跟原本遞迴的實作相比有好一些 不過若跟上面改進後的 buttom-up 實作相比，這裡的實作執行時間又降低了不少，可以觀察到 cache-misses 低了不少，我覺得應該跟先去合併相同大小的區塊這點有關 --- ### 引入 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) [commit 471ded9](https://github.com/Korin777/lab0-c/commit/471ded9a390aa75591110937848758df3d1e9754) 一開始 git commit 時無法成功，錯誤訊息如下： ``` list_sort.c:15:19: error: Null pointer dereference: (struct element_t*)0 [nullPointer] return strcmp(list_entry(a, element_t, list)->value, ^ list_sort.c:16:19: error: Null pointer dereference: (struct element_t*)0 [nullPointer] list_entry(b, element_t, list)->value); ``` 上面的 `(struct element_t*)0` 對應到 `container_of` 巨集的 `(((type *) 0))` ，而 cppcheck 所檢測出來的問題就是我們對 0 dereference `(((type *) 0)->member)`，不過之前在 queue.c 也有用到 `list_entry` 卻還是可以 commit 成功，看了 `scripts/pre-commit.hook` 可以發現裡面有一行 `--suppress=nullPointer:qtest.c` ， 參閱 [Cppcheck manual](https://cppcheck.sourceforge.io/manual.pdf) 了解到他的用途是過濾掉產生的錯誤 ， 而透過 `--inline-suppr` 我們也可以透過 `suppression comment` 過濾掉 cppcheck 偵測出來的錯誤，最後也透過 Inline suppressions 的方式成功將 `list_sort` 引入，另外也在 `qtest.c` 中新增 `list_sort` 命令來使用它 #### 效能比較 [commit e87aba6](https://github.com/Korin777/lab0-c/commit/e87aba629e912497cde69ee91935d02d08a70cc4) 參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#%E6%AF%94%E8%BC%83-liblist_sortc-%E5%92%8C%E8%87%AA%E5%B7%B1%E5%AF%A6%E4%BD%9C%E7%9A%84-merge-sort) 撰寫測試程式產生排序用的資料，確保比較時排序的資料是相同的，並透過 perf 工具比較效能，排序一百萬筆隨幾產生的字串(每個字串為 5~10 個小寫字母組成)之結果如下 | 排序方式 | time | cycles | instructions | cache-misses | cache-refrences | strcmp call | |--|--|--|--|--|--|--| |my quicksort|0.73528s|30,5216,0933|21,6207,6539|3036,8419|6249,1175|24880386| | linux list_sort |0.43839s|18,5576,2153|18,6235,4913|1262,4588|3827,9864|18686563| | my_mergesort |0.71662s |29,7889,3727|18,9145,7316|1373,0805|3967,0762|18673584| | my_mergesort 更改後 |0.52061s |21,2301,7352|17,8158,6690|1591,8822|5125,5537|18673584| 可以發現雖然 instructions 差不多，但我的實作 cycles 卻高出 `list_sort` 許多，顯然我的實作未考慮現代處理器特性，而在 cache-misses 的變現在我的實作偏高，至於排序過程中比較的次數，兩者都相當接近於 $O(n \ log n)$ ```diff static struct list_head *merge(struct list_head *a, struct list_head *b) { - // ptr : Update list_head->next to link node - // node : Each comparison will advance one either a or b - struct list_head *head = NULL, **ptr = &head, **node; - for (; a && b; *node = (*node)->next) { - node = strcmp(list_entry(a, element_t, list)->value, - list_entry(b, element_t, list)->value) <= 0 - ? &a - : &b; - *ptr = *node; - ptr = &(*ptr)->next; + struct list_head head; + struct list_head *h = &head; + + while(a && b) { + if(strcmp(list_entry(a, element_t, list)->value, + list_entry(b, element_t, list)->value) <= 0) { + h->next = a; + a = a->next; + a = a->next; + } else { + h->next = b; + b = b->next; + } + h = h->next; } - *ptr = (struct list_head *) ((uintptr_t) a | (uintptr_t) b); - return head; + + h->next = (struct list_head *) ((uintptr_t)a | (uintptr_t)b); + return head.next; } ``` 觀摩 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_sort) 的開發紀錄，發現他 merge sort 的實作執行時間跟 cycle 與 linux `list_sort` 相當接近，而他跟我 merge sort 的不同主要在 `merge` 的實作，這裡也改進了最後 `h->next` 所造成的分支 從上面的表格可以發現，執行時間與 cycles 確實降低了，但 cache-misses 卻增加了，不知道是什麼原因造成的 我也發現如果透過 `-O3` 最佳化來編譯，運用指標得指標就不會比更改後的 merge sort 差了，同時又能精簡程式碼
Last changed by  
 
Korin777
329

Read more

2023q1 Homework7 (ktcp)

contributed by < Korin777 > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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

5/8/2023
2023q1 Homework5 (quiz5)

contributed by < Korin777 > 測驗題目 測驗一 運作原理 pool_malloc 透過 get_loc_to_place 從 memory pool 的 free block 中配置記憶體給使用者 配置記憶體的大小會根據 32 bits 或 64 bits 進行 round up

4/21/2023
2023q1 Homework4 (quiz4)

contributed by < Korin777 > 測驗題目 測驗三 RB_LOG2_MAX_NODES node_t 的大小為 sizeof(void*) * 4 所以 node 最多有 $$\frac{1 << (sizeof(void ) << 3)} {(sizeof(void) * 4)}$$ 取 log2 可以得到 RB_LOG2_MAX_MEM_BYTES - log2(sizeof(void*)*2) - 1，若 sizeof(void*) == 8 就會是 RB_LOG2_MAX_MEM_BYTES - 4 - 1 tree_insert 這裡透過 path 來記錄插入節點的所有祖先節點，所以節點不須記錄自己的親代節點也能在插入後向上修復紅黑數，遇到黑色節點就可以停下，因為只有紅色節點可能會違反規則

4/8/2023
2023q1 Homework3 (quiz3)

contributed by < Korin777 > 測驗四 int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x > 0xFFFF) << 4; x >>= r;

3/15/2023
Read more from Korin777
Published on HackMD