2022q1 Homework1 (lab0)

contributed by < ShallowFeather >

Reviewed by ItisCaleb

• 程式碼的改動可以附上 git commit 的連結
• 改動 dudect 時，應該去解釋改動的意義

開發環境

Windows 11 WSL2

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 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-9300H CPU @ 2.40GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    BogoMIPS:            4800.01

開發過程

q_new

利用 malloc 來配置記憶體
並使用 list.h 中的 INIT_LIST_HEAD 來初始化 head 並且進行回傳

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

如果使用 list_for_each 進行走訪，會導致當釋放掉目前的 pos 時會讓他無法找到下一個節點
因此使用 list_for_each_entry_safe 巨集，此巨集會使用一個額外的 n 來暫時儲存下一個節點的 entry 值，讓他可以在刪除掉目前的節點以後還能夠繼續執行。

改進漢語描述，特別是「每次循環時」這句。

jserv

而在開始時，需先檢查 l 是否為空，如為空就無須額外處理。

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

q_insert_head / q_insert_tail

這兩段程式碼的實作方式很相似，都是利用 malloc 函數分配記憶體給新節點，若分配失敗則直接回傳 false。接著使用 strdup 函數為新節點的 value 成員分配記憶體空間，並將傳入的字串 s 複製到新分配的空間中。若分配失敗，則需要回傳 false 並釋放先前使用 malloc 分配的記憶體空間。最後，呼叫 list_add 或 list_add_tail 函數，將新節點加入到串列中。

改進漢語描述。

jserv

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

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

q_remove_head / q_remove_tail

跟上面一樣 這兩段的實作很相像
目標在於清除佇列的第一個元素，sp 是一個已分配記憶體空間的字元陣列，而 bufsize 是他的大小(長度)。
首先利用 list_del 來刪除第一個元素，並利用 strncpy 去將剛剛刪除的元素中的 value 複製到 sp 中，並且也需要檢查 bufsize 為 0 的情況來避免 bufsize - 1 為 -1 的情況

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head)) 
        return NULL;
    element_t *tmp = list_entry(head->next, element_t, list);
    list_del(head->next);
    if (sp && bufsize != 0) {
        strncpy(sp, tmp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return tmp;
}

而 remove_tail 只需要將 head->next 修改成 head->prev 即可

/* 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)) 
        return NULL;
    element_t *tmp = list_entry(head->prev, element_t, list);
    list_del(head->prev);
    if (sp && bufsize != 0) {
        strncpy(sp, tmp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return tmp;
}

q_size

利用 list_for_each 來迭代整個串列並利用 len 變數來計算總共的數量，最後回傳

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    int len = 0;
    struct list_head *li;

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

q_delete_mid

利用兩個指標一個走的速度是另一個的兩倍，而當跑到最後一項時，較慢的那個指標便會是中間值，參考連結中 Leetcode 的解法

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if(head == NULL || head->next == NULL) return false;

    struct list_head *fastNode = head->next, *slowNode = head->next, *lastNode = head->prev;
    while(fastNode != lastNode && fastNode->next != lastNode) {
        fastNode = fastNode->next->next;
        slowNode = slowNode->next;
    }
    list_del(slowNode);
    return true;
}

TODO:降低記憶體存取的數量。

jserv

參考自 Linux 核心實作 (2023): 第 1 週課程 (隨堂測驗)
根據 1:46:30 所說，由於是雙向的，所以可以從頭尾跑。

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (head == NULL || head->next == NULL)
        return false;
    struct list_head *frontNode = head->next, *backNode = head->prev;
    while (frontNode != backNode && frontNode->next != backNode) {
        frontNode = frontNode->next;
        backNode = backNode->prev;
    }
    list_del(frontNode);
    q_release_element(list_entry(frontNode, element_t, list));
    return true;
}

q_delete_dup

由於該串列已「排序」，因此只需要利用 strcmp 去檢查目前的節點和下一個節點是否相同，需要注意:

1. 是否只有單個節點，如果沒有去檢查且只有單個節點也就是 head->next 等於 head 時，會將該節點刪除，導致不符合所求
2. 要求為刪除有重複的節點，而非讓整個串列不會出現重複的節點，因此需要多一個 bool 去紀錄紀錄上一個節點是否需要被刪除。

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if(head == NULL) return false;
    bool checkDup = false;
    element_t *pos, *n;
    list_for_each_entry_safe(pos, n, head, list) {
        if(&n->list != head && strcmp(pos->value, n->value) == 0) {
            checkDup = true;
            list_del(&pos->list);
            q_release_element(pos);
        }
        else if(checkDup) {
            list_del(&pos->list);
            q_release_element(pos);
            checkDup = false;
        }
    }
    return true;
}

q_reverse

迭代整個串列並且對每個節點交換其 next 以及 prev 值

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (head == NULL)
        return;
    struct list_head *pos, *n, *tmp;
    list_for_each_safe (pos, n, head) {
        tmp = pos->next;
        pos->next = pos->prev;
        pos->prev = tmp;
    }
    tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

q_reverseK

用一個 cnt 紀錄經過的節點數量，當等於 k 時利用 list_cut_position 去切割，而根據 list.h 當中函數的說明中可以得知當第二個參數非空時，會將第一格參數取代。
最後再將執行過 reverse 操作的節點丟回去 tmp 的前面，並將 tmp 設定在 n->prev 的位置上也就是上次切割的點。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (head == NULL)
        return;
    struct list_head *pos, *n, *tmp = head;
    int cnt = 0;
    LIST_HEAD(tmp_head);
    list_for_each_safe (pos, n, head) {
        cnt++;
        if (cnt == k) {
            list_cut_position(&tmp_head, tmp, pos);
            q_reverse(&tmp_head);
            list_splice_init(&tmp_head, tmp);
            cnt = 0;
            tmp = n->prev;
        }
    }
    return;
}

q_sort

參考 itiscaleb 的程式碼

附上對應的超連結。

jserv

使用 mergeSort 來實作排序首先利用快慢指標找到中點並去做切割。
而後進入遞迴，將其分割成小塊並利用 strcmp 來比較大小並合併。

void merge2list(struct list_head *left,
                struct list_head *right,
                struct list_head *result)
{
    while (!list_empty(left) && !list_empty(right)) {
        element_t *first = list_entry(left->next, element_t, list);
        element_t *second = list_entry(right->next, element_t, list);
        if (strcmp(first->value, second->value) <= 0)
            list_move_tail(&first->list, result);
        else
            list_move_tail(&second->list, result);
    }
    if (!list_empty(left))
        list_splice_tail(left, result);
    else
        list_splice_tail(right, result);
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *slow = head, *fast = head;
    do {
        fast = fast->next->next;
        slow = slow->next;
    } while (fast != head && fast->next != head);
    LIST_HEAD(left);
    LIST_HEAD(right);
    list_splice_tail_init(head, &right);
    list_cut_position(&left, &right, slow);
    q_sort(&left);
    q_sort(&right);
    merge2list(&left, &right, head);
}

q_descend

如果讓他由後跑到前，題目就變成了找出遞增數列。

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

    struct list_head *now = head->prev, *tmp = now->prev;

    while (tmp != head) {
        if (strcmp(list_entry(tmp, element_t, list)->value,
                   list_entry(now, element_t, list)->value) < 0) {
            list_del_init(tmp);
            q_release_element(list_entry(tmp, element_t, list));
        } else {
            now = tmp;
        }
        tmp = now->prev;
    }
    return q_size(head);
}

q_merge

單純將所有 list 組合起來並直接 sort。

int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (head == NULL || list_empty(head))
        return 0;
    queue_contex_t *contex = list_first_entry(head, queue_contex_t, chain),
                   *pos = NULL;
    int ret = q_size(contex->q);
    list_for_each_entry (pos, head, chain) {
        if (contex == pos)
            continue;
        ret += pos->size;
        list_splice_tail_init(pos->q, contex->q);
    }
    q_sort(contex->q);
    return ret;
}

TODO 利用分治等手段加速該函式

---

實作 Shuffle 命令

在 console.h 中發現了

/* Add a new command */
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

之後在 qtest.c 中加入 do_shuffle 當中內容參考 do_reverseK 以及 do_merge 的檢查

static book 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");
    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();
}

