2024q1 Homework1 (lab0)

contribute by < nosba0957 >

針對佇列的操作

`q_new`

使用 INIT_LIST_HEAD 初始化 head。因 malloc 不一定成功配置，所以使用 INIT_LIST_HEAD 前要先檢查 head 是否為 NULL。

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

`q_free`

需要先檢查 head 是否為 NULL 再釋放每個節點。

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

`q_insert_head`, `q_insert_tail`

應注意每次 malloc 是否都有成功。複製字串後要記得在尾端加上 '\0'來表示字串結束。但目前使用 make test 時 trace-17-complexity 不會通過。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;
    int str_size = sizeof(char) * (strlen(s) + 1);
    node->value = malloc(str_size);
    if (!node->value) {
        free(node);
        return false;
    }
    memcpy(node->value, s, str_size - 1);
    node->value[str_size - 1] = '\0';
    list_add(&node->list, head);

    return true;
}

`q_remove_head`, `q_remove_tail`

改進你的漢語表達。

memcpy 時要記得留位子給字串結束字元 '\0'。目前和 q_insert_head 有同樣問題，trace-17-complexity 無法通過。

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

    if (sp) {
        memcpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->next);
    return node;
}

`q_delete_mid`

參照「你所不知道的 C 語言: linked list 和非連續記憶體」的方式，使用指標的指標找到中間節點。但此鏈結串列為雙向的，所以即使將指標的指標 **indir 換成指標 *slow，也能運行。

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

注意程式碼縮排規範。

`q_delete_dup`

在 list_for_each_entry_safe 中，entry 和 safe 為前後關係的節點。所以透過 list_for_each_entry_safe 比對 entry->value 和 safe->value 即可把重複的節點透過 entry 刪除。此外，需要另外一個布林變數 dup 來紀錄是否為重複節點，以便處理最後一個重複節點。

`q_swap`

用另一個變數 head_tmp 作為可移動的 head，每次都將 head_tmp 後的第二個節點往前移到 head_tmp 前，如此一來就是前後互換，再將 head_tmp 往後移兩個節點尋找下個目標。

`q_reverse`

實作方式是將第一個節點以後的節點依序從頭加入佇列，而第一個節點進行到結束就會成為最後一個節點。我使用 pointer to pointer 方式。一開始將 **indir 指向第一個節點的 next 成員，依下圖例即為 A 的 next 成員。

接下來將第一個節點 A 以後的所有成員依序從頭加入佇列。此時 *indir 指向 B，就把 B 移動到佇列開頭。

此時 *indir 仍是指向 A->next，但 A->next 現在指向 C，所以仍然可以重複使用 indir 這個指標的指標來將剩餘的節點移動到佇列開頭。

`q_reverseK`

和 q_reverse 的作法類似，但和 q_swap 一樣需要另一個變數 sub_head 作為移動的 head，每次都依序將後 K-1 個節點加入到 sub_head 前，並移動 sub_head 到下一個地方。

`q_sort`

參考「你所不知道的 C 語言: linked list 和非連續記憶體」中 merge sort 的方式。原本的實作方式是想在每個階段都是保持環狀鏈結串列，但實行到一半發現不僅要額外操作保持節點間 prev 和 next 的關係，且每個環狀鏈結串列都要一個 list_head 作為起點，所以耗時又耗空間。後來觀摩 wanghanchi 的方式，採取將環狀鏈結串列斷開，每次 merge sort 都將子串列的結尾設為 NULL，如此一來在迭代的時候方便判斷是否抵達盡頭尾端。

改進你的漢語表達。
查詢辭典，以得知「盡頭」的寓意。本例中，鏈結串列的尾端 (tail) 絕對不是「盡頭」，因為是環狀的結構。

另外，在實作 merge_two_lists 時，需要比較兩串列值大小，並將較小者加入到存放結果的串列 *ptr 中，我自作聰明將 *ptr = R; 換為 ptr = &R;，花了將近一整天時間才找到錯誤。

static struct list_head *merge_two_lists(struct list_head *L,
                                         struct list_head *R)
{
    struct list_head *head = NULL;
    struct list_head **ptr = &head;

    for (; L && R; ptr = &(*ptr)->next) {
        element_t *left = list_entry(L, element_t, list);
        element_t *right = list_entry(R, element_t, list);
        if (strcmp(left->value, right->value) > 0) {
            *ptr = R;
            R = R->next;
        } else {
            *ptr = L;
            L = L->next;
        }
    }
    *ptr = (struct list_head *) ((uintptr_t) R | (uintptr_t) L);
    return head;
}

