2023q1 Homework1 (lab0)

contributed by < alanjian85 >

開發環境

$ gcc --version
gcc (GCC) 12.2.1 20230111
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            12
    CPU(s) scaling MHz:  36%
    CPU max MHz:         4200.0000
    CPU min MHz:         400.0000
    BogoMIPS:            4201.88

開發過程

目前透過自動評分系統得到的分數是 100/100。

`q_new()`

根據 malloc(3):

The malloc() function returns a pointer to the allocated memory, which is suitably aligned for any built-in type. On error, this function returns NULL.

如果 malloc() 在配置記憶體時失敗，得到的指標值會是 NULL 而非一個合法的記憶體位置。而 NULL 正好符合 queue.h 中規範 q_new() 在無法正確配置記憶體時回傳的值。因此，這邊在記憶體配置成功時會進行額外的初始化，而在配置失敗時，q_new() 也能使用同樣的流程處理結果，確保 malloc() 的結果會直接傳回至呼叫端。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (head)
        INIT_LIST_HEAD(head);
    return head;
}

`q_free()`

走訪佇列中的每個元素時使用 list_for_each_entry_safe 巨集，後者藉由一個額外的指標 safe 儲存下一次循環的 entry 值，即 entry->next，這種方法讓程式可以在每次循環執行時刪除元素而不會影響迴圈的執行。而迴圈內不需要用 list_del 移除串列節點的連結，因為被釋放的串列在後續不會再被使用。當釋放完每個元素以及相應的字串後，最後的程式會釋放佇列內部鏈結串列的起始節點（這並非第一個元素，而是一個僅標示第一個元素和最後一個元素位置的節點）。如果 l 在這個函式執行的一開始就是空的，釋放元素的迴圈就不會執行，而是直接開始釋放起始節點，因此這種狀況不需要額外處理也能得到正確的結果。

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

`q_insert_head()` / `q_insert_tail()`

首先定義一個在隨機位置插入元素的函式，如果 node 是一個空的佇列，新的元素就會成為佇列中的第一筆資料，而 list.h 所提供的介面會自動處理這種狀況。接著，此函式為新的元素配置一個 element_t 資料結構，element_t 含有一個稱作 list 的成員作為連結到內部串列的節點，這會在倒數第三行中被加入到佇列內部的串列中。最後，程式使用 strdup(3) 複製呼叫端提供的字串，如果記憶體配置失敗，要注意釋放前面為新元素本身所配置的記憶體，否則會造成記憶體洩漏。

static inline bool q_insert(struct list_head *node, char *s)
{
    if (!node)
        return false;
    element_t *element = malloc(sizeof(element_t));
    if (!element)
        return false;
    element->value = strdup(s);
    if (!element->value) {
        free(element);
        return false;
    }
    list_add(&element->list, node);
    return true;
}

q_insert_head() 和 q_insert_tail() 使用這個函式，傳入不同的起始節點。要注意的是，q_insert_tail() 需要存取 head->prev，所以必須事先檢查 head 是否是有效的佇列，而 q_insert_head() 則讓上面的函式代為檢查。

bool q_insert_head(struct list_head *head, char *s)
{
    return q_insert(head, s);
}

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    return q_insert(head->prev, s);
}

為何不重用 q_insert_head 的程式碼？
q_insert 沒必要存在。
jserv

@@ -43,22 +43,15 @@ static inline bool q_insert(struct list_head *node, char *s)
         free(element);
         return false;
     }
-    list_add(&element->list, node);
+    list_add(&element->list, head);
     return true;
 }
 
-/* Insert an element at head of queue */
-bool q_insert_head(struct list_head *head, char *s)
-{
-    return q_insert(head, s);
-}
-
-/* Insert an element at tail of queue */
 bool q_insert_tail(struct list_head *head, char *s)
 {
     if (!head)
         return false;
-    return q_insert(head->prev, s);
+    return q_insert_head(head->prev, s);
 }
 
 /* Remove an element from head of queue */

commit 6091f73

