# 2023q1 Homework1 (lab0)
contributed by < [davidlai1999](https://github.com/davidlai1999) >

## 開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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-8750H CPU @ 2.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4100.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4399.99

## 實作 queue.c
### list_head

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

### element_t

typedef struct {
    char *value;
    struct list_head list;
} element_t;

### q_size

:::danger
注意書寫規範：中英文間用一個半形空白字元區隔
:notes: jserv
:::
**實作步驟**
* 使用 `list.h` 所提供的 `list_for_each` 走訪一整個佇列，每經過一個節點就將長度加 1 ，直到走訪完畢後將長度回傳。

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_new
**實作步驟**
* 配置佇列的開頭需要先對記憶體配置一個 `list_head` 大小的空間，若配置失敗則回傳 NULL ，配置成功則使用 `INIT_LIST_HEAD` 將指標 next 與 pre 指向自己本身。

struct list_head *q_new()
{
    struct list_head *empty =
        (struct list_head *) malloc(sizeof(struct list_head));

    if (!empty)  // if malloc failed, return NULL
        return NULL;
    INIT_LIST_HEAD(empty);

    return empty;
}

### q_insert_head
**實作步驟**
* 新增一個元素到佇列的開頭，首先要配置與 `element_t` 同大小的空間，接著再配置字串之前，我們需要先確認元素的空間是否配置成功，若配置失敗則回傳 false 。
* 接著配置空間存放字串並確認配置成功後，使用 `strncpy` 將傳入字串放入新配置的空間中，最後使用 `list_add` 將元素插入到佇列的開頭。
* 第一次實作時不慎在配置的空間範圍外放置 '\0' ，造成實作 `q_free` 時出現錯誤，在後面的更新已重新更正。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)  // if佇列is NULL
        return false;

    element_t *element = malloc(sizeof(element_t));
    if (!element)  // if malloc failed, return NULL
        return false;

    int s_len = strlen(s) + 1;  // handle the value of element
    char *str = malloc(s_len * sizeof(char));
    if (!str) {         // if malloc failed, return NULL
        free(element);  // because insert failed,release memory
        return false;
    }
    strncpy(str, s, s_len);
    //  str[s_len] = '\0';
    element->value = str;

    list_add(&element->list, head);
    return true;
}

### q_insert_tail
* 實作方式與 `q_insert_head` 相同，但插入佇列的時使用 `list_add_tail`。

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)  // if佇列is NULL
        return false;

    element_t *element = malloc(sizeof(element_t));
    if (!element)  // if malloc failed, return NULL
        return false;

    int s_len = strlen(s) + 1;  // handle the value of element
    char *str = malloc(s_len * sizeof(char));
    if (!str) {         // if malloc failed, return NULL
        free(element);  // because insert failed,release memory
        return false;
    }
    strncpy(str, s, s_len);
    element->value = str;

    list_add_tail(&element->list, head);
    return true;
}

### q_reverse
**實作步驟**
* 實作反向等價於從開頭開始將所有元素從新插入到佇列的開頭，使用 `list_for_each_entry_safe` 走訪佇列並使用 `list_move` 依序將元素移動到開頭。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))  // if佇列is NULL or head = NULL
        return;

    element_t *it = NULL, *is = NULL;
    list_for_each_entry_safe (it, is, head, list) {
        list_move(&it->list, head);
    }
}

### q_free
**實作步驟**
* 使用 `list_for_each_entry_safe` 走訪佇列並使用 `list_del` 將元素從佇列中移除，接著使用 `q_release_element` 釋放元素所佔用的記憶體空間，最後再將佇列的開頭釋放。

void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *it = NULL, *is = NULL;
    list_for_each_entry_safe (it, is, l, list) {
        list_del(&it->list);
        q_release_element(it);
    }
    free(l);
}

### q_remove_head
**實作步驟**
* 使用 `list_first_entry` 取得第一個元素並用 `list_del_init` 將其從佇列中移除，接著使用 `strncpy` 將元素中的 value 依 bufsize 大小放入 sp 中，最後回傳從佇列中刪去的元素。
* 更新：之前沒處理當 sp 指向 NULL 時的情況。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))  // if佇列is NULL or head = NULL
        return NULL;

    element_t *element = list_first_entry(head, element_t, list);
    list_del_init(&element->list);

    if (sp != NULL) {
        strncpy(sp, element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return element;
}

### q_remove_tail
**實作步驟**
* 與 `q_remove_head` 實作方法相同，差別在使用 `list_last_entry` 得到最後一個元素。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))  // if佇列is NULL or head = NULL
        return NULL;

    element_t *element = list_last_entry(head, element_t, list);
    list_del_init(&element->list);

    if (sp != NULL) {
        strncpy(sp, element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return element;
}

:::warning
思考縮減程式碼的手法，善用前置處理器。
:notes: jserv
:::

### q_delete_mid
**實作步驟**
* 找中間值使用兩個快慢指標對進行佇列進行走訪，快指標的走訪速度是慢指標的兩倍，當快指標只到的下個元素或下下個元素為佇列開頭時，慢指標指向的元素即為 middle ，利用 `list_del` 將其從佇列中去除並釋放該空間。

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->next, *slow = head->next;
    do {
        slow = slow->next;
        fast = fast->next->next;
    } while (fast->next != head && fast->next->next != head);

    element_t *mid = list_entry(slow, element_t, list);
    list_del(slow);
    q_release_element(mid);

    return true;
}