後來發現，ptr = &R; 的意思是將 *R 的位址直接指派給 **ptr，但 *ptr = R; 是將 *R 指派給 **ptr 內儲存的值 (初始情況是 *head)，所以後者可以分析為 head = R;。

`q_ascend`, `q_descend`

兩者都是使用 list_for_each_entry_safe 檢查每個節點。檢查方式是使用 for 迴圈從此節點開始往 next 方向依序使用 strcmp 來比較大小。若不符合規定的情況，就直接跳離 for 迴圈並將此節點刪除(delete)。

`q_merge`

參考「你所不知道的 C 語言: linked list 和非連續記憶體」的 Merge k Sorted List 題目的講解，我是使用頭尾合併的方式。merge_head 和 merge_tail 分別代表第一個和最後一個佇列，並且會將合併完的佇列指派給 merge_head。合併完後兩者往佇列的鏈結串列中間點各走一步(如下程式碼)，並繼續合併。

merge_head = merge_head->next;
merge_tail = merge_tail->prev;

合併結束的條件有兩種，當合併的佇列數量是偶數時，因 merge_head 和 merge_tail 最後一次合併會是相鄰的，所以當執行完 merge_two_lists 時，這兩個指標還是會再移動一次。所以合併結束的條件為 merge_head->prev != merge_tail。當合併的佇列數量為奇數，則最後兩個指標會重疊在同一個位置，即可結束此輪合併。
要合併全部的佇列需要 (初始佇列數量 + 1) / 2 輪，並且每次 merge_head 都要重置為第一個佇列，而 merge_tail 在前一輪就會前進到未合併佇列中的最後一個佇列，所以不須更動。全部的輪次結束後，再將環狀鏈結串列回復原狀。
在實作過程中，一直出現非法操作記憶體的錯誤，此處參考 wanghanchi 的筆記，佇列合併後，要將另一個空的佇列使用 INIT_LIST_HEAD 將佇列初始化，避免出現錯誤。

使用 valgrind 排除 qtest 記憶體問題

在 terminal 輸入

make valgrind

執行後發現和老師說的一樣，執行速度會下降很多，尤其是 trace-17-complexity 測試時間複雜度需要花很多時間。
目前執行結果並沒有找到記憶體問題。

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

Simulation 解釋

開啟 simulation 後，若使用 ih, it, rh, rt 此四種指令，會跳到 fixture.c 內的 test_const 函式。在 test_const 函式中，doit 執行了 i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1 次，其中可以看到我們需要有 ENOUGH_MEASURE 次的測試結果(此為 10000)，而每次 doit 內會執行 N_MEASURE 次(目前為 150)，DROP_SIZE 為丟棄測試資料的數量，乘 2 是頭尾各丟棄 DROP_SIZE 個。

改進 lab0-c

查看 dudect 的原始程式碼後，可以知道 lab0-c/dudect/fixture.c 為對應的檔案，但 lab0-c 是比較簡略的實作，在 update_statistics 缺少 percentile test 實作，在原 dudect 原始程式碼實作中會將執行時間超過臨界值(thresholds)的資料略過。所以我們會需要新增計算和記錄 percentile 的程式碼。

新增了 percentile test 後，make test 中 trace-17-complexity 即可滿分。
在 update_statistics 中，dudect 的實作在一開始會捨去前十個測量的值。percentiles[] 是透過數學式 1 - (pow(0.5, 10 * (double)(i + 1) / NUMBER_PERCENTILES)) 將 150 份測試資料分成 NUMBER_PERCENTILES 個臨界值(目前設為 100)。接下來在就可以在 update_statistics 中比較執行時間和第 n(0~99) 個臨界值，符合的執行時間再加入該臨界值的 t-test。

for (size_t crop_index = 0; crop_index < NUMBER_PERCENTILES; crop_index++) {
    if (difference < percentiles[crop_index]) {
        t_push(t[crop_index + 1], difference, classes[i]);
    }
}

最後得到的數值有 1 個包含所有執行時間的 t-test，在程式碼中是 t[0]，和另外 100 個依照臨界值取值再計算的 t-test，在程式碼中是 t[1]~t[101]。最後 report 函式回傳的值是透過 max_test 從 101 個值找出最大 t 值回傳。

static t_context_t *max_test()
{
    size_t ret = 0;
    double max = 0;
    for (size_t i = 0; i < DUDECT_TESTS; i++) {
        if (t[i]->n[0] > ENOUGH_MEASURE) {
            double x = fabs(t_compute(t[i]));
        if (max < x) {
            max = x;
            ret = i;
        }
        }
    }
    return t[ret];
}

搞懂原理並著手修正 dudect 後，可嘗試提交 pull request