`q_remove_head()` / `q_remove_tail()`

這邊原本使用 strncpy(3)。然而，如果 strncpy() 在複製字串時遇到還在複製長度限制內但來源的字串已經完整複製完的狀況，剩下的部份會全部被以 0 填充。所以，為了節省複製多餘字元的開銷，這邊使用 for 迴圈複製字串，並在最後加上一個標示結尾的字元，其餘的部份就不做修改。

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

這邊其實也可以使 q_remove_tail() 利用 q_remove_head() 中重複的程式碼，以佇列結尾的前一個節點（head->prev->prev）作為刪除的佇列的起始節點。

@@ -72,16 +72,9 @@ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
 /* Remove an element from tail of queue */
 element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
 {
-    if (!head || list_empty(head))
+    if (!head)
         return NULL;
-    element_t *element = list_last_entry(head, element_t, list);
-    list_del(&element->list);
-    if (sp) {
-        for (char *i = element->value; bufsize > 1 && *i; sp++, i++, bufsize--)
-            *sp = *i;
-        *sp = '\0';
-    }
-    return element;
+    return q_remove_head(head->prev->prev, sp, bufsize);
 }

`q_size()`

因為鏈結串列元素的記憶體位置不一定連續，且 list.h 沒有提供計算串列大小或長度的方法，所以這邊使用一個迭代迴圈走訪每個元素，並持續遞增紀錄的大小（介面規範沒有要求 q_size() 的執行時間是常數）。如果 head 是空的佇列，那迴圈就不會執行，而是直接回傳 0 為佇列的大小。

int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    int size = 0;
    struct list_head *node;
    list_for_each (node, head)
        size++;
    return size;
}

`q_delete_mid()`

我原本使用 Floyd's Tortoise and Hare 演算法實作，此演算法運用兩個指標：fast 和 slow，fast 每次迭代前進兩步，slow 每次前進一步。當 fast 到達序列的結尾時，slow 會指向序列中間的元素（如果序列沒有位在正中間的元素，slow 指向的元素從零開始計算的索引會是

⌈ \frac{n - 1}{2} ⌉

，

n

為序列長度）。

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

後來參考 KHLee529 的筆記，發現可以從佇列的兩端用不同的指標開始走訪，當兩個指標指向同一個元素即停止執行。

由 Leetcode 上的題目描述得知當一個序列只有兩個元素時，要移除的會是第二個元素，因此這邊使用變數 backward 作為移除元素使用的節點，並在迴圈條件中加入檢測 forward 和 backward 相鄰的狀況。

