2024q1 Homework1 (lab0)

contributed by < ssheep773 >

Reviewed by `SuNsHiNe-75`

- 請把完整程式碼移除，如要討論才將要討論之部分「重點列出」。 - 注意標點符號的使用，有些地方都沒有「句號」。 - 進度太慢。 - 可善用 Valgrind 工具來追蹤記憶體使用狀況。

你的洞見呢？與其談「心法」，不如設想「如果我是你」，我會怎麼做，示範一次給同學看，而且檢討自己哪裡沒做好，從而呼應原本學員的不足處。
清楚標示學員的 git commits 和敘述的不足處，予以檢討。
軟體工程師要學會說故事，本作業要求學員從良性詳盡的批評開始。繼續檢討！

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

Reviewed by `stevendd543`

q_ascend 中按照你的程式邏輯，是從左向右尋找並檢查，所花的複雜度高達 \(O(n^2)\) ，可以嘗試換方向思考從右邊開始處理，可讓複雜度降到 \(O(n)\)。

感謝你的建議，我已於筆記新增修改後程式的開發過程
commit 98a4c46

Reviewed by `st10740`

q_swap 中交換兩兩節點位置的方法可以使用 list.h 提供的 list_move 方法取代 list_del_init 和 list_add，可以達到一樣的效果且更簡潔。

感謝建議，已修改成更精簡的程式
commit 98a4c46

有些 commit 未利用 commit messages 說明該次變更的內容, 原因和做法，可以將其補上方便他人理解程式碼的變更。

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  32
  On-line CPU(s) list:   0-31
Vendor ID:               GenuineIntel
  Model name:            13th Gen Intel(R) Core(TM) i9-13900
    CPU family:          6
    Model:               183
    Thread(s) per core:  2
    Core(s) per socket:  24
    Socket(s):           1
    Stepping:            1
    CPU max MHz:         5600.0000
    CPU min MHz:         800.0000
    BogoMIPS:            3993.60
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   896 KiB (24 instances)
  L1i:                   1.3 MiB (24 instances)
  L2:                    32 MiB (12 instances)
  L3:                    36 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-31

指定的佇列操作

`q_new`

使用 list.h 中的 INIT_LIST_HEAD 來初始化 struct list_head

struct list_head *q_new()
{
    struct list_head *new_head = malloc(sizeof(struct list_head));
    if (!new_head)
        return NULL;

    INIT_LIST_HEAD(new_head);

    return new_head;
}

`q_free`

使用 list.h 中的 list_for_each_entry_safe(entry, safe, head, member) 走訪每個節點。

在走訪的過程中，可以對 entry 作任意操作，且不影響後續節點的走訪，利用這個特性逐個節點刪除。

目前的例子中則是透過 element_t 中的struct list_head list

void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *current, *next;
    list_for_each_entry_safe (current, next, head, list) {
        q_release_element(current);
    }
    free(head);
}

`q_insert_head`

使用list.h 中的 list_add() 函式，將新增的節點添加在佇列的開頭
使用 strdup() 可以動態配置字串的記憶體空間，沒有使用 strncpy() 的原因是需要另外計算字串長度

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    new->value = strdup(s);
    if (!new->value) {
        free(new);
        return false;
    }
    list_add(&new->list, head);
    return true;
}

`q_insert_tail`

作法與 q_insert_head() 差異在於節點插入的位置不同，使用 list_add_tail() 函式將節點新增在尾端。
commit

-   list_add(&new->list, head);
+   list_add_tail(&new->list, head);

`q_remove_head`

使用到 list.h 中的函式

