2024q1 Homework1 (lab0)

contributed by < steven523 >

Reviewed by `SuNsHiNe-75`

注意標點符號的使用，有些地方都沒有「句號」。
請把完整程式碼移除，如要討論才將要討論之部分「重點列出」。
如有終端機相關的訊息，可在「程式區塊」的點點後加上「shell」。

Reviewed by `stevendd543`

q_free 有提到「q_release_element 刪除 entry 時不會發生錯誤」，具體錯誤原因可以清楚描述。
q_ascend 中前段的漢語表達讓讀者不容易，可透過 ChatGPT 修飾。
注意標點符號的使用，有些地方都沒有「句號」。

開發環境

$ 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:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz
    CPU family:          6
    Model:               165
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         5000.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5199.98

指定的佇列實作

`q_new`

allocate 翻譯為「配置」，以區格 dispatch (分發/分配) 的翻譯

已更改

使用 malloc 為佇列 new 配置一個動態記憶體空間，如果成功配置足夠大小的空間給 new 指標，則透過 INIT_LIST_HEAD 做初始化使 new 的 prev 和 next 皆指向自己，否則返回 NULL

struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    if (new) {
    INIT_LIST_HEAD(new);
        return new;
    } else {
        return NULL;
    }
}

`q_free`

留意資訊科技詞彙翻譯

已更改

用 list.h 的巨集 list_for_each_entry_safe 逐一走訪整個佇列並透過 safe 紀錄每個迭代當前節點的下一個節點，以致逐一走訪節點的過程中安全使用 q_release_element 刪除目前的節點

traverse (動詞) 和 traversal (名詞)

根據 Dictionary.com 的解釋: (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)

to pass or move over, along, or through.
to go to and fro over or along.

其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。

當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。

還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。

在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。

遍歷 (Ergodic) 源於以下二個希臘詞：

ergon (對應英語的 work)
odos (對應英語的 path 或 way)

最初這是由奧地利物理學家波茲曼 (Ludwig Boltzmann) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。

因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。

\to

資訊科技詞彙翻譯

void q_free(struct list_head *head)
{
    if (head) {
        element_t *entry, *safe;
        list_for_each_entry_safe (entry, safe, head, list)
            q_release_element(entry);
        free(head);
    } else
        return;
}

說好的進度呢？

`q_insert_head`

新增一個 element_t 並使用 malloc 為其配置記憶體空間，接著使用 list.h 中的 list_add 將節點插入佇列開頭。但是在測試時出現以下訊息：

cmd> new
l = []
cmd> ih a
ERROR: Need to allocate and copy string for new queue element

這個錯誤提示是在說建立新的佇列元素時需要為其分配記憶體並複製字串
所以我使用 strdup 這個函式來複製參數 s 並配置記憶體空間給它

element_t *new = malloc(sizeof(element_t));
    if (new) {
+       new->value = strdup(s);
+       if (!new->value) {
+           q_release_element(new);
+           return false;
+       }
-       new->value = s;
        list_add(&new->list, head);
        return true;
    }

`q_insert_tail`

與 q_insert_head 差不多的做法，新增一個 element_t 並使用 malloc 為其配置記憶體空間，接著使用 strdup 來複製參數 s 並配置記憶體空間給它，最後使用 list.h 中的 list_add_tail 將節點插入佇列尾端

cmd> new
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> it c
l = [b a c]
cmd> it 7
l = [b a c 7]

`q_remove_head`

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

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

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

利用 list.h 裡的 list_first_entry 將第一個節點的位址取出，接著使用 list_del_init 移除頭節點後讓節點的前後相連
最後將移除的節點數值複製到 sp ，並且複製字串到 sp 時為其加上 null terminator 的空間

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *delement = list_first_entry(head, element_t, list);
    list_del_init(head->next);

    /*If sp is non-NULL and an element is removed, copy the removed string to
     *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)*/
    if (sp) {
        strncpy(sp, delement->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return delement;
}

`q_remove_tail`

同 q_remove_head ，使用 list_last_entry 將最後一個節點的位址取出，並改用 list_del_init(head->next); 移除尾節點

l = [a b c d e]
cmd> rh
Removed a from queue
l = [b c d e]
cmd> rh
Removed b from queue
l = [c d e]
cmd> rt
Removed e from queue
l = [c d]
cmd> rt
Removed d from queue
l = [c]

`q_size`

首先判斷佇列是否為空或不存在，再來用 list.h 中的 list_for_each 逐一走訪佇列中的每個節點並將長度數值 + 1

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int len = 0;
    struct list_head *node;

    list_for_each (node, head)
        len++;
    return len;
}

