# 2025q1 Homework1 (lab0)
contributed by < [BennyWang1007](https://github.com/BennyWang1007) >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
架構：                    x86_64
  CPU 作業模式：          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
供應商識別號：            GenuineIntel
  Model name:             12th Gen Intel(R) Core(TM) i7-12700H
    CPU 家族：            6
    型號：                154
    每核心執行緒數：      2
    每通訊端核心數：      14
    Socket(s):            1
    製程：                3
    CPU(s) scaling MHz:   23%
    CPU max MHz:          4700.0000
    CPU min MHz:          400.0000
    BogoMIPS:             5376.00
Virtualization features:  
  虛擬：                  VT-x
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 節點：             1
  NUMA node0 CPU(s)：     0-19

## 針對佇列操作的程式碼實作

### q_new
> Commit [1414f73](https://github.com/BennyWang1007/lab0-c/commit/1414f73beabb6d61d56c64da7411ac5ea088fefe)

此函式會創建一個全新的、初始為空的佇列，實作如下
1. 使用`malloc`申請一個`list_head`節點的空間，若申請失敗則返回`NULL`
2. 使節點的`prev`和`next`皆指向自己，滿足雙向鏈結串列的定義

### q_free
> Commit [1414f73](https://github.com/BennyWang1007/lab0-c/commit/1414f73beabb6d61d56c64da7411ac5ea088fefe)

此函式會移除並釋放佇列中的所有節點，實作過程如下
1. 首先判斷 head 是否為 `NULL`，若空則返回
2. 接著遍歷整個 `queue`，釋放將所有節點的 `value` 和節點本身

### q_insert_head
> Commit [a9ee6cc](https://github.com/BennyWang1007/lab0-c/commit/a9ee6cc99754b502d537a00f24799c977ef245a5)

此函式會在佇列的頭部插入一個元素，實作過程如下：

1. 若 head 為 `NULL`，則返回 `false`。
2. 使用 `malloc` 申請 `element_t` 節點的空間，若申請失敗則返回 `false`。
3. 初始化 `new_element` 節點。
4. 使用 `strdup()` 複製輸入字串 `s`，若複製失敗，則釋放 `new_element` 並返回 `false`。
5. 使用 `list_add` 將新節點加入 head。

### q_insert_tail
> Commit [a9ee6cc](https://github.com/BennyWang1007/lab0-c/commit/a9ee6cc99754b502d537a00f24799c977ef245a5)

此函式會在佇列的尾部插入一個元素，實作過程如下：

1. 若 head 為 `NULL`，則返回 `false`。
2. 使用 `malloc` 申請 `element_t` 節點的空間，若申請失敗則返回 `false`。
3. 初始化 `new_element` 節點。
使用 strdup 複製輸入字串 s，若 `strdup` 失敗則釋放 `new_element` 並返回 `false`。
4. 使用 `list_add_tail` 將新節點加入 head。

### q_remove_head
> Commit [edec651](https://github.com/BennyWang1007/lab0-c/commit/edec6510404ee291a14746eb3c86401a9ddc4f06)

此函式會從佇列的頭部移除一個元素，實作過程如下：

1. 若 head 為 `NULL` 或佇列為空，則返回 `NULL`。
2. 取得佇列的第一個元素 entry。
若 `sp` 和 `entry->value` 不為 `NULL`，則將 `entry->value` 複製到 `sp`，並確保字串以 `\0` 結尾。
3. 使用 `list_del_init` 從鏈結串列中移除該節點。
4. 返回 `entry`，由呼叫者負責釋放記憶體。

### q_remove_tail
> Commit [edec651](https://github.com/BennyWang1007/lab0-c/commit/edec6510404ee291a14746eb3c86401a9ddc4f06)

此函式會從佇列的尾部移除一個元素，實作過程如下：

1. 若 head 為 `NULL` 或佇列為空，則返回 `NULL`。
2. 取得佇列的最後一個元素 `entry`。
若 `sp` 和 `entry->value` 不為 NULL，則複製字串至 sp，確保字串結尾為 `'\0'`。
3. 使用 `list_del_init` 從鏈結串列中移除該節點。
4. 返回 `entry`，由呼叫者負責釋放記憶體。

### q_size
> Commit [6f82f18](https://github.com/BennyWang1007/lab0-c/commit/6f82f187d788dd7152631e071072bf2476bc0d00)

此函式會回傳佇列中的元素數量，實作過程如下：

1. 若 head 為 `NULL`，則返回 0。
使用變數 `count` 記錄節點數量，初始化為 `0`。
2. 使用 `for` 迴圈遍歷佇列，每遇到一個節點就將 `count` 增加 1。
3. 最後返回 `count` 值。

### q_delete_mid
> Commit [3048563](https://github.com/BennyWang1007/lab0-c/commit/3048563bb6fcf55dc75bf9b1b23f1479f7f29565)

此函式會刪除佇列的中間節點，實作過程如下：

1. 若 head 為 `NULL` 或佇列為空，則返回 `false`。
2. 使用兩個指標 `slow` 和 `fast`，`slow` 每次移動一步，而 `fast` 每次移動兩步，以此找到佇列的中間節點。
3. 當 `fast` 到達佇列尾部時，slow 會指向中間節點。
4. 使用 `list_del` 移除 `slow` 指向的節點，並釋放其 value 及節點本身的記憶體。
5. 返回 `true` 以表示刪除成功。

### q_delete_dup
> Commit [9d5bb17](https://github.com/BennyWang1007/lab0-c/commit/9d5bb173b17bbd1cd164c90af71fcdf0b2c92c1d)

此函式會刪除所有具有重複字串的節點，實作過程如下：

1. 若佇列為空，則直接返回 `true`。
2. 使用 `prev` 指向當前處理的節點，`prev_node` 指向 `prev` 的 `list_head`，`node` 用於走訪佇列。
3. 若當前節點與 `prev` 的 value 相同，則標記 `is_dup = true`，並刪除當前節點。
4. 若當前節點與 `prev` 不同，則檢查 `is_dup` 是否為 `true`，若是則刪除 `prev_node`，否則將 `prev` 更新為當前節點。
5. 走訪完成後，若 `is_dup` 為 `true`，則刪除最後一個重複節點。
6. 返回 `true` 代表刪除成功。

### q_swap
> Commit [5f13d84](https://github.com/BennyWang1007/lab0-c/commit/5f13d84caebba07aa35bd6a5cda6ccc9a402ea09)

此函式會交換佇列中每兩個相鄰的節點，實作過程如下：

1. 若佇列為空或只有一個節點，則不需進行交換，直接返回。
2. 使用 `node` 走訪佇列，每次處理兩個節點。
3. 透過調整指標，將 `node` 和 `node->next` 互換位置。
4. 更新 `node`，跳過剛剛交換的節點，繼續處理下一對相鄰節點。

### q_reverse
> Commit [1b7b7ad](https://github.com/BennyWang1007/lab0-c/commit/1b7b7ad7ae970422f82c89c07edd6510eec09801)

此函式會將佇列中的元素順序完全反轉，實作過程如下：

1. 若 head 為 `NULL`，則直接返回。
2. 使用 `node` 遍歷佇列，並在每個節點上交換 `prev` 和 `next` 指標。
3. 最後調整 head 的 `next` 和 `prev`，完成反轉。

> Commit [25bcd80](https://github.com/BennyWang1007/lab0-c/commit/25bcd80b966654c28dc5fa7d7ed0a42ff2033cf8)

此提交修正了原先實作雙向鏈結串列指標的錯誤，並將 `for` 迴圈改成 `while` 迴圈增加可讀性。

### q_reverseK
> Commit [e8c1632](https://github.com/BennyWang1007/lab0-c/commit/e8c16323738568ba14b354da1ead74fc8ec14891)

此函式會將佇列中的元素以 k 個節點為一組進行翻轉，實作過程如下：

1. 若 head 為 `NULL` 或對列為空，或 `k <= 1`，則直接返回。
2. 若佇列的節點數 `count < k` 則無需翻轉。
3. 設定整型變數 `round` 為 `count / k`，表示需要翻轉的區塊數。
4. 使用 `node` 作為翻轉起點，逐區塊進行處理：
1. `cur` 為當前區塊的第一個節點。
2. 使用 `list_move(cur, node);` 將節點移動到當前區塊的起點。
3. 逐步翻轉 `k` 個節點後，將 `node` 移動到下一區塊的起點。

> Commit [61ae3a9](https://github.com/BennyWang1007/lab0-c/commit/61ae3a95c14bbeaa377f70ea7ebf7f194d8e0b77)

此提交優化了 `q_reverseK` 的效率：
1. 將 `list_move` 改成直接的 pointer 交換，免去多餘的雙向串列操作 (`list_del` + `list_add`)。
2. 將原本迭代 `k` 次的 `for` 迴圈改為直接設 `node = node->next;` ，大幅降低尋找下一個 group 的起點的操作數（ $O(k) \rightarrow O(1)$ ）。

void q_reverseK(struct list_head *head, int k)
{
    ...
    for (int i = 0; i < round; i++) {
        ...
        /* Reverse the nodes */
        for (int j = 0; j < k; j++) {
            next = cur->next;
-           list_move(cur, node);
+           tmp = cur->next;
+           cur->next = cur->prev;
+           cur->prev = tmp;
            cur = next;
        }
        /* Swap the pointers */
+       next->prev->prev = node;
+       node->next->next = next;
+       tmp = next->prev;
+       next->prev = node->next;
+       node->next = tmp;
        /* Move to the next group */
-       for (int j = 0; j < k; j++)
-           node = node->next;
+       node = next->prev;
    }
}

### q_sort
> Commit [38f7439](https://github.com/BennyWang1007/lab0-c/commit/38f7439d66a67415945096668a3d996af38ad96e)

此函式會對佇列中的元素進行排序，並可選擇升冪或降冪排序，實作過程如下：

透過 `merge_sort_ascend` 使用 **合併排序** 演算法對佇列進行升冪排序。
若 `descend` 為 `true`，則呼叫 `q_reverse` 進行反轉，使佇列變為降冪排序。

### merge_sort_ascend
> Commit [38f7439](https://github.com/BennyWang1007/lab0-c/commit/38f7439d66a67415945096668a3d996af38ad96e)

此函式使用合併排序將佇列 **升冪排序**：

1. 若佇列為空或只有一個元素，則直接返回。
2. 使用 **快慢指標** 找到佇列的 **中間節點**，將佇列拆分為左右兩半。
3. 透過遞迴呼叫 `merge_sort_ascend` 分別對 `left` 和 `right` 排序。
4. 使用 `merge` 合併 `left` 和 `right`，將結果存入 head。

### merge
> Commit [38f7439](https://github.com/BennyWang1007/lab0-c/commit/38f7439d66a67415945096668a3d996af38ad96e)

此函式負責合併兩個已排序的子串列 l 和 r，並將結果存入 head：

1. 比較 l 和 r 首節點的 value，將較小的節點移至 head 的尾部。
2. 當 l 或 r 中有節點未處理完時，直接將剩餘的節點拼接到 head。

此函式是參考去年作業< `LIAO-JIAN-PENG` > 的[架構](https://github.com/LIAO-JIAN-PENG/lab0-c/blob/master/queue.c#L265)，在該實作之上我將該程式碼的分支簡化，提昇效率和品味。又因 `list_splice_tail_init` 內就會判斷是否為空，因此可以將 `if` 判斷式移除。

void merge(struct list_head *head, struct list_head *l, struct list_head *r)
{
    /* Merge the two sorted lists left and right into head */
    while (!list_empty(l) && !list_empty(r)) {
        char *l_val = list_first_entry(l, element_t, list)->value;
        char *r_val = list_first_entry(r, element_t, list)->value;
-       if (strcmp(l_val , r_val) < 0) {
-           list_move_tail(l->next, head);
-       } else {
-           list_move_tail(r->next, head);
-       }
+       struct list_head *node = strcmp(l_val, r_val) <= 0 ? l->next : r->next;
+       list_move_tail(node, head);
    }

-   if (!list_empty(l))
-       list_splice_tail_init(l, head);
-   if (!list_empty(r))
-       list_splice_tail_init(r, head);
    /* Move the remaining elements to head */
+   list_splice_tail_init(l, head);
+   list_splice_tail_init(r, head);
}

### q_ascend
> Commit [2008bc4](https://github.com/BennyWang1007/lab0-c/commit/2008bc4cf88cb1aa1e2d5a1f2f9745619390a2b1)

此函式會 移除所有非遞增的節點，確保佇列中的值嚴格遞增，具體實作過程如下：

1 若佇列為空或僅有一個節點，則直接返回對應大小。
2. 從 **倒數第二個節點開始** 向前走訪佇列，並維護一個 `min` 變數，記錄目前遇到的最小值。
3. 若當前節點的值 小於 `min`，則更新 `min`，保留該節點；否則刪除該節點。
4. 最後返回佇列剩餘的節點數量。

此函式是參考去年作業< `LIAO-JIAN-PENG` > 的架構，但做了兩個效能上的優化：
1. 避免兩次 `q_reverse` 操作：
* 原實作先反轉鏈結串列，然後使用 `list_for_each_safe` 走訪刪除不符合條件的節點，最後再反轉回來，這樣多做了兩次 `O(n)` 的反轉操作。
* 優化後直接從尾端開始走訪，省去了 `q_reverse` 的額外開銷。
2. 刪除多餘的 `NULL` 判斷：
* 原實作在走訪過程中皆需判斷 `min` 是否為 `NULL`。
* 優化後我直接將 `min` 初始化為最後一個節點的值 `(head->prev)`，避免了多餘的 `NULL` 判斷，減少不必要的條件分支，並從倒數第二個節點開始走訪。

int q_ascend(struct list_head *head)
{
-   q_reverse(head);
    ...
-   char *min = NULL;
+   const char *min = list_entry(node, element_t, list)->value;
    ...
-       if (!min || strcmp(e->value, min) < 0)
+       if (strcmp(e->value, min) < 0)
    ...
-   q_reverse(head);
    return q_size(head);
}

### q_descend
> Commit [2008bc4](https://github.com/BennyWang1007/lab0-c/commit/2008bc4cf88cb1aa1e2d5a1f2f9745619390a2b1)

此函式會 移除所有非遞減的節點，確保佇列中的值是嚴格遞減的，具體實作過程如下：

1. 若佇列為空或僅有一個節點，則直接返回對應大小。
2. 從 **倒數第二個節點開始** 向前走訪佇列，並維護一個 `max` 變數，記錄目前遇到的最大值。
3. 若當前節點的值 大於 `max`，則更新 `max`，保留該節點；否則刪除該節點。
4. 最後返回佇列剩餘的節點數量。

### q_merge
> Commit [77eba2e](https://github.com/BennyWang1007/lab0-c/commit/77eba2e366ac057021ad8d5c514a16295adccb18)

此函式的作用是 合併所有已排序的佇列，並按照指定的升序或降序排列，具體實作過程如下：

1. 若 `head` 為空，則返回 0。
2. 取得 `head` 中的第一個 `queue_contex_t` 作為合併的主要佇列 `qc`。
3. 走訪 `head` 中的其他 `queue_contex_t`，將其佇列 (`q`) 併入 `qc->q`，並更新 `size`。
4. 併入後，對 `qc->q` 進行排序。
5. 最後返回合併後的佇列大小。

> Commit [f656bf8](https://github.com/BennyWang1007/lab0-c/commit/f656bf8987026b408399fb3f5cdbd4c8eecf07fa)

此提交優化了：
1. 修正變數名稱，增加可讀性。（`qc` → `first_qc`, `tmp` → `cur_qc`）
2. 不使用 `list_for_each_entry` ，顯式地從第二個元素開始走訪，優化掉了迭代中的 `if` 判斷。

int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
-    queue_contex_t *qc = list_first_entry(head, queue_contex_t, chain);
-    queue_contex_t *tmp = NULL;
+    queue_contex_t *first_qc = list_first_entry(head, queue_contex_t, chain);
+    struct list_head *cur_chain = (&(first_qc->chain))->next;

-    list_for_each_entry (tmp, head, chain) {
+    for (; cur_chain != head; cur_chain = cur_chain->next) {
-        if (tmp == qc)
-            continue;
+        queue_contex_t *cur_qc = list_entry(cur_chain, queue_contex_t, chain);
        ...
    }
    ...
}

## Dudect 修正
> Commit [a3405ea](https://github.com/BennyWang1007/lab0-c/commit/a3405eac8db3b8fe9c369ed0ca5ab2606a3a3bd4)

1. 首先我先準備 `prepare_percentiles()` 函式來生成指數遞減的不同的取樣域值： $threshold(x)=1-{0.5}^{\dfrac{10\ \cdot\ x}{NUM\_PERCENTILES}}$ ，此處 $NUM\_PERCENTILES$ 取 $100$，可得以下曲線。

2. 接著在執行的過程中，使用不同的區間來進行 Welch's t-test，藉由取不同區間段的資料來排除掉極端值，或是因被 CPU 排程影響的異常值。

// t-test on cropped execution times, for several cropping thresholds.
for (size_t j = 0; j < NUM_PERCENTILES; j++) {
    if (difference < percentiles[j]) {
        t_push(t, difference, classes[i]);
    }
}

## Shuffle
### 實作 **Fisher–Yates shuffle** 演算法：
> Commit [c67bb6e](https://github.com/BennyWang1007/lab0-c/commit/c67bb6ed7f0852e3110aa5a6e72fa1b05a74e1ad)

    /* Fisher-Yates shuffle */
    for (size_t i = qsize - 1; i > 0; i--) {
        size_t j = rand() % (i + 1);
        struct list_head *cur = head->next, *swap = head->next;
        for (size_t k = 0; k < i; k++)
            cur = cur->next;
        for (size_t k = 0; k < j; k++)
            swap = swap->next;
        swap_nodes(swap, cur);
    }

從尾部開始走訪，從該節點之前（包含）隨機抽取一個點進行互換。
### 機率計算
考慮佇列包含 $n$ 個節點，記 $a_1, a_2, ..., a_n$。
$a_n$為隨機與所有元素調換，故其值為$a_1-a_n$之機率皆為$\dfrac{1}{n}$。
假設從 $a_{k+1}-a_n$ 的所有點成為任一點的機率皆為$\dfrac{1}{n}$，則點 $a_1-a_k$ 有 $\dfrac{1}{n}$ 成為 $a_n$、$\dfrac{1}{n-1}\cdot\dfrac{n-1}{n}=\dfrac{1}{n}$ 的機率成為 $a_{n-1}$、$\dfrac{1}{n-2}\cdot\dfrac{n-2}{n}=\dfrac{1}{n}$ 的機率成為 $a_{n-2}$，...。
此時點$a_k$成為$a_{k-1}$的機率為$\dfrac{1}{k}\cdot\dfrac{n-(n-k)}{n}=\dfrac{1}{n}$，．．．，成為$a_1$的機率為 $\dfrac{1}{n}$。
因此$a_k$成為任一點的機率也皆為$\dfrac{1}{n}$。
根據數學歸納法，$a_n$成為任一點的機率皆為$\dfrac{1}{n}\Rightarrow$所有點成為任一點的機率皆為$\dfrac{1}{n}$。

### Shannon entropy
根據上述推導與熵的公式：$H=-\sum{P(p_i)\cdot log(P(p_i))}$，此演算法的亂度$H=-\displaystyle\sum_{i=1}^{n!}{\frac{1}{n!}\cdot log(\frac{1}{n!})}=log(n!)$ 為理論最大亂度。（$n!$ 種排列，機率各$\dfrac{1}{n!}$）

### 模擬測試
由[測試用的 Python 腳本](https://hackmd.io/@sysprog/linux2025-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) `shuffle_test.py` 測試，得出以下結果以及作圖。

Expectation:  41666
Observation:  {'1234': 41894, '1243': 41595, '1324': 41504, '1342': 41843, '1423': 41723, '1432': 41952, '2134': 41567, '2143': 41137, '2314': 41565, '2341': 41480, '2413': 41757, '2431': 41664, '3124': 41991, '3142': 41419, '3214': 41515, '3241': 41999, '3412': 41906, '3421': 41648, '4123': 41547, '4132': 41873, '4213': 41349, '4231': 41656, '4312': 41730, '4321': 41686}
chi square sum:  25.505448087169388


從 $\chi^2=25.5$ 以及上圖卡方分佈在 $df=23$ 時的表可得 $p_{value} > 0.2$，因此不拒絕虛無假設 $\Rightarrow$ 此 Shuffle 方法是均勻分佈的。

## Linux List Sorting
> Commit [940cc05](https://github.com/BennyWang1007/lab0-c/commit/94895e1213605c5d31711e9cc872210d244f735b)

我將 Linux kernel 中的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 移植到 `linux_listsort.c` 中，並在 `qtest` 內新增指令 `sort_l` 以供測試。

> Commit [f0147c7](https://github.com/BennyWang1007/lab0-c/commit/f0147c79cf2f1f54a584d534a3859375d0e167b2)

並撰寫測試程式 `sort_eff_read.c` (讀取測試資料)、`sort_eff_qsort.c` (執行q_sort) 以及 `sort_eff_linux.c` (執行Linux listsort)、 配合 `clock()` 和以下 `perf` 指令進行測試。

$ perf stat ./test_filename

得出以下輸出：

Read testcases took  4.838672 sec
q_sort         took 18.697750 sec
Linux sort     took  8.900504 sec

Read test cases took 4.838672 sec

 Performance counter stats for './sort_eff_read':

          5,043.21 msec task-clock                       #    1.000 CPUs utilized             
                48      context-switches                 #    9.518 /sec                      
                 4      cpu-migrations                   #    0.793 /sec                      
         2,109,444      page-faults                      #  418.274 K/sec                     
     9,694,053,542      cpu_atom/cycles/                 #    1.922 GHz                         (0.00%)
    23,277,332,448      cpu_core/cycles/                 #    4.616 GHz                         (100.00%)
     5,632,706,802      cpu_atom/instructions/           #    0.58  insn per cycle              (0.00%)
    62,900,097,052      cpu_core/instructions/           #    6.49  insn per cycle              (100.00%)
     1,114,237,134      cpu_atom/branches/               #  220.938 M/sec                       (0.00%)
    12,711,879,975      cpu_core/branches/               #    2.521 G/sec                       (100.00%)
        50,854,925      cpu_atom/branch-misses/          #    4.56% of all branches             (0.00%)
        12,050,810      cpu_core/branch-misses/          #    1.08% of all branches             (100.00%)
             TopdownL1 (cpu_core)                 #     31.0 %  tma_backend_bound      
                                                  #      2.0 %  tma_bad_speculation    
                                                  #     20.0 %  tma_frontend_bound     
                                                  #     47.1 %  tma_retiring             (100.00%)
             TopdownL1 (cpu_atom)                 #     41.9 %  tma_bad_speculation    
                                                  #     13.6 %  tma_retiring             (0.00%)
                                                  #      0.0 %  tma_backend_bound      
                                                  #     44.5 %  tma_frontend_bound       (0.00%)

       5.045026600 seconds time elapsed

       3.029803000 seconds user
       2.013869000 seconds sys


q_sort took 18.697750 sec

 Performance counter stats for './sort_eff_qsort':

         23,617.91 msec task-clock                       #    0.999 CPUs utilized             
               882      context-switches                 #   37.345 /sec                      
                43      cpu-migrations                   #    1.821 /sec                      
         2,109,442      page-faults                      #   89.315 K/sec                     
    80,433,036,134      cpu_atom/cycles/                 #    3.406 GHz                         (0.17%)
   108,092,876,794      cpu_core/cycles/                 #    4.577 GHz                         (99.77%)
    46,758,971,684      cpu_atom/instructions/           #    0.58  insn per cycle              (0.20%)
    89,704,983,258      cpu_core/instructions/           #    1.12  insn per cycle              (99.77%)
     8,907,805,711      cpu_atom/branches/               #  377.163 M/sec                       (0.20%)
    17,480,987,840      cpu_core/branches/               #  740.158 M/sec                       (99.77%)
       198,552,105      cpu_atom/branch-misses/          #    2.23% of all branches             (0.20%)
       213,863,677      cpu_core/branch-misses/          #    2.40% of all branches             (99.77%)
             TopdownL1 (cpu_core)                 #     67.2 %  tma_backend_bound      
                                                  #      3.1 %  tma_bad_speculation    
                                                  #     10.9 %  tma_frontend_bound     
                                                  #     18.8 %  tma_retiring             (99.77%)
             TopdownL1 (cpu_atom)                 #     11.2 %  tma_bad_speculation    
                                                  #     12.3 %  tma_retiring             (0.20%)
                                                  #     69.3 %  tma_backend_bound      
                                                  #      7.2 %  tma_frontend_bound       (0.20%)

      23.646281130 seconds time elapsed

      21.631719000 seconds user
       1.986239000 seconds sys


Linux sort took 8.900504 sec

 Performance counter stats for './sort_eff_linux':

         13,850.40 msec task-clock                       #    0.996 CPUs utilized             
             1,606      context-switches                 #  115.953 /sec                      
                 9      cpu-migrations                   #    0.650 /sec                      
         2,109,444      page-faults                      #  152.302 K/sec                     
    48,078,089,762      cpu_atom/cycles/                 #    3.471 GHz                         (0.05%)
    63,453,990,816      cpu_core/cycles/                 #    4.581 GHz                         (99.93%)
   114,601,258,673      cpu_atom/instructions/           #    2.38  insn per cycle              (0.06%)
    84,023,936,486      cpu_core/instructions/           #    1.75  insn per cycle              (99.93%)
    23,391,891,100      cpu_atom/branches/               #    1.689 G/sec                       (0.06%)
    17,286,557,130      cpu_core/branches/               #    1.248 G/sec                       (99.93%)
        26,820,239      cpu_atom/branch-misses/          #    0.11% of all branches             (0.06%)
       406,362,795      cpu_core/branch-misses/          #    1.74% of all branches             (99.93%)
             TopdownL1 (cpu_core)                 #     29.5 %  tma_backend_bound      
                                                  #      4.2 %  tma_bad_speculation    
                                                  #     22.2 %  tma_frontend_bound     
                                                  #     44.1 %  tma_retiring             (99.93%)
             TopdownL1 (cpu_atom)                 #      2.1 %  tma_bad_speculation    
                                                  #     53.7 %  tma_retiring             (0.06%)
                                                  #     21.2 %  tma_backend_bound      
                                                  #     22.9 %  tma_frontend_bound       (0.06%)

      13.908267131 seconds time elapsed

      11.717652000 seconds user
       2.127757000 seconds sys

注：以下皆以 **Linux 實作** 與 **原版** 代稱 `Linux listsort` 與 `q_sort` 。
比較perf輸出可發現：
1. 可以發現 Linux 實作的效率比原版高非常多，Linux 實作的效率是原板的$\dfrac{8.90}{18.70}=2.10$倍。
2. Linux 實作的 instructions/cycle 比原版高（1.75 > 1.12），這是因為 Linux 實作中，merge sort 的 bottom up 實作對 cache 較友善。
3. Linux 實作的 branch miss 也比原版的低，可能是因為 Linux 實作比傳統的 bottom-up mergesort少了 $0.2^n$ 個比較，並且Linux實作少了很多檢查（如頭是否為空），讓CPU更容易預測分支。

> Commit [cca2af4](https://github.com/BennyWang1007/lab0-c/commit/cca2af408fc3779e12ec161ec743dfae28c41b22)

此提交將 `sort_eff_qsort.c`、`sort_eff_linux.c`以及`sort_eff_read.c `合併到`sort_eff.c`中，減少程式碼重複性並增加維護性。

可以執行以下命令測試

$ make sort_eff
$ ./sort_eff [linux, qsort, read] [-wait]

### 嘗試改進
首先我先用 `perf top` 取樣：

$ perf top -p pid

q_sort：

  44.30%  sort_eff_qsort  [.] merge
  34.06%  libc.so.6       [.] __strcmp_avx2
  10.86%  sort_eff_qsort  [.] q_reverse
   8.27%  sort_eff_qsort  [.] merge_sort_ascend
   0.57%  sort_eff_qsort  [.] strcmp@plt
   ...

Linux listsort：

  56.03%  libc.so.6       [.] __strcmp_avx2
  19.15%  sort_eff_linux  [.] cmp_descend
  16.85%  sort_eff_linux  [.] linux_merge
   2.94%  sort_eff_linux  [.] list_sort
   1.67%  sort_eff_linux  [.] strcmp@plt
   1.03%  sort_eff_linux  [.] merge_final
   ...

以及用 `perf record` 取樣並配合 `perf report`（篩選過後）
q_sort：

+   34.06%    33.48%  sort_eff_qsort  sort_eff_qsort     [.] merge
+   29.52%    28.88%  sort_eff_qsort  libc.so.6          [.] __strcmp_avx2
+   17.97%     1.60%  sort_eff_qsort  sort_eff_qsort     [.] alloc
+   11.63%     0.80%  sort_eff_qsort  libc.so.6          [.] malloc
+   11.44%     3.65%  sort_eff_qsort  libc.so.6          [.] _int_malloc
+    6.91%     6.88%  sort_eff_qsort  sort_eff_qsort     [.] merge_sort_ascend
+    6.38%     6.37%  sort_eff_qsort  sort_eff_qsort     [.] q_reverse
+    4.24%     4.03%  sort_eff_qsort  libc.so.6          [.] __random
+    1.95%     0.58%  sort_eff_qsort  sort_eff_qsort     [.] read_test_cases 
+    1.13%     0.59%  sort_eff_qsort  sort_eff_qsort     [.] strcmp@plt 
+    0.83%     0.74%  sort_eff_qsort  libc.so.6          [.] __random_r 
     0.25%     0.06%  sort_eff_qsort  sort_eff_qsort     [.] malloc@plt 

Linux listsort：

+   35.88%    35.09%  sort_eff_linux  libc.so.6          [.] __strcmp_avx2
+   29.43%     2.31%  sort_eff_linux  sort_eff_linux     [.] alloc
+   19.25%     1.29%  sort_eff_linux  libc.so.6          [.] malloc
+   18.89%     6.07%  sort_eff_linux  libc.so.6          [.] _int_malloc
+   14.71%    13.36%  sort_eff_linux  sort_eff_linux     [.] cmp_descend
+   12.97%    10.12%  sort_eff_linux  sort_eff_linux     [.] linux_merge
+    7.16%     6.83%  sort_eff_linux  libc.so.6          [.] __random
+    3.04%     0.84%  sort_eff_linux  sort_eff_linux     [.] read_test_cases
     1.70%     1.65%  sort_eff_linux  sort_eff_linux     [.] list_sort
+    1.55%     0.79%  sort_eff_linux  sort_eff_linux     [.] strcmp@plt
+    1.24%     1.03%  sort_eff_linux  libc.so.6          [.] __random_r
     0.75%     0.51%  sort_eff_linux  sort_eff_linux     [.] merge_final
     0.74%     0.62%  sort_eff_linux  libc.so.6          [.] __strlen_avx2

觀察：
1. 首先，`q_reverse` 佔了其中不小的比例，要提昇效率應該使用兩個不同的cmp函式而不是先排序成遞增再反轉。
2. 另外，發現在兩種實作方法中，Linux `merge`所佔的比例約只有q_sort 的 20% 。下圖為q_sort `merge`不同程式碼段佔的時間比例，可以發現在指標的指派上花了很多時間，可能是因為cache miss的關係。
3. 字串比較的時間也是 Linux 實作更快（雖然Linux看似比例較高，但整個程式花的時間差了兩倍以上，因此 Linux 還是更快），這源自於 Linux 實作時減少的比較數量。

       │    char *l_val = list_first_entry(l, element_t, list)->value;         ▒
       │    char *r_val = list_first_entry(r, element_t, list)->value;         ▒
       │    struct list_head *node = strcmp(l_val, r_val) <= 0 ? l->next : r->n◆
 23.41 │      mov     -0x8(%rbx),%rsi
 40.18 │      mov     -0x8(%rbp),%rdi
  1.40 │    → call    strcmp@plt
  0.15 │      test    %eax,%eax
  2.11 │      cmovle  %rbp,%rbx
       │    struct list_head *next = node->next;
 12.55 │      mov     0x8(%rbx),%rdx
       │    struct list_head *prev = node->prev;
  0.02 │      mov     (%rbx),%rax
       │    next->prev = prev;
 12.81 │      mov     %rax,(%rdx)

## Address Sanitizer
在執行 `make SANITIZER=1 && make test` 後，並沒有遇到錯誤訊息產生，完美通過 Address Sanitizer 的檢測。

## Valgrind
我寫了一個簡單的 shell script 來使用 Valgrind 測試是否有記憶體錯誤，並將 stdout 導到 `/dev/null` 使輸出更整潔：

for file in traces/*.cmd; do
    # test 14 and 16 are too slow with valgrind
    if [[ $file == *"14"* ]] || [[ $file == *"16"* ]]; then
        echo "Running test with $file without SIGALRM"
        valgrind -q --leak-check=full ./scripts/debug.py -d < "$file" > /dev/null
        continue
    fi
    echo "Running test with $file"
    valgrind -q --leak-check=full ./qtest < "$file" > /dev/null
done

除了 14 和 16 號之外的測試皆沒有問題，而分析 14 和 16 號測試發現錯誤是來自 `./qtest` 在超時後會直接報錯並中止程式，造成記憶體未正常釋放。（超時原因是因為 Valgrind 插入的測試程式嚴重脫慢程式）因此改為用 `./scripts/debug.py -d` 來取消 Alarm clock。
最後所有測試皆通過 Valgrind 測試，如下圖所示。

Running test with traces/trace-01-ops.cmd
Running test with traces/trace-02-ops.cmd
Running test with traces/trace-03-ops.cmd
Running test with traces/trace-04-ops.cmd
Running test with traces/trace-05-ops.cmd
Running test with traces/trace-06-ops.cmd
Running test with traces/trace-07-string.cmd
Running test with traces/trace-08-robust.cmd
Running test with traces/trace-09-robust.cmd
Running test with traces/trace-10-robust.cmd
Running test with traces/trace-11-malloc.cmd
Running test with traces/trace-12-malloc.cmd
Running test with traces/trace-13-malloc.cmd
Running test with traces/trace-14-perf.cmd without SIGALRM
Running test with traces/trace-15-perf.cmd
Running test with traces/trace-16-perf.cmd without SIGALRM
Running test with traces/trace-17-complexity.cmd

更新：後來才發現有 `make valgrind` 可以使用，仍然有通過測試。

## Web 命令/網頁伺服器改善
> Commit [83ed391](https://github.com/BennyWang1007/lab0-c/commit/83ed391a6e117f0b2e6fcd9277f95e9d00e72fa2)

1. 首先我將變數 `web_connfd` 從區域變數變成全域變數，方便在 `report.c` 中進行是否有連線的判斷，以及關閉連線。
2. 接著在 `report()` ，在訊息尾部傳送`\0`給接收者，並關閉連線並重置變數 `web_connfd = 0;`。

void report(int level, char *fmt, ...)
{
    ...
    if (web_connfd) {
        ...
        web_send(web_connfd, buffer);
+       if (write(web_connfd, "\0", 1) == -1)
+           perror("write");
+       close(web_connfd);
+       web_connfd = 0;
     }
 }

3. 新增 `void send_response(int out_fd)` 取代原本的回覆： `HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n`，讓瀏覽器可以正常連接，解決favicon.ico的問題。
4. 新增測試程式 [test_web.c](https://github.com/BennyWang1007/lab0-c/blob/master/test_web.c) 測試結果如下，輸出有如預期。

HTTP/1.1 200 OK
%s%s%s%s%s%sContent-Type: text/html

<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="#"></head><body><table>
l = []

7 7
Match

5. 使用 `curl` 命令測試結果

curl http://localhost:9999/new --output -
curl http://localhost:9999/ih/1 --output -
curl http://localhost:9999/ih/2 --output -
curl http://localhost:9999/ih/3 --output -
curl http://localhost:9999/sort --output -
curl http://localhost:9999/quit --output -

輸出也如預期：

<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = []
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = [1]
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = [2 1]
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = [3 2 1]
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
l = [1 2 3]
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:image/x-icon;," type="image/x-icon"></head><body><table>
Freeing queue

6. 使用瀏覽器進行測試，如圖所示傳送了 `ih 2` 給伺服器，伺服器則返回了插入了 2 的佇列 `l = [2, 4, 5]`。

> Commit [b6b6bf2](https://github.com/BennyWang1007/lab0-c/commit/b6b6bf247efd47e902fd4f9329d670d33f37536d)

在測試中發現使用瀏覽器傳送 request 的時候，會重複執行兩次命令，如下圖：
終端也確實收到了兩份 request 並且兩個都接受了。終端顯示：

cmd> 
l = [2]
cmd> 
l = [2 2]

在與 [@nyraa](https://github.com/nyraa/) 詢問後，發現範例程式碼中 `"</style><link rel=\"shortcut icon\" href=\"#\">"` 會將 request 導到也就是`目前網址#`，但 `#` 會在瀏覽器內處理掉，因此等同於原網址。因此將 `href` 改為空的 data url ，以防止送出重複的 request，修改如下。

void send_response(int out_fd)
    ...
    "td {padding: 1.5px 6px;}"
-   "</style><link rel=\"shortcut icon\" href=\"#\">"
+   "</style><link rel=\"shortcut icon\" href=\"data:image/x-icon;,\" type=\"image/x-icon\">"
    "</head><body><table>\n";
    ...

修改後，當瀏覽器傳送空的 request 時，server端會收到 `.` 指令，如下圖：
因此新增了command `.` 去處理。

bool do_no_command(int argc, char *argv[])
{
    report(1, "Empty command");
    return true;
}

void init_cmd()
{
    ...
    add_cmd(".", do_no_command, "Empty command", "");
    ...
}

經過改動後，瀏覽器能進行正常的request，不會重複傳送之外，也解決了 `Unknown command '.'` 的問題。