list_first_entry() 回傳 head 的第一個節點
list_del() 雖然名稱有 del 但並沒有將節點刪除，而是將節點 node 從 linked list 上 remove，成為單獨的節點

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *rm_node = list_first_entry(head, element_t, list);
    list_del(&rm_node->list);
    if (sp != NULL) {
        strncpy(sp, rm_node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return rm_node;
}

`q_remove_tail`

作法與 q_remove_head 差異在於移除節點的位置不同，使用list_last_entry() 函式獲取鏈結串列的尾端節點

-   element_t *rm_node = list_first_entry(head, element_t, list);
+   element_t *rm_node = list_last_entry(head, element_t, list);

`q_delete_mid`

使用你所不知道的 C 語言: linked list 和非連續記憶體中提到的快慢指標，找到中間的節點並刪除

bool q_delete_mid(struct list_head *head)
{
    if (!head || !head->next)
        return false;
    struct list_head *slow = head->next;
    for (struct list_head *fast = head->next;
         fast != head && fast->next != head; fast = fast->next->next) {
        slow = slow->next;
    }
    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}

`q_delete_dup`

參考 Risheng 進行實作
函式假設： *head 是排序好的鏈結串列

變數說明：
cur : 指向當前節點的指標
next : 指向 cur 下一個節點的指標
flag : 表示是否發生資料相同的情況

因為 head 是排序好的串列使用，所以加入 !strcmp(cur_entry->value, nxt_entry->value) 作為迴圈中止的條件

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫。

好的老師

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head) || list_is_singular(head))
        return false;
    struct list_head *cur = head->next, *next = cur->next;
    bool flag = false;

    while (cur != head && next != head) {
        element_t *cur_entry = list_entry(cur, element_t, list);
        element_t *nxt_entry = list_entry(next, element_t, list);
        while (next != head && !strcmp(cur_entry->value, nxt_entry->value)) {
            list_del(next);
            q_release_element(nxt_entry);
            next = cur->next;
            nxt_entry = list_entry(next, element_t, list);
            flag = true;
        }
        if (flag) {
            list_del(cur);
            q_release_element(cur_entry);
            flag = false;
        }
        cur = next;
        next = next->next;
    }
    return true;
}

`q_swap`

避免非必要的項目縮排 (即 * , - 或數字)，以清晰、明確，且流暢的漢語書寫。

授課教師在大學教書十餘年，見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。為此，要求學員書寫開發紀錄，並隨時做好「當主管問起，就能清晰解釋自己的投入狀況」，是強調讓學員「翻身」的本課程所在意的事。

濫用條列 (或說 bullet) 來展現，乍看很清爽，但在面試的場合中，就很難用流暢的話語說明。反之，若平日已有這方面的練習，則面試過程中，才可充分展現自己專業之處。

建立兩個指標 first 和 second

digraph ele_list {
    rankdir=LR;
    node[shape=record];
    head [label="Head"]
    e1   [label="A"]
    e2   [label="B"]
    e3   [label="C"]
    e4   [label="D"]
    e5   [label="..."]
    first [shape=plaintext;label="first"]
    second [shape=plaintext;label="second"]
    // next 方向
    head -> e1
    e1   -> e2
    e2   -> e3
    e3   -> e4
    e4   -> e5
    e5   -> head
    // prev 方向
    head -> e5
    e5   -> e4
    e4   -> e3
    e3   -> e2
    e2   -> e1
    e1   -> head
    // pointer 初始化
    first -> e1  [color=green]
    second -> e2 [color=blue]
}

使用 list_del_init 將 first 指向的節點從 linked list 取出

digraph ele_list {
    rankdir=LR;
    node[shape=record];
    head [label="Head"]
    e1   [label="A"]
    e2   [label="B"]
    e3   [label="C"]
    e4   [label="D"]
    e5   [label="..."]
    first [shape=plaintext;label="first"]
    second [shape=plaintext;label="second"]
    // next 方向
    head -> e2
    // e1   -> 
    e2   -> e3
    e3   -> e4
    e4   -> e5
    e5   -> head
    // prev 方向
    head -> e5
    e5   -> e4
    e4   -> e3
    e3   -> e2
    e2   -> head
    // pointer 初始化
    first -> e1  [color=green]
    second -> e2 [color=blue]

}

使用 list_add(first, second) 將 first 指向節點加到 second 節點指向的下一個節點位置，達到兩節點交換位置