`q_delete_mid`

參考第一周教材提到的快慢指標來實作，在每次迴圈中 fast 都會比 indir_slow 移動兩倍的距離，直到 fast 或fast->next 指回 head，此時 slow 就會剛好在佇列中間的位置
接著使用 list_del_init 確保在移除目標節點後前後節點相連
最後利用 list_entry 找出目標節點並使用 q_release_element 釋放記憶體空間

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head **indir_slow = &head->next;

    for (struct list_head *fast = head->next;
        fast != head && fast->next != head; fast = fast->next->next)
        indir_slow = &(*indir_slow)->next;

    struct list_head *delement = *indir_slow;

    list_del_init(delement);
    q_release_element(list_entry(delement, element_t, list));

    return true;
}

`q_delete_dup`

為一個排序後的鏈結串列刪除所有有重複字串的節點
想法是使用 list_for_each_entry_safe 逐一走訪節點，且能得到當前的以及下一個 element_t 的位址
使用 strcmp 比對兩者的 value 是否相同，相同的話則透過 list_del_init 和 q_release_element 來移除並釋放該重複節點的記憶體空間
宣告一個變數 flag 用來確認如果字串相同，則在下一個迴圈就會以相同方法移除另一個重複的節點

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

但在做輸入 gdb ./qtest 測試後發現以下錯誤

l = [b a a]
cmd> dedup

Program received signal SIGSEGV, Segmentation fault.
__strcmp_avx2 () at ../sysdeps/x86_64/multiarch/strcmp-avx2.S:775
775	../sysdeps/x86_64/multiarch/strcmp-avx2.S: No such file or directory.

access 的翻譯是「存取」，而非「訪問」(visit)

已更改

意思是在呼叫 strcmp 函式時存取了無效的記憶體位址，檢查過後發現是當透過 list_for_each_entry_safe 走訪到最後一個節點時，該節點的 next 是指向 head，但 head 的型態是 list_head，所以它沒有 value 可以存取，進而發生 sagemetation fault

所以我多加了一個判斷式，判斷當前節點的下一個節點是否指向 head

list_for_each_entry_safe (element, next, head, list) {
-   if (strcmp(element->value, next->value) == 0) {
+   if (&next->list != head && strcmp(element->value, next->value) == 0) {
        list_del_init(&element->list);
        q_release_element(element);
        flag = true;
    }

`q_swap`

宣告 cur 指標指向 head，再宣告兩個指標指向第一個節點和第二個節點
在每次迴圈時將指標兩兩交換，並在迴圈結束前將兩個指標皆往後移動兩個節點，直到其中一個指標指向 head

要注意更新鏈結指標的順序，如果更新邏輯有誤可能會導致鏈結結構錯亂，例如重複處理節點或形成循環鏈結

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

l = [a b c d]
cmd> swap
l = [b a d c]
cmd> rh
Removed b from queue
l = [a d c]
cmd> swap
l = [d a c]

改進你的漢語表達。

`q_reverse`

使用 list_for_each 走訪佇列，透過 list_del 將當前的節點移除，接著用 list_add 將其移至開頭，走訪完後即完成反轉，但是在測試報出以下錯誤訊息：

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

意思是形成了一個無窮迴圈，這個無窮迴圈導致程式運行時間超過了限制

後來想到了原因，首先 list_for_each 巨集如下：

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

可以發現這個 node 指向的節點在被移至佇列開頭後，進入下個迴圈前仍然指向開頭節點的下一個節點。因此每次迴圈都會做佇列前二節點互相交換的操作，從而導致了一個無限循環。

所以使用 list_for_each_safe 走訪並透過 safe 儲存下個節點，在每次迴圈結束時 node 會指向 safe，就能透過 node 逐一將節點移至開頭，最後實作佇列反轉的效果

- list_for_each (cur, safe, head) {
+ list_for_each_safe (cur, safe, head) {
      list_del(cur);
      list_add(cur, head);
  }

不過後來在 The Linux Kernel API 中找到其實可以只利用 list_move 來實作 list_del + list_add 的功能，所以修改函式進一步精簡程式碼

+ list_for_each_safe (cur, safe, head) {
-     list_del(cur);
-     list_add(cur, head);
+     list_move(cur, head);
  }

l = [a b c d]
cmd> reverse
l = [d c b a]

`q_reverseK`

將每一組的 k 個節點逐一移至最前面實作佇列反轉，接著迭代每一組

使用 q_size 紀錄佇列整體長度，來確保最後剩下不足 k 個節點不會做反轉排列，並透過間接指標 reverse_node 紀錄 cur->next 的位址，tmp 用來紀錄每一組的 head

「當前」一詞可能會造成閱讀的困難。例如下面的「當前組」是「當前面一組」，抑或「目前這組」呢？

你可回想國中和高中的教材中，「當前」出現次數較高，還是「目前」較高呢？若是後者較頻繁出現，為何你現在不依據中學教材的方式來書寫？

已更改

利用 q_reverse 做法為目前這組實作反轉後，此時 cur 會指向該組的最後一個節點，並將 cur->next 指派給 cur，此時 cur 就會指向下一組的第一個節點

所以下一次迭代就會從 *reverse_node 指向的節點開始逐一移至該組最前面，實作反轉

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head) || k < 2)
        return;

    int len = q_size(head);
    for (struct list_head *cur = head->next; cur != head && cur->next != head;cur = cur->next) {
        struct list_head **reverse_node = &cur->next, *tmp = cur->prev;
        for (int i = 1; i < k; i++) {
            if (len >= k)
                list_move(*reverse_node, tmp);
        }
        len -= k;
    }
}