### q_delete_dup
**重點參數**
* marker：紀錄當前是否存在重複的 element，當走訪中的 element 數值即將改變，用於判斷當前 temp 節點是否需要刪除。
* temp：若 marker 為 true，則此 element 為 duplicate。

**實作步驟**
* 先確認佇列是否存在或是因為為空或唯一而不需要刪除。
* 利用 `list_for_each_entry_safe` 走訪 queue。
* 若當前 element 與 temp相同，移除該節點並設定 marker 為 true。
* 若當前 element 不為重複且已存在重複 element，刪除 temp，更新 temp。

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;

    bool marker = false;
    element_t *entry = NULL, *safe = NULL, *temp = NULL;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (temp != NULL && strcmp(temp->value, entry->value) == 0) {
            list_del(&entry->list);
            q_release_element(entry);
            marker = true;
        } else {
            if (marker == true) {
                list_del(&temp->list);
                q_release_element(temp);
                marker = false;
            }
            temp = entry;
        }
    }

    if (marker == true) {
        list_del(&temp->list);
        q_release_element(temp);
    }

    return true;
}

### q_swap
* ~~使用一個 count 紀錄當前 element 為偶數還是基數，若為基數則將當前 element 移動到前一個 element 之前，直到整個佇列走訪完畢~~。
* 更新：從新設計過 `q_reverseK` 後修改 `q_swap` 的實作方式

void q_swap(struct list_head *head)
{
    // ttps://leetcode.com/problems/swap-nodes-in-pairs/

    if (!head)
        return;
    q_reverseK(head, 2);
}

### q_reverseK
**重點參數**
* temp：用於儲存當前元素要反轉的起始位置，會隨反轉過程而位移。
* node：指向當前要移動的節點，透過 safe 來更新。
* count：紀錄當前元素是否滿足條件要進行反轉，判斷條件為對其進行 k 的模運算。
**實作步驟**
* 從佇列開頭走訪，當 count 被 k 整除，以從當前元素往前數 k 個元素進行反轉，過程中當前元素將利用 `list_move` 被位移到 temp 之後，並將 temp 與 node 更新。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))  // if佇列is NULL or head = NULL
        return;

    int count = 1;
    struct list_head *node = NULL, *safe = NULL, *temp = head;
    list_for_each_safe (node, safe, head) {
        if (count % k == 0) {
            for (int i = 0; i < k; i++) {
                list_move(node, temp);
                temp = temp->next;
                node = safe->prev;
            }
        }

        count++;
    }
}

### q_sort
* 使用 merge sort 實作，新增函數 mergesort , split , mergelist 來實現 merge sort 的運行，因為無法配置記憶體，將佇列修改成沒有開頭以便實作。

**實作步驟**
* 指派一個 list_head 型別指向佇列的第一個元素。
* 使用 `list_del_init` 將開頭移除佇列，並呼叫 `mergesort`。
* 將開頭重新與排序完成的佇列相連。

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))  // if佇列is NULL or head = NULL
        return;

    struct list_head *front = head->next;
    list_del_init(head);

    mergesort(&front);
    head->prev = front->prev;
    head->next = front;
    front->prev->next = head;
    front->prev = head;

}

**mergesort**

**實作步驟**
* 判斷佇列是否只剩一個元素，是則回傳。
* 利用 `split` 將佇列一分為二， front 指向前一個子佇列， back 指向後面的子佇列。
* 兩個子佇列遞迴做 `mergesort` 完成排序。
* 將兩個排序好的子佇列用 `mergelist` 重新合成。

void mergesort(struct list_head **head)
{
    if ((*head)->next == *head)
        return;
    struct list_head *front = *head, *back = NULL;
    split(&front, &back);

    mergesort(&front);
    mergesort(&back);

    *head = mergelist(front, back);
}

**split**