原本 lab0-c 的實作中，DROP_SIZE 會在 measure 中發揮作用，measure 內的 for 迴圈會將 cpucycles 放在 before_ticks[] 和 after_ticks[] 兩陣列中，並且是從索引 DROP_SIZE 放到索引 N_MEASURES - DROP_SIZE。但在 differentiate 函式中，計算執行時間卻是從索引值為 0 的位置開始計算。
下面資料是在 differentiate 函式內新增 printf 將資料全部印出，可以看見開頭和結尾的地方都是 0。

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1469 1714 1014 716 581 577 208 160 157 309 182 490 210 178 195 162 163 587 180 494 153 159 284 538 520 442 546 178 160 490 307 182 304 478 186 162 155 155 357 167 151 303 451 397 405 607 183 175 504 189 157 395 180 208 157 157 385 218 404 202 578 197 160 158 161 619 524 512 482 396 208 391 310 182 160 601 171 159 637 173 162 155 159 163 153 458 192 405 174 160 159 458 206 676 218 393 177 396 565 266 156 159 400 383 169 163 163 344 207 160 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

所以應該改為在測量期間(measure)應該要記錄全部資料，接下來在 update_statistic 才將頭尾的值刪去。以 insert_head 為例：

switch (mode) {
     case DUT(insert_head):
-        for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
+        for (size_t i = 0; i < N_MEASURES; i++) {
             char *s = get_random_string();
             dut_new();
             dut_insert_head(

在 update_statistics 將前後刪去 DROP_SIZE 數量的值

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

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

一開始直接從 list_sort 開始閱讀，一開始可以看到 __attribute__((nonnull(2,3))) 可以知道是 gnu extensions，其意義指定此函式的參數不能為 NULL。例如範例為 nonnull(2,3)，即第 2 和 3 的參數不能為 NULL。

nonnull (arg-index, …)
The nonnull attribute specifies that some function parameters should be non-null pointers.

接下來看到內部區域變數，其中 pending 比較需要解釋。他也是一條鏈結串列，內部存放等待被合併的串列，而不同於此程式碼中的 list 鏈結串列，pending 是使用 prev 形成的串列。
而 do-while 迴圈就是 list sort 的重點。首先會有一個變數 count，每走一次迴圈都會增加 1，並且是從 0 開始。第一個 for 迴圈會使用到 bits 變數。而 bits 就是將 count 內的值複製過去，然後用來進一步計算而已。
do-while 迴圈內部執行的過程有三件事

for 迴圈，用來移動 tail 和對 bits 做右移計算。
合併階段，用 if 敘述判斷，由剛剛被右移計算的 bits 來判斷要不要合併。
不論上一階段是否有合併，都要增加一個節點到 pending 上。

由於 count 是在這三階段執行以後才會被加 1，所以下列表格的 count 都以執行此三階段時的大小來表示。透過下表 count 二進位值和 list_sort.c 中 for 迴圈的條件限制，可以發現當 count 的二進位值都是 1 的時候(例如 1, 3, 7)，就不會執行合併，只會新增一個元素在 pending 串列上。

Count	Count 二進位值	Pending
0	0000	1
1	0001	1 ← 1
2	0010	(2) ← 1
3	0011	2 ← 1 ← 1
4	0100	2 ← (2) ← 1
5	0101	(4) ← 1 ← 1
6	0110	4 ← (2) ← 1
7	0111	4 ← 2 ← 1 ← 1

此程式碼中最奇妙的部分是可以透過 count 的二進位值移動指標的指標 tail 來指定此次要合併的串列。從上表中舉 count 為 5 的例子，二進位值為 0101，還沒合併且未新增節點到 pending 前，pending 為 2 <- 2 <- 1。所以在 for 迴圈，會將 tail 移動到黃色底的 2 上，2 <- 2 <- 1，就可以將兩個 size 為 2 的串列合併。

閱讀 Queue-mergesort 論文

Queue-mergesort 的做法是會有一個佇列儲存等待合併的資料，初始情況是每個佇列內的元素的 size 都是 1，每次都會取出 head 前兩個元素出來合併，再將其加入到佇列尾端。
接下來要證明 Queue-mergesort 是最佳(optimal)的 merge sort，證明是透過 worst-case 的比較次數，Queue-mergesort 的比較次數不能多於其他的 mergesort。mergesort 中比較次數是來自於將兩陣列合併的數值比較。若有兩個串列大小分別為 n1，n2，我們可以知道合併的最差情況(worst-case)為 n1 + n2 - 1。並將 worst-case 比較次數的表示為

\sum_{v \in T, v i n t e r n a l} [w (v) - 1]

，其中 T 是 merge tree，

w (v)

是該節點的 weight，也就是合併後的串列大小。又定義

w (T) = \sum_{v \in T, v i n t e r n a l} w (v)

，這樣證明 Queue-mergesort 是否為 optimal 透過比較不同合併排序的

w (T)

即可。

w (T) \leq w (T^{'})

T

為 Queue-mergesort，

T^{'}

為其他合併排序。

We use the fact that the weight of a merge tree is equal to its external path length.

也就是

w (T) = E (T)

，

E (T)

為此二元樹的 external path length，為每個葉節點(leaves)到

T

的根節點所需的路徑長度總和。接下來就可以證明的方式就可以換成

E (T) \leq E (T^{'})

下一步要使用 Huffman encoding 的特性來證明。Huffman tree 的建立方式是會將節點先依照權重(weight)大小排列，再從最小的節點一次取出兩個節點，合併成一個子樹，其產生的新的根節點的權重為剛才兩節點的總和，再將這個新節點依照合併後的權重大小列入到待排序的序列中，再取出最小的兩個節點合併。一直到只剩一個節點就結束。
而 Huffman tree 的特性是其 weighted external path length

\sum_{i \leq n} h (l_{i}) w_{i}

是最小的。
Queue-mergesort 和 Huffman tree 的建立形式一樣，每次都取最小 size 的兩個串列來合併。所以 Queue-mergesort 同樣擁有

\sum_{i \leq n} h (l_{i}) w_{i}

是最小的特性。而又 Queue-mergesort 初始情況是每個 size 為 1 的串列來合併，所以其

w_{i}

皆為 1。這樣就可以得到

\sum_{i \leq n} h (l_{i})

是最小的，就證明 Queue-mergesort 的 external path length

E (T) \leq E (T^{'})

為真，就證明出 Queue-mergesort 為 optimal merge sort。

在 qtest 提供新的命令 shuffle

老師上課提及測試 timsort 的資料可以用 shuffle 產生，所以先處理 shuffle 命令。實作方式是從最後一個節點開始，從這個節點以前的串列隨機找一個節點交換。交換完就再進行倒數第二個節點，以此類推。而我交換節點的方式只有單純交換指標，本來最直觀的想法是用 list API 來移動整個節點，但後來發現這樣會新增許多鏈結串列的操作，而且指標處理很容易錯誤。所以後來思考後發現因為 element_t 內的 value 成員也只是指向我們額外配置的記憶體，所以我們可以交換指標就可以達成交換值。

static void swap(struct list_head *a, struct list_head *b)
{
    element_t *a_entry = list_entry(a, element_t, list);
    element_t *b_entry = list_entry(b, element_t, list);
    char *tmp = b_entry->value;
    b_entry->value = a_entry->value;
    a_entry->value = tmp;
}

透過老師的測試程式，得到的圖可以看出大致符合 Uniform distribution。

比較 timsort, list_sort 和 merge sort

timsort 的實作是使用第二周作業的內容，我只有改進 minrun 和新增插入排序。list_sort 是直接取自 linux 的原始程式碼，而 merge sort 是原本實作的 q_sort 函式。
我使用兩種不同的資料分佈，第一種是全部為亂數的資料分佈。從 0 個節點開始，每次增加 1000 個節點，直到 100000。然後透過 shuffle 指令使資料隨機排序。再輸入三個排序方法的命令，紀錄時間和節點數量的關係圖。圖中有些資料突然飆高，可以視為離群值。

TODO: 重用部分 dudect 程式碼來協助統計。

好

第二種資料分佈是為了符合 timsort 的資料分佈，所以這些資料有四分之三的值是已經排序好的，只有前四分之一會被隨機排序。可以看到我實作的結果中，timsort 耗時反而是最高的，我認為是我在第二周作業並沒有將 timsort 改進的很好。

在這些實驗過程中，有使用 perf 來查看程式熱點，發現執行 it 命令時，會透過 q_show() 印出目前佇列的情況。其佔執行時間的 66%。所以在此實驗的情況，可以不用知道插入新節點的佇列情況，可以先將 q_show() 隱藏。

參考 cpython 的測試資料後重新實驗，並且使用 sortperf.py 來產生隨機資料，並且選擇用 list_sort_ascending_one_percent，即為 1% 的資料是隨機的。節點數量為 15384、16384、17384，其中 16384 為 2 的冪。可以發現 timsort 在 15384 個節點所花的時間會比另外兩組節點所花的時間還要多。

2024q1 Homework1 (lab0)

針對佇列的操作

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_sort

q_ascend, q_descend

q_merge