@@ -2,11 +2,14 @@ bool q_delete_mid(struct list_head *head
 {
     if (!head || list_empty(head))
         return false;
-    struct list_head *slow, *fast;
-    slow = fast = head->next;
-    for (; fast != head && (fast = fast->next) != head; fast = fast->next)
-        slow = slow->next;
-    element_t *element = list_entry(slow, element_t, list);
+    struct list_head *forward, *backward;
+    forward = head->next;
+    backward = head->prev;
+    while (forward != backward && forward != backward->prev) {
+        forward = forward->next;
+        backward = backward->prev;
+    }
+    element_t *element = list_entry(backward, element_t, list);
     list_del(&element->list);
     q_release_element(element);
     return true;

只要列出程式碼差異，不用張貼完整程式碼。可用 for 敘述改寫，縮減程式碼。
jserv

為了比較兩者在效能上的差異，我在 qtest 執行以下命令：

new
it RAND 1000000
time dm

在我的電腦上使用 Floyd's Tortoise and Hare 和分別從頭和尾走訪得到的結果主要都分佈在 0.135 ~ 0.137 秒。因此我猜測兩者在效能沒有太大差別，且都是以走訪連續或相近的元素為主，在 Cache 的使用上有類似的結果。但是後者具有較直觀的優點。

這與每個節點佔用的記憶體空間有關，設計實驗時，應避免只做單一存取樣式 (memory pattern) 就下定論的狀況。
jserv

`q_delete_dup()`

以 { 1, 1, 1, 2, 3, 3 } 這個序列舉例，以下圖示用綠色標示迴圈的當前元素和紅色標示已經被刪除（delete，釋放並從串列中移除元素）的元素。為簡化圖示製作過程，這邊僅使用單向鏈結串列表示。

最後此序列只剩下 2 這一個元素。注意，當迴圈結束後，還需要處理最後一個元素和前面的元素連續的狀況，因此需要一個額外的檢查負責刪除最後一個元素。

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    bool dup = false;
    element_t *prev = NULL, *curr;
    list_for_each_entry (curr, head, list) {
        bool equal = prev && !strcmp(prev->value, curr->value);
        if (equal || dup) {
            list_del(&prev->list);
            q_release_element(prev);
            dup = equal;
        }
        prev = curr;
    }
    if (dup) {
        list_del(&prev->list);
        q_release_element(prev);
    }
    return true;
}

`q_swap()`

這個函式交換佇列中所有成對的元素，如果某元素不和其他元素成對，則停止迴圈。每次迭代中的 list_move() 的使用將當前元素的下一個元素當作一個串列的頭的前一個節點，所以移動當前元素會導致當前元素被移動至下一個元素的後方。注意，這裡不用使用 list_for_each_safe，因為被移動後的當前元素的下一個節點將會是下一次迭代中要處理的元素。

void q_swap(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node;
    list_for_each (node, head) {
        if (node->next == head)
            break;
        list_move(node, node->next);
    }
}

`q_reverse()`

我原本在迴圈中對元素間的連結進行手動操作，但經由老師提醒後發現可以使用 list.h 中的 list_move() 將當前元素移動到佇列的最前端，使佇列形成和原本相反的排列。因為元素被移動到第一項之後和原本位置的下一項元素之間的相對位置會改變，所以這邊必須使用 list_for_each_safe 儲存下一次迭代存取的元素位置。

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

`q_reverseK()`

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;
    struct list_head *node = head->next;
    for (;;) {
        struct list_head *safe = node, *start = node->prev;
        for (int i = 0; i < k; i++, node = node->next) {
            if (node == head)
                return;
        }
        node = safe;
        safe = node->next;
        for (int i = 0; i < k; i++, node = safe, safe = safe->next)
            list_move(node, start);
    }
}

`q_merge_two()`

《Introduction to Algorithms》討論 merge 這個操作，提及這樣的譬喻：假設有兩堆已排序的撲克牌，各堆中數值最小的撲克牌都被放在最上面，要得到一個單一已排序過並且最小的牌在最下方的牌堆的方法就是：持續將兩堆中數值較小的放到第三堆牌的上方直到其中一個牌堆沒有剩下的牌，最後如果有牌堆還剩下牌，就將所有牌直接顛倒後疊到輸出的牌堆上面（因為剩下的牌已經排序過，且都大於輸出牌堆頂端的牌）。這邊的實作在細節上有些不同，兩個佇列合併後的結果會被直接放在第一個佇列中。

這個函式建立一個首先暫存用的串列，接著執行上面說明的演算法，最後將暫存的串列移回 first，即完成將 second 併入 first 的操作。這個實作同時計算合併後的串列大小，提供 q_merge() 等操作使用。下面是一開始的實作，後來為了通過測試程式，將計算大小的部份移除，更詳細的內容在 dudect 小節後方的討論內。

int q_merge_two(struct list_head *first, struct list_head *second)
{
    if (!first || !second)
        return 0;
    int size = 0;
    struct list_head temp_head;
    INIT_LIST_HEAD(&temp_head);
    while (!list_empty(first) && !list_empty(second)) {
        element_t *first_front = list_first_entry(first, element_t, list);
        element_t *second_front = list_first_entry(second, element_t, list);
        char *first_str = first_front->value, *second_str = second_front->value;
        element_t *minimum =
            strcmp(first_str, second_str) < 0 ? first_front : second_front;
        list_move_tail(&minimum->list, &temp_head);
        size++;
    }
    size += q_size(first);
    list_splice_tail_init(first, &temp_head);
    size += q_size(second);
    list_splice_tail_init(second, &temp_head);
    list_splice(&temp_head, first);
    return size;
}

