2025q1 Homework1 (lab0)

contributed by < CodeStone1125 >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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 字元

開發環境

$ 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
Byte Order:                      Little Endian
Address sizes:                   46 bits physical, 48 bits virtual
CPU(s):                          28
On-line CPU(s) list:             0-27
Thread(s) per core:              2
Core(s) per socket:              20
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           183
Model name:                      Intel(R) Core(TM) i7-14700 ＠ 1.50 GHz
Stepping:                        1
CPU MHz:                         1100.3190
CPU max MHz:                     5400.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4224.00  
Virtualization:                  VT-x
L1d cache:                       768 KiB
L1i cache:                       1 MiB
L2 cache:                        28 MiB
L3 cache:                        33 MiB 
NUMA node0 CPU(s):               0-27

教材閱讀

佇列操作的程式碼實作

q_new

Commit 8a99fa7

使用 malloc 避免物件的生命週期隨著 q_new 一起結束。

Commit 999800f

研讀 list.h 後使用 INIT_LIST_HEAD 簡化程式。

q_free

最一開始構思的程式碼有以下問題：

沒有仔細研讀 qtest.c 導致沒有發現不需要在函式中釋放 queue_contex_t 的記憶體。
誤用 list_for_each 而非 list_for_each_safe 導致 segemnt fault。

修正後版本：

Commit e07f9bb

void q_free(struct list_head *head)
{
    if (head == NULL)
        return;
    struct list_head *node;
    struct list_head *safe;
    list_for_each_safe (node, safe, head) {
        element_t *e_new = list_entry(node, element_t, list);
        if (e_new->value)
            free(e_new->value);
        free(e_new);
    }
    free(head);
    return;
}

q_size

Commit 25c014d

我使用了 list_for_each_safe 走訪佇列的每一個元素並計算佇列長度但因為操作沒有涉及元素的刪除應該使用 list_for_each 即可可以省下一半的走訪成本。

另外也許可以結合 queue_contex_t 的使用在每次對佇列的操作都對 queue_contex_t.size 進行佇列長度的維護這樣的話呼叫 q_size 就直接回傳 queue_contex_t.size 即可。

q_del_mid

Commit 55147bf

參考指標篇的快慢指標實作 q_del_mid，值得注意的是 slow & fast 指標的起始點從 head 或是 head->next 結果是一樣的，因為已經設定了只要佇列長度小於1就不會進入迴圈計算而在佇列長度大於等於2的情況下兩者結果一樣，但是 head->next 可以減少一次迴圈次數所以我認為是更優異的選擇。


struct list_head * slow = head->next;
for(struct list_head * fast = head->next; fast->next!=head && fast->next->next!=head; fast=fast->next->next){
    slow = slow->next;
}

Commit 5afc936

這個提交修正了初版沒有手動釋放包含 mid 的元素記憶體空間，導致的記憶體洩漏。

+    element_t *e = list_entry(slow, element_t, list);
+    free(e->value);
+    free(e);

q_insert_head ＆ q_insert_tail

q_insert_head：Commit 4a12cd0
q_insert_tail：Commit 879b201

插入在開頭和結尾的邏輯類似，差別在於只在於透過開頭的 ->prev 存取結尾來操作。並且二者都要針對當前佇列是否為空做處理。

+    element_t *e_new = (element_t *)malloc(sizeof(element_t));
+    e_new->value = (char *)malloc(sizeof(char)*(1+strlen(s)));

使用 malloc 分配記憶體空間到堆積避免插入的 element_t 及其中的物件生命週期隨著函式結束終止產生 dangling pointer 問題。 malloc 回傳的 void * 是不可以直接進行物件存取，要透過強制轉型成適配的資料型態以作進一步操作。

Dangerous function detected in strcpy(e_new->value, s);
Read 'Common vulnerabilities guide for C programmers' carefully.

針對 strcpy 導致可能發生的溢位問題使用 strlcpy 限制使用的記憶體位址範圍防範。

q_remove_head & q_remove_tail

q_remove_head：Commit 5ad38c7
q_remove_tail:：Commit 16be85b

需要注意的點和實作邏輯和 q_insert_head ＆ q_insert_tail 類似故不贅述。

Commit 4070736

