2023q1 Homework1 (lab0)

contributed by < tseng0201 >

詳閱作業規範！

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

jserv

開發環境

$ gcc -v
gcc version 9.4.0 (Ubuntu 9.4.0-1ubuntu1~20.04.1)

$ 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):                          16
On-line CPU(s) list:             0-15
Thread(s) per core:              2
Core(s) per socket:              8
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           151
Model name:                      12th Gen Intel(R) Core(TM) i9-12900K
Stepping:                        2
CPU MHz:                         3200.000
BogoMIPS:                        6374.40
Virtualization:                  VT-x
L1d cache:                       384 KiB
L1i cache:                       256 KiB
L2 cache:                        10 MiB
L3 cache:                        30 MiB
NUMA node0 CPU(s):               0-15

完成 queue.c

q_new

建立新的~~鏈結串列~~ 佇列

鏈結串列是用來實作佇列的機制，而 queue.h 正是封裝一系列佇列操作，因此你該用「建立佇列」來說明 q_new 的作用，並指明是藉由 List API 達成。

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

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_delete_element

自定義函式用於刪除整個節點，先將節點移出鏈結串列接著釋放掉該節點其值 (node->value) 所指向的記憶體空間，最後釋放節點本身的記憶體空間
void q_delete_element(struct list_head *node)

{
    if (!node) {
        return;
    }
    list_del_init(node);
    free(list_entry(node, element_t, list)->value);
    free(list_entry(node, element_t, list));
}

q_free

將該鏈結串列所使用的記憶體空間詮釋放，使用 list_for_each_safe () 進行鏈結串列的走訪， safe 指標會額外保存 ptr 指標指向的下一個節點 (ptr->next) 因此可對 ptr 指表所指向的節點進行刪除，且不影響鏈結串列的走訪

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *ptr, *safe;
    list_for_each_safe (ptr, safe, l) {
        q_delete_element(ptr);
    }
    free(l);
    return;
}

q_insert_head

對鏈結串列的開頭插入一個節點，每次執行 malloc 函式時都要確定使否成功配置記憶體，建立新節點後使用 list_add() 進行插入

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

q_insert_tail()

對鏈結串列的尾部插入一個節點，方法同 q_insert_head 但將 list_add() 改為 list_add_tail()

q_remove_head

移除鏈結串列開頭的第一個節點，同時使用 stencpy 函式保存該節點的值，將 bufsize - 1 設為 '\0' 是避免當節點的值長度大於 bufsize 時 stencpy 函式不會自動補 '\0'

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);
    list_del_init(&node->list);
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

q_remove_tail

移除鏈結串列開頭的第一個節點，方法同 q_remove_head，但將 list_first_entry() 改為 element_t *node = list_last_entry(head, element_t, list);

q_size

取得鏈結串列的長度，使用 list_for_each 對鏈結串列進行走訪，每走訪一個節點將 size+1

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

q_delete_mid

刪除鏈結串列中間的節點，根據 leetcode 描述中間點定義為 \(⌊n / 2⌋^th\)，n 為 index 從 0 開始計算，本方法透過快慢指標，快指標走兩步慢指標走一步，當快指標無法完整走兩步時慢指標正好指著中間節點

index	0、1	2、3
對應的 middle	0	1

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    struct list_head *fast = head, *slow = head;
    do {
        fast = fast->next->next;
        slow = slow->next;
    } while (fast != head->prev && fast != head);
    q_delete_element(slow);
    return true;
}

q_delete_dup

從已排序的鏈結串列中刪除值重複的節點，將 ptr 指標指向節點的值與下一個節點 (ptr->next) 的值比較，如果值相同就刪除下一個節點並將 kill_self 設為 true，當 ptr 指標指向節點的值與下一個節點的值不同時將 ptr 指標移至下一個節點，隨後檢查kill_self 是否為 true，如過 kill_self 為 true 刪除 ptr->prev

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    if (list_empty(head) || list_is_singular(head)) {
        return true;
    }
    struct list_head *ptr = head->next;
    bool kill_self = false;
    while (ptr != head && ptr->next != head) {
        while (ptr->next != head &&
               !strcmp(list_entry(ptr, element_t, list)->value,
                       list_entry(ptr->next, element_t, list)->value)) {
            q_delete_element(ptr->next);
            kill_self = true;
        }
        ptr = ptr->next;
        if (kill_self) {
            q_delete_element(ptr->prev);
            kill_self = false;
        }
    }
    return true;
}

q_swap