digraph ele_list {
    rankdir=LR;
    node[shape=record];
    head [label="Head"]
    e1   [label="A"]
    e2   [label="B"]
    e3   [label="C"]
    e4   [label="D"]
    e5   [label="..."]
    first [shape=plaintext;label="first"]
    second [shape=plaintext;label="second"]
    // next 方向
    head -> e2
    e1   -> e3
    e2   -> e1
    e3   -> e4
    e4   -> e5
    e5   -> head
    // prev 方向
    head -> e5
    e5   -> e4
    e4   -> e3
    e3   -> e1
    e1   -> e2
    e2   -> head
    // pointer 初始化
    first -> e1  [color=green]
    second -> e2 [color=blue]
}

first 指向 node C 結束這次的迴圈

void q_swap(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *first = head->next;

    while (first != head && first->next != head) {
        struct list_head *second = first->next;
        list_del_init(first);
        list_add(first, second);
        first = first->next;
    }
}

經由 st10740 的建議我再次查看 list_del_init 、list_add 、 list_move 這三個函式，我發現 list_move 的操作跟 list_del_init 加 list_add 的操作相比，只是少了
過程中移除 node 後的節點初始化，而在 swap 的過程中我們其實不需要將移除的節點初始化，因為我們馬上會在後續的 list_add 為其分派指標位置

-        list_del_init(first);
-        list_add(first, second);
+        list_move(first, second)

`q_reverse`

使用 list_for_each_safe 走訪原始的鏈結串列，並使用 list_move 將節點移至串列的開頭，結束後即可得到反轉的鏈結串列

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *cur, *safe;
    list_for_each_safe (cur, safe, head) {
        list_move(cur, head);
    }
}

`q_reverseK`

cut : 指向未完成反轉的串列
count ：紀錄訪問節點個數
每當訪問 K 個節點，就將那 K 個節點透過 list_cut_position(&tmp, cut, node) 切出來放到 tmp ，並透過 q_reverse() 反轉，使用 list_splice(&tmp, cut) 把 tmp 接回 cut ，最後更新 cut 指向未完成反轉的串列

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;
    struct list_head *node, *safe, *cut = head;
    LIST_HEAD(tmp);
    int count = 0;
    list_for_each_safe (node, safe, head) {
        count++;
        if (count == k) {
            list_cut_position(&tmp, cut, node);
            q_reverse(&tmp);
            count = 0;
            list_splice(&tmp, cut);
            cut = safe->prev;
        }
    }
}

`q_merge_two`

參考王彥傑同學進行實作，發現在決定排序的程式碼可進行優化
透過真值表說明 descend 與 cmp <= 0 的關係是互斥或 ( XOR )

descend ：決定串列是否遞減
cmp <= 0 ：表示 L1 數值較小
list_move_tail() : 將節點新增到串列中

descend	cmp <= 0	list_move_tail()
True	True	L2
True	False	L1
False	True	L1
False	False	L2

static int q_merge_two(struct list_head *L1, struct list_head *L2,
                       bool descend)
{
    if (!L1 || !L2)
        return 0;

    int count = 0;
    LIST_HEAD(tmp);
    while (!list_empty(L1) && !list_empty(L2)) {
        element_t *L1_entry = list_first_entry(L1, element_t, list);
        element_t *L2_entry = list_first_entry(L2, element_t, list);
        int cmp = strcmp(L1_entry->value, L2_entry->value);
-       if (descend)
-           cmp = -cmp;
-       if (cmp <= 0)
-           list_move_tail(&L1_entry->list, &tmp);
+       if (descend ^ cmp <= 0))
+           list_move_tail(&L1_entry->list, &tmp);
        else
            list_move_tail(&L2_entry->list, &tmp);
        count++;
    }
    count += q_size(L1) + q_size(L2);
    list_splice(&tmp, L1);
    list_splice_tail_init(L2, L1);
    return count;
}

`q_sort`

參考 yanjiew1 同學進行實作，同時改成使用快慢指標來尋找中間節點

你如何確認目前的測試方式/資料已涵蓋排序演算法的最差狀況？

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    /* Find middle point */
-   struct list_head *mid, *left, *right;
-   left = right = head;
-   do {
-       left = left->next;
-       right = right->prev;
-   } while (left != right && left->next != right);
-   mid = left;