**實作步驟**
* 宣告兩個指標為快慢指標，指向佇列的第一個元素，快指標一次移動為慢指標的兩倍。
* 當快指標下次移動會指向開頭時停止走訪，慢指標指向的位置即為 middle 。
* 將佇列一分為二， front 指向前子佇列， back 指向後子佇列。

void split(struct list_head **front, struct list_head **back)
{
    struct list_head *fast = *front, *slow = *front;
    while (fast->next != *front && fast->next->next != *front) {
        slow = slow->next;
        fast = fast->next->next;
    }

    *back = slow->next;
    slow->next = *front;
    (*back)->prev = (*front)->prev;
    (*front)->prev->next = *back;
    (*front)->prev = slow;
}

**mergelist**

**重點參數**
* result：指向新的佇列第一個元素，為回傳值。
* temp：為建立過程中，指向佇列的最後一個元素。
* walk1 & walk2：個別指向走訪過程中，尚未被排序的元素。
* front->tail & back->tail：指向子佇列的結尾。

**實作步驟**
* 從各自子佇列的第一個元素開始走訪，當其中一個佇列為空時結束走訪。
* 判斷兩個子佇列當前元素的 value 哪個較小，將其加入新的 佇列，使該元素與 temp 互相連接，並用 temp 指向它表示其為結尾。
* 當其中一個佇列為空，剩餘子佇列接到新的佇列的最後面，並利用 tail 將頭尾重新相連接。
* 回傳新佇列的開頭。

struct list_head *mergelist(struct list_head *front, struct list_head *back)
{
    struct list_head *result = NULL, *temp = NULL, *walk1 = front,
                     *walk2 = back;
    struct list_head *front_tail = front->prev, *back_tail = back->prev;
    front_tail->next = NULL, back_tail->next = NULL;

    while (walk1 != NULL && walk2 != NULL) {
        element_t *element1 = list_entry(walk1, element_t, list);
        element_t *element2 = list_entry(walk2, element_t, list);
        if (strcmp(element1->value, element2->value) < 0) {
            if (!result) {
                result = walk1;
                temp = result;
            } else {
                temp->next = walk1;
                walk1->prev = temp;
                temp = temp->next;
            }

            walk1 = walk1->next;
        } else {
            if (!result) {
                result = walk2;
                temp = result;
            } else {
                temp->next = walk2;
                walk2->prev = temp;
                temp = temp->next;
            }

            walk2 = walk2->next;
        }
    }

    if (walk2 == NULL) {
        temp->next = walk1;
        walk1->prev = temp;
        front_tail->next = result;
        result->prev = front_tail;
    } else {
        temp->next = walk2;
        walk2->prev = temp;
        back_tail->next = result;
        result->prev = back_tail;
    }

    return result;
}

### q_descend
**實作步驟**
* 將 `list_for_each_entry_safe` 修改成逆向走訪 queue。
* 宣告 temp 指標指向已走訪路逕上有最大值的元素。
* 若當前元素的值比 temp 小，將其刪除。
* 若當前元素的值比 temp 大，將 temp 指向它定更新 len。
* 回傳 len。

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    int len = 0;
    element_t *entry = NULL, *safe = NULL, *temp = NULL;
    for (entry = list_entry((head)->prev, element_t, list),
        safe = list_entry(entry->list.prev, element_t, list);
         &entry->list != (head);
         entry = safe, safe = list_entry(safe->list.prev, element_t, list)) {
        if (!temp || strcmp(entry->value, temp->value) >= 0) {
            temp = entry;
            len++;
            continue;
        }

        list_del(&entry->list);
        q_release_element(entry);
    }

    return len;
}

### q_merge
**重點參數**
* first：指向第一個佇列的開頭。
* walk：紀錄目前走訪到哪個佇列。
* front：指向第一個佇列的第一個元素。
* back：指向當前佇列的第一個元素。

**實作步驟**
* 使用 walk 走訪以 queue_contex_t 構成的 list ，將當前佇列與 first 的開頭從佇列中移除並用 front 與 back 指向其開頭。
* 利用 mergelist 將 front 與 back 合併成新的佇列。
* len 等於兩個佇列合併之後的長度。
* 走訪完畢將 first 與合併後的佇列重新連接，回傳 len。

int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head)
        return 0;

    struct list_head *first = NULL, *walk = head->next->next;
    struct list_head *front = NULL, *back = NULL;
    first = list_entry(head->next, queue_contex_t, chain)->q;
    front = first->next;
    int len = list_entry(head->next, queue_contex_t, chain)->size;
    list_del_init(front->prev);
    while (walk != head) {
        back = list_entry(walk, queue_contex_t, chain)->q->next;
        list_del_init(back->prev);
        front = mergelist(front, back);

        len = len + list_entry(walk, queue_contex_t, chain)->size;
        walk = walk->next;
    }

    first->next = front;
    first->prev = front->prev;
    front->prev->next = first;
    front->prev = first;
    list_entry(head->next, queue_contex_t, chain)->size = len;

    return len;
}