這次提交修正了對於 strlcpy 理解不完全輸入錯誤的參數導致的無法通過 truncated strings 的測試。

q_ascend & q_descend

Commit e43716f

q_ascend 和 q_descend 的實作邏輯類似

利用堆疊儲存元素
當下在堆疊頂端的元素嚴格大於（小於）當下的檢查的元素
直到堆疊頂端不再嚴格大於（小於）當下的檢查的元素
將堆疊的結果放回佇列中並釋放堆疊

q_reverseK & q_reverse

q_reverseK：Commit 5937720
q_reverse：Commit 904be06

q_reverseK 的做法利用兩個指標 start 和 end：
用 while 迴圈走訪整個佇列，start 和 end 放在第一個元素並且 end 持續走訪佇列每當 end 向前走訪 K-1 個元素則用另一個 tmp 搭配 list_add_tail 反轉佇列在放回原本的佇列中。

此外我的 q_reverse 是 q_reverseK 的特例 q_size == K

q_delete_dup

Commit 672cee2

首先我的想法是：

利用 q_sort 將所有重複的元素排序在一起
使用 list_for_each_safe 走訪所有元素
兩兩比較確認是否有的重複元素，利用 dup 記錄當前的元素是否和下一個元素重複，
- 如果重複，刪除當前的元素dup 改成 true。
- 如果沒有重複則把當下元素加入 tmp 暫時存放。
當 dup == true 時可以知道當前的元素是重複的（即使當下兩兩比較的元素不同），因此刪除當前的元素並將 dup 改回 false。
最後把 tmp 中不重複元素放回原本的佇列。

q_swap

Commit 467decc

在迴圈中每兩個一組 <first, second> 的進行交換，每一次迴圈 first 指標指向下兩個元素並且將 swp_tmp 指向 second 進行元素的刪除和加入，此處應可用 list_del_init 簡化程式碼。

        swp_tmp->next = first;
        first->prev = swp_tmp;

+       first = first->next;
-       first = first->next->next;

另外，測試結果中發現我使用交換的方式，並且交換完後使用 first->next->next 存取下一對元素會出現錯誤，因為 first 經過交換後實際上只需要使用 first->next 即可存取到下一對元素的 first。

以下是錯誤更正前的執行結果:

l = [a b c d e f]
cmd> swap
l = [b a c e d f]

q_sort

Commit a14ee65

這個提交是我實作的 stable 的 merge sort ，利用遞迴版本 q_sort 切割佇列元素，並且用 mergeTwoList（left, right） 排序並結合分為兩種情況：

left， right 都非空及 NULL
兩者其中一個是空或 NULL
情況1.需要分別比較兩者的最小元素比較小的元素來做合併，並重複比較直到情況2.後直接將剩餘的元素合併進入結果即可：

參考了 lib/list_sort.c 利用 strcmp >= 0 來保證排序的穩定性

Segment Fault

我原本的思路是在 mergeTwoList 使用額外建立 result 儲存合併結果在情況2.後直接將剩餘的元素合併進入 result 並回傳。但是 result 是在 mergeTwoList 中建立的，物件的生命週期和函式運行週期綁定，所以回傳後再去存取 result 就會導致 Segment Fault。

    if (!list_empty(left)) {
-       list_splice(left, &result);
-       return &result;
+       list_splice(&, left);
+       return left;
    } else {
-       list_splice(right, &result);
-       return &result;
+       list_splice(&result, right);
+       return right;
    }

參考了 alexc-313 情況2.的做法將 result 利用 list_splice 加入 left 或 right並回傳，我認爲使用指標的指標可以進一步把回傳值的部分移除。

q_merge

觀察 qtest.c 發現整體架構中有四種物件：

list_head：實際用來管理佇列的物件
element_t：用於儲存佇列中的元素
queue_context_t：用於鏈結和統計單一佇列資訊
queue_chain_t：用於鏈結和統計所有佇列資訊

Commit 324ef82

q_merge 需要存取及管理到 queue_chain_t 和 queue_context_t 的部分。我目前的做法將每一輪都拿第一個佇列來做 mergeTwoList，導致第一個佇列的元素數特別多又做了很多次額外比較操作，如果能把這部分也改成 buttom-up 最後再把結果合併到第一個佇列應該可以提高效能。