+   struct list_head *slow, *fast, *mid;
+   slow = fast = head;
+   do {
+       slow = slow->next;
+       fast = fast->next->next;
+   } while (fast != head && fast->next != head);

    mid = slow;

    LIST_HEAD(second);
    list_cut_position(&second, mid, head->prev);
 
    /* Conquer */
    q_sort(head, descend);
    q_sort(&second, descend);

    /* Merge */
    q_merge_two(head, &second, descend);
}

若要實作分治法（Divide and conquer）則需要尋找串列的中間節點，我首先想到可以使用 q_delete_mid 中找中點的方法，然而在q_sort 上卻會出錯

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

實作下列的修改後雖然可以執行，但是 mid 的數值都是等於串列的第一個節點，由此推斷在原先的迴圈結束後 slow 會等於 head

-   mid = slow;
+   mid = slow->next;

修改初始值 *fast = head->next->next ，則可以成功執行，但其中的緣由還在釐清當中

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

`q_ascend` / `q_descend`

q_ascend 和 q_descend 使用相同的方法，差異只在其中 strcmp() 比較節點資訊的是大於還是小於
這裡以 q_descend 作範例說明

避免非必要的項目縮排 (即 * , - 或數字)，以清晰、明確，且流暢的漢語書寫。

我們會走訪串列的每個節點，並且同時檢查它右邊節點是否大於目前的節點，若成立則表示目前的節點需要刪除，才能滿足串列是遞減的，並使用 flag 紀錄目前節點需要刪除，在後續的程式碼中刪除此節點。

int q_ascend(struct list_head *head)
{
    if (!head)
        return 0;

    struct list_head *cur = head->next;

    while (cur != head && cur->next != head) {
        struct list_head *nxt = cur->next;
        element_t *cur_entry = list_entry(cur, element_t, list);
        bool flag = false;

        while (nxt != head) {
            element_t *nxt_entry = list_entry(nxt, element_t, list);
            if (strcmp(cur_entry->value, nxt_entry->value) > 0) {
                flag = true;
                break;
            }
            nxt = nxt->next;
        }
        struct list_head *tmp = cur->next;
        if (flag) {
            list_del(cur);
            q_release_element(cur_entry);
        }
        cur = tmp;
    }
    return q_size(head);
}

開發紀錄：

原先沒有使用 tmp 先儲存 cur->next ，造成讀取到遭刪除的 cur

+       struct list_head *tmp = cur->next;
        if (flag) {
            list_del(cur);
            q_release_element(cur_entry);
        }
-       cur = cur->next;
+       cur = tmp;

在除錯過程中發現，因為編譯器會執行程式的最佳化，使程式的執行不是如程式碼一樣線性的執行，所以我在除錯過程中，有先關閉編譯器最佳化

/* Makefile */
-   CFLAGS = -O1 -g -Wall -Werror -Idudect -I.
+   CFLAGS = -g -Wall -Werror -Idudect -I.

經由 stevendd543 的建議，我將複雜度降到 \(O(n)\) ，我首先使用 cur 與 next 指向目前節點與目前節點的前一個節點，因為我們要倒著走訪整個鏈結串列，在走訪的過程中我們會比較目前的節點與前一個節點的值，若目前的節點較大，等於是說在串列中有一個節點比它後面的節點小，這樣就違反遞增的條件需要刪除，而若是符合遞增條件，則將會往下一個節點走訪。

原本的作法的複雜度會是 \(O(n^2)\) ，因為每個節點的走訪都是獨立的，每次都需要重新走訪所有目前節點的所有右邊的節點，等於是我們重複走訪最後一個節點 n-1 次
而目前方法則是用 cur 紀錄目前值最大節點，因為若是節點符合條件，則表示他是目前最大的節點，透過走訪刪除不符合的節點或是更新目前的最大節點，來達到嚴格遞減的串列

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head)
        return 0;

    struct list_head *cur = head->prev;
    struct list_head *next = cur->prev;

    while (next != head) {
        element_t *cur_entry = list_entry(cur, element_t, list);
        element_t *next_entry = list_entry(next, element_t, list);
        
        if (strcmp(cur_entry->value, next_entry->value) > 0){
            list_del(next);
            q_release_element(next_entry);
        } else {
            cur = next;
        }
        next = next->prev;
    }
    return q_size(head);
}