### queue.c 功能實作時遇到的問題
* 目前得到的分數為 95 分，在 insert 的部份出現執行時間非 constant time 的問題。

:::danger
詳閱作業書寫規範，文字訊息「不要」用螢幕截圖來展現，尊重視障朋友閱讀的權益。
:notes: jserv
:::

## 在 `ficture.c` 中補上欠缺的 `percentile` 處理
[文獻參考](https://eprint.iacr.org/2016/1123.pdf)
[oreparaz/dudect](https://github.com/oreparaz/dudect)
[willwillhi1 共筆](https://hackmd.io/@willwillhi/lab0-2023)
* 當我在檢查 trace-17 錯誤原因時，從 qtest 的 `do_ih` 中發現是因為 `is_insert_head_const` 回傳的值非 true 而回傳錯誤訊息，而追到 `fixture.c` 時發現 `doit` 與 `oreparaz/dudect` 中的 `dudect_main` 存在相似之處卻缺少 `prepare_percentiles` 的實作，這與作業要求相符合，於是開始補上這個處理過程。
* 經過觀察可以發現 `oreparaz/dudect` 將執行時間、輸入資料等等變數儲存成結構 `dudect_ctx_t` ，而 `lab0-c` 則是在 `doit` 才使用 `calloc` 宣告，所以必須將 `lab01-c` 中缺少的 `percentiles` 在 `doit` 中自行補上，宣告方式與 `oreparaz/dudect` 相同。

typedef struct {
  int64_t *ticks;
  int64_t *exec_times;
  uint8_t *input_data;
  uint8_t *classes;
  dudect_config_t *config;
  ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
  int64_t *percentiles;  /*lab01-c 欠缺*/
} dudect_ctx_t;

percentiles = calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t));

* 將 `oreparaz/dudect` 中的 `prepare_percentiles` 修改成符合 `lab01-c` 的格式，由於 `prepare_percentiles` 只須用到 `dudect_ctx_t`結構中的 `percentiles` 與 `exec_times` ，對 `prepare_percentiles` 中的參數進行修改。

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);
    }
}

* 最後依照 `oreparaz/dudect` 中的 `dudect_main` 修改 fixture.c 中的 `doit` ，即可通過 trace-17 。
>+++ TESTING trace trace-17-complexity:
\# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100

## 在 qtest 中實作 shuffle 命令
**shuffle 實作方式**

**重要參數**
* len：用於存取當前佇列中還有多少元素可以被隨機選取，會隨迴圈次數下降，當 len 歸零表示佇列中已無能處理之元素，結束迴圈。初始值為佇列長度。
* old：為 list_head 型別之指標，指向執行過程中隨機選中的元素。
* new：為 list_head 型別之指標，指向佇列中排序為最後且還沒被選取的元素。
* temp1 與 temp2：分別指向 old 與 new 的 prev ，用於 `list_move` 。

**實作步驟**
* 當佇列為空或為一時，直接回傳。
* 將 len 設定為佇列長度， new 指向佇列結尾， old 指向第一個元素。
* 當 len 不無零時，代表佇列中尚存在還沒被選取到的元素，繼續執行。
* 利用 `rand` 取得隨機數並與 len 進行模運算達到在 len 中隨機選取的效果，並將 old 位移到指向該元素，將 old 與 new 傳入 `swap` 進行交換。
* 在 `swap` 中，首先會判斷 old 與 new 是否指向相同元素，是則無須交換。
* 設定 temp1 與 temp2 ， 當 old 與 new 相鄰時只須作將 new 利用 `list_move` 移動到 old 前方即可完成對調，非相鄰則須作兩次位移才能完成對調。
* 回到 `q_shuffle` ， 將 new 指向 old 的 prev 並將 old 只回第一個元素， len 減 1 。

static void swap(struct list_head *old, struct list_head *new)
{
    if (old == new)  // location same, don't switch
        return;

    struct list_head *temp1 = old->prev;
    struct list_head *temp2 = new->prev;

    if (old->next != new) {  // if old and new are adjacent, then move one node.
        list_move(new, temp1);
    }
    list_move(old, temp2);
}