此外這個做法有一些記憶體洩漏問題沒有被解決依據 queue.h 需求必須把第一個佇列以外的佇列變成 NULL-queue 但是直接將佇列變成 NULL-queue 卻沒有初始化 list_head 會導致記憶體洩漏，因為不知道指標會指向哪裡。但在此同時直接在函式中呼叫 free() 釋放記憶體又是不被允許的，我有嘗試過將變成 NULL-queue 後呼叫 INIT_LIST_HEAD 或反過來的做法都會導致 Segment Fault，但不正確初始化會導致後續 list_head 的釋放出現記憶體洩漏，我目前還沒有找到解法先做紀錄。

    ctx->q = NULL;
+   INIT_LIST_HEAD(ctx->q);

Commit 4b0a9be

參考 allen741 的做法利用 list_splice_init 將所有佇列的元素移到第一個佇列再做 q_sort，這方法可以順利初始化並避免記憶體洩漏但是會導致已經排序過的序列再次排序造成額外的比較次數，這方法就算所有序列都沒有排序過也是用算是一個更廣泛的解法，但list_splice_init 的方式避免了 mergeTwoList 不同佇列間的元素比較，哪個方法比較好要透過實際的效能測量確定。

研讀 lib/list_sort.c

研讀 Linux 核心原始程式碼

施工中

嘗試引入 `list_sort.c` 到 lab0-c 專案

Commit 93c6190

修改 `list_sort.c`

我參考 kart81604 的做法嘗試引入linux核心風格的程式碼到 lab-0-c：

// original version
__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
				struct list_head *a, struct list_head *b);
__attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
			struct list_head *a, struct list_head *b);
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);

為了引入這段程式碼我做了以下改寫：

我移除了一些額外的部分像 priv like 和 unlike __attribute__，
把 merge，merge_final，list_sort 加上前綴 lx_ 方便識別
把 cmp 用 strcmp 代替

static struct list_head *lx_merge(struct list_head *a,
                                struct list_head *b);

static void lx_merge_final(struct list_head *head,
			struct list_head *a, struct list_head *b);

void lx_list_sort(struct list_head *head);

針對我做了以上改變後遇到執行 lx_sort 遇到 segment fault，透過debug.py 訊息發現問題出在 439 行因為我在取得 element_t 物件時錯誤使用成 list_first_entry 而非 list_entry 導致。

Program received signal SIGSEGV, Segmentation fault.
0x000055555555c14d in lx_merge (a=a@entry=0x55555556a708, b=0x55555556a678) at queue.c:439
439             if (strcmp(e_a->value, e_b->value) <= 0) {

-    element_t *e_a = list_first_entry(a, element_t, list);
-    element_t *e_b = list_first_entry(b, element_t, list);
+    element_t *e_a = list_entry(a, element_t, list)
+    element_t *e_b = list_entry(b, element_t, list)->value)
if (strcmp(e_a->value, e_b->value) <= 0)

為 `qtest.c` 添加指令

Commit fd00b86

為了可以在 qtest.c 呼叫 c_sort 必須為 qtest.c 添加指令 c_sort 功能並透過選項控制使用的排序演算法。

/* Get sorting method */
const char *sort_method = argv[1];
...
if (strcmp(sort_method, "-l") == 0) {
    lx_sort(current->q);
} else if (strcmp(sort_method, "-s") == 0) {
    sediment_sort(current->q);
} else if (strcmp(sort_method, "-t") == 0) {
    tree_sort(current->q);
} else {
    report(1, "Invalid sorting method: %s", sort_method);
    return false;
}

以下是呼叫範例：

l = [dlagrm kxuimm crecsp zqzde xczea oecvj thhbki gtiji jiuauin tlldmszei]
cmd> c_sort -t // -t for treesort
l = [crecsp dlagrm gtiji jiuauin kxuimm oecvj thhbki tlldmszei xczea zqzde]

在 console_init 中加入後就可以在 qtest.c 中呼叫 lx_sort 並且呼叫後 qtest.c 會啟動 do_lx_sort ，這部分我直接複製 do_sort 並把 q_sort 改成 lx_sort。

#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

ADD_COMMAND(c_sort,
             "Various sorting queue methods, -t:tree_sort, -s:sediment_sort "
             ", -m:lx_sort",
             "");