上面程式在 make test 的過程中，會出現存取 NULL 指標的錯誤情況出現，我分析是因為當 next 被刪除後，又在後續執行 next = next->prev 時存取next ，所以我將程式修改如下，改成透過不會被刪除的 cur 執行走訪

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head)
        return 0;

    struct list_head *cur = head->prev;
-   struct list_head *next = cur->prev;
+   struct list_head *next;

-    while (next != head) {
+    while (cur->prev != head) {
+        next = cur->prev;
        element_t *cur_entry = list_entry(cur, element_t, list);
        element_t *next_entry = list_entry(next, element_t, list);
        
        if (strcmp(cur_entry->value, next_entry->value) > 0){
            list_del(next);
            q_release_element(next_entry);
        } else {
            cur = next;
        }
-        next = next->prev;
        
    }
    return q_size(head);
}

`q_merge`

首先了解要合併的資料格式，是由許多 queue_contex_t 串接而成，我們要合併的佇列是在 queue_contex_t->q
我使用的方法事先將所有的 q 都取出來存在 tmp 最後再對 tmp 作排序，以及計算他的長度

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head)) {
        return 0;
    }

    if (list_is_singular(head)) {
        return list_first_entry(head, queue_contex_t, chain)->size;
    }

    LIST_HEAD(tmp);
    queue_contex_t *cur, *safe;
    queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);

    list_for_each_entry_safe (cur, safe, head, chain) {
        list_splice_init(cur->q, &tmp);
    }

    int size = q_size(&tmp);
    list_splice_init(&tmp, first->q);
    q_sort(first->q, descend);

    return size;
}

在 make test 測試時，trace-17-complexity.cmd 無法每次檢測都通過，目前推測是無法在常數時間內完成

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

Valgrind + 自動測試程式

使用 massif 得到分析數據，會得到行程在記憶體使用狀況的 snapshot 。

$ valgrind --tool=massif ./qtest -f <trace file>

使用 massif-visualizer 圖形化數據

$ massif-visualizer massif.out.<pid>

使用 Valgrind 驗證程式後，並沒有出現記憶體使用錯誤的狀況，但仍然會有錯誤訊息 ERROR: Probably not constant time or wrong implementation

xsheep@xsheep-super-computer:~/linux2024/lab0-c$ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
ERROR: Probably not constant time or wrong implementation
Probably constant time
Probably constant time
Freeing queue

運行 trace-017-complexity
Screenshot from 2024-03-03 15-20-45

在指令運行階段，此時佔用堆積最主要的函式是 test_malloc ，也就是在運行 q_insert_head() 和 q_insert_tail() 時會用來分配記憶體的函式

實作 `shuffle` 命令

指令

command 是「命令」，而非「指令」(instruction)

實作 Fisher-Yates shuffle Algorithm

透過閱讀 Fisher–Yates shuffle 來實作亂數演算法

commit 1152bc0

其中因為無法更改 queue.h ，我另外新建 shuffle.c ，當我要 commit shuffle.c 時，會出現錯誤

shuffle.c:25:30: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
        element_t *newnode = list_entry(new, element_t, list);
                             ^

Fail to pass static analysis.

我在參考 SHChang-Anderson 同學的 commit 後，加入註解 // cppcheck-suppress nullPointer 就可以忽略警告，詳細可以看 ~~cppcheck.net~~(網址待更新)

element_t *oldnode =
            list_entry(old, element_t, list);  // cppcheck-suppress nullPointer

統計方法驗證

利用 lab0-d 提供的程式碼測試亂度