呼叫的 q_shuffle 需在 queue.h 中定義並於 queue.c 中實作

void q_shuffle(struct list_head *head) {
    if(head == NULL || list_empty(head))
        return;
    int len = q_size(head);
    struct list_head *tmp;
    while(len) {
        tmp = head->next;
        for(int i = 0; i < (rand() % len) - 1; i++) {
            tmp = tmp->next;
        };
        list_move_tail(tmp, head);
        len--;
    }
    return; 
}

不過由於修改到 queue.h 好像跑不過測試QQ

避免帶有個人色彩的發言，更別說「好像」，理工人說話要精準。

jserv

dudect

dudect 的檢查主要分成三部分

1. 反覆測量兩個不同的測資的運行時間，其一值固定，而另一值則在每次測量時皆為隨機值
2. 預處理以及將如 process interupt 之類無關的時間剪裁掉或丟棄大於固定的、無關閾值的測量值
3. 嘗試去推翻兩個時間分布相等的假設，利用以下兩種檢測
   1. t-test: Welch's t-test(當 t 值超過某個閾值就能斷定可能存在性能方面的問題)
   2. Non-parametric tests

改進 duduct

依據作業要求知道缺乏了 percentile 因此將 oreparaz/dudect 當中的程式碼移植到 dudect/fixure.c 當中

static int cmp(const int64_t *a, const int64_t *b)
{
    return (int) (*a - *b);
}

static int64_t percentile(int64_t *a, double which, size_t size)
{
    qsort(a, size, sizeof(int64_t), (int (*)(const void *, const void *)) cmp);
    size_t array_position = (size_t) ((double) size * (double) which);
    assert(array_position >= 0);
    assert(array_position < size);
    return a[array_position];
}

/*
 set different thresholds for cropping measurements.
 the exponential tendency is meant to approximately match
 the measurements distribution, but there's not more science
 than that.
*/
static void prepare_percentiles(int64_t *percentiles, int64_t *exec_times)
{
    for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
        percentiles[i] = percentile(
            exec_times,
            1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)),
            N_MEASURES);
    }
}

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

        /* do a t-test on the execution time */
        t_push(ttest_ctxs[0], difference, 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 < percentiles[crop_index]) {
                t_push(ttest_ctxs[crop_index + 1], difference, 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]);
        // }
    }
}