將鏈結串列的節點兩兩進行順序交換，透過 ptr 指標將 ptr->next、ptr->next-next 兩個節點進行順序交換，最後將 ptr 指標移至 ptr->next-next 對下兩個節點進行位置交換，直到剩下 0 個或 1 個未被交換的節點便停止

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    struct list_head *ptr = head;
    while (ptr->next != head && ptr->next->next != head) {
        struct list_head *first = ptr->next;
        struct list_head *second = ptr->next->next;
        first->next = second->next;
        first->prev = second;
        first->next->prev = first;
        ptr->next = second;
        second->next = first;
        second->prev = ptr;
        ptr = ptr->next->next;
    }
}

q_reverse

將結串列中的節點順序反轉，透過走訪 list 並將每個節點的 next 與 prev 指向的位置交換

q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *temp = head;
    do {
        list_swap(&temp->next, &temp->prev);
        temp = temp->prev;
    } while (temp != head);
}

q_reversek

以 K 個節點為一組，進行順序反轉，如果剩下未處理的節點列少於 K 就不進行動作

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head) || list_is_singular(head) || k == 1)
        return;
    struct list_head *from = NULL, *to = head->next, *ptr = NULL;
    while (to != head) {
        from = to;
        for (int i = k - 1; i > 0; i--) {
            to = to->next;
            if (to == head)
                return;
        }
        from->prev->next = to;
        to->next->prev = from;
        ptr = from;
        to = to->next;
        from = from->prev;
        for (; ptr != to; ptr = ptr->prev) {
            list_swap(&ptr->next, &ptr->prev);
        }
        from->next->prev = from;
        to->prev->next = to;
    }
    return;
}

merge_two_sorted_list

參照你所不知道的 C 語言: linked list 和非連續記憶體將兩條已排序的鏈結串列合併為一條已排序的鏈結串列