Expectation:  41666
Observation:  {'1234': 41827, '1243': 41665, '1324': 41542, '1342': 41630, '1423': 41859, '1432': 41759, '2134': 41789, '2143': 41974, '2314': 41851, '2341': 41778, '2413': 41641, '2431': 41381, '3124': 41769, '3142': 41289, '3214': 41437, '3241': 41520, '3412': 41863, '3421': 41710, '4123': 41678, '4132': 41705, '4213': 41514, '4231': 41478, '4312': 41652, '4321': 41689}
chi square sum:  15.7246195939135

從圖表來看 shuffle 的頻率大致符合 Uniform distribution

Figure_2

論文閱讀〈Dude, is my code constant time?〉

這邊論文的目的是評估一段程式碼是否是常數時間執行。
而常數時間執行的程式，可以確保程式或系統的安全性，避免有心人的攻擊，像是常見的旁路攻擊 (Side-channel attack) 會用於破譯密碼，通過分析執行加密演算法所花費的時間來嘗試破解密碼系統。

論文提出的方法是從使用者的角度或者是說從攻擊者個角度出發，因為當我們無法通過不斷執行程式，達到嘗試破譯密碼時，其實就算是達到常數時間執行，讓使用者無法推測出程式的執行邏輯。
這個方法與現有常數時間檢測方法的差異在於不需要模擬硬體設備。

TIMING LEAKAGE DETECTION
實驗的理論是根據執行時間的 leakage detection test ，透過觀察兩個不同測資的執行時間分布是否有顯著的差異。

step 1. Measure execution time
使用 fix-vs-random tests 的方法測試，這種方法是使用兩組測資，一組是每次都固定的測資，另一組是每次都會隨機產生的測資。

step 2. Apply post-processing
典型的時間分佈會向較長的執行時間方向傾斜，這是因為當主程式執行時，可能會被作業系統中斷，造成測量誤差
(measurement artifacts)，我覺得這步驟主要是彌補沒有對硬體進行模擬。

step 3. Apply statistical test
使用 Welch's t-test 的統計分析，這個方法的特點是可以對樣本大小與資料具有不同變異數的資料進行分析。
兩次測試即使一開始設定相同的樣本的大小，也會因為後處理導致最後的樣本數出現差異，這時使用 Welch's t-test 就十分適合。

我比較論文提供的程式 dudect 與 lab0 程式碼沒有 step 2 的後處理處理測量誤差
commit 5bf3fe0

研讀並嘗試引入 Linux 核心原始程式碼的 lib/list_sort.c

老師的講解筆記
我所使用的 merge sort 方法是 top-down ，雖然使用更改串列連結的方式，可以改善原有方法對於 cache 的不友善，然而使用遞迴的方式可能會造成 stack overflow
Linux kernel 中 list_sort 所使用的方法是 bottom-up ，他是 in-place 直接在原始的數據上實作，使用到 cache 的 Temporal Locality ，畢竟鏈結串列應該是較難發生 Spatial Locality

list sort 主要是要處理原本 bottom-up 在合併時，需要較多比較次數，而因為比較是需要透過呼叫 cmp 函式，較多的比較次數也就代表需要更多的函式呼叫成本。
list sort 透過改變合併規則，確保每次合併的兩個子串列的大小比例不超過 2:1，以提高排序效率。

嘗試引入 `lib/list_sort.c`

首先，將 lib/list_sort.c 和 linux/list_sort.h 引入本專案中

首先刪除程式碼中不必要的 include

並發現程式碼中 u8 並未定義。而原本是在 linux/types.h 中被定義為 uint8_t，而 uint8_t 是由 stdint.h 所提供。因此在 list_sort.h 中新增 #include "stdint.h" ，並將 u8 更改為uint8_t，以確保相關型別的定義正確。

/* list_sort.h */
+    #include "stdint.h"

/* list_sort.c */
-    u8 count = 0;
+    uint8_t count = 0;

接著編譯時出現 implicit declaration of function ‘unlikely’ 發現程式碼中的 likely 與 unlikely 並未被定義，這裡參考 [Linux Kernel慢慢學]likely and unlikely macro 中的說明：
在 Linux kernel 2.6 之後提供了 likely, unlikely 這兩個巨集，被定義在 /include/linux/compiler.h 中，用於告訴編譯器程式碼中哪個分支轉跳的機率高，幫助編譯器作優化。