void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))  // if queue is NULL or head = NULL
        return;

    int len = q_size(head), target;
    struct list_head *old = head->next;
    struct list_head *new = head->prev;

    while (len != 0) {
        target = rand() % len;
        printf("%d\n", target);
        while (target != 0) {
            old = old->next;
            target--;
        }

        swap(old, new);
        len--;
        new = old->prev;
        old = head->next;
    }
    return;
}

**在 qtest 中設定命令**
* 在 `console.h` 中 `ADD_COMMAND` shuffle ， 並實作 `do_shuffle` ， 當 current 為空或沒有存取佇列時，回傳錯誤訊息，若不存在以上問題即可呼叫 `q_shuffle` 。

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");
    error_check();

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

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

:::danger
instruction 的翻譯是「指令」，command 的翻譯是「命令」
:notes: jserv
:::

:::warning
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:notes: jserv
:::

## 引入 `list_sort.c`
### 引入步驟
* 起初是打算將向 `queue.c` 與 `queue.h` 那種形式將 `list_sort` 引入，所以將 `list_sort.c` 中的 `merge` , `merge_final` , `list_sort` 參數進行修改，去掉 `priv` 與 `cmp` ，並將 `cmp` 寫在 `list_sort.c` 中，我錯誤的將 element_t 這個架構也宣告在 `list_sort.h` 中，忽略了結構只能宣告一次這個問題。
* 我在將 `queue.h` 引入 `list_sort.h` 中與將 `cmp` 重新用函式指標傳入兩種修改方案中選擇了後者， 將 cmp 寫在 `qtest.c` 中並使用函式指標以引數形式傳入，`list_sort.c` 中新的函式宣告如下。

struct list_head *merge(list_cmp_func_t cmp, struct list_head *a, struct list_head *b);
void merge_final(list_cmp_func_t cmp, struct list_head *head, struct list_head *a, struct list_head *b);
void list_sort(list_cmp_func_t cmp, struct list_head *head);

* 由於 `merge_final` 中的 `count` 型別為 `uint8_t` 而在 `list_sort.c` 加入 `stdint.h`。

#include <stdint.h>

uin8_t count = 0;

* 在 `list_sort.h` 中加入 `likely` 與 `unlikely` 兩個巨集的定義，這兩者原先位於 [include/linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 中。

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

:::warning
不該修改 `queue.h`，研讀 `Makefile` 以思考整合的方式。
:notes: jserv
>已修改 list_sort 的引入方式。
:::

* 在 `qtest.c` 中 `do_sort` 複製一個並更改為用 `list_sort` 進行排列，新增命令 `sort2` 使 `qtest` 能選擇排序的實作方式是 `list_sort` 還是 `mysort`。

ADD_COMMAND(sort2, "Sort queue in ascending order with list_sort", "");

:::danger
注意用語！
:::

### 與 mysort 進行性能比較
* 建立一個 `.cmd` 檔，目的是讓 `qtest` 執行一段命令，使我們能透過 `perf` 觀察排列所需的 `cache-misses` , `cache-references` , `cycles` 等等資訊，其內容如下。

option fail 0
option malloc 0
new
ih RAND 500000
sort/sort2
free

* 輸入命令 `perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles` ，其中 `--repeat 5` 代表執行 5 次， `-e` 為我們在意的資訊，而執行程式為 `./qtest -f perf-test-listsort.cmd` 。

* mysort 結果

Performance counter stats for './qtest -f perf-test-mysort.cmd' (5 runs):

        52,406,045      cache-misses              #   54.574 % of all cache refs      ( +-  3.08% )
        94,845,015      cache-references                                              ( +-  0.45% )
     2,333,641,546      instructions              #    0.64  insn per cycle           ( +-  0.05% )
     3,598,180,009      cycles                                                        ( +-  1.05% )

            0.9341 +- 0.0131 seconds time elapsed  ( +-  1.40% )

* list_sort 結果

 Performance counter stats for './qtest -f perf-test-listsort.cmd' (5 runs):

        46,359,552      cache-misses              #   58.680 % of all cache refs      ( +-  0.32% )
        79,446,039      cache-references                                              ( +-  0.41% )
     2,294,685,005      instructions              #    0.67  insn per cycle           ( +-  0.06% )
     3,435,985,515      cycles                                                        ( +-  0.26% )

           0.87305 +- 0.00398 seconds time elapsed  ( +-  0.46% )

* <s>由於 `list_sort` 有依據硬體架構進行設計</s>，不論是
:::danger
清楚解釋落差，「據硬體架構進行設計」太含糊。應該要分析:
* cache locality
* 排序演算法對於比較次數的設計
* 特殊或邊界狀況

注意用語，唯有掌握各式細節，你才可撰寫真正有強度的程式碼。
:notes: jserv
:::