/*

struct list_head *merge_two_sorted_list(struct list_head *q_1,
                                        struct list_head *q_2)
{
    if (!q_1 || !q_2)
        return (struct list_head *) ((__UINTPTR_TYPE__) q_1 |
                                     (__UINTPTR_TYPE__) q_2);
    struct list_head *head = NULL, **ptr = &head, **node;
    for (node = NULL; (__UINTPTR_TYPE__) q_1 & (__UINTPTR_TYPE__) q_2;
         *node = (*node)->next) {
        node = (strcmp(list_entry(q_1, element_t, list)->value,
                       list_entry(q_2, element_t, list)->value) <= 0)
                   ? &q_1
                   : &q_2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr =
        (struct list_head *) ((__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2);
    return head;
}

q_sort

對鏈結串列中節點的值進行排序
閱讀 lab0 作業說明Linux 核心的鏈結串列排序，仿造文中提到的方法進行 merge sort

void q_sort(struct list_head *head)
{
    if (!head || list_is_singular(head) || list_empty(head))
        return;
    struct list_head *list = head->next, *pending = NULL;
    int count = 0;

    // make doublely link list to singly linked list
    head->prev->next = NULL;
    do {
        struct list_head **tail = &pending;
        // check wether count + 1 is pow of 2, if true  merge
        if (count & (count + 1)) {
            for (int bits = count; bits & 1; bits >>= 1) {
                tail = &(*tail)->prev;
            }
            struct list_head *a = *tail, *b = a->prev;
            a = merge_two_sorted_list(a, b);
            a->prev = b->prev;
            *tail = a;
        }
        list->prev = pending;
        pending = list;
        list = list->next;
        pending->next = NULL;
        count++;
    } while (list);
    // merge all the list in pending
    list = pending;
    pending = pending->prev;
    while (pending) {
        struct list_head *next = pending->prev;
        list = merge_two_sorted_list(list, pending);
        pending = next;
    }
    // rebuild prev;
    head->next = list;
    list = head;
    while (list->next != NULL) {
        list->next->prev = list;
        list = list->next;
    }
    head->prev = list;
    list->next = head;
    return;
}

q_descend

從頭開始走訪鏈結串列，當該節點的所有右側節點中有一個節點的值大於該節點便刪除該節點，透過 top-down 作法從尾巴開始往頭部檢查，當 ptr 指向的節點其值小於上一個節點 (ptr->prev) 的值時時刪除上一個節點反之移動 ptr 至 ptr->prev

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;
    struct list_head *ptr = head->prev;
    while (ptr != head && ptr->prev != head) {
        int cmp = strcmp(list_entry(ptr, element_t, list)->value,
                         list_entry(ptr->prev, element_t, list)->value);
        if (cmp >= 0)
            q_delete_element(ptr->prev);
        else
            ptr = ptr->prev;
    }
    return q_size(head);
}

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

該篇論文提出一個新的工具 dudect 透過統計方法，在不受硬體差異的限制下，偵測目標函式是否為常數時間的實作。
dudect 透過兩種不同的輸入：

固定輸入(Fixed Inputs), 論文建議可以挑選一些可能該函式能處理較快速的 Corner Case，
隨機輸入(Random Inputs), 每次的輸入都不相同，以隨機產生

當目標函式對固定輸入與隨機輸入所花費的時間分佈有顯著差異，便可推翻虛無假說(目標函式為常數時間的實作)，反之無法拒絕該虛無假說

dudect 的執行步驟如下：

第一步： Measure execution time
使用固定與隨機兩種輸入，重複數次進行時間的測量
第二步 Apply post-processing
由於時間的測量可能會因為中斷發生導致導致數據不準確，因此需要刪除部份測量結果，降低離群值的影響，論文中提到的方法如下
Cropping：設定一個閥值，將大於閥值的測量結果捨棄，論文實做，透過 qsort 將測量結果由小到大排列，取得第數據量 * p 個測量結果作為閥值， p 為 0 ~ 1 的值
Higher-order preprocessing：根據不同的數據使用不同的前處理

第三步 Apply statistical test
透過統計學方法，判斷兩種輸入花費的時間分佈是否一致，論文中提到的方法如下
t-test：判斷兩種輸入是否有相同的平均值，論文使用 online Welch’s t-test with Welford’s variance computation 方法進行實作當計算出的 t 值小於 4.5 時，無法拒絕虛無假設，及兩種輸入來自相同的分佈故，並可推測該函式為常數時間的實作

什麼是Welch’s t-test 、 online Welch’s t-test 與 Welford’s variance computation
Chatgpt：
Welch's t-test是一種 Student's t-test(又稱 t-test) 的變體，用於比較兩個樣本的平均值是否有顯著的差異。與傳統的獨立樣本 t-test 不同，Welch's t-test 不要求兩個樣本具有相同的變異數。

online Welch’s t-test 是 Welch's t-test 的一種實現方式，它可以逐步計算每個新的數據點的 t 值，並在任何時刻使用已有的數據點的均值和標準差來更新t值。這種方法被稱為在線方法，因為它可以適應新的數據點，而不必重新計算所有數據點的均值和標準差。

Welford’s variance computation 是一種用於計算平均值和變異數的遞推算法，其基本思想是在處理每個數據點時更新平均值和變異數的估計值。該算法具有以下優點：
    1. 適用於在線處理。不需要保存整個數據集，只需要處理每個新數據點即可。
    2. 數值穩定。算法中使用差值的平方和來計算變異數，避免了舍入誤差的累積。

Non-parametric tests：如 Kolmogorov-Smirnov，該方法對於數據分佈的潛在假設較少，但可能會需要更多樣本且收斂較為緩慢

為 lab0 c 改進 dudect

TODO

目前的實作為將 random_string 改為 fixed_string 使隨機部份只在於佇列的長度，但仍然無法保證 trace-17-complexity 的測試，需要再理解 percentile 後處理對於數據的影響

改進 random_string 對測量時間的影響

參考 yanjiew1 同學的共筆後開始研究 lab0-c 中 measure 函式與 prepare_inputs 函式的實作，嘗試尋找改進空間
prepare_inputs 程式碼如下

void prepare_inputs(uint8_t *input_data, uint8_t *classes)
{
    randombytes(input_data, N_MEASURES * CHUNK_SIZE);
    for (size_t i = 0; i < N_MEASURES; i++) {
        classes[i] = randombit();
        if (classes[i] == 0)
            memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);
    }

    for (size_t i = 0; i < N_MEASURES; ++i) {
        /* Generate random string */
        randombytes((uint8_t *) random_string[i], 7);
        random_string[i][7] = 0;
    }
}

prepare_inputs 函式有以下幾個階段

將 input_data 使用 randombytes 函式對每個 byte 進行 0~255 的填充，
使用 randombit 函式分配隨機每筆測試資料所屬的組別(0 -> fixed, 1 -> random)，並將組別 0 所對應到的 input_data 寫為 0
使用 randombytes 函式對 random_string 進行隨機賦值
接下來看看 measure 函式(只顯示 case DUT(insert_head) 部份)