將 likely, unlikely 這兩個巨集的定義加入 list_sort.h

/* list_sort.h */
+    #define likely(x) __builtin_expect(!!(x), 1)
+    #define unlikely(x) __builtin_expect(!!(x), 0)

最後我們還會遇到 error: data definition has no type or storage class 是在 lisy_sort.c 的最後一行，目的是要使list_sort 可以在 kernel 內部自由的呼叫使用，但我們並不需要這個功能所以刪除。

-    EXPORT_SYMBOL(list_sort);

其中 list_sort 的呼叫須傳入比較函式 cmp ，我參考 chiangkd 同學的實作，在 qtest.c 中新增一個比較函式 cmp ，並以此為參數傳入 list_sort。

效能比較

參考 chiangk 的比較方法，並使用 pref 分析執行狀態

perf stat --repeat 5 -e instructions,cycles ./qtest -f traces/trace-sort.cmd

trace-sort.cmd

option fail 0
option malloc 0
new
ih RAND 500000
time
sort
time

執行時間比較

我實作的 q_sort 執行時間表：

測試次數	執行時間（秒）
1	0.45127
2	0.46406
3	0.46809
4	0.46880
5	0.45892

Instructions	Cycles
2,410,251,144	2,605,468,924

linux 的 list_sort 執行時間表：

測試次數	執行時間（秒）
1	0.44600
2	0.43859
3	0.44770
4	0.44346
5	0.44078

Instructions	Cycles
2,350,066,317	2,392,634,305

根據上述實驗結果，相較於我自己實作的排序演算法，list_sort 在執行時間呈現出更佳的效能表現。

ttt

1.將 Linux 核心的 linux/list.h 標頭檔與 jserv/ttt 中 list.h 相關的程式碼抽出，成為 hlist.h
我在查看 linux/list.h 時發現，linux kernel 有使用 READ_ONCE WRITE_ONCE 來實作 lockless contexts 避免 load-tearing (後續要查看 READ_ONCE WRITE_ONCE 功能)

2.我將原有的 ttt/main.c 改寫成 ttt_main.[ch] 方便之後在 qtest.c 中呼叫
在引入的過程中仿照 dudect 的方式將 agents 加入 Makefile ，而在 commit 時會出現出現許多 [constVariable] 與 [variableScope] 的修正提示

/* mt19937-64.c */
uint64_t mt19937_rand(void)
{
    uint64_t x;
-   int i    
    if (mti >= NN) { /* generate NN words at one time */
+        int i;
+        const static uint64_t mag01[2] = {0ULL, MATRIX_A};
-        static uint64_t mag01[2] = {0ULL, MATRIX_A};

並使用 Monte Carlo tree search (MCTS) 演算法，確保使用定點數來取代原本 jserv/ttt 的浮點數運算。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

2024q1 Homework1 (lab0)

Reviewed by SuNsHiNe-75

Reviewed by stevendd543

Reviewed by st10740

開發環境

指定的佇列操作

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_merge_two

q_sort

q_ascend / q_descend

q_merge

Valgrind + 自動測試程式

實作 shuffle 命令

實作 Fisher-Yates shuffle Algorithm

統計方法驗證

論文閱讀 〈Dude, is my code constant time?〉

研讀並嘗試引入 Linux 核心原始程式碼的 lib/list_sort.c

嘗試引入 lib/list_sort.c

效能比較

執行時間比較

ttt

Reviewed by `SuNsHiNe-75`

Reviewed by `stevendd543`

Reviewed by `st10740`

`q_new`

`q_free`

`q_insert_head`

`q_insert_tail`

`q_remove_head`

`q_remove_tail`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseK`

`q_merge_two`

`q_sort`

`q_ascend` / `q_descend`

`q_merge`

實作 `shuffle` 命令

論文閱讀〈Dude, is my code constant time?〉

嘗試引入 `lib/list_sort.c`