`q_sort()`

這邊採用經典的遞迴 Merge Sort 實作，透過分治法將佇列以 q_delete_mid() 中使用過的快慢指標技巧重複切割。直到出現只有單一元素的子串列（只有一個元素的串列必定排序過），再把所有子串列以有排序的方式合併。未來還可引入 Linux 的排序實作改進。

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *slow = head, *fast = head->next;
    for (; fast != head && fast->next != head; fast = fast->next->next)
        slow = slow->next;
    struct list_head left;
    list_cut_position(&left, head, slow);
    q_sort(&left);
    q_sort(head);
    q_merge_two(head, &left);
}

`q_descend()`

這個演算法走訪所有的元素，並持續向前查找是否有小於當前元素的元素，並將其移除並釋放。這邊有一個 Loop Invariant：在每次迭代的當前元素之前的所有元素必定會依降序方式排列，所以在迴圈中可以確保遇到比當前元素大的元素時，在那個元素前面的所有元素都會比當前元素大，因此會和當前元素組成一個降序子序列，不用繼續往前尋找不符合條件的元素。

A full declarator is a declarator that is not part of another declarator. The end of a full declarator is a sequence point.

根據 C99 規格書，在 declarator list 中的變數初始化是有規範順序的，因此 safe 在初始化的時候能使用 prev 的值。

int q_descend(struct list_head *head)
{
    element_t *entry = NULL;
    int size = 0;
    list_for_each_entry (entry, head, list) {
        struct list_head *prev = entry->list.prev, *safe = prev->prev;
        for (; prev != head; prev = safe, safe = safe->prev) {
            element_t *prev_entry = list_entry(prev, element_t, list);
            if (strcmp(prev_entry->value, entry->value) >= 0)
                break;
            size--;
            list_del(prev);
            q_release_element(prev_entry);
        }
        size++;
    }
    return size;
}

`q_merge()`

q_merge() 的實作歷經了三個階段的變更：在每個佇列中尋找最小值並插入到新的串列，最後用新串列取代原本的串列（對應的 commit 1aad68e）；使用 Queue-Mergesort^[1] 合併每個佇列直到只剩下一個佇列（commit 95570cd）；和最後的依序合併每個佇列，並把合併後的佇列設為 NULL 後放到串列結尾，作為操作結束的標記（commit 13fc941）。而現在的方式是三個之中最簡短的。

此實作使用一個額外的函式 q_merge_two()，這個函式也會在現在的 Merge Sort 實作中被使用，它將兩個已用升序排列排序的串列合併，最後輸出一個一樣已排序的串列，並回傳合併後的大小。這裡使用了最後一次迭代中得到的大小作為此函式的回傳值（即最後兩個串列合併的大小，也就是所有元素的數量）。在每次迴圈迭代中此程式還會將被合併後，而變為空佇列的第二個佇列設為 NULL ，當 while 迴圈遇到 NULL 佇列時，就能得知已經處理完所有呼叫端輸入的佇列，並可結束此演算法。

int q_merge(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return q_size(list_first_entry(head, queue_contex_t, chain)->q);
    int queue_size = 0;
    queue_contex_t *first, *second;
    first = list_first_entry(head, queue_contex_t, chain),
    second = list_entry(first->chain.next, queue_contex_t, chain);
    while (second->q) {
        queue_size = q_merge_two(first->q, second->q);
        second->q = NULL;
        list_move_tail(&second->chain, head);
        second = list_entry(first->chain.next, queue_contex_t, chain);
    }
    return queue_size;
}

實作 shuffle 命令