`q_sort`

在 trace-15-perf.cmd 的文件裡有提到測試 sort 要求時間複雜度必須為

O (n \log n)

，若使用像 bubble sort 這種時間複雜度為

O (n^{2})

的排序法會造成測試失敗，所以選擇 merge sort 以符合期待。

參考你所不知道的 C 語言: linked list 和非連續記憶體 merge sort 的實作，我使用三個函式呈現

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

`q_sort`

執行 merge_sort 前要先將 head 斷開，使其變成單向鏈結串列來避免產生無窮迴圈
最後要再迭代一次排序後的鏈結串列，因為當前排序過後是單向鏈結串列，所以要將 prev 指標更新，也需將佇列的尾巴與開頭相互連結，讓其變回循環雙向鏈結串列，以維持 list_head 的型態

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

    head->prev->next = NULL;
    head->next = merge_sort(head->next);

    struct list_head *cur = head, *n = head->next;

    while (n) {
        n->prev = cur;
        cur = n;
        n = n->next;
    }

    cur->next = head;
    head->prev = cur;
}

`merge_sort`

如果鏈結串列為空或只包含一個節點，則直接返回。
先透過快慢指標的方法來尋找中間節點，再呼叫 merge_list 將第一個節點開頭的佇列及中間節點開頭的佇列，合併成一個有序的佇列。
其中 slow->next = NULL; 是必須要將第一個節點開頭的串列尾巴指向 NULL。

struct list_head *merge_sort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *fast, *slow = head;

    for (fast = head->next; fast && fast->next; fast = fast->next->next) {
        slow = slow->next;
    }

    struct list_head *left, *right;

    right = slow->next;
    slow->next = NULL;

    left = merge_sort(head);
    right = merge_sort(right);

    return merge_list(left, right);
}

`merge_list`

使用 list_entry 可以取得 left 指向的 struct list_head 結構中 element_t 的指標，然後再透過 element_t 裡 value 的值做比較，比較後將 value 較小的放到新的佇列裡，然後將 ptr 移至下一個位置，當迭代完成後，將剩下的節點加入佇列

運用 indirect pointer 的技巧避免佇列合併過程中創建額外節點的記憶體空間

struct list_head *merge_list(struct list_head *left, struct list_head *right)
{
    struct list_head *head = NULL, **ptr = &head;

    for (; left && right; ptr = &(*ptr)->next) {
        if (strcmp(list_entry(left, element_t, list)->value,
                   list_entry(right, element_t, list)->value) < 0) {
            *ptr = left;
            left = left->next;
        } else {
            *ptr = right;
            right = right->next;
        }
    }

    if (left) {
        *ptr = left;
    } else {
        *ptr = right;
    }
    return head;
}

執行結果

