2025q1 Homework1 (lab0)

contributed by < yy214123 >

Reviewed by `Andrushika`

q_insert_head, q_insert_tail

commit f63c3aa & 4123e63

此處在 malloc 新的 element_t 後，直接指定 new_elem->value = s：

element_t *new_elem = malloc(sizeof(element_t));
if (!new_elem)
 return false;
new_elem->value = s;

然而，這樣的方法很容易造成 dangling pointer：因為 s 是由傳進函式的 char*，身為函式的實作者，沒辦法保證函式呼叫者之後會不會對 s 做其他處置。如果函式呼叫者將 s 的記憶體空間釋放（或做其他修改），後續就會發生 use after free 或存取的值和預想中不同的問題。
比較好的作法，是將 s 先 copy 一份後放進 value：

new_elem->value = strdup(s);

q_ascend & q_descend q_reverse 版本

commit d6d8c49 & commit bd72375

你先前使用 q_reverse 來簡化操作，後來發現錯誤。先假設這樣的實作是正確的，也會存在效能的問題。q_reverse 的時間複雜度是

O (n)

，所以 q_descend 會比 q_ascend 多一次對鏈結串列的走訪。雖然兩者在 big-O notation 下都是

O (n)

，但

n

前方的常數會有所差異。

對，這的確是我當下沒考量到的細節，多執行一次 q_reverse 的確會造成額外的效能損失。 yy214123

HackMD 的小問題

可以將各標題層級、內文的結構分清楚一些，目前「研讀〈Dude, is my code constant time?〉」被和 queue.c 相關說明放在一起，但兩者似乎沒有太大相關；「處理 commit message 遺失 Change-Id 的錯誤」也可以獨立寫成一個標題，方便查找。

感謝你的建議，我已經對排版進行了修改。關於「研讀〈Dude, is my code constant time?〉」，我將其獨立為新的標題。而對於「處理 commit message 遺失 Change-Id 的錯誤」，相關的內容我已移至額外問題紀錄中進行描述。若有其他排版建議也歡迎提出，我希望能使整體筆記排版更精美。 yy214123

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ hostnamectl 
Operating System: Ubuntu 24.04.2 LTS              
Kernel: Linux 6.11.0-17-generic

$ 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:          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:             13th Gen Intel(R) Core(TM) i5-13600KF
CPU family:             6
Model:                  183
Thread(s) per core:     2
Core(s) per socket:     14
Socket(s):              1
Stepping:               1
CPU(s) scaling MHz:     29%
CPU max MHz:            5100.0000
CPU min MHz:            800.0000
BogoMIPS:               6988.80    
L1d:                    544 KiB (14 instances)
L1i:                    704 KiB (14 instances)
L2:                     20 MiB (8 instances)
L3:                     24 MiB (1 instance) 
NUMA node(s):           1
NUMA node0 CPU(s):      0-19

前置作業

這是我第二次選修這門課，因此去年已經有相同的 repository。我利用 GitHub 網站提供的 import repository 功能，將原先的 repository 重新命名為 lab0-c_2024，接著，我使用 GitHub 提供的 sync fork 功能來初始化 lab0-c。

課程教材會反覆出現，你不用特別提，除非你要指出其中關鍵描述。

收到。

指定的佇列操作

在實作 queue.c 中的任意函式之前，應先仔細閱讀對應的標頭檔 queue.h，理解其中對各函式的說明。此外，可輔以 The Linux Kernel API - List Management Functions 中的相關巨集來實現功能。

依據作業指示，在執行 git commit 前，須先執行 clang-format -i queue.c，來排除程式碼排版和風格檢查的錯誤。

在共筆紀錄中須附上對應的 commit message 連結，輸入下方命令可以節省前往 GitHub 複製的時間：

$ git log -1 --pretty=format:"commit [%h](https://github.com/yy214123/lab0-c/commit/%H)" | xsel --clipboard --input

q_size

commit 55ed393

既然是作業描述，就沒必要特別放超連結。你該探討作業要求背後的因應措施。

收到。

上面程式碼沒有討論的必要，不用列出，你該回顧自己的 commit message 是否有長進。

回顧去年的 commit 97f2a53，當時的 commit message 雖然詳細，但過於冗長，包含了不必要的細節（如 list_for_each 的具體行為），此外，標題使用了 "Refactor"，這個單字適用於優化程式架構或提高程式可讀性，而 q_size 原先總是回傳 -1，這顯然是錯誤的實作，故使用 "Fix" 更為恰當。

我認為今年的 commit message 比較好，準確描述了問題與修正內容，使讀者能快速理解。

q_new

commit 0a99902

首先，使用 malloc 為 head 分配配置記憶體空間。然而，由於 malloc 可能會失敗，因此在配置後應進行檢查。
若記憶體配置成功，則可使用 list.h 中的 INIT_LIST_HEAD 來初始化節點，並將其回傳。

allocate 譯作「配置」，避免和 dispatch 的翻譯混淆。

注意空白字元。

已修正。

q_free

commit a17ec8e

在釋放佇列之前，應先檢查 head 是否存在，若 head 為空，則表示佇列不存在，無需進一步處理。
接著，檢查佇列是否僅包含 head 節點而無其他元素，若確實如此，則直接釋放 head 的記憶體空間即可。
若佇列內仍有其他元素，則應使用 list_for_each_safe 巨集遍歷逐一走訪每個節點佇列中的所有節點，並透過 q_release_element 釋放每個元素佔用的記憶體。最後，再釋放 head 節點的記憶體，以確保佇列被完全釋放

注意用語！參見「資訊科技詞彙翻譯」及「詞彙對照表」

已修正用語，traverse every node 的合理翻譯應為 "逐一走訪每個節點"，而非 "遍歷每個節點"。

q_insert_head & q_insert_tail

commit a7b2431 & commit 2deb4b2
我檢查 commit message 時發現，這兩則 commit message 的結尾沒有正確顯示 Change-Id，我不知道問題發生的原因。

$\to$ 使用 git rebase -i，修改 commit message，接著 Git hooks 應該就會生效

問題已解決，我先嘗試 git rebase -i 的方式，但沒有效果，後來使用 git reset --hard HEAD~2 將這兩則 commit message 刪除後重新 push ，參見額外問題紀錄-處理 commit message 遺失 Change-Id 的錯誤。

執行 qtest 時發現錯誤

commit a61a1d0

專案中的 qtest 執行檔提供了方便的測試工具，可用於驗證各函式實作的正確性，對應 q_insert_head 及 q_insert_tail 的命令分別為 ih 及 it：

$ ./qtest

cmd> new
l = []
cmd> ih xxx
ERROR: Need to allocate and copy string for new queue element
l = [xxx]
cmd> it xxx
ERROR: Need to allocate and copy string for new queue element
l = [$��� xxx]

從結果可以看出，出現了錯誤訊息 "ERROR: Need to allocate and copy string for new queue element"，而且佇列元素還出現了亂碼。為了確定這個錯誤訊息出現在程式碼的哪個部分，我使用 grep 命令進行搜尋：

$ grep -rn "ERROR: Need to allocate and copy"

grep: qtest: binary file matches
qtest.c:247:                           "ERROR: Need to allocate and copy string for new "
grep: qtest.o: binary file matches

在 qtest.c 中：

if (!cur_inserts) {
    report(1, "ERROR: Failed to save copy of string in queue");
    ok = false;
} else if (r == 0 && inserts == cur_inserts) {
    report(1,
           "ERROR: Need to allocate and copy string for new "
           "queue element");
    ok = false;
    break;
} else if (r == 1 && lasts == cur_inserts) {
    report(1,
           "ERROR: Need to allocate separate string for each "
           "queue element");
    ok = false;
    break;
}
lasts = cur_inserts;

inserts 變數存放 argv[1] 的記憶體位址（即 ih xxx 的 xxx）；而 cur_inserts 會在指定的佇列插入操作完成後，使用 list_last_entry 或 list_first_entry 讀取特定佇列節點中結構體的 value 值的記憶體位址。

而我原先的實作如下：

new_elem->value = s;

這會導致 inserts 與 cur_inserts 相等，進而觸發對應的錯誤資訊，我進行修改：

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_elem = malloc(sizeof(element_t));
    if (!new_elem)
        return false;
-   new_elem->value = s;
+   new_elem->value = malloc(sizeof(strlen(s) + 1));
+   if (!new_elem->value)
+       return false;
+   strcpy(new_elem->value, s);
    list_add(&new_elem->list, head);
    return true;
}