這個函式是底層佇列操作的抽象化封裝，仿照 do_reverseK() 和 do_merge() 實作。首先檢查有沒有輸入多餘的參數，並確保呼叫者提供的佇列（在 qtest 中使用 new 命令）。接著呼叫 error_check() 並捨棄其回傳值以忽略之前殘存的錯誤。下一步，禁止接下來的程式配置記憶體，以確保佇列操作的實作無誤且符合限制，並初始化例外子系統，使用 setjmp() 提供接下來可能產生例外的部份使用。最後顯示出重新排列後的佇列的元素順序，並回傳是否有錯誤發生。

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

    if (!current || !current->q) {
        report(3, "Warning: Calling shuffle on null queue");
        return false;
    }
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();

    set_noallocate_mode(false);
    q_show(3);
    return !error_check();
}

並在 qtest.c 中的 console_init() 加入以下以註冊該命令。

ADD_COMMAND(shuffle, "Reorder all nodes in a random manner", "");

這邊使用 Fisher-Yates shuffle 的其中一個變種，由 Richard Durstenfeld 在 1964 年發明，被 Knuth 稱作 Algorithm P。此演算法改良原本的洗牌法，省去了紀錄交換過的元素的步驟，將複雜度降低，且不用額外配置記憶體。程式後面的交換方法是：先儲存 node 未來插入的串列的頭，接著將選中的元素放到 node 後面，並把 node 移動到事先存好的子串列中，最後將 node 改為替代它的節點，讓後續的迭代能繼續往前一個元素存取。這邊還有另一種實作方法，可以直接交換每個節點對應的字串，而不用改變節點間的順序。

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    int i = q_size(head) - 1;
    struct list_head *node;
    for (node = head->prev; node != head; node = node->prev, i--) {
        struct list_head *other = head->next;
        for (int j = rand() % (i + 1); j > 0; j--)
            other = other->next;
        if (node == other)
            continue;
        struct list_head *temp = other->prev;
        list_move(other, node);
        list_move(node, temp);
        node = other;
    }
}

在這張圖中，賦予 { 1, 2, 3, 4 } 這個序列的

4! = 24

種排列 1 ~ 24 的編號，統計在

10^{6}

次 shuffle 後每種排序出現的次數。可看到資料大致呈現均勻分佈，測試後得到的 Chi-Square Sum 為

X^{2} = 19.4759

（取到小數點後四位）。

若以統計的方法分析這個結果，此母體的自由度是所有排列總和

24 - 1 = 23

，再選擇顯著水準為

α = 0.05

，根據網路上的 Chi-Square 分佈表，可看到

X^{2}

介於 0.25 和 0.5 之間。因為 P value（0.25 ~ 0.5）>

α

（0.05），統計檢定的結果不拒絕虛無假說，所以無法推翻這個 shuffle 實作在此樣本資料中是均勻分佈的假設。

Valgrind 與 Address Sanitizer 記憶體檢查

第一次執行 make valgrind，得到類似以下結果：

==13908== 160 bytes in 5 blocks are possibly lost in loss record 2 of 3
==13908==    at 0x4841888: malloc (vg_replace_malloc.c:381)
==13908==    by 0x10C754: do_new (qtest.c:145)
==13908==    by 0x10D916: interpret_cmda (console.c:181)
==13908==    by 0x10DEAA: interpret_cmd (console.c:201)
==13908==    by 0x10E276: cmd_select (console.c:610)
==13908==    by 0x10EB27: run_console (console.c:705)
==13908==    by 0x10CD9D: main (qtest.c:1247)

因此懷疑 qtest 在離開時忘記釋放佇列的記憶體，觀察 qtest.c 中的 q_quit() 發現第一行多了一個 return true; 導致後續的指令都被忽略，移除後大部分 Valgrind 產生的警告都消失了，但是產生了新的錯誤：

+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
ERROR: Freed queue, but 2 blocks are still allocated
==14219== 112 bytes in 2 blocks are still reachable in loss record 1 of 1
==14219==    at 0x4841888: malloc (vg_replace_malloc.c:381)
==14219==    by 0x10EC6A: test_malloc (harness.c:133)
==14219==    by 0x10F03D: q_new (queue.c:17)
==14219==    by 0x10C860: do_new (qtest.c:149)
==14219==    by 0x10D9E9: interpret_cmda (console.c:181)
==14219==    by 0x10DF7D: interpret_cmd (console.c:201)
==14219==    by 0x10E349: cmd_select (console.c:610)
==14219==    by 0x10EBFA: run_console (console.c:705)
==14219==    by 0x10CE70: main (qtest.c:1246)
==14219==

