--- # System prepended metadata title: 2025q1 Homework1 (lab0) --- # 2025q1 Homework1 (lab0) contributed by < `kurtislin` > ## Reviewed by BennyWang1007 1. 倉庫應使用 rebase 而不是直接 merge，如 commit `221c30e`、`4b811c7`等。 2. Commit 連結皆指向不屬於任何分支的 commit，例如 [3066919](https://github.com/sysprog21/lab0-c/commit/3066919ac0617bb76fa6680f5539b3a8f3ea6d47)，或許是 rebase 之類的操作導致。 3. 最後一部分應該為 `q_delete_dup`，標題錯誤。 4. `q_delete_dup` 可考慮改成只使用一層迴圈走訪鏈結串列，將與 `curr_elem` 重複的節點釋放，最後再將 `curr_elem` 釋放（若有重複），即可避免字串的複製，也不會產生懸空指標。 5. 注意排版以及句尾的句號。 6. Commit message 可以再更詳盡，例如 `q_reverseK`。 7. 缺乏的部分如 tiny web server 等，有空可以慢慢補上。 {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 開發環境 ```shell $gcc --version gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0 $lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 46 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 24 On-line CPU(s) list: 0-23 Vendor ID: GenuineIntel Model name: 13th Gen Intel(R) Core(TM) i7-13700 CPU family: 6 Model: 183 Thread(s) per core: 2 Core(s) per socket: 16 Socket(s): 1 Stepping: 1 CPU(s) scaling MHz: 55% CPU max MHz: 5200.0000 CPU min MHz: 800.0000 BogoMIPS: 4224.00 ``` ## 用linked list實做queue ### q_new,q_free [Commit 732fa62](https://github.com/kurtislin/lab0-c/commit/732fa6268fcaec33fa0a854a34b82b344461d512) `new` 和 `free` 是密切相關的操作 `q_new` 建立新的鍊結串列的節點 回傳初始化完成的queue `q_free` 遍歷鍊結串列 釋放所有節點 最後還要釋放head ### q_insert_head , q_insert_tail [Commit aab9360](https://github.com/kurtislin/lab0-c/commit/aab93606010b3fe58c8fc874b6ed48a817722327) `q_insert_head` 在佇列的頭部插入新元素 `q_insert_tail` 在佇列的尾部插入新元素 * 首先檢查輸入參數的有效性 * 為新元素分配記憶體 * 為字串值創建一個副本 * 使用 `list.h` 中定義的 `list_add` 函數將節點添加到頭部 * 返回操作結果 ### q_size,q_remove_head,q_remove_tail [Commit 3066919](https://github.com/kurtislin/lab0-c/commit/3066919ac0617bb76fa6680f5539b3a8f3ea6d47) `q_size` 在計算佇列裡的元素數量 `q_remove_head`,`q_remove_tail` 在移除佇列的頭部元素和尾部元素 在實作 `q_remove_head` 和 `q_remove_tail` 函數時，我們採用輸出參數模式，透過 sp 緩衝區參數和返回值同時提供元素指針與元素內容。這種設計讓單一函數調用能夠返回多種資訊，提升了函數的靈活性，使調用者可根據需求選擇獲取所需的資料形式。 ### q_reverse [Commit c04198f](https://github.com/kurtislin/lab0-c/commit/c04198f5af66efa42886378fc6845161f9c46e49) `q_reverse`將佇列所有元素反轉 ### q_swap [Commit a46fa1d](https://github.com/kurtislin/lab0-c/commit/a46fa1d96caec6600d0eb6a452cf42be63dc44b1) `q_swap` 將相鄰的節點交換 ### q_delete_mid q_reverseK [Commit d3a52e3](https://github.com/kurtislin/lab0-c/commit/d3a52e3ce7b88315fb6d54977c970a591907aa02) `q_delete_mid` 利用快慢指標實現 `q_reverseK` 利用`temporary list` 實現，在`q_reverseK` 函數中，我使用了 `struct list_head temp_head` 而不是指標 `struct list_head *temp_head` 來宣告臨時頭節點，主要有以下原因： #### 堆疊（Stack）分配 vs. 堆（Heap）分配: 直接宣告 `struct list_head temp_head` 會在函數的堆疊上分配記憶體 使用指標 `struct list_head *temp_head` 則需要使用 `malloc` 從堆中分配記憶體，並在使用完後需要 `free` 堆疊分配更快速，也不需要擔心記憶體洩漏 ### q_delete_dup [Commit a290040](https://github.com/kurtislin/lab0-c/commit/a29004075c0c873749788b72e1ba990cb751aee7) ```c bool q_delete_dup(struct list_head *head) { if (!head || list_empty(head)) return false; bool removed = false; struct list_head *node = head->next; while (node != head && node->next != head) { element_t *curr_elem = list_entry(node, element_t, list); element_t *next_elem = list_entry(node->next, element_t, list); if (!strcmp(curr_elem->value, next_elem->value)) { removed = true; char *dup_val = curr_elem->value; while (node != head) { element_t *check_elem = list_entry(node, element_t, list); if (!strcmp(check_elem->value, dup_val)) { struct list_head *tmp = node->next; list_del(node); q_release_element(check_elem); node = tmp; } else break; } } else node = node->next; } return removed; } ``` 以上是我一開始的代碼但是不管怎麼測試都會剩下一個元素 測試資料中沒有要刪除的元素時也會有以下問題 ```shell l = [1 2 3 4] cmd> dedup ERROR: Calling delete duplicate on null queue ``` 之後發現問題是出現在執行`q_release_element(check_elem)`時，釋放了元素的記憶體，包括 `check_elem->value`。但是`dup_val` 指針是指向 `curr_elem->value`，所以造成懸空指標，之後改成`char *dup_val = strdup(curr_elem->value);`就可以了 ### q_sort 和 merge sort 實作 [Commit f32ba44](https://github.com/kurtislin/lab0-c/commit/f32ba44ca9fa33a7143a0b43b7286328e80b18f3) `q_sort` 使用 merge sort 演算法來排序，整個實作分成三個主要的 helper functions： #### merge_sort() 遞迴式的 merge sort 主體，採用分治法的概念。先把鏈結串列切成兩半，各自排序後再合併。時間複雜度是 O(n log n)，對鏈結串列來說效率不錯。 #### split_list() 用快慢指標的技巧把鏈結串列分成兩半。慢指標走一步，快指標走兩步，當快指標到底時慢指標就在中間位置。這樣可以在一次遍歷中找到分割點。 #### merge_lists() 把兩個已排序的鏈結串列合併成一個。比較兩個串列的頭部元素，選較小（或較大）的放到結果中，重複到其中一個串列空了為止，剩下的直接接上去。 整個 merge sort 的設計很適合鏈結串列，因為不需要額外的記憶體空間，只要重新連接指標就行了。 ### q_ascend, q_descend, q_merge [Commit 9c0d6d0](https://github.com/kurtislin/lab0-c/commit/9c0d6d03513683f5f66c08e2efb97a7cb6b74045) **q_ascend()** 和 **q_descend()** 都用了單調棧的概念，從尾部開始往前掃描，只保留符合條件的節點。ascend 會移除右邊有更小值的節點，descend 則相反。 **q_merge()** 把多個佇列合併成一個，先把所有元素收集到第一個佇列裡，最後用 q_sort 排序。實作上比較直觀，就是先合併再排序。 ## Valgrind 記憶體分析 使用 `make valgrind` 進行動態記憶體分析 ### 測試結果 ``` --- TOTAL 100/100 ``` ## 研讀 lib/list_sort.c 並比較實作的sort ### 閱讀 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) [Linux核心的鏈接串列排序](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-e) **發現**： 1. 使用 bottom-up merge sort 而非 recursive 2. Power-of-two 合併策略：確保每次合併都是 2:1 平衡的 可避免極端情況 例如 1024個已排序好的元素 再去合併4個元素 3. 使用位元運算追蹤合併狀態 4. 設計考慮 cache-friendly 的合併順序 ```c=226 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()` 是一個編譯器優化提示，用於分支預測優化。 `likely(bits)` 告訴編譯器這個條件很可能為真，從而進行以下優化： 1. **分支預測**：CPU 會傾向於預測條件為真，減少管線停頓 2. **程式碼布局**：將 `if` 區塊放在較近的記憶體位置，提高快取命中率 3. **管線優化**：減少分支預測錯誤時的效能懲罰 這種優化在高頻執行的程式碼路徑中特別有效。 ### 比較原本的sort 和 list_sort.c #### 在queue.c加入切換機制 [Commit 83a61cb](https://github.com/kurtislin/lab0-c/commit/83a61cbca932253cfe90a966d003c99414b3f471) **實作內容**： 1. **新增 ksort 命令**：切換排序演算法 - `ksort 0`: 原版 merge sort - `ksort 1`: Linux kernel list_sort 2. **新增 benchmark 命令**： - 支援多種資料分布：random, sorted, reverse, partial - 使用 `clock_gettime(CLOCK_MONOTONIC)` - 自動計算加速比並報告結果 3. **修改檔案**： - `queue.c`: 加入 `q_set_kernel_sort()` 和比較函數 - `qtest.c`: 實作 `do_ksort()` 和 `do_benchmark()` 命令 - `Makefile`: 加入 `list_sort.o` 編譯目標 - 新增 `list_sort.c/h`: Linux kernel 排序實作 ### benchmark 命令使用範例 #### 基本語法 ```bash ./qtest > benchmark [distribution_type] ``` #### 使用範例 ```bash # 測試 1000 個隨機元素 > benchmark 1000 random # 測試 5000 個已排序元素 > benchmark 5000 sorted # 測試 10000 個反向排序元素 > benchmark 10000 reverse # 測試 2000 個部分排序元素（80% 已排序 + 20% 隨機） > benchmark 2000 partial ``` #### 支援的分布類型 - `random` (預設): 隨機生成的元素 - `sorted`: 預先排序好的元素（升序） - `reverse`: 反向排序的元素（降序） - `partial`: 部分排序的元素（80% 已排序 + 20% 隨機） #### 範例輸出 ``` Benchmarking with 10000 elements (random distribution) Original merge sort: 2.45 ms Linux kernel list_sort: 1.89 ms Speedup: 1.30x (Linux kernel is 29.6% faster) ``` #### 切換排序演算法 ```bash # 使用原版 merge sort > ksort 0 # 使用 Linux kernel list_sort > ksort 1 # 確認當前使用的演算法 > help ksort ``` 這個commit我是用clock_gettime 去取得時間 但是執行 benchmark 10000 random 幾次後 發現每次的結果差異都不小(包含效能提升比例) #### 測試結果 以下是用10000個測試資料的時候的結果 結果都是kernel sort更快 差異最小的是1.26倍 差異最大的是1.5倍 後續數量改為500k 和100k 的結果也差不多 ```bash cmd> benchmark 10000 random === Benchmark Results === Data size: 10000 elements Distribution: random Original merge sort: 7.343 ms Linux kernel list_sort: 5.837 ms Kernel sort is 1.26 times faster cmd> benchmark 10000 random === Benchmark Results === Data size: 10000 elements Distribution: random Original merge sort: 8.219 ms Linux kernel list_sort: 5.483 ms Kernel sort is 1.50 times faster ```