cmd> new
l = []
cmd> ih RAND 5
l = [rmlts bgxaxcfpq ldienge rrspzs mrvlz]
cmd> sort
l = [bgxaxcfpq ldienge mrvlz rmlts rrspzs]

`q_ascend`

題目是說如果目刪除具有較小值在右側的節點，結果為升序的佇列。

一開始的想法是利用從佇列的第一個節點開始比對右側的每個節點，但這個方法會用到雙層迴圈，不過思考後發現可以從佇列尾端比對，只需要單層迴圈即可

方法是先利用 q_reverse 將佇列反轉，以 min 儲存最小值，並用 list_for_each_entry_safe 逐一比對當前節點與 min 的大小，如果比 min 大就刪掉，否則將其指派給 min

最後的結果會是降序的佇列，所以要再用 q_reverse 將其反轉回來

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

    element_t *cur, *safe;
    q_reverse(head);
    char *min = list_entry(head->next, element_t, list)->value;

    list_for_each_entry_safe (cur, safe, head, list) {
        if (strcmp(cur->value, min) > 0) {
            list_del_init(&cur->list);
            q_release_element(cur);
        } else {
            min = cur->value;
        }
    }
    q_reverse(head);
    return q_size(head);
}

l = [6 1 5 3 2 4]
cmd> ascend
l = [1 2 4]

不過在與 ollieni 討論時發現 The Linux Kernel API 裡面的 list_for_each_entry_safe_reverse 可以實作從佇列尾端走訪，但 list.h 裡並沒有看到相關實作，不過可以將 list_for_each_entry_safe 巨集裡面的所有 ->next 改成 ->prev 實作相同功能，以省去我原本還要將佇列做兩次反轉的方法

`q_descend`

與 q_ascend 做法類似，只差在刪除的是具有較大值在右側的節點

l = [f d b a c]
cmd> descend
l = [f d c]

`q_merge`

從 queue.h 可以了解 queue_contex_t 的架構描述

q 用來指向 queue 的 head
chain 用來將每一個 queue_contex_t 結構串連起來
size 表示這個 queue 的長度
id 表示每一個 queue 唯一的編號

接著從 qtest.c 發現有宣告 queue_chain_t 的結構，並從do_new 函式可以發現，他是用來當 queue_contex_t 結構的 head，並且每次配置一個新的 queue_contex_t 結構的記憶體空間，都會將此結構插入到佇列的尾端

同時在 qtest.c 的 do_merge 函式可以發現它傳入的參數是 queue_chain_t 結構的 head，因為 qtest.c 裡面有宣告 q_chain_t 的結構，所以邊界條件不用判斷 !head，所以設置 list_empty(head) 與 list_is_singular(head) 為邊界條件即可

想法就是逐一將所有佇列合併到第一個佇列，與 q_sort 差不多，執行 merge_list 前要先將 head 斷開，使其變成單向鏈結串列來避免產生無窮迴圈，最後要再迭代一次排序後的佇列，讓他變回循環雙向鏈結串列

其中要加上 INIT_LIST_HEAD(pos->q) 將原本的串列做初始化

l = [a e m]
l = [b o r]
l = [c d r]
cmd> merge
l = [a b c d e m o r r]

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

參考 Fisher–Yates shuffle 演算法，對佇列中所有節點進行 shuffle，做法是從 1 到 n 之間隨機出一個數字和最後一個數 n 交換，然後從 1 到 n-1 之間隨機出一個數和倒數第二個數 n-1 交換..

假設有一長度為

n

的陣列，其洗牌演算法的條件：

會有
$n!$ 種不同的排列組合
必須可以產生出每一種結果
所有結果出現的機率相等

此為提供的 pseudocode

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

在 queue.c 按照上述程式碼實作 q_shuffle

迴圈從佇列最後一個元素開始，每次迭代皆會隨機挑一個數並以 cur 指標紀錄節點位置，接著將其數值與 end 的數值做交換
end 會透過 end = end->prev 紀錄每次迭代最後一個節點的位置。

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *end = head->prev;

    for (int i = q_size(head); i > 0; i--) {
        int ran = rand() % i;
        struct list_head *cur = head;
        for (int j = 0; j <= ran; j++) {
            cur = cur->next;
        }
        swap(list_entry(cur, element_t, list),
             list_entry(end, element_t, list));
        end = end->prev;
    }
}

交換節點數值的方法透過以下 swap 函式來執行