However, q_merge() is responsible for making the queues to be NULL-queue, except the first one.

繼續調查後發現是我對 queue.h 中的這句話產生誤解，在 q_merge() 中不用將佇列設為 NULL，移除所有元素即可。

改進 dudect 實作

一開始我為了排除記憶體配置所導致的時間上的不確定因素，更改了 cpucycles() 這個函式的實作

首先增加一個 cpucycles.c，並加入以下三個變數紀錄當前是否暫停計時：

static bool stop = false;
static int64_t stop_time = 0;
static int64_t delta = 0;

並將原本的 cpucycles() 改名為 cpucycles_internal()，再增加另外三個函式：

int64_t cpucycles(void)
{
    if (stop)
        return stop_time;
    return cpucycles_internal() + delta;
}

void cpucycles_start(void)
{
    if (!stop)
        return;
    delta += stop_time - cpucycles_internal();
    stop = false;
}

void cpucycles_stop(void)
{
    stop = true;
    stop_time = cpucycles_internal();
}

最後在 harness.c 中的 test_malloc() 的開頭和結尾分別呼叫 cpucycles_stop() 和 cpucycles_start()。

這個實作應用一個叫做 delta 的變數，紀錄所有記憶體配置所消耗的時間，並在之後的 cpucycles() 呼叫將 cycle 計數器的值減掉記憶體配置的時間，給予呼叫者記憶體配置沒發生過的錯覺。

接著，在 qtest.c 中的 q_init() 添加以下設定：

cpu_set_t set;
CPU_ZERO(&set);
CPU_SET(getcpu(NULL, NULL), &set);
sched_setaffinity(getpid(), sizeof(set), &set);
struct sched_param sp;
sp.sched_priority = sched_get_priority_max(SCHED_FIFO);
sched_setscheduler(0, SCHED_FIFO, &sp);

盡可能降低 context switch 所花費的時間，並且將目前的行程維持在同一個處理器核上。

經過上述的更改後，insert_head() 和 insert_tail() 的測試結果通常都是常數時間，但 remove_head() 和 remove_tail() 仍然被偵測出不是常數時間。

後來我發現作業要求中有提及目前的 dudect 的實作缺少一個叫做 Percentile Test 的功能，導致測量出來的時間資料沒經過正確的處理。此測試將統計資料中超過一定範圍的資料忽略，以避免被非預期的因素影響，只要加入這個功能，dudect 就能正常運作，通過所有項目。

a) Pre-processing: We pre-process measurements prior to
statistical processing. We discard measurements that are larger
than the p percentile, for various values of p. The rationale
here is to test a restricted distribution range, especially the
lower cycle count tail. The upper tail may be more influenced
by data-independent noise.

要如何解釋 GitHub Actions 上面的 make test 結果？
jserv

修正 dudect 實作後發現無法通過 trace-14-perf.cmd 的測試，檢查 GitHub Actions 後發現第一次出現這個錯誤是在 commit d7077fc 中。進一步追蹤後，可以觀察到 q_merge() 在這次變更中使用了 q_size() 計算最終結果的長度。

@@ -207,8 +207,10 @@ int q_merge_two(struct list_head *first, struct list_head *second)
         list_move_tail(&minimum->list, &temp_head);
         size++;
     }
+    size += q_size(first);
     list_splice_tail_init(first, &temp_head);
-    list_splice_tail(second, &temp_head);
+    size += q_size(second);
+    list_splice_tail_init(second, &temp_head);
     list_splice(&temp_head, first);
     return size;
 }

然而，q_sort() 的實作中沒有使用到合併後的最終大小，因此可以透過將計算大小的部份移除（q_merge() 有使用合併的大小，所以在 q_merge() 另外新增計算佇列大小的程式，如以下所示）以增加合併兩個佇列的效率並通過測試。