但當執行 git commit -a 時出現下方資訊：

Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/boju/Linux2025/lab0-c/queue.c
51:    strcpy(new_elem->value, s);
67:    strcpy(new_elem->value, s);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml
Running static analysis...
queue.c:48:47: warning: Found calculation inside sizeof(). [sizeofCalculation]
    new_elem->value = malloc(sizeof(strlen(s) + 1));
                                              ^
queue.c:64:47: warning: Found calculation inside sizeof(). [sizeofCalculation]
    new_elem->value = malloc(sizeof(strlen(s) + 1));
                                              ^

Fail to pass static analysis.

於是我再次修改，我將 +1 移出：

bool q_insert_head(struct list_head *head, char *s)
{
    ...
-   new_elem->value = malloc(sizeof(strlen(s) + 1));
+   new_elem->value = malloc(sizeof(strlen(s)) + 1);
    ...
}

再次執行 git commit -a 時出現下方資訊：

Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/boju/Linux2025/lab0-c/queue.c
51:    strcpy(new_elem->value, s);
67:    strcpy(new_elem->value, s);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml
Running static analysis...

根據 Common vulnerabilities guide for C programmers 的描述：

The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.

並且提到最佳的解決方式是使用 strlcpy。

q_remove_head & q_remove_tail

commit f63c3aa ＆ commit 4123e63

首先根據 queue.h 的描述，要注意這邊只是 remove 而非 delete，兩者差異如下：

remove：從佇列中移除指定的元素，但不釋放該元素所佔用的記憶體空間。
delete：不僅從佇列中移除指定的元素，還會釋放其所佔用的記憶體空間。

commit 2c2d15f

現有的實作存在瑕疵，導致在執行 make test 時出現以下的警告資訊：

+++ TESTING trace trace-07-string:
# Test of truncated strings: 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', and 'q_sort'
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
Error limit exceeded.  Stopping command execution, and quitting
---	trace-07-string	0/6

首先搜尋相關的程式碼段落位置：

$ grep -rn "copying of string in remove_head overflowed destination buffer"

grep: qtest: binary file matches
grep: qtest.o: binary file matches

相關的程式碼如下：

STRINGPAD 被定義為 1024，string_length 也被靜態宣告為 1024。

先為指標變數 remove 分配記憶體空間，大小為 1024 + 1024 + 1：

char *removes = malloc(string_length + STRINGPAD + 1);

接下來看到這三行程式碼：

removes[0] = '\0';
memset(removes + 1, 'X', string_length + STRINGPAD - 1);
removes[string_length + STRINGPAD] = '\0';

此時 remove 會被填充為 \0XX,....XX\0，然後透過下方的 while 迴圈檢查原先填充至 STRINGPAD 區段的 X 總數是否有變動，以判斷是否發生溢出：

/* Check whether padding in array removes are still initial value 'X'.
 * If there's other character in padding, it's overflowed.
 */
int i = string_length + 1;
while ((i < string_length + STRINGPAD) && (removes[i] == 'X'))
    i++;
if (i != string_length + STRINGPAD) {
    report(1,
           "ERROR: copying of string in remove_head overflowed "
           "destination buffer.");
    ok = false;
} else {
    report(2, "Removed %s from queue", removes);
}

看到下方的程式碼，之前提過 string_length 被靜態宣告為 1024。

re = pos == POS_TAIL
           ? q_remove_tail(current->q, removes, string_length + 1)
           : q_remove_head(current->q, removes, string_length + 1);

因此我之前實作的錯誤在於，我不小心覆蓋了 caller 的 buffersize，應進行如下修正：

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *rm_node = head->next;
    element_t *rm_elem = list_entry(rm_node, element_t, list);
-   bufsize = strlen(rm_elem->value) + 1;
    strlcpy(sp, rm_elem->value, bufsize);
    list_del(rm_node);
    return rm_elem;
}

註解修正

sysprog21 #218

在 queue.h 中可以看到本作業各個函式的細節說明，我注意到：

/**
 * q_insert_head() - Insert an element in the head
 * @head: header of queue
 * @s: string would be inserted
 *
...
 */
bool q_insert_head(struct list_head *head, char *s);

/**
 * q_insert_tail() - Insert an element at the tail
 * @head: header of queue
 * @s: string would be inserted
 *
...
 */
bool q_insert_tail(struct list_head *head, char *s);

/**
 * q_remove_head() - Remove the element from head of queue
 * @head: header of queue
 * @sp: string would be inserted
 * @bufsize: size of the string
 *
...
 */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize);

/**
 * q_remove_tail() - Remove the element from tail of queue
 * @head: header of queue
 * @sp: string would be inserted
 * @bufsize: size of the string
...
 */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize);

其中對於 sp 的描述與 q_insert_head 及 q_insert_head 中對於 s 的描述相同，但實際上 sp 並沒有進行插入的動作，詢問授課老師後，可提交 pull request 以修正此錯誤。

由於我沒有提交 pull request 的經驗，授課老師提供 About pull requests 指南，讓我進一步熟悉相關流程。

根據指南描述：

A pull request is a proposal to merge a set of changes from one branch into another. In a pull request, collaborators can review and discuss the proposed set of changes before they integrate the changes into the main codebase. Pull requests display the differences, or diffs, between the content in the source branch and the content in the target branch.

目前的分支包含了 queue.c 內所有函式的功能修改。如果在此分支上進行註解修改並提交 pull request，這些變更也會一併提交，因此應該建立一個新的分支。

$ git remote -v                             

origin	git@github.com:yy214123/lab0-c.git (fetch)
origin	git@github.com:yy214123/lab0-c.git (push)

目前只有我 forked 的 repository，輸入下列命令新增：

$ git remote add upstream git@github.com:sysprog21/lab0-c.git

此時就會看到：

$ git remote -v                        
 
origin	git@github.com:yy214123/lab0-c.git (fetch)
origin	git@github.com:yy214123/lab0-c.git (push)
upstream	git@github.com:sysprog21/lab0-c.git (fetch)
upstream	git@github.com:sysprog21/lab0-c.git (push)

接著在這個乾淨的 repository 新增分支：

$ git checkout -b fix-comment-errors upstream/master

branch 'fix-comment-errors' set up to track 'upstream/master'.
Switched to a new branch 'fix-comment-errors'

切換到這個分支後，本地端的檔案會恢復乾淨：

$ git diff

此時就可以進行對應的註解修正。

但當我想要提交時遇到下方問題：

$ git commit -a       
Following files need to be cleaned up:
queue.h
[!] You are not allowed to change the header file queue.h or list.h

詢問授課老師後，老師指出須產生新的 SHA-1 checksum。

原始的 SHA-1 checksum 如下：

$ git show HEAD:queue.h | sha1sum

db6784ff3917888db4d1dceaa0570d99ed40e762

我修改 queue.h 後其 SHA-1 checksum 如下：

$ git hash-object queue.h

bcd1088ee2066de45069ea164f67fac5e93119c0

使用 grep 命令搜尋：

$ grep -R "db6784ff3917888db4d1dceaa0570d99ed40e762" .

./scripts/checksums:db6784ff3917888db4d1dceaa0570d99ed40e762  queue.h

對 checksum 檔案進行修改：

-   db6784ff3917888db4d1dceaa0570d99ed40e762  queue.h
+   bcd1088ee2066de45069ea164f67fac5e93119c0  queue.h
    9be9666430f392924f5d27caa71a412527bf9267  list.h
    3bb0192cee08d165fd597a9f6fbb404533e28fcf  scripts/check-commitlog.sh

此時提交依然出現：

$ git commit -a       
Following files need to be cleaned up:
queue.h
[!] You are not allowed to change the header file queue.h or list.h

後來發現是我用於查詢修改後的 SHA-1 checksum 有誤，不應該使用：

$ git hash-object queue.h

而是：

$ sha1sum queue.h        ok  07:44:03 PM 

45da6585400a15237f09d896bbb807f85f449e92  queue.h

再次修改 checksum 檔案：

-   bcd1088ee2066de45069ea164f67fac5e93119c0  queue.h
+   45da6585400a15237f09d896bbb807f85f449e92  queue.h
    9be9666430f392924f5d27caa71a412527bf9267  list.h
    3bb0192cee08d165fd597a9f6fbb404533e28fcf  scripts/check-commitlog.sh

此時執行 git commit -a 就不會出現相關警告了，撰寫完 commit message 後，須先提交這個分支：

$ git push origin fix-comment-errors

再用此分支發 pull request 到 sysprog21/lab0-c。

q_delete_mid

根據 LeetCode 2095 的說明，中間節點定義為第

⌊ \frac{n}{2} ⌋

個節點，其中 n 為佇列長度，並且是基於 0-based indexing。