void swap(element_t *n1, element_t *n2)
{
    char *tmp = n1->value;
    n1->value = n2->value;
    n2->value = tmp;
}

接著在 qtest.c 裡的 console_init 中加上以下新命令，並寫一個 do_shuffle 呼叫我們實作的 q_shuffle

ADD_COMMAND(shuffle, "Shuffle the nodes of the queue", "");

不過在我編譯時出現以下錯誤：

qtest.c: In function ‘do_shuffle’:
qtest.c:1027:9: error: implicit declaration of function ‘q_shuffle’; did you mean ‘do_shuffle’? [-Werror=implicit-function-declaration]

意思是編譯器在 do_shuffle 中找不到 q_shuffle 函式的聲明，並將其視為一個隱式函式聲明，所以導致編譯錯誤

file 的翻譯是「檔案」，而非「文件」(document)

已更改

後來我在 qtest.c 檔案中添加 void q_shuffle(struct list_head *head);，這樣編譯器就可以找到這個函式的聲明，並正確地編譯 do_shuffle

cmd> new
l = []
cmd> ih RAND 8
l = [fvthxutit raywmvk pkylr qijibeiyd vjxyloj vggmsyzyb hnwspnomd cmisexmr]
cmd> shuffle
l = [pkylr vjxyloj vggmsyzyb raywmvk hnwspnomd fvthxutit qijibeiyd cmisexmr]
cmd> shuffle
l = [qijibeiyd cmisexmr hnwspnomd fvthxutit vggmsyzyb raywmvk pkylr vjxyloj]

以統計的原理來分析你的實作

根據作業說明：統計方法驗證 shuffle
將測試程式新增到 scripts/shuffle.py

1. 先計算 chi-squared test statistic

X^{2} = \sum_{i = 1}^{n} \frac{(O_{i} - E_{i})^{2}}{E_{i}}

執行 $ python3 scripts/shuffle.py
在測試 shuffle 1000000 次後，24種結果各自的頻率如下表：

排列組合	觀察到的頻率	期待的頻率	$\frac{(O_{i} - E_{i})^{2}}{E_{i}}$
[1, 2, 3, 4]	41,432	41,666	1.31416502664
[1, 2, 4, 3]	41,588	41,666	0.14601833629
[1, 3, 2, 4]	41,972	41,666	2.24729995680
[1, 3, 4, 2]	41,910	41,666	1.42888686219
[1, 4, 2, 3]	41,562	41,666	0.25958815341
[1, 4, 3, 2]	41,637	41,666	0.02018432294
[2, 1, 3, 4]	41,607	41,666	0.08354533672
[2, 1, 4, 3]	41,544	41,666	0.35722171554
[2, 3, 1, 4]	41,860	41,666	0.90327845245
[2, 3, 4, 1]	41,403	41,666	1.66008256132
[2, 4, 1, 3]	41,900	41,666	1.31416502664
[2, 4, 3, 1]	41,338	41,666	2.58205731292
[3, 1, 2, 4]	41,522	41,666	0.49767196275
[3, 1, 4, 2]	41,759	41,666	0.20757932126
[3, 2, 1, 4]	41,841	41,666	0.73501176018
[3, 2, 4, 1]	41,568	41,666	0.23049968799
[3, 4, 1, 2]	41,556	41,666	0.29040464647
[3, 4, 2, 1]	42,060	41,666	3.72572361158
[4, 1, 2, 3]	41,691	41,666	0.01500024000
[4, 1, 3, 2]	41,730	41,666	0.09830557288
[4, 2, 1, 3]	41,708	41,666	0.04233667738
[4, 2, 3, 1]	41,640	41,666	0.01622425958
[4, 3, 1, 2]	41,502	41,666	0.64551432822
[4, 3, 2, 1]	41,670	41,666	0.00038400614
Total			18.1624633994

X^{2}

= 18.1624633994

2. 決定自由度（degrees of freedom）

對於 N 個隨機樣本而言，自由度為 N - 1
而本次實驗有 24 個結果，故自由度為 23

3. 選擇顯著水準

從 Chi-Square Distribution Table 找合適的 P value，我們的自由度為23

可看到 17.187 < 18.1624633994 < 19.021，所以其 P value 介於 0.7 和 0.8 之間

而

α

設為常見的 0.05

4. 統計檢定的結果不拒絕虛無假說