bool measure(int64_t *before_ticks,
             int64_t *after_ticks,
             uint8_t *input_data,
             int mode)
{
    assert(mode == DUT(insert_head) || mode == DUT(insert_tail) ||
           mode == DUT(remove_head) || mode == DUT(remove_tail));

    switch (mode) {
    case DUT(insert_head):
        for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
            char *s = get_random_string();
            dut_new();
            dut_insert_head(
                get_random_string(),
                *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
            int before_size = q_size(l);
            before_ticks[i] = cpucycles();
            dut_insert_head(s, 1);
            after_ticks[i] = cpucycles();
            int after_size = q_size(l);
            dut_free();
            if (before_size != after_size - 1)
                return false;
        }
        break;

透過 case DUT(insert_head) 步驟可推知每次測量數據時會經過以下步驟

指標 s 取得隨機字串
透過 dut_new 函式建立新的佇列
插入 *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000) 個節點，其值為 get_random_string()，進一部分析 "input_data + i * CHUNK_SIZE" 的數值範圍，由 input_data 函式實作可以得知當測試資料為 Fixed 組別時其值為 0，而當測試資料為 Random 組別時 "input_data + i * CHUNK_SIZE" 可以表現出 0 ~ 65535(\(2^16-1\)) 在對 10000 進行 mod 運算可得其值為 0 ~ 9999
紀錄執行操作前的佇列大小
紀錄執行操作前的時間
執行指定操作，上述程式碼會執行 insert_head 函式，其值為指標 s
紀錄執行操作後的時間
紀錄執行操作後的佇列大小
刪除該佇列
透過比較操作前後的佇列大小確保操作成功
步驟 3 每次產生不同大小的佇列，來測量指定操作是否可在常數時間完成

而 [yanjiew1] 同學於共筆提到，因為 randombytes 函式有可能產生數值 0，導致 random_string 陣列中每個 string 的長度會不相同，導致無法正確判斷函式是否為常數時間的實作，同時觀察 DUT(remove_head) 與 DUT(remove_tail) 部份，執行remove 時的參數為 (l, NULL, 0)，這代表在進行 remove 函式的測量時，並不會考量到記憶體的複製操作，不受隨機長度 string 的影響因此我認為應該將 random_string 改為定值，使其與 remove 函式有相同的測試基準。

透過上述的解析，可推得 lab0-c 對於 measure 的實現，其隨機的部份應該在於每次進行指定操作時的佇列長度不一進行操作，為此我認為應該將 random_string 改為定值

疑問

在看完 Dude, is my code constant time 後，經過 lab0c 的提示下，決定在 lab0c 中實現 percentile 後處理功能，在參考數位同學如 alanjian85、chiangkd 的筆記後，都有提到加入 percentile 功能後，程式便可以通過 trace-17-complexity，但我追蹤 ducet 的原始碼在 src/dudect.h 的 report() 後產生了疑問，不了解為什麼實現 percentile 後處理功能後便可以正確測量函式實作是否為常數實作
首先 src/dudect.h 的 report() 程式碼如下

static dudect_state_t report(dudect_ctx_t *ctx) {
    .
    .
    .
    ttest_ctx_t *t = max_test(ctx);
    double max_t = fabs(t_compute(t));
    double number_traces_max_t = t->n[0] +  t->n[1];
    double max_tau = max_t / sqrt(number_traces_max_t);
    .
    .
    .
    if (max_t > t_threshold_bananas) {
        printf(" Definitely not constant time.\n");
        return DUDECT_LEAKAGE_FOUND;
    .
    .
    .
  }
}

由判斷式 if (max_t > t_threshold_bananas) 可得知 dudect 是用 max_t 與 t_threshold 判斷是否為常數時間，max_t 由 max_test 函式取得，而 max_test 函式程式碼如下：

static ttest_ctx_t *max_test(dudect_ctx_t *ctx) {
  size_t ret = 0;
  double max = 0;
  for (size_t i = 0; i < DUDECT_TESTS; i++) {
    if (ctx->ttest_ctxs[i]->n[0] > DUDECT_ENOUGH_MEASUREMENTS) {
      double x = fabs(t_compute(ctx->ttest_ctxs[i]));
      if (max < x) {
        max = x;
        ret = i;
      }
    }
  }
  return ctx->ttest_ctxs[ret];
}

由上述程式碼可得知 max_test 會將不同前後處理中擁有最大的 t 值的數據作為回傳值，為了了解有那些不同的後處理數據需要了解 update_statistics 函式，其程式碼如下

static void update_statistics(dudect_ctx_t *ctx) {
  for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {
    int64_t difference = ctx->exec_times[i];

    if (difference < 0) {
      continue; // the cpu cycle counter overflowed, just throw away the measurement
    }

    // t-test on the execution time
    t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]);

    // t-test on cropped execution times, for several cropping thresholds.
    for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
      if (difference < ctx->percentiles[crop_index]) {
        t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
      }
    }

    // second-order test (only if we have more than 10000 measurements).
    // Centered product pre-processing.
    if (ctx->ttest_ctxs[0]->n[0] > 10000) {
      double centered = (double)difference - ctx->ttest_ctxs[0]->mean[ctx->classes[i]];
      t_push(ctx->ttest_ctxs[1 + DUDECT_NUMBER_PERCENTILES], centered * centered, ctx->classes[i]);
    }
  }
}