方法一

程式碼

最基本的方式是先取得佇列的長度（可使用 q_size 函式函數）。接著，使用除法運算計算欲刪除的元素索引，然後逐一走訪佇列，最終刪除對應的佇列元素。

詳閱資訊科技詞彙翻譯，以得知 function 的翻譯。

已修正，應該使用函式而非函數

方法二

程式碼

另一個策略是使用快慢指標。慢指標每次走訪一個節點，而快指標每次走訪兩個節點。當快指標到達佇列的最後一個節點時，慢指標會恰好位於要刪除的中間節點。計算走訪次數如下：
快指標：

n

次
慢指標：

\frac{n}{2}

次
總共：

\frac{3 n}{2}

次

方法三

commit 684ea99

"access" 譯作「存取」，而非「訪問」(visit)。

已修正。

commit 4555913
在 3 月 27 日的直播課程中獲得了老師的建議，由於在合併排序演算法中也需要使用搜尋中間節點的操作，因此我將相關程式碼邏輯獨立出來成為一個函式，這樣可以實現程式碼的重用。

考慮到使用的資料結構是環狀雙向鏈結串列，我們可以使用兩個指標：一個指標每次存取訪問下一個元素，另一個指標則返回到前一個元素。如下圖所示：

再次計算其走訪次數：
指標 1：

\frac{n}{2}

次
指標 2：

\frac{n}{2}

次
總共：

n

次

相比之前快慢指標的策略，走訪總次數減少了

\frac{n}{2}

次。

在實作過程中，需要特別考慮到佇列元素為偶數的情況。在這種情況下，兩個指標不會指向同一個佇列節點，而是會交錯，如下所示：

因此，我在實作中使用了以下邏輯進行判斷：

while ((access_next != access_prev) && (access_prev->next != access_next)) {
        access_next = access_next->next;
        access_prev = access_prev->prev;
    }

這樣不論佇列中元素的總數是奇數還是偶數，都能夠正確地實現其功能。

TODO：效能比較

目前上述各種方法均是基於理論分析提出，授課老師在 3 月 20 日的直播課程中指出，可以進行相應的效能分析。直播課程提到可以將額外的程式碼使用 GitHub Gist 展示，我將會提交方法一和方法二的程式碼（已更新於上方）。

根據去年的經驗，在 qtest 中使用的 q_show 會顯著影響效能分析的結果：若開啟 q_show，執行結果為：

$ ./qtest          

cmd> new
l = []
cmd> time it xxx 10000000
l = [xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx ... ]
Delta time = 0.791
cmd> time dm
l = [xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx ... ]
Delta time = 0.496

若關閉q_show，執行結果為：

$ ./qtest                                    

cmd> new
cmd> time it xxx 10000000
Delta time = 0.613
cmd> time dm
Delta time = 0.143

因此，我另準備了一個分支，將 q_show 註解掉以便於實驗進行：

-   q_show(3);
+   // q_show(3);

我先寫了一個 Python 檔案來生成測試資料：

import random
import os

os.makedirs("cmds", exist_ok=True)

for i in range(1000):
    size = random.randint(100000, 1000000)
    with open(f"cmds/rand_dm_{i}.cmd", "w") as f:
        f.write(f"new\n")
        f.write(f"it xxx {size}\n")
        f.write(f"time dm\n")
        f.write(f"free\n")

這將生成 1000 筆尺寸在 100K 至 1000K 之間的佇列，最低從 100K 開始是因為若低於 100K，顯示的時間會為 0 秒，經過篩選發現只有大於 100K的數據才會顯示時間。接著，我用一個腳本去執行這些檔案，並將結果記錄於 CSV 中。

#!/bin/bash

mkdir -p results_10F
echo "run_id,queue_size,time_s" > results_10F/timing_v3.csv

results=()  

for i in $(seq 0 999); do
    cmdfile="cmds/rand_dm_${i}.cmd"
    [ -f "$cmdfile" ] || continue

    output=$(./qtest -f "$cmdfile")
    size=$(grep "it xxx" "$cmdfile" | awk '{print $3}')
    time=$(echo "$output" | grep -E "Delta time" | awk '{print $4}')

    if [[ -z "$time" ]]; then
        time="-1"
    fi

    results+=("$i,$size,$time")
done

for line in "${results[@]}"; do
    echo "$line"
done >> results_10F/timing_v3.csv

隨後，我使用 gnuplot 將三種方法的執行時間呈現如下圖：

從結果來看，方法三是最穩定且平均執行時間最低的。不過，有一部分引起了我的好奇，藍色和綠色的部分隨著佇列尺寸增大而發散的情況愈加明顯，在佇列尺寸相近的情況下，時間上卻有兩倍的差距，我尚未搞懂原因。

目前的時間顯示精度只到小數點後三位，於是我嘗試放大精度：

static bool do_time(int argc, char *argv[])
{
    double delta = delta_time(&last_time);
    bool ok = true;
    if (argc <= 1) {
        double elapsed = last_time - first_time;
-       report(1, "Elapsed time = %.3f, Delta time = %.3f", elapsed, delta);
+       report(1, "Elapsed time = %.3f, Delta time = %.10f", elapsed, delta);
    } else {
        ok = interpret_cmda(argc - 1, argv + 1);
        if (block_flag) {
            block_timing = true;
        } else {
            delta = delta_time(&last_time);
-           report(1, "Delta time = %.3f", delta);
+           report(1, "Delta time = %.10f", delta);
        }
    }

    return ok;
}

接著，我使用 taskset 將程式碼的執行限制於給定的 CPU 核，這時發現發散幾乎消失，三種方法均非常穩定，並未隨佇列尺寸增大而出現震盪：

為進一步推導起因，我使用 perf 進行分析，比較開關 taskset 對效能指標的具體影響，這裡我隨意選了一個樣本數較多的測試資料，各進行 10 次測試觀察結果。

未開 taskset 的執行結果如下：

$ for i in {1..10}; do
    perf stat -e cache-references,cache-misses,cycles,instructions ./qtest -f cmds/rand_dm_555.cmd 2>> perf_no_taskset.log
done

run	cache_references	cache_misses	cache_miss_rate	cycles	instructions	ipc	time_elapsed	user_time	sys_time
1	17241656	9892382	57.37	826228499	1923288981	2.33	0.339832	0.179012	0.191972
2	14612480	8109421	55.50	795509847	1700698307	2.14	0.356477	0.204828	0.185673
3	23332294	12157972	52.11	1107577268	2504119125	2.26	0.335217	0.201407	0.163024
4	19864791	11531163	58.05	930359706	2187284696	2.35	0.340756	0.194819	0.175354
5	17080863	10516592	61.57	836851854	1979001851	2.36	0.339477	0.186157	0.185172
6	16963089	10041551	59.20	815348651	1933153510	2.37	0.338824	0.181302	0.189109
7	16047071	10110594	63.01	782730855	1884546384	2.41	0.341982	0.195674	0.177970
8	16136009	10222131	63.35	780970954	1873592083	2.40	0.347788	0.191405	0.191768
9	16059625	8368806	52.11	877706813	1839762446	2.10	0.353229	0.199560	0.185950
10	17805306	10371304	58.25	809727991	1909271619	2.36	0.342096	0.200188	0.174454

開 taskset 的執行結果如下：：

$ for i in {1..10}; do
    taskset -c 0 perf stat -e cache-references,cache-misses,cycles,instructions ./qtest -f cmds/rand_dm_555.cmd 2>> perf_with_taskset.log
done

run	cache_references	cache_misses	cache_miss_rate	cycles	instructions	ipc	time_elapsed	user_time	sys_time
1	32026149	6741449	21.05	1446414938	2584233584	1.79	0.268393	0.188281	0.078488
2	32269571	6576403	20.38	1444059468	2583152521	1.79	0.268202	0.167397	0.098835
3	32133614	6689984	20.82	1448809063	2583787717	1.78	0.269490	0.173320	0.093786
4	31761274	6846540	21.56	1442830213	2582785998	1.79	0.267744	0.177639	0.088509
5	31735067	7403465	23.33	1448393784	2583511397	1.78	0.269289	0.179936	0.087251
6	31906122	6534310	20.48	1433374836	2579936789	1.80	0.266988	0.170548	0.093753
7	32207039	6501005	20.19	1440156894	2583018317	1.79	0.268275	0.186147	0.079369
8	31717134	6502431	20.50	1438018532	2577943850	1.79	0.267203	0.172772	0.092433
9	31970193	6832129	21.37	1447859351	2580957381	1.78	0.269134	0.183556	0.083528
10	31956559	6654394	20.82	1443032754	2580864068	1.79	0.269123	0.183641	0.082409