對於要拒絕的虛無假說（

H_{0}

），觀察到的結果必須具有統計顯著性，即觀察到的 P value 要小於預先指定的顯著水準

α

因為 P value（0.7~0.8）>

α

（0.05），統計檢定的結果不拒絕虛無假說（

H_{0}

）

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

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

閱讀 Linux 核心的鏈結串列排序 , list_sort.c 以及 linked list 和非連續記憶體操作

`list_sort`

一開始會將鏈結串列透過 head->prev->next = NULL; 將頭尾分開

另外在註解中有提到：

* - All lists are singly linked and null-terminated; prev
	 *   pointers are not maintained.

意思是說雖然輸入的是循環雙向鏈結串列，但在此函式裡會將其視為單向的

相關變數宣告為以下：

struct list_head *list = head->next, *pending = NULL;
size_t count = 0;

將 head 的第一個節點指派給 list，然後將 pending 指向 NULL

之後會進入 do while 迴圈，他會一步步把 list 裡面的節點移到 pending 中，並將 count +1，直到 list 為空，而 list 和 pending 分別為：

list：原始未排序的鏈結串列，且隨著 while 迴圈一步步減少節點數
pending：為 list of lists，可理解為「串起來的串列」，lists 代表已合併且排序好的串列，list 則是將這些 lists 串起來的串列

一開始會看到以下 for 迴圈，他的用途是讓 tail 往前移動到要 merge 的位置，而移動的條件是根據 count 的二進制值最小位有多少連續的 1 來移動 tail 多少步

for (bits = count; bits & 1; bits >>= 1)
	tail = &(*tail)->prev;

在 for 迴圈執行期間， bits 會慢慢向右移一個位元，所以當迴圈跑完後最小位全部連續的 1 會不見，下表為範例：

count	count 二進位	tail 往前移動步數	bits 二進位值在迴圈跑完後
0	0000	0	0000
1	0001	1	0000
2	0010	0	0010
3	0011	2	0000
4	0100	0	0100
5	0101	1	0010
6	0110	0	0110
7	0111	3	0000

再來會根據 if(bits) 判斷是否該在 pending 上進行合併 ( merge )，並依 tail 移動的步數來判斷要合併哪兩個串列，最後從 list 新增一個節點，以下表例：

count	tail 往前移動步數	bits	pending 狀態
0	0	0000	從 list 新增一節點
1	1	0000	從 list 新增一節點
2	0	0010	合併第 0 跟第 1 個串列，並從 list 新增一節點
3	2	0000	從 list 新增一節點
4	0	0100	合併第 0 跟第 1 個串列，並從 list 新增一節點
5	1	0010	合併第 1 跟第 2 個串列，並從 list 新增一節點
6	0	0110	合併第 0 跟第 1 個串列，並從 list 新增一節點
7	3	0000	從 list 新增一節點

以下圖例是 do while 根據 count 值，list 和 pending 的狀態：
一開始：

count = 0

count = 1

count = 2 ( 紅色為執行 merge )

count = 3 ( 藍色為已排序的串列 )

count = 4

count = 5

count = 6

count = 7

`merge` & `merge_final`

兩者的共通點都是將兩個已排序好的串列做合併。
但差別就是 merge_final 會重建 prev 指標的鏈接，將結果轉換為一個循環雙向鏈結串列，在 list 為空時執行。

在 list_sort.c 裡面有用到 __attribute__((nonnull)) 這個函式屬性

此屬性用於告訴 compiler 該函式的某些參數不能為 NULL。
在 list_sort.c 的例子中，__attribute__((nonnull(2,3,4))) 表示 compiler 可以對第 2、3、4 個參數為 NULL 時發出警告。

以及 likely unlikely 這兩個巨集，他們被定義在 /include/linux/compiler.h 中

# define likely(x)	__builtin_expect(!!(x), 1)           
# define unlikely(x)	__builtin_expect(!!(x), 0)

__built_expect()是 gcc 的內建函式，用來將 branch 的相關資訊提供給 compiler，告訴 compiler 設計者期望的比較結果，以便對程式碼改變分支順序來進行優化
而這兩個巨集，可以讓 compiler 在編譯 assembly code 的時候做一些最佳化，可以告訴 compiler 某段 if 敘述為 true 的機率較高或低，讓 compiler 把對應程式碼接在判斷的後面
如果程式碼被放到比較相近的位置，那他們就可能一起被搬到 cache 中，使 cache hit 機率上升，就有可能提升程式的執行效能。