可以看到 ctx->ttest_ctxs[0] 是儲存不經過 percentile 後處理的數據，而ctx->ttest_ctxs[1 ~ DUDECT_NUMBER_PERCENTILES] 才會儲存經過 percentile 後處理的數據，因此可以得知 max_test 函式在選擇最大的 t 值時也會考慮沒有後處理的數據，那麼為什麼在原本 Lab0-c 的實現中未經過後處理的數據 t 值會大於閥值，而加上 percentile 後處理後，未經過後處理的數據 t 值就會小於閥值(假設未經過前處理的數據的 t 值會最大)

追蹤 alanjian85 同學的 github 可看到其動如下

-   double max_t = fabs(t_compute(t));
+   t_context_t *t = max_test();
+   double max_t = fabs(t_compute(t_ctxs[0]));
+   double number_traces_max_t = t->n[0] + t->n[1];
+   double max_tau = max_t / sqrt(number_traces_max_t);

其用 t_ctxs[0]算出來的 t 值作為 max_t 的值，而非使用 max_test() 的回傳值 t，代表 max_test 函式毫無作用，在追蹤 update_statistics 可以發現以下改動

-   t_push(t, difference, classes[i]);
+   t_push(t_ctxs[0], difference, classes[i]);
+
+   for (size_t j = 0; j < N_PERCENTILES; j++) {
+       if (difference < percentiles[j])
+           t_push(t_ctxs[j + 1], difference, classes[i]);

其中 t_ctxs[0] 的確是未經過 percentiles 前處理的數據，最後比較 t_ctxs[0] 相關的差異如下

-   t_push(t, difference, classes[i]);
+   t_push(t_ctxs[0], difference, classes[i]);

-   double max_t = fabs(t_compute(t));
+   double max_t = fabs(t_compute(t_ctxs[0]));

尚無法了解其改動後與原 lab0-c 實現的差異。

TO DO

滿足 make test 自動評分系統的所有項目

目前只差 trace-17-complexity 無法通過且每次結果都不一樣，翻閱其他同學的筆記後發現目前判斷的程式有問題，無法正確判斷實作是否為常數時間，需詳閱論文〈Dude, is my code constant time?〉與其程式碼後，對判斷程式進行修正再對 trace-17-complexity 進行測試

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

尚無法理解如何利用二進位的 0、1 判斷 \(3 \times 2^k\) 是否發生，預計透過 perf 進行效能落差比較

改善 web 命令

尚未開始研究

提供 shuffle 命令並以統計的原理來分析實作，並探究洗牌的「亂度」

尚未開始研究

設計一組新的命令或選項，得以在 qtest 切換不同的 PRNG 的實作

尚未開始研究

N96104234曾晧峖

2023/03/07 17:49:25

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

了解 (Edited)

Jim Huang

2023/03/01 03:34:44

改進漢語描述，善用 ChatGPT: https://www.facebook.com/groups/system.software2023/posts/626412385977586/ (Edited)

2023/03/01 04:15:15

好的，之後會更仔細詳閱相關規定 (Edited)

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.

2023q1 Homework1 (lab0)

開發環境

完成 queue.c

q_new

q_delete_element

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

merge_two_sorted_list

q_sort

q_descend

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

為 lab0 c 改進 dudect

TODO

改進 random_string 對測量時間的影響

疑問

TO DO

滿足 make test 自動評分系統的所有項目

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

改善 web 命令

提供 shuffle 命令並以統計的原理來分析實作，並探究洗牌的「亂度」

設計一組新的命令或選項，得以在 qtest 切換不同的 PRNG 的實作

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