# 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 %}
## 開發環境

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

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

以上是我一開始的代碼但是不管怎麼測試都會剩下一個元素

測試資料中沒有要刪除的元素時也會有以下問題

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 的合併順序

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 命令使用範例

#### 基本語法

./qtest
> benchmark <size> [distribution_type]

#### 使用範例

# 測試 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)

#### 切換排序演算法

# 使用原版 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 的結果也差不多

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