翻閱計算機組織/結構的教科書，從 branch prediction 的角度去確認上述說法。

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

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 →

品質是價值與尊嚴的起點

創建並複製 list_sort.c 程式碼到 lab0-c

另外 list_sort.c 裡面有使用到下列兩個巨集，所以也需要加入到程式碼開頭

#define likely(x) __builtin_expect(!!(x), 1)           
#define unlikely(x)	__builtin_expect(!!(x), 0)

接著將宣告 list_cmp_func_t 的定義加入到程式碼開頭

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
        const struct list_head *, const struct list_head *);

為一個 Function Pointer ，並且第二以及第三個參數不能為 NULL

根據 list_sort.c 裡的註解實作 cmp_function

The comparison function @cmp must return > 0 if @a should sort after
@b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
sort before @b or their original order should be preserved.

if (a > b) return > 0
if (a < b) return <= 0 或保留其原本排序
list_sort 是 stable sort，所以沒必要區分 a < b 和 a == b 的情況

int cmp_function(void *priv, const struct list_head *a, const struct list_head *b)
{
    element_t *a_entry = list_entry(a, element_t, list);
    element_t *b_entry = list_entry(b, element_t, list);

    if (strcmp(a_entry->value, b_entry->value) <= 0)
        return 0;
    else
        return 1;
}

參照 qtest.c 裡的 do_sort 函式實作 do_linux_sort。
與實作 q_shuffle 一樣的做法，因為要執行 list_sort(NULL, current->q, cmp_function);，所以要添加下列函式聲明才可以正確編譯 do_linux_sort。

void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);

最後從 qtest.c 裡的 console_init 加入新命令

ADD_COMMAND(linux_sort, "Linux Sort queue in ascending/descening order", "");

不過在編譯時出現以下錯誤訊息：

error: unknown type name ‘u8’

在 list_sort.c 的第 56 行有宣告一個型態為 u8 的變數，意思是 unsigned 8-bit integer，被定義在 /tools/include/linux/types.h 裡，我的做法是直接自己定義

typedef unsigned char u8;

在 Makefile 中，OBJS 變數通常用來存放需要編譯的目標檔案。當新增一個 list_sort.c 檔案後，需要將 list_sort.o 加入到 OBJS 變數中。

- OBJS := qtest.o report.o console.o harness.o queue.o\
+ OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o\

這樣在執行 make 命令時，list_sort.c才會被編譯成list_sort.o目標檔案。

cmd> new
l = []
cmd> ih RAND 10
l = [lrwuv zvwqvcdc bqlunk uptmb mgrqphizi fwifqt abwfjcil vtysowf gusbrqrzv lizyyagzl]
cmd> linux_sort
l = [abwfjcil bqlunk fwifqt gusbrqrzv lizyyagzl lrwuv mgrqphizi uptmb vtysowf zvwqvcdc]

比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差

閱讀並學習如何使用 Perf

在 perf stat 提供的範例中提到將 array[i][j]++ 的 i，j 對調改成 array[i][j]++ 會同時降低許多 cache reference 和 cache miss 次數，主要是因為：

多維陣列通常是以 Row-major 的方式儲存在記憶體中
在改進程式後的資料讀取方式從原本 column-major 變成 row-major，好處是因為他利用了空間局部性 (Spatial locality) 的優點

空間局部性：當一個記憶體區塊被載入快取時，相鄰的區塊也很可能會被載入。
當程式能夠利用空間局部性的優點時，除了能減少 cache-reference 次數外，命中率也會上升，而不須從 main memory 中重新載入
無論是 cache reference 還是 cache miss，都是需要花費時間的，只差在時間長短，因此將兩者次數降低相對也代表著執行時間更短

學習如何寫 shell scripts，優點是可以一次執行多個命令

首先新增 test_linux_sort.sh 和 test_sort.sh 兩個 shell scripts 用來執行效能測試

#!/bin/bash
for i in ./traces/traces_perf_linux_sort/*.cmd
do
    perf stat --repeat 5 -o "${i%.cmd}"_report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i"
done

檢測的項目有 cache-misses, branches, instructions 和 context-switches

接著在 ./lab0-c/traces 新增以下兩個目錄，分別存放用來測試 linux_sort 與 sort 的命令檔

.
├── traces_perf_linux_sort
│   ├── RAND_1000.cmd
│   ├── RAND_10000.cmd
│   ├── RAND_100000.cmd
│   └── RAND_1000000.cmd
└── traces_perf_sort
    ├── RAND_1000.cmd
    ├── RAND_10000.cmd
    ├── RAND_100000.cmd
    └── RAND_1000000.cmd

RAND_1000.cmd 內容：

option fail 0
option malloc 0
new
ih RAND 1000
linux_sort
free

輸入 chmod u+x *.sh 為 .sh 檔設定執行權限，否則會遇到 Permission denied

最後輸入 ./test_linux_sort.sh 就會在 traces_perf_linux_sort 目錄下為每個 cmd 檔新增一個 report，點開後即可看到以下效能分析內容

# started on Wed Mar 27 21:22:44 2024


 Performance counter stats for './qtest -v 0 -f ./traces/traces_perf_linux_sort/RAND_1000.cmd' (5 runs):

              8422      cache-misses                                                            ( +- 23.38% )
           84,9436      branches                                                                ( +-  0.09% )
          582,1613      instructions                                                            ( +-  0.07% )
                 0      context-switches                                                      

         0.0010624 +- 0.0000258 seconds time elapsed  ( +-  2.43% )

實驗結果

sort

# node	cache-misses	branches	instructions	context-switches	time
1000	1,2426	85,7773	578,5872	0	0.0011827
10000	7,2960	636,5969	4503,6733	0	0.007541
100000	436,9531	6447,4547	4,5055,1876	10	0.1036
1000000	9829,0049	6,7463,1160	46,2739,7185	8	1.2517

list_sort

# node	cache-misses	branches	instructions	context-switches	time
1000	8422	84,9436	582,1613	0	0.0010624
10000	3,2865	629,6853	4570,8874	0	0.0063344
100000	226,5870	6387,2396	4,5985,1778	1	0.078921
1000000	7861,2101	6,6845,0006	47,4151,1080	7	1.1422

在 Linux 核心的 list_sort 實作提到，除了 list_sort 是以 bottom up 來實作之外，他相較於一般的 merge_sort 擁有更有效利用 cache 的合併方式，合併時機是當有

3 \times 2^{k}

個節點時會合併前兩個

2^{k}

，使其維持著合併：不合併為 2：1 的比例，這樣更能實現空間局部性。

所以從空間局部性來看，list_sort 可以使 cache 中現存的資料更容易被用到，所以 cache miss 在節點數量越多時的差距會越來越大，進而影響執行時間。而 merge sort 通常需要額外的記憶體空間來儲存很多個子串列，然後一次合併，這時通常會發生很多 cache-misses，在空間局部性的表現上較差，甚至導致 cache trashing。

branch 次數的部份，list_sort 是使用迭代的算法，它通常較少涉及到函式的重複呼叫，只透過循環來完成任務，這相較於一般 merge_sort 遞迴的算法 branch 次數會更少，因為遞迴的本質是將大問題分解成小問題，但這會重複呼叫同個函式比較多次

2024q1 Homework1 (lab0)

Reviewed by SuNsHiNe-75

Reviewed by stevendd543

開發環境

指定的佇列實作

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_sort

merge_sort

merge_list

q_ascend

q_descend

q_merge

在 qtest 提供新的命令 shuffle

以統計的原理來分析你的實作

1. 先計算 chi-squared test statistic

2. 決定自由度（degrees of freedom）

3. 選擇顯著水準

4. 統計檢定的結果不拒絕虛無假說

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

list_sort

merge & merge_final

嘗試引入到 lab0-c 專案

比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差

將 jserv/ttt 專案的程式碼部分整合進 lab0-c

Read more

Linux 核心專題: Netfilter

2024q1 Homework6 (integration)

2024q1 Homework5 (assessment)

2024q1 Homework2 (quiz1+2)

Reviewed by `SuNsHiNe-75`

Reviewed by `stevendd543`

`q_new`

`q_free`

`q_insert_head`

`q_insert_tail`

`q_remove_head`

`q_remove_tail`

`q_size`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseK`

`q_sort`

`q_sort`

`merge_sort`

`merge_list`

`q_ascend`

`q_descend`

`q_merge`

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

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

`list_sort`

`merge` & `merge_final`

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