queue.h 不能修改?

針對 queue.h 不能修改但是 qtest.c 需要從 queue.h 引入的解決辦法可以在 qtest.c 中 #include "queue.h" 的後面下一行（或更多行）宣告：

+ void lx_sort(struct list_head *head);

環狀雙向鏈結串列的排序效能比較

將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋

Commit c59ebc6

參考 2025q1 第 2 週測驗 1 穩定排序版的快速排序將程式碼整合進 lab0 提及的 qtest
將 listitem 改成 element_t 並稍微改變參數名稱和函式名即可。

Commit 51db328

先實作了一個 sort_perf.bash 使用 perf 測量不同排序法的不同指標，並且使用 gnuplot 畫圖片
以下是測量長度十萬到一百萬的排序延遲時間：
sort_comparison

Tree sort 和 Quick sort 雖然是 O(NlogN) 的演算法但是隨著鏈結串列長度增加延遲大幅上升逼近甚至超過 Sediment Sort
- Tree sort 推測時間來自 top-down 建立二元搜尋數
- Quick sort 推測來自大量的指標和陣列管理
Linux 核心的 List sort 在不論鏈結串列長度幾乎都是最佳選擇
排除 List sort 的話 Sediment Sort 雖在鏈結串列長度短的很慢但表現穩定在很長的鏈結串列長度是比 Tree sort 和 Quick sort 更快的選擇。

嘗試改進針對鏈結串列排序實作的效能

施工中

在 `qtest` 提供新的命令 `shuffle`

Commit e09e4cf

Fisher–Yates shuffle 實作

以下是我利用 Fisher–Yates shuffle 演算法實作 shuffle:

針對以下 1.~2.要重複運行 Ｎ - 1 次，Ｎ取自佇列的尺寸 q_size

從前面第 1 ~ q_size - iteration 個元素中隨機挑選一個元素 Ｒ
將Ｒ 插入佇列尾端

我透過以上想法實作 shuffle 並且在 qtest.c 加入do_shuffle

統計的原理來分析洗牌「亂度」

Expectation:  4166
Observation:  {'1234': 4166, '1243': 4180, '1324': 4234, '1342': 4327, '1423': 4251, '1432': 4173, '2134': 4186, '2143': 4113, '2314': 4142, '2341': 4173, '2413': 4209, '2431': 4223, '3124': 4168, '3142': 4183, '3214': 4174, '3241': 4180, '3412': 4061, '3421': 4072, '4123': 4183, '4132': 4053, '4213': 4166, '4231': 4163, '4312': 4107, '4321': 4096}
chi square sum:  21.31757081132981

這是測試 100000次的結果：

	觀察到的頻率	期待的頻率	$\frac{(O_{i} - E_{i})^{2}}{E_{i}}$
[1, 2, 3]	166391	166666	0.45375181500726003
[2, 1, 3]	166829	166666	0.15941463765855063
[2, 3, 1]	166807	166666	0.11928647714590858
[1, 3, 2]	166790	166666	0.0922563690254761
[3, 1, 2]	166862	166666	0.23049692198768795
[3, 2, 1]	166321	166666	0.7141528566114265
Total			1.76935907743631

從卡方分布表找合適的 P value，我們的自由度為 23，

X^{2}

為 21.31757081132981，因為 21.31757081132981 < 32.007，於是 P value 大於 0.1 。

df	0.995	0.99	0.975	0.95	0.90	0.10	0.05	0.025	0.01	0.005
20	7.434	8.260	9.591	10.851	12.443	28.412	31.410	34.170	37.566	39.997
21	8.034	8.897	10.283	11.591	13.240	29.615	32.671	35.479	38.932	41.401
22	8.643	9.542	10.982	12.338	14.041	30.813	33.924	36.781	40.289	42.796
23	9.260	10.196	11.689	13.091	14.848	32.007	35.172	38.076	41.638	44.181
24	9.886	10.856	12.401	13.848	15.659	33.196	36.415	39.364	42.980	45.559
25	10.520	11.524	13.120	14.611	16.473	34.382	37.652	40.646	44.314	46.928

因為 P value（>0.1）> alpha（0.05），統計檢定的結果不拒絕虛無假說（

H_{0}

）
也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution。

shuffle