@@ -273,20 +270,22 @@ int q_merge(struct list_head *head, bool descend)
     // https://leetcode.com/problems/merge-k-sorted-lists/
     if (!head || list_empty(head))
         return 0;
+    queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
+    int size = q_size(first->q);
     if (list_is_singular(head))
-        return q_size(list_first_entry(head, queue_contex_t, chain)->q);
-    int queue_size = 0;
-    queue_contex_t *first, *second, *end = NULL;
-    first = list_first_entry(head, queue_contex_t, chain),
-    second = list_entry(first->chain.next, queue_contex_t, chain);
+        return size;
+    queue_contex_t *second =
+        list_entry(first->chain.next, queue_contex_t, chain);
+    queue_contex_t *end = NULL;
     while (second != end) {
-        queue_size = q_merge_two(first->q, second->q, descend);
+        size += q_size(second->q);
+        q_merge_two(first->q, second->q, descend);
         if (!end)
             end = second;
         list_move_tail(&second->chain, head);
         second = list_entry(first->chain.next, queue_contex_t, chain);
     }
-    return queue_size;
+    return size;
 }

commit f34b3b6

透過 Massif 分析記憶體使用量

可透過以下命令產生分析 heap 記憶體使用情形的檔案。要注意的是，挑選適當的測試資料時要避免效能類型的測試，因為以 Valgrind 執行測試程式會比較慢，容易導致出現超過時間限制的狀況，所以後面使用 trace-eg.cmd 作為範例，分析其記憶體使用量：

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

接著，使用由 KDE 社群開發的 Massif-Visualizer 工具，產生記憶體使用情形的時間分佈圖：

massif-visualizer massif.out.<pid>

觀察下方的圖示，可看到一開始程式藉由 malloc_or_fail() 分配大量的記憶體，導致出現陡坡，這對應到 console.c 中的前置執行環境準備。

接著是綠色的 _IO_file_doallocate()，這是一個由 glibc 所提供的函式，負責進行載入檔案所需要的記憶體分配，儲存如輸入的命令 trace-eg.cmd 等檔案相關資料。

最後是由 test_malloc() 配置的記憶體，這部份由qtest.c 和佇列的各操作一起使用。可看到此部份的使用量在一開始緩慢的增加，並進入一個接近平坦的狀況，到最後再快速的下降。會出現這種情形是因為 trace-eg.cmd 中的命令一開始單獨新增個別節點，所以出現成長緩慢的趨勢。並進行不影響節點數量的佇列操作，出現平坦的狀況。最後，使用 free 命令一次釋放佇列的所有記憶體，並呼叫 quit 釋放 qtest 的記憶體，代表程式結束。

新增升序/降序選項

注意到在 qtest.c 的第 611 行中有註解：

/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */

我新增一個選項 descend 負責改變 q_sort() 和 q_merge() 的順序，並增加一個命令和佇列操作 q_ascend() 作為和 q_descend() 相反的部份，負責移除升序串列中不符合規範的節點：

ADD_COMMAND(ascend,
                "Remove every node which has a node with a strictly less "
                "value anywhere to the right side of it",
                "");
add_param("descend", &descend, "Sort and merge queue in ascending/descending"
                "order", NULL);

因為 q_sort() 和 q_merge 的實作都使用到了 q_merge_two() 這個輔助函式，因此只要負責額外接收一個 descend 參數並傳遞到 q_merge_two() 即可。對應的更新是 commit b9a14c3。

接著修改 traces 目錄中的測試資料，加入降序排列操作的檢測，對應的 commit 1999405。

請提交 pull request
jserv

Queue-Mergesort
Mordecai J. Golin, Robert Sedgewick
Information Processing Letters, 48(5):253–259, 10 December 1993 ↩︎

2023q1 Homework1 (lab0)

開發環境

開發過程

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_merge_two()

q_sort()

q_descend()

q_merge()