對比結果顯示，開啟 taskset 後的 miss rate 顯著下降，並且觀察到兩個表格中執行時間的部分：

taskset	min	max	波動
關閉	0.335217	0.356476	0.0213
打開	0.266988	0.269489	0.0025

可以看到，震蕩幅度相差接近 10 倍，這也就是為何實驗初期出現嚴重的發散情況。

註解修正

sysprog21 #219

/**
 * q_delete_mid() - Delete the middle node in queue
 * @head: header of queue
 *
 * The middle node of a linked list of size n is the
 * ⌊n / 2⌋th node from the start using 0-based indexing.
 * If there're six elements, the third member should be returned.
 *
 * Reference:
 * https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
 *
 * Return: true for success, false if list is NULL or empty.
 */ bool q_delete_mid(struct list_head *head);

此函示為布林型別，會根據是否成功刪除佇列的中間節點來回傳 ture 或 false，在原先的註解有一處錯誤："If there're six elements, the third member should be returned." 應該將 returned 改為 deleted 才正確，因為該節點僅被刪除並沒有作為函式的回傳對象。

q_delete_dup

commit 2f84552

我一開始的想法如下：

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    struct list_head *curr_1,*curr_2;
    list_for_each(curr_1,head){
        curr_2 = curr_1->next;
        list_for_each(curr_2,head){
            if(list_entry(curr_1, element_t, list)->value == list_entry(curr_2, element_t, list)->value){
                list_del(curr_2);
                q_release_element(list_entry(curr_2, element_t, list));
            }
        }
    }
    return true;
}

但這邊有個致命性的錯誤，我在內層迴圈使用了 list_for_each，這會導致佇列中的重複字串若是相鄰節點，則刪除後會導致無法繼續存取下一個元素，並且我宣告了 curr_2 = curr->next，這個行為也沒有意義，因為查看 list_for_each 可知：

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

該巨集會初始化為 head->next，如此會造成 Segmentation fault。應該要搭配 for 迴圈來實作。

使用 qtest 進行測試時我發現奇怪的地方，當重複的節點是相鄰的：

$ ./qtest             

cmd> new
l = []
cmd> it 1
l = [1]
cmd> it 1
l = [1 1]
cmd> it 2
l = [1 1 2]
cmd> it 2
l = [1 1 2 2]
cmd> dedup
l = []

此時沒有問題，但當重複節點不是相鄰的：

cmd> it 1
l = [1]
cmd> it 2
l = [1 2]
cmd> it 1
l = [1 2 1]
cmd> it 2
l = [1 2 1 2]
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = []

最後的結果雖正確，但卻先出現了 "ERROR: Duplicate strings are in queue or distinct strings are not in queue" 這段警告訊息。

詢問授課老師後，此題目有預設佇列已排序好，所以我的實作有改善空間，目前使用內外兩層迴圈去走訪節點刪除，時間複雜度為：

O (n^{2})

，但考慮到佇列已排序，可以優化使時間複雜度降為：

O (n)

。

q_swap

commit 09d310d
其實這個作法是 q_reversek 的一個特例，因此我們可以直接調用 q_reversek，並將 k 設定為 2 即可。

q_reverse

commit 075d580

commit 641e410
使用了 list_move 來簡化程式碼。

在實作 shuffle 時獲得了一個啟發，原先的交換方式是去改變串列節點的結構來達成此實作，而既然每個節點都內嵌在 element_t 這個結構體，可不可以只對值做交換而不去改變串列節點的結構呢？於是我做了以下的實驗。

程式碼

測試資料準備：
隨機生成 100 個長度介於 1000000 ~ 10000000 間的佇列，其中每個佇列元素的字串均相同（16個字元），並紀錄其執行 reverse 時所花的時間。且有使用 taskset 將程式碼的執行限制於給定的 CPU 核。

結果：

以結果來看，僅對值交換一定程度上有改善執行時間，且觀察後可發現會隨著佇列尺寸變大，兩者間的差距也逐漸變大。

q_reverseK

commit 069f235

commit 774d3bf
此次更新對於 k 的某些邊緣情況進行了優化，當 k 等於 1 時，函式將直接結束；而當 k 與佇列的長度相符時，將調用 q_reverse。

q_ascend & q_descend

commit d6d8c49 & commit bd72375
我先完成了 q_ascend 的實作，基本上這邊的整體程式架構與 q_delete_dup 雷同，我們可以注意到一系列數字若是以降序排列，反轉後將會變成升序。因此，我們可以首先使用 q_reverse 將佇列反轉，接著呼叫 q_ascend 來進行排序，最後再呼叫一次 q_reverse 就能實現所需的功能。

commit 4fd07ed
對程式碼進行優化，使檢查提早結束，不需要每次都走訪到最後一個節點。gi

commit 27345e0

先前的實作有缺陷，並不能透過調用佇列反轉及 q_ascend，來實現 q_descend，假設現有一個佇列：3 -> 1 -> 2，原因如下：

q_ascend 定義（從左到右看）：

移除任何一個節點，如果該節點右側存在一個比它更小的數字。

節點	右邊節點	是否右邊有更小的數字	是否刪除
3	1,2	有，1<3	刪除
1	2	無	不刪除
2	no	無	不刪除

正確結果：1 -> 2

q_descend 定義（從左到右看）：

移除任何一個節點，如果該節點右側存在一個比它更大的數字。

節點	右邊節點	是否右邊有更小的數字	是否刪除
3	1,2	無	不刪除
1	2	有，2>1	刪除
2	no	無	不刪除

正確結果：3 -> 2

按照原先的程式邏輯，首先先將佇列反轉，變成 2 -> 1 -> 3，執行 q_ascend：

節點	右邊節點	是否右邊有更小的數字	是否刪除
2	1,3	有，1<2	刪除
1	3	無	不刪除
3	no	無	不刪除

結果為：1 -> 3，在執行一次佇列反轉：3 -> 1，與正確結果不符合。

q_sort

commit b484286
去年直接將 merge sort、tim sort 等排序算法的實作寫在 queue.c 中，但發現這樣會使程式碼變得很混亂，因此今年額外新增了 sort.c 檔案。

commit 49e47aa
引入 lib/list_sort.c到 lab0-c 專案

commit 39829a8
實作非遞迴版本的合併排序。

TODO：排序法效能比較

準備測試資料

去年在進行這個作業時，我在這一部分卡住了，讓我有許多好奇的點：測試資料的準備以及相關的統計分析。我為什麼設計了1000筆測試資料，而每筆又是由長度介於5到15的隨機字串組成，數量從1K到1000K，會不會其實不需要這麼多？

隨機字串長度設計：
隨機字串的長度我參考了《Introduction to Information Retrieval》這本書的第五章第二節，書中提到英文中一個詞的平均長度約為八個字符，因此我將隨機字串的長度設為8，字元範圍為A到Z以及小寫字母a到z。

單一樣本的元素數目：
至於單一樣本的元素數量，我參考了論文《Engineering a Sort Function》中關於比較排序的段落：

To assess timing, we ran the programs on computers of disparate architectures: a VAX
8550 and a 40MHz MIPS R3000 (with 64-kilobyte data and instruction caches and a sec-
ondary cache of one megabyte), compiling with lcc on both. Table II reports times in sec-
onds to sort 10,000 integers chosen randomly from the range 0 to 999,999 on each of the
testbed’s six input types. Each time is the average of ten runs.

該段描述了他們在不同架構的電腦上運行程序來測試時間，包括VAX 8550和40MHz MIPS R3000，結果顯示在範圍 0 到 999,999 中隨機選擇 10000 個整數進行排序的時間。我決定將元素數量提高到 1000K，因為相較於當時的設備，我的 CPU 效能更強。

在實驗中我遇到了一些問題，當使用list_sort時可以順利記錄時間，但切換到merge_sort時出現了：

ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient

不過這個情況僅在元素數量為 1000K 時發生，降低到 500K 後就沒有這個警報，由於需要進一步分析，我只能暫時降低這個數字。這也意味著我目前的 merge_sort 在效率上還有很大的改進空間，雖然理論上的時間複雜度與 list_sort 相同，但實際效率卻有差異。

樣本數：
根據中央極限定理，當樣本數量大於等於 30 時，樣本的分佈相對穩定。因此我決定將樣本數設為 100。

結果

所有測試均使用taskset執行。

排序法	平均值	標準差	變異數
list_sort	0.189545 s	0.007821 s	0.000061
merge_sort	0.719091 s	0.017078 s	0.000292

可以明顯看到，list_sort 比 merge_sort來得更快，平均僅需 26% 的時間，且 list_sort的穩定性也較高。

接下來，我考慮不同分佈的測試資料，這次使用已排序好的資料進行測試：

排序法	平均值	標準差	變異數
list_sort	0.248384 s	0.007395 s	0.000055
merge_sort	0.108697 s	0.004558 s	0.000021

這裡顯示 merge_sort 在已排序資料下更快且穩定，這現象的原因在於我對 merge_sort 加入了額外的判斷邏輯，如下：

static int is_list_sorted(struct list_head *head, list_cmp_func_t cmp) {
    if (list_empty(head) || list_is_singular(head))
        return 1;
    
    struct list_head *node = head->next;
    while (node->next != head) {
        if (cmp(node, node->next) > 0)
            return 0;
        node = node->next;
    }
    return 1;
}

我們可以將這次的 list sort 結果與前一個實驗 list sort 結果疊加來看：

從這邊可以發現有議題值得討論：

此結果顯示 list_sort 對這種特例並未進行優化，若對 list_sort 進行已排序資料的優化，則每次排序前都需先遍歷一次，這對隨機資料的效能會有什麼影響呢？

q_merge

commit 6ab9c8f

這邊一開始在實作時，使用測試程式時一直出現錯誤資訊，原先的程式碼如下：

/* Merge all the queues into one sorted queue, which is in ascending/descending
 * order */
int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head)
        return 0;
    if (head->next == head)
        return q_size(list_entry(head, queue_contex_t, chain)->q);
    struct list_head *queue = head->next;
    queue_contex_t *curr_1 = list_entry(queue, queue_contex_t, chain);
    while (queue!= head) {
        queue_contex_t *curr_2 = list_entry(queue->next, queue_contex_t, chain);
        list_splice_tail_init(curr_2->q, curr_1->q);
        queue = queue->next;
    }
    curr_1->size = q_size(curr_1->q);
    q_sort(curr_1->q, descend);
    return curr_1->size;
}

思考後發現是迴圈中止條件的設定有誤，假設目前有三個佇列需要合併。

第一次迭代時：

這邊用加號來代表完成合併

第二次迭代時：

第三次迭代時：

這邊會把 head 也加進來，但實際上 head 並沒有嵌入 q_context_t 結構體，所以會出現錯誤。

此處實作有優化的空間，Merge k Sorted Lists，還在參考案例探討: LeetCode 21. Merge Two Sorted Lists 進行改善中。

研讀〈Dude, is my code constant time?〉

在完成前面數個指定的佇列操作後，此時執行 make test，其分數顯示如下：

$ make test

...
+++ 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
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
Probably constant time
Probably constant time
---     trace-17-complexity     0/5
---	TOTAL		95/100
make: *** [Makefile:62: test] Error 1

目前還沒有辦法獲得滿分，先追蹤專案中相關的程式碼以便確認問題所在處。

lab0-c 相關程式碼追蹤

從 test_const 開始：

static bool test_const(char *text, int mode)
{
    bool result = false;
    t = malloc(sizeof(t_context_t));

    for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
        printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
        init_once();
        for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
             ++i)
            result = doit(mode);
        printf("\033[A\033[2K\033[A\033[2K");
        if (result)
            break;
    }
    free(t);
    return result;
}

看到外層迴圈，在這邊因為 TEST_TRIES 被定義為 10，所以針對個別指定的佇列操作常數時間判定，最多會有十輪，每輪中會進行多次測量，已確保樣本數充沛（內層的迴圈）。

如何測量時間呢？我們進一步追蹤 doit 這個函式：

static bool doit(int mode)
{
    int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
    uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
    uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));

    if (!before_ticks || !after_ticks || !exec_times || !classes ||
        !input_data) {
        die();
    }

    prepare_inputs(input_data, classes);

    bool ret = measure(before_ticks, after_ticks, input_data, mode);
    differentiate(exec_times, before_ticks, after_ticks);
    update_statistics(exec_times, classes);
    ret &= report();

    free(before_ticks);
    free(after_ticks);
    free(exec_times);
    free(classes);
    free(input_data);

    return ret;
}

這邊總共有幾個關鍵步驟，我們依序追蹤，首先是 prepare_input：

void prepare_inputs(uint8_t *input_data, uint8_t *classes)
{
    randombytes(input_data, N_MEASURES * CHUNK_SIZE);
    for (size_t i = 0; i < N_MEASURES; i++) {
        classes[i] = randombit();
        if (classes[i] == 0)
            memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);
    }

    for (size_t i = 0; i < N_MEASURES; ++i) {
        /* Generate random string */
        randombytes((uint8_t *) random_string[i], 7);
        random_string[i][7] = 0;
    }
}

每次測試都準備 N_MEASURES 筆資料，並隨機分類（class 0 或 class 1），第一個 for 迴圈與此次指定佇列的操作次數有關：

input_data 會指向連續的記憶體空間，分為 150 個 chuck(每個 chuck 的大小為 2)。示意圖如下：

接著會呼叫 randombytes 將這 300 bytes 進行填充：

接著會對每個 chunk 進行分類，若被分派程 class 0 則將其 2 bytes 清為 0，關鍵程式碼如下：

memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);

而第二個迴圈生成的就是這筆樣本插入的隨機字串。

下一個呼叫的函式是 measure，這邊假設我們進行的是 q_insert_head：

case DUT(insert_head):
    for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
        char *s = get_random_string();
        dut_new();
        dut_insert_head(
            get_random_string(),
            *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
        int before_size = q_size(l);
        before_ticks[i] = cpucycles();
        dut_insert_head(s, 1);
        after_ticks[i] = cpucycles();
        int after_size = q_size(l);
        dut_free();
        if (before_size != after_size - 1)
            return false;
    }
break;

可以看到 dut_insert_head 有兩個傳入參數：

參數一：透過 get_random_string() 去獲得該樣本對應的隨機字串（對應到 prepare_inputs 中第二個 for 迴圈）。
參數二：將個別 chunk 裡面的 2 bytes % 10000，可以得到介於 0~9999 的數值。

用 chunk 0 來舉例，就會是插入某個隨機字串至佇列頭部 0x5F12 % 10000 次。過程中透過 before_tick 與 after_tick 來紀錄起始與結束時間。

下一個呼叫的函式是 differentiate，其實就只是紀錄 before_tick 與 after_tick 間的差值，就是該樣本的執行時間。

最後呼叫的函式是 update_statistics：

static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
    for (size_t i = 0; i < N_MEASURES; i++) {
        int64_t difference = exec_times[i];
        /* CPU cycle counter overflowed or dropped measurement */
        if (difference <= 0)
            continue;

        /* do a t-test on the execution time */
        t_push(t, difference, classes[i]);
    }
}

呼叫 t_push 來將各個執行時間依序放入對應的資料結構中：

void t_push(t_context_t *ctx, double x, uint8_t class)
{
    assert(class == 0 || class == 1);
    ctx->n[class]++;

    /* Welford method for computing online variance
     * in a numerically stable way.
     */
    double delta = x - ctx->mean[class];
    ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
    ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
}

在各類別中，會獨立保存各自的平均值及平方差總和，這邊使用的是 Welford 演算法，不需要紀錄歷史資料即可更新：

當有新資料加入，先計算 delta：新資料值 - 過去歷史平均值，
接著更新平均值，新的平均值 = 過去歷史平均值 + delta / 資料總數。

舉例如下：

假設現有資料為 4,8,12，則平均為 8，新加入了 16 這筆資料，先算
$d e l t a = 16 - 8 = 8$ 。
更新平均值：
$a v g (n e w) = 8 + 8 / 4 = 10$ ，與實際平均值相同。

平方差總和同理：

現有資料的平方差總和為 32，新加入了 16 這筆資料。
更新平方差總和：

$\begin{aligned} m^{2} (n e w) & = 32 + 8 \cdot (16 - 10) = 80 \\ = (4 - 10)^{2} + (8 - 10)^{2} + (12 - 10)^{2} + (16 - 10)^{2} \end{aligned}$

經過上述步驟，我們現在擁有這些資料：

這次 150 個樣本中被分派到 class 0 的平均值及平方差總和。
這次 150 個樣本中被分派到 class 1 的平均值及平方差總和。

有了這些資料，在 report 中：

static bool report(void)
{
    double max_t = fabs(t_compute(t));
    double number_traces_max_t = t->n[0] + t->n[1];
    double max_tau = max_t / sqrt(number_traces_max_t);

    printf("\033[A\033[2K");
    printf("measure: %7.2lf M, ", (number_traces_max_t / 1e6));
    if (number_traces_max_t < ENOUGH_MEASURE) {
        printf("not enough measurements (%.0f still to go).\n",
               ENOUGH_MEASURE - number_traces_max_t);
        return false;
    }

    /* max_t: the t statistic value
     * max_tau: a t value normalized by sqrt(number of measurements).
     *          this way we can compare max_tau taken with different
     *          number of measurements. This is sort of "distance
     *          between distributions", independent of number of
     *          measurements.
     * (5/tau)^2: how many measurements we would need to barely
     *            detect the leak, if present. "barely detect the
     *            leak" = have a t value greater than 5.
     */
    printf("max t: %+7.2f, max tau: %.2e, (5/tau)^2: %.2e.\n", max_t, max_tau,
           (double) (5 * 5) / (double) (max_tau * max_tau));

    /* Definitely not constant time */
    if (max_t > t_threshold_bananas)
        return false;

    /* Probably not constant time. */
    if (max_t > t_threshold_moderate)
        return false;

    /* For the moment, maybe constant time. */
    return true;
}

這邊會透過 t_compute 去計算先前兩個類別的變異數：

double t_compute(t_context_t *ctx)
{
    double var[2] = {0.0, 0.0};
    var[0] = ctx->m2[0] / (ctx->n[0] - 1);
    var[1] = ctx->m2[1] / (ctx->n[1] - 1);
    double num = (ctx->mean[0] - ctx->mean[1]);
    double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
    double t_value = num / den;
    return t_value;
}

我統計非常爛，所以得先搞懂變異數是什麼，根據維基百科的描述，我的總結如下：

翻閱統計學教科書

已在下方說明。

變異數（Variance）是用來衡量一組數據的離散程度或波動幅度。換句話說，它告訴你：
→ 整體資料「偏離平均值有多遠」。

在這個實驗中，資料被分為兩個類別（class 0 與 class 1）：

所以統計上可以視為來自同個母體（populations）的兩個不同樣本

兩個樣本的統計結構如下：

類別	Class 0	class 1
樣本數	$n_{1}$	$n_{2}$
樣本平均值	${\bar{x}}_{1}$	${\bar{x}}_{2}$

Class 0 中有

x_{1}, x_{2}, . . . x_{n_{1}}

筆資料
Class 1 中有

x_{1}, x_{2}, . . . x_{n_{2}}

筆資料

因此，兩組樣本的平均值分別為：

{\bar{x}}_{1} = \frac{1}{n_{1}} \sum_{i = 1}^{n_{1}} x_{i}

{\bar{x}}_{2} = \frac{1}{n_{2}} \sum_{i = 1}^{n_{2}} x_{i}

有了平均值，就能計算平方差，兩組樣本的各個樣本點的平方差分別為：

\forall i \in {1, 2, \dots, n_{1}}, (x_{i} - {\bar{x}}_{1})^{2}

\forall i \in {1, 2, \dots, n_{2}}, (x_{i} - {\bar{x}}_{2})^{2}

為什麼要平方呢？
舉例來說：
有三個數字分別是
$1, 2, 3$ ，其平均是
$2$ ，各值與平均相減為：

$1 - 2 = - 1$

$2 - 2 = 0$

$3 - 2 = 1$
直接加總會抵銷為
$0$ ，所以才須對各樣本點的差值取平方再加總。

所以兩組樣本的平方差總和為：

S S D_{1} = \sum_{i = 1}^{n_{1}} (x_{i} - {\bar{x}}_{1})^{2}

S S D_{2} = \sum_{i = 1}^{n_{2}} (x_{i} - {\bar{x}}_{2})^{2}

有了上述的資料，我們就可以進一步計算變異數，平方差總和是一個母體中所有樣本的總體偏離程度，那麼變異數可以視為個別樣本點的每筆資料的平均偏離程度。

所以兩組樣本的樣本變異數為：

{S_{1}}^{2} = S S D_{1} / (n_{1} - 1)

{S_{2}}^{2} = S S D_{2} / (n_{2} - 1)

為什麼分母是樣本數 -1 而非樣本數呢？
因為後續要做 t test，所以將一個母體分成了兩個樣本，所以我們計算的是樣本變異數。

接著進行 Welch’s t-test

這個檢定方式來自於 Student's t-test 的改良，當要進行比較的兩個樣本其樣本數或變異數不一致，就可以使用 Welch’s t-test 來計算兩組樣本的差異性，程式當初在分組是隨機的，顯然 Class 0 與 Class 1 的樣本數不一致。

公式如下：

t = \frac{{\bar{x}}_{1} - {\bar{x}}_{2}}{\sqrt{\frac{S_{1}^{2}}{n_{1}} + \frac{S_{2}^{2}}{n_{2}}}}

以上就是 t_compute 這個函式的背景知識，最後會將 t 值回傳，回到 report 這個函式：

double max_t = fabs(t_compute(t));

宣告一個 max_t 變數儲存剛剛的 t 值。

取絕對值的原因在於會因為出來的 t 值有負有正，這取決於兩組樣本的大小，不過這不是我們關注的地方，我們只關注差距有多大。

接著要進行正歸化：

double max_tau = max_t / sqrt(number_traces_max_t);

宣告一個 max_tau 變數儲存正歸化後的 t 值。

原因在於前面提到的 Welch’s t-test 公式，觀察分母不難得知會因為樣本數變大而使 t 值變大，我們需要將這個部份的影響抵銷。

最後進行比較：

if (max_t > 500)
    return false;

if (max_t > 10)
    return false;

對應原始 dudect 專案：

static void update_statistics(dudect_ctx_t *ctx) {
  for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {
    int64_t difference = ctx->exec_times[i];

    if (difference < 0) {
      continue; // the cpu cycle counter overflowed, just throw away the measurement
    }

    // t-test on the execution time
    t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]);

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

    // second-order test (only if we have more than 10000 measurements).
    // Centered product pre-processing.
    if (ctx->ttest_ctxs[0]->n[0] > 10000) {
      double centered = (double)difference - ctx->ttest_ctxs[0]->mean[ctx->classes[i]];
      t_push(ctx->ttest_ctxs[1 + DUDECT_NUMBER_PERCENTILES], centered * centered, ctx->classes[i]);
    }
  }
}

其實進行了多次的測試，第一組與目前專案相同，直接使用原始的執行時間進行 t test，這會得到一個 t 值，接著第二階段是會對執行時間進行裁剪，舉一個簡單的範例說明：
class [0] = [0,0,0,0,0,0,0,0,0,0]
class [1] = [1,2,3,4,5,6,7,8,9,10]
第一階段直接進行 t test 得到 t1。
第二階段會設計裁剪門檻，並分成 10 個 bucket，並為每個 bucket 設定門檻值：
門檻值計算公式：

p_{i} = 1 - {0.5}^{(i + 1)}

b u c k e t (0) ： p_{0} = 0.5

i n d e x = ⌊ 10 * 0.5 ⌋ = 5

class[1] 中索引為 5 的是 6，所以 bucket[0] 會搜集所有比 6 小的數：

1,2,3,4,5

依此類推，並拿各個 bucket 與 class[0] 進行 t test 這也會求算出多個 t 值（t2,…,t11）。
最後從 t1,…,t11 中取最大的 t 值，作為 constant time 的判斷結果，由此可以發現，原專案的精神更像是「寧可錯殺，也不錯放」。

我們可以將這個裁剪策略引進 lab0 中，我們可以先看看原始方式的執行時間分佈：

下圖所呈現的是執行 make test 時，經統計檢定後有顯著差異的總體資料分佈。

對這些資料，我們套用先前提過的裁剪方式，經裁剪後的分佈如下：

這邊的實驗有一點問題，正在排除中。

commit 83077d6
有其他學員導入原始 dudect 專案的裁剪策略，現在執行 lab0-c 的 make test 時可通過 trace trace-17-complexity。

+++ 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

也順利的在 Actions 出現可愛的卡比：

研讀 Linux 核心原始程式碼的 lib/list_sort.c

整合網頁伺服器

去年我也沒有完成這部份，應該說我一直不懂這個部份到底要幹麻，不像是其他佇列指定操作那麼具體，雖然作業截止期限已過，但我還是決定在進行作業六之前，嘗試解決這個部份。

在 qtest 中也有提供 web 命令，如下輸入後會等待 port 9999 的輸入：

$ ./qtest

cmd> web
listen on port 9999, fd is 3

此時開啟另一個終端機，當輸入：

$ curl http://localhost:9999/new

此時第一個終端機會如同正常使用 qtest 初始化一個佇列：

$ ./qtest

cmd> web
listen on port 9999, fd is 3
cmd> 
l = []

接著進行一連串的佇列操作：

$ curl http://localhost:9999/it/1   
$ curl http://localhost:9999/it/2
$ curl http://localhost:9999/it/3

當然剛剛初始化的佇列也會完成對應的操作：

$ ./qtest

cmd> web
listen on port 9999, fd is 3
cmd> 
l = []
cmd> 
l = [1]
cmd> 
l = [1 2]
cmd> 
l = [1 2 3]

在 qtest 中的命令都會對應到一個 do_xxx 函式，搜尋 do_web 後會發現其實作在 console.c 中：

static bool do_web(int argc, char *argv[])
{
    int port = 9999;
    if (argc == 2) {
        if (argv[1][0] >= '0' && argv[1][0] <= '9')
            port = atoi(argv[1]);
    }

    web_fd = web_open(port);
    if (web_fd > 0) {
        printf("listen on port %d, fd is %d\n", port, web_fd);
        line_set_eventmux_callback(web_eventmux);
        use_linenoise = false;
    } else {
        perror("ERROR");
        exit(web_fd);
    }
    return true;
}

這邊可以看到，將 9999 作為參數傳入 web_open 函式，其實作在 web.c 中：

int web_open(int port)
{
    int listenfd, optval = 1;
    struct sockaddr_in serveraddr;

    /* Create a socket descriptor */
    if ((listenfd = socket(AF_INET, SOCK_STREAM, 0)) < 0)
        return -1;

    /* Eliminates "Address already in use" error from bind. */
    if (setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, (const void *) &optval,
                   sizeof(int)) < 0)
        return -1;

    // 6 is TCP's protocol number
    // enable this, much faster : 4000 req/s -> 17000 req/s
    if (setsockopt(listenfd, IPPROTO_TCP, TCP_CORK, (const void *) &optval,
                   sizeof(int)) < 0)
        return -1;

    /* Listenfd will be an endpoint for all requests to port
       on any IP address for this host */
    memset(&serveraddr, 0, sizeof(serveraddr));
    serveraddr.sin_family = AF_INET;
    serveraddr.sin_addr.s_addr = htonl(INADDR_ANY);
    serveraddr.sin_port = htons((unsigned short) port);
    if (bind(listenfd, (struct sockaddr *) &serveraddr, sizeof(serveraddr)) < 0)
        return -1;

    /* Make it a listening socket ready to accept connection requests */
    if (listen(listenfd, LISTENQ) < 0)
        return -1;

    server_fd = listenfd;

    return listenfd;
}

在 CS:APP 第 11 章重點提示有介紹到 client 及 server 的細節：

呼叫 getaddrinfo() 解析位址並取得 struct addrinfo，其中包含 IP、通訊埠與服務名稱等資訊
接著透過 socket() 建立通訊端，回傳一個檔案描述子；此步驟僅建立端點，不會觸發網路傳輸
server 呼叫 bind() 將 socket 與指定 IP 與通訊埠連結 (位於核心空間)
server 進入監聽狀態並呼叫 listen()，等待 client 連線
server 使用 accept() 接受連線並為該 client 建立新的 socket
client 端則在 connect() 發出連線要求並等待 server accept
連線建立後，雙方透過 read／write (或封裝如 rio，reliable I/O)進行資料交換
當 client 結束會送出 EOF，server 接收後關閉對該 client 的 socket
server 關閉後可選擇再接受下一個 client，或關閉整體服務

追蹤程式的執行順序：

第 1 步：
在 qtest.c 的 main 函式，接近末端的部份會呼叫 run_console()。

第 2 步：
因為在 console.c 中會把變數 use_linenoise 設為 false，所以在 run_console() 中，一旦 CLI 輸入命令 web 時，另一個 client 的終端機會執行下面的程式區塊：

if (!use_linenoise) {
    while (!cmd_done())
        cmd_select(0, NULL, NULL, NULL, NULL);
}

第 3 步，在 cmd_select 中會呼叫 linenoise()，而接著又呼叫 line_raw()：

/* This function calls the line editing function line_edit() using
 * the STDIN file descriptor set in raw mode.
 */
static int line_raw(char *buf, size_t buflen, const char *prompt)
{
    if (buflen == 0) {
        errno = EINVAL;
        return -1;
    }

    if (enable_raw_mode(STDIN_FILENO) == -1)
        return -1;
    int count = line_edit(STDIN_FILENO, STDOUT_FILENO, buf, buflen, prompt);
    disable_raw_mode(STDIN_FILENO);
    printf("\n");
    return count;
}

而由於在 do_web() 中會：

line_set_eventmux_callback(web_eventmux);

所以此時　eventmux_callback　為　web_eventmux。而回到 line_ediｔ() 中：

if (eventmux_callback != NULL) {
    int result = eventmux_callback(l.buf, l.buflen);
    if (result != 0)
        return result;
}

第 4 步，在 web_eventmux 實現 accept()，其中 web_recv 會解析我們輸入的 client 命令：

curl http://localhost:9999/new

在 `qtest` 提供新的命令 shuffle

commit 1729ab3

在 qtest.c 中，可以觀察到各個 do_xxx 函式與 console_init 中的 ADD_COMMAND 是成對出現的：


static bool do_free(int argc, char *argv[])
{
    ...
}
static bool do_new(int argc, char *argv[])
{
    ...
}

...
    
static void console_init()
{
    ADD_COMMAND(new, "Create new queue", "");
    ADD_COMMAND(free, "Delete queue", "");
    ...
}

shuffle 並不需要額外參數，在命令列中應該輸入 shuffle 就能執行對應的操作，所以可以模仿其他函式進行錯誤警告的實作：

if (argc != 1) {
    report(1, "%s takes no arguments", argv[0]);
    return false;
}

if (!current) {
    report(3, "Warning: Try to shuffle null queue");
    return false;
}

結果當我執行 qtest 時：

$ ./qtest                                

cmd> new
l = []
cmd> it RAND 100
l = [rfxvub erkbcmqy khphreco ufbtmy ciwwwqvd mslfbza lglwjtlqc drorzqted vqjhtf xiebqselp gauonpxm sznzaef nkilnoysx vovqrvkfu skxoxte nacllgf bvlbrb eysxaneo mkdxqw jdaxhd bgzgoyv caijpch oinxah jgibwiyp vanadkls wvyowlqg kwihxzx bwkapu hnvjvx qppvhoi ... ]
cmd> shuffle
ERROR:  Queue is not doubly circular

回顧我目前的實作，我發現我的程式碼有一個致命的問題：

在這種狀況下交換是沒有問題的，但是當 old 與 new 相鄰時：

我原先的實作又用了兩個指標去指向 old->prev 及 new->prev：

接著透過 list_move 來完成交換，這樣會發生 list_move(old,old)，而 list_move 本身的實作是透過 list_del 及 list_add 來完成，所以才會出錯。

所以我後來額外實作一個用於交換兩個指定節點的 swap 函式。再次執行 qtest 驗證：

$ ./qtest         

cmd> new
l = []
cmd> it RAND 10
l = [rmnqgw ipjdadbzo kiifcpvo zeprnzjxd chvtmir hudomvao dzmqjgxrf oasrjacv rjdkwjbkm viuaiyi]
cmd> shuffle
l = [kiifcpvo chvtmir rjdkwjbkm zeprnzjxd viuaiyi rmnqgw hudomvao dzmqjgxrf oasrjacv ipjdadbzo]

在實作的過程中，我意識到一個問題：

實際上，交換兩個節點的值未必得進行節點的移動。可以直接利用 list_entry 來獲取內嵌的 element_t 結構體的值，僅需進行簡單的值交換。這個思路或許可以進一步應用於 q_reverse、q_reverseK 和 q_swap 等函式中，仍待驗證。

rebase

根據 N03: review 檢查事項 3，須利用 git rebase ，將先前的已提交的 commit 移至 3 月 18 日或之後的更新之上。

首先加入上游的 branch：

$ git remote add upstream https://github.com/sysprog21/lab0-c.git

用 rebase 把自己的 commit 移到最新 upstream 後面：

$ git rebase upstream/main

Auto-merging scripts/check-repo.sh
Auto-merging scripts/checksums
CONFLICT (content): Merge conflict in scripts/checksums
Auto-merging scripts/commit-msg.hook
Auto-merging scripts/common.sh
Auto-merging scripts/install-git-hooks
CONFLICT (content): Merge conflict in scripts/install-git-hooks
Auto-merging scripts/prepare-commit-msg.hook
error: could not apply 1e6e0c0... Utilize common script when possible
hint: Resolve all conflicts manually, mark them as resolved with
hint: "git add/rm <conflicted_files>", then run "git rebase --continue".
hint: You can instead skip this commit: run "git rebase --skip".
hint: To abort and get back to the state before "git rebase", run "git rebase --abort".
Could not apply 1e6e0c0... Utilize common script when possible

首先看到衝突出現在 scripts/checksums

<<<<<<< HEAD
bff0704601c8197ae6b847647b4167664b7d6abc  queue.h
b26e079496803ebe318174bda5850d2cce1fd0c1  list.h
=======
398b59c23f699ff1bf1e73a94503a9a91caa9207  queue.h
9be9666430f392924f5d27caa71a412527bf9267  list.h
>>>>>>> 1e6e0c0 (Utilize common script when possible)
1029c2784b4cae3909190c64f53a06cba12ea38e  scripts/check-commitlog.sh

根據先前提交 pull request 的經驗，這邊選擇保留 upsteam 的版本。

-   <<<<<<< HEAD
    bff0704601c8197ae6b847647b4167664b7d6abc  queue.h
    b26e079496803ebe318174bda5850d2cce1fd0c1  list.h
-   =======
-   398b59c23f699ff1bf1e73a94503a9a91caa9207  queue.h
-   9be9666430f392924f5d27caa71a412527bf9267  list.h
-   >>>>>>> 1e6e0c0 (Utilize common script when possible)
    1029c2784b4cae3909190c64f53a06cba12ea38e  scripts/check-commitlog.sh

接著：

$ git add scripts/checksums
$ git status     ok  16:12:09 
interactive rebase in progress; onto 5223a1d
Last commands done (11 commands done):
   pick 075d580 Implement q_reverse
   pick 1e6e0c0 Utilize common script when possible
  (see more in file .git/rebase-merge/done)
Next commands to do (23 remaining commands):
   pick a82c116 Change 'commit_msg_lines' to  'COMMIT_MSG_LINES'
   pick eee3f39 Utilize common script for pre-commit hook
  (use "git rebase --edit-todo" to view and edit)
You are currently rebasing branch 'master' on '5223a1d'.
  (fix conflicts and then run "git rebase --continue")
  (use "git rebase --skip" to skip this patch)
  (use "git rebase --abort" to check out the original branch)

Changes to be committed:
  (use "git restore --staged <file>..." to unstage)
	modified:   scripts/checksums

Unmerged paths:
  (use "git restore --staged <file>..." to unstage)
  (use "git add <file>..." to mark resolution)
	both modified:   scripts/install-git-hooks

這邊顯示還有另一個檔案的衝突須處理，也是保留 upsteam 版本的 scripts/install-git-hooks，將所有的衝突解決後最後再用：

$ git push origin master --force

如此即完成指定的檢查項目。

留意 git rebase 操作，預期:

已修正，目前的 commit 歷史已符合預期了。

在 3 月 20 日的直播中，授課老師檢查了我的 rebase 情況，發現了一些錯誤。我的解決方式如下：

首先檢查我自己所提交的 commit：

$ git log --oneline --author=yy214123

切換到一個與 upstream 相同的乾淨分支，利用 cherry-pick 將之前的 commit 合併到這個乾淨的分支上：

$ git cherry-pick f591d8a 8b6b5dc 6e45da5 0dbc29a f78288d e0515ae 6bbdec7 ddb885b bec2a7b da25fce a56881b 6c2c172 c37bc7f 681806a 341fbed a8e6d35 724a562 0384b18 9794565 fb7fbaa 0d3d3e4 d40f772 8f2422c aaaea07

接著切換回 master 分支：

$ git checkout master

並將 master 的內容完全重設為剛才乾淨的內容：

$ git reset --hard clean-rebase

最後，再次執行 pus：

$ git push origin master --force

review

根據信件，指定我回顧及審查的學員有以下 5 位：

N04: kxo

為什麼不存浮點數？
用 arm 架構舉例，平常做 context switch 時只要保存 cpsr 及 spsr 內容即可，若要存浮點數，則須額外依賴 vfp(一個 double 8 bytes，需要額外 8 * 16 bytes 空間)。

額外問題紀錄

處理 commit message 遺失 Change-Id 的錯誤

使用 git rebase -i 來解決上方 Change-Id 不正確顯示的問題。由於出現問題的是最新兩則 commit message，故使用下方命令：

$ git rebase -i HEAD~2

pick a7b2431 Implement q_insert_head
pick 2deb4b2 Implement q_insert_tail

# Rebase dfb08dd..2deb4b2 onto dfb08dd (2 commands)
#
# Commands:
# p, pick <commit> = use commit
# r, reword <commit> = use commit, but edit the commit message
# e, edit <commit> = use commit, but stop for amending
# s, squash <commit> = use commit, but meld into previous commit
# f, fixup [-C | -c] <commit> = like "squash" but keep only the previous
#                    commit's log message, unless -C is used, in which case
#                    keep only this commit's message; -c is same as -C but
#                    opens the editor
# x, exec <command> = run command (the rest of the line) using shell
# b, break = stop here (continue rebase later with 'git rebase --continue')
# d, drop <commit> = remove commit
# l, label <label> = label current HEAD with a name
# t, reset <label> = reset HEAD to a label
# m, merge [-C <commit> | -c <commit>] <label> [# <oneline>]
#         create a merge commit using the original merge commit's
#         message (or the oneline, if no original merge commit was
#         specified); use -c <commit> to reword the commit message

因為我只要修改 commit message，並沒有要修改 commit 的程式碼，所以此處選擇 reword。

-   pick a7b2431 Implement q_insert_head
-   pick 2deb4b2 Implement q_insert_tail
+   reword a7b2431 Implement q_insert_head
+   reword 2deb4b2 Implement q_insert_tail

此時會開啟這兩則 commit message，我進行小幅度修改後，接著：

$ git push --force-with-lease origin master

commit 012fc82 ＆ commit 98d66c4
檢查新的 commit message 還是沒有觸發 Git hooks。

隨後我刪除這兩次 commit：

$ git reset --hard HEAD~2
$ git push --force

commit f63c3aa ＆ commit 4123e63
重新 clone 專案並修改程式碼，再重新 git push 一次，檢查 commit message 後發現 Change-Id 遺失的問題已解決。

Peter Chen; Kohan Chen

2025/03/07 16:13:52

不會出現相關警告

奇怪的知識增加了，之前 weishsinyei 說不能修改，我問 GPT 也說不能修改。因為 git hook 會在當地檢查，這樣我了解了。

POJU

2025/03/20 05:08:49

我也是問完老師後，去追蹤 queue.h list.h 等檔案的過往更新紀錄，才懂怎麼改。

2025/03/20 02:20:34

commit b484286 https://github.com/yy214123/lab0-c/commit/b484286db17ac2702adc9f100183fd5645113bec

這個 commit 是空的！

2025/03/20 05:04:46

對，這個 commit 只是新增檔案而已。後續相關的實作會有其他 commit。

Jim Huang

2025/03/20 14:34:03

環狀

「環狀」應在「雙向」之前

2025/03/20 15:46:41

2025/03/20 14:49:21

程式碼變得很混亂，因此今年額外新增了 sort.c 檔案

TODO: 針對不同的資料排序實作，補上效能分析

2025/03/21 14:13:35

2025/03/27 10:20:19

Glist

2025/03/27 10:27:21

我打錯字了，正確名稱是 "Gist" 才對。

2025q1 Homework1 (lab0)

Reviewed by Andrushika

q_insert_head, q_insert_tail

q_ascend & q_descend q_reverse 版本

HackMD 的小問題

開發環境

前置作業

指定的佇列操作

q_size

q_new

q_free

q_insert_head & q_insert_tail

執行 qtest 時發現錯誤

q_remove_head & q_remove_tail

註解修正

q_delete_mid

TODO：效能比較

註解修正

q_delete_dup

q_swap

q_reverse

q_reverseK

q_ascend & q_descend

q_sort

TODO：排序法效能比較

準備測試資料

結果

q_merge

研讀 〈Dude, is my code constant time?〉

lab0-c 相關程式碼追蹤

研讀 Linux 核心原始程式碼的 lib/list_sort.c

整合網頁伺服器

在 qtest 提供新的命令 shuffle

rebase

review

N04: kxo

額外問題紀錄

處理 commit message 遺失 Change-Id 的錯誤

Read more

2025q1 Homework5 (assessment)

2025q1 Homework3 (kxo)

2025q1 Homework6 (ktcp)

2025q1 Homework1 (ideas)

Reviewed by `Andrushika`

研讀〈Dude, is my code constant time?〉

在 `qtest` 提供新的命令 shuffle