owned this note
owned this note
Published
Linked with GitHub
# 2024q1 Homework1 (lab0)
contributed by < [devarajabc](https://github.com/devarajabc) >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 11
CPU max MHz: 3900.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
```
## 開發過程
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
:::info
了解
:::
### `q_new`
:::danger
不懂就說不懂，不要不懂裝懂說「不太懂」。
改進你的漢語表達。
:::
:::info
1.了解
:::
原本不懂要 new 的是哪個東西？是 queue_contex_t 還是element_t 或是單純的 list_head，直到翻閱 [qtest.c](https://github.com/devarajabc/lab0-c/blob/master/qtest.c#L143) 才知道 q_new 要新增的是佇列的 `head` (下圖藍色處)
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold" color = blue ]
node4 [label="element_t|{<left>prev|<right>next}", style="bold"]
node3 [label="etc.", style="bold"]
node2 [label="element_t|{<left>prev|<right>next}", style="bold"]
node1 [label="element_t|{<left>prev|<right>next}", style="bold"]
list [label="qctx->q", style="normal", color="white"]
head:right:e -> node4:w
node4:left:w -> head:e
node4:right:e -> node3:w
node3:left:w -> node4:e
node3:right:e -> node2:w
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
head:left:e -> node1:w
list -> head:n
}
```
```c
queue_contex_t *qctx = malloc(sizeof(queue_contex_t));
list_add_tail(&qctx->chain, &chain.head);
qctx->size = 0;
qctx->q = q_new();
qctx->id = chain.size++;
```
同時程式也說明了如何建立 `qctx` ，這對於思考如何進行 `q_merge` 很有幫助
:::danger
詳閱作業要求！
:::
### `q_free`
利用 `list_for_each_entry_safe`來走訪每一個節點，再利用 `q_release_element` 來釋放該節點( `element_t` )與節點內指向的字串（綠色部分），最後再釋放 head node (藍色部分)
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_0 {
style=invisible;
value [label="{value}"];
head [label="{<prev>prev|<next>next}"];
style=bold;
label=element_t
}
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=blue];
e1 -> head :right:w [color=blue];
value->string
string [color = green ]
}
```
### `q_insert_head`, `q_insert_tail`
原本是使用 `strncpy` 以及用 `strlen` 來判斷長度避免造成記憶體區段錯誤，後來發現函式 `strdup` 就可以達到所需的功能，而且記憶體配置失敗時會回傳 NULL ，非常方便
不過在 [stackoverflow](https://stackoverflow.com/questions/252782/strdup-what-does-it-do-in-c) 發現以下敘述
>Keeping in mind it's actually not part of the current (C17) ISO C standard itself(a) (it's a POSIX thing), it's effectively doing the same as the following code:
此外在 git commit 的時候一直收到
```
queue.c:64:5: error: Memory leak: temp [memleak]
return true;
^
queue.c:88:5: error: Memory leak: temp [memleak]
return true;
^
Fail to pass static analysis.
```
後來將
```c
INIT_LIST_HEAD(&(temp->list));
list_add_tail(&(temp->list), head));
```
改成
```c
INIT_LIST_HEAD(&temp->list);
list_add_tail(&temp->list, head);
```
就通過 static analysis 了，目前還不知道為什麼
:::warning
注意看 C 語言運算子的優先順序。
:::
### `q_remove_head` / `q_remove_tail`
先利用 `list_first_entry` / `list_last_entry` 來取出欲移除的節點 `removed `
接著使用 `list_del_init` 來將該節點移出佇列
並利用 `strncpy` 將 `removed->value` 拷貝到字串 `sp` 之中
最後要將字串 `sp` 的最後一元素 `sp[bufsize - 1]` 指派為 `'\0'` 。
:::danger
你該用 ChatGPT 改進你的漢語表達，並避免將自己的專業成長訴諸大語言模型。
> 我知道錯了
:::
### `q_size`
:::danger
避免贅字
:::
:::success
已刪除
:::
>參考[作業說明](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a)
在範例的基礎上加入 `list_empty(head)` 來處理佇列為空的情況。
### `q_delete_mid`
利用 `list_for_each_entry` 與一相反方向走訪的指標 `rev_node` 來尋找中間點，再利用`list_del_init`和 `q_release_element`來刪除節點，以下為部分程式碼：
```c
if(node==rev_node||node->next==rev_node){
list_del_init(rev_node);
q_release_element(list_entry(rev_node,element_t,list));
return true;
}
rev_node=rev_node->prev;
```
選擇 `rev_node` 為要刪除的中間節點而非使用 `node` 是為了處理 node 數量為偶數的情況
### `q_delete_dup`
程式的執行主要分成兩種情況：
* 目前節點與下一個節點相同：利用 while loop 刪除相同的節點
* 目前節點與下一個節點相異：又可分成兩種可能:
1. 剛離開 while loop：刪除目前節點
2. 未曾進入 while loop：什麼都不必做
以下是細節說明：
利用 `list_for_each_entry_safe` 來走訪每節點，當發現下一個節點與目前節點相等時，就會利用 while loop 不斷走訪並刪除 「目前節點的下一個節點」直到出現相異的節點或是走訪到 head ，因此原先指向「目前節點的下一個節點」的指標 `safe` 會被改變。
此外在進入 while loop 之前會進行判斷，避免在 `entry->list.next` 為 `head` 的情況下使用 `list_entry` 而造成記憶體區段錯誤。
在第四行將指向「目前節點的下一個節點」的指標儲存在 `Next` 而非直接用 `list_entry` 的輸出節果來作為函式 `list_del` 與函式 `q_release_elemen` 的輸入，因為執行 `list_del` 之後的佇列會被改變，直接將 `list_entry` 的輸出作為 `q_release_element` 的輸入會破壞佇列的結構。
```diff
while (entry->list.next != head &&
!strcmp(entry->value,
list_entry(entry->list.next, element_t, list)->value)) {
+ element_t *Next = list_entry(entry->list.next, element_t, list);
- list_del(entry->list.next)
+ list_del(&Next->list);
- q_release_element(list_entry(entry->list.next, element_t, list));
+ q_release_element(Next);
}
```
接著要判斷 `safe` 是否被改變過，如果是 `safe` 依然是「目前節點的下一個節點」，代表該節點沒有進去過 while loop ，因此不需要刪除目前節點。
:::danger
改進你的漢語表達。
> <s>已對內容進行更改</s>
> 還差得遠，要用清晰明確且流暢的漢語書寫，你該展現自己學了二十餘年漢語的能耐。
:::
反之則要刪除該節點，並指派 `safe` 正確的值，以便 `list_for_each_entry_safe` 可以繼續運作。
```diff
+if (list_entry(entry->list.next, element_t, list) != safe) {
-if (!safe){
safe = list_entry(entry->list.next, element_t, list);
list_del_init(&entry->list);
q_release_element(entry);
}
```
`safe` 再其所指向的節點被刪除後，會指向一位置不明、不固定且無法 dereference 的地址而非 NULL，原因不明，甚妙。
所以若使用 `safe` 是否為 NULL 來判斷是否要刪除該節點，則會在後續的步驟造成記憶體區段錯誤，以下是 valgrind 的輸出結果：
```shell
==267663== Invalid read of size 8
==267663== at 0x10FCB1: q_delete_dup (queue.c:168)
==267663== by 0x10C093: do_dedup (qtest.c:467)
==267663== by 0x10E0ED: interpret_cmda (console.c:181)
==267663== by 0x10E6A2: interpret_cmd (console.c:201)
==267663== by 0x10F30C: run_console (console.c:691)
==267663== by 0x10D4DF: main (qtest.c:1288)
```
### `q_reverse`/`q_reverseK`/`q_swap`
> 參考 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_delete_dup)
1. 利用 `list_for_each_safe` 走訪每一個節點並用 `list_move` 把目前節點移到 `head`，以達到翻轉順序的目的。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
2. 在撰寫 `q_reverseK` 的時候一開始誤會題意，以為只要處理前 k 個，還好在 [HotMercury](https://hackmd.io/@NeedSleep/linux2024-homework1) 的提醒下才改正，實作如下:
利用 `list_for_each_safe` 走訪每個節點並利用 `list_move` 將其移至 `new_head` 。
每經歷 k 個 node 就會更新 `new_head` 的值，以達到題目的要求，當走訪的節點數量不足 k 時則不會改變 `new_head` 的值。
```c
list_for_each_safe (node, safe, head) {
if (!i--) {
new_head = node->prev;
i = k - 1;
}
list_move(node, new_head);
}
```
3. `q_swap` 是 `q_reverseK` 的一個特例，用 K = 2 來實踐。
:::danger
1. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
2. 改進漢語表達
:::
:::info
1.已改正
2. :notes: 沒做到的事，不要急著回應。斟酌字句值得佔用你的青春去淬鍊。
:::
### `q_ascend`/`q_descend`
:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
> 將「遍歷」全數更正為「走訪」、「當前」皆更新為「目前」
"queue" 更正為「佇列」、 "linked list" 更正為「鏈接串列」
>
> 漢語詞彙不該直接對應到英語，仍該針對情境去調整。 :notes: jserv
:::
在走訪的過程中若目前節點大於 `min` 則會更新 `min` ，並將用於記錄 node 數量的變數 `i` 加一 ，反之則將其刪除，細節如下：
```c
if (strcmp(entry->value, min->value) < 0) {
list_del(&entry->list);
q_release_element(entry);
} else {
min = entry;
i++;
}
```
而 `q_descend` 則是把 `lish_for_each_safe` 改成往 prev 的方向走訪，其他部分則跟 `q_ascend` 一樣。
:::danger
這是環狀雙向鏈結串列，何來「右邊」？工程人員說話要精準。
:::
:::success
已更正
:::
### ` q_sort`, `merge_two`
>參考 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_delete_dup) 和[alanjian85](https://github.com/alanjian85/lab0-c) 的作法
`merge_two` 是額外寫的函式，是為了方便 `q_sort` 和 `q_merge` 使用而特別獨立出來。
參考 [(2023): 第 1 週作業檢討](https://youtu.be/pB0YOqkNk4Y?t=6588) 後決定在 void 前面標註 static .
使用 `list_first_entry` 來取出兩個佇列的第一個節點來進行比較，之後再依據 `descend` 的值來決定要插入較大或是較小的節點 。
```c
if ((descend && strcmp(l->value, r->value) > 0) ||
(!descend && strcmp(l->value, r->value) <= 0))
list_move_tail(&l->list, &temp);
else
list_move_tail(&r->list, &temp);
```
在老師的提點之下才發現自己其實根本分不清出 Top-down 和 Bottom-Up 於是便去閱讀 [Linux 核心排序實作的演進](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e)
使用 Top-down (recursive) merge sort 來實作 `q_sort `
實作內容如下：
利用 `list_for_each_safe` 走訪每一個節點
* 若目前節點為佇列的**中間**節點：
1. 利用 `list_cut_position` 將佇列分成兩段並分別放入 `q_sort` 進行排序
2. 利用 `merge_two` 合併已排序好的佇列
3. 離開迴圈
* 反之則更新反向走訪的指標 `rev_node` 以利後續判斷是否走訪到中間節點
```c
LIST_HEAD(R);
list_for_each_safe (node, safe, head) {
if ((node == rev_node || node->next == rev_node) && rev_node != head) {
list_cut_position(&R, node, head->prev);
q_sort(&R, descend);
q_sort(head, descend);
merge_two(head, &R, descend);
break;
}
rev_node = rev_node->prev;
}
```
:::danger
你如何確認目前的測試已涵蓋排序演算法的最差狀況？
:::
**確認目前的測試已涵蓋排序演算法的最差狀況**
>參考 [排序測試和效能評估機制](https://hackmd.io/@sysprog/Hy5hmaKBh)
對於 Top-down (recursive) merge sort 而言，不管在最佳、平均、最差的情況下，時間複雜度皆為 $O(n\log{n})$ ，差別在於節點間比較的次數，假設有兩個子佇列 $Q_1, Q_2$ ，長度分別為 $n_1, n_2$ ，最差情況下的比較次數 $C_{n1,n2}$ 為 $n_1+n_2-1$ 次，即每一個節點皆被比較過。
$min(n_1,n_2)\leq C_{n1,n2} \leq n_1+n_2-1$
1. 怎樣的測試資料是最差情況呢？
> 參考 [When Will the Worst Case of Merge Sort Occur?](https://www.baeldung.com/cs/merge-sort-time-complexity) 、[2024-03-{19,21} 討論簡記](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ)
只要比較次數少於 $n_1+n_2-1$ 次，就不是最差的情況，例如在合併 $Q_1, Q_2$ 的過程中，其中一個子佇列提早被比較完，這樣比較次數就會少於 $n_1+n_2-1$ 次。
因此最差情況的測試資料要確保在每次合併的過程中都會比較到每一個節點。
2. 新增 `q_worst_case`
> [commit 16f69b2](https://github.com/devarajabc/lab0-c/commit/16f69b2a5af1ab778850c6c37f5c3242fcb3e507)
先準備一個嚴格遞增的佇列，再使用遞迴的方式將佇列拆成奇數項、偶數項兩個子佇列，直至子佇列只剩一個節點，最後再將所有節點串連起來。
因為在合併兩個交錯排例的子佇列如 $[1,3,5,7], [2,4,6,8]$ 時就能避免其中一個子佇列提早被比較完的情況，然而為了確保每一次的合併都能達到最差的情況，所以要再將 $[1,3,5,7]$ 拆成 $[1,5], [3,7]$ 而 $[1,5]$ 又要再拆成 $[5], [1]$ $...........$
流程如下：
```graphviz
digraph list {
l1 [shape=rect label="1,2,3,4,5,6,7,8"];
l21 [shape=rect label = "1,3,5,7" ];
l22 [shape=rect label = "2,4,6,8" ];
l31 [shape=rect label = "1,5" ];
l32 [shape=rect label = "3,7" ];
l33 [shape=rect label = "2,6" ];
l34 [shape=rect label = "4,8" ];
l41 [shape=rect label = "5" ];
l42 [shape=rect label = "1" ];
l43 [shape=rect label = "7" ];
l44 [shape=rect label = "3" ];
l45 [shape=rect label = "6" ];
l46 [shape=rect label = "2" ];
l47 [shape=rect label = "8" ];
l48 [shape=rect label = "4" ];
lf [shape=rect label="5,1,7,3,6,2,8,4"];
l1 -> { l21 l22 };
l21 -> { l31 l32 };
l22 -> { l33 l34 };
l31 -> { l41 l42 };
l32 -> { l43 l44 };
l33 -> { l45 l46 };
l34 -> { l47 l48 };
l41 -> lf;
l42 -> lf;
l43 -> lf;
l44 -> lf;
l45 -> lf;
l46 -> lf;
l47 -> lf;
l48 -> lf;
}
```
我很好奇 $[5,1,7,3,6,2,8,4]$ 和 $[1,5,3,7,2,6,4,8]$ 會不會造成比較次數的不同
（在最差環境下的表現數據：比較次數、時間、cache miss ratio）
（要確認是否符為合穩定排序，要有數學證明）
（穩定排序的檢測？）
```shell
Queue size = 8
l = [a b c d e f g i]
cmd> worst_case
l = [a e c g b f d i]
cmd> list_sort
Comparisons: 17
l = [a b c d e f g i]
Freeing queue
```
**確認目前的排序是否為穩定排序**
>參考 [yenslife](https://hackmd.io/@yenslife/linux2024-homework1#q_sort) 、[wiki](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability)
穩定排序的定義是：如果一個排序演算法是穩定的，當有兩個相等鍵值的紀錄 $R$ 和 $S$，且在原本的串列中 $R$ 出現在 $S$ 之前，在排序過的串列中 $R$ 也將會是在 $S$ 之前。
所以我使用常數列來判斷 `q_sort` 是否為穩定排序，若出現任何排列的動作則 `q_sort` 為不穩頂排序。
仔細檢查之後才發現原本的程式碼錯誤百出，至於為什麼能通過測資還待分析，以下是對程式碼做出的修改
### `q_merge`
:::danger
失敗的過程可能也值得反覆推敲。
:::
>參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-86-Partition-List) :
>naive
直觀地用第一條串列接上剩下的串列，這樣會導致 lists[0] 愈來愈長，立即會遇到的問題是：多數的情況下合併速度會愈來愈慢。
利用 list_first_entry 來找到第一個節點 (queue_context_t) 並用變數 `l` 來記錄其指標，而 `r` 則用來記錄「下一個」節點的指標。
在 while loop 中，利用 `merge_two` 將剩餘的節點都合併到 `l` 上，合併過後的節點會被移到尾端，若再次造訪則會跳出迴圈 ，這部分是參考自 [alanjian85](https://github.com/alanjian85/lab0-c) 的作法，但與 [alanjian85](https://github.com/alanjian85/lab0-c) 的做法不同之處在於是我利用 `list_empty(r->q)` 來判斷是否造訪過該節點。
:::danger
改進你的漢語表達。
:::
```c
while (!list_empty(r->q)) {
merge_two(l->q, r->q, descend);
list_move_tail(&r->chain, head);
r = list_entry(l->chain.next, queue_contex_t, chain);
}
```
>參考 [Queue-Mergesort](https://www.sciencedirect.com/science/article/abs/pii/002001909390088Q?via%3Dihub)
>Queue-Mergesort
---
## 研讀論文 [〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf)
> 參考 [jimmylu0303](https://hackmd.io/@jimmylu0303/linux2024-homework1#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87-%E3%80%88Dude-is-my-code-constant-time%E3%80%89)
作者在 **Introduction** 中介紹了時間攻擊（[Timing attack](https://en.wikipedia.org/wiki/Timing_attack)）與其危害，在時間攻擊中，攻擊者會通過分析程式的執行時間差異來推斷出加密過程中使用的密鑰或者其他敏感資訊。
為了防範時間攻擊，工程師會設法讓特定程式的執行時間始終保持恆定 （Constant time），避免因輸入不同而造成執行時間差異，使攻擊者法從該程式的執行時間中獲得有用的資訊。
:::warning
指出之前手法的缺陷。
:::
然而檢測特定程式是否能維持固定的執行時間絕非易事，作者指出了現行檢測方法的缺點並提出了一套新的測量工具 :
> This manual approach can be very time consuming already for moderately sized code bases, and should be repeated for every exact combination of compiler flags being used.
有別於以往的測量方式，作者借用旁路攻擊（[Side-channel attack](https://en.wikipedia.org/wiki/Side-channel_attack)）的概念來測量程式的執行時間，並利用統計學方法對其進行分析，以便判斷該程式是否能在不同的輸入下依然保持恆定的執行時間。
接著作者在 **OUR APPROACH: TIMING LEAKAGE DETECTION** 中說明了**dudect** 運作的流程：
1. 測量程式在兩筆不同測試項目下的執行時間
2. 利用統計方法分析該程式是否有維持恆定的執行時間
:::warning
討論「恆定的執行時間」一詞是否精準。
:::
以下是對流程的細節說明：
##### 1.測量執行時間（Repeatedly measure exeution time）
* 使用兩筆不同類型（class）的測試資料，分別是固定值（fix）和隨機值（random），固定值為一常數，可以用來測試某些特殊臨界情況。
* 利用現代 CPU 提供的 cycle counters 來作為測量依據
*
:::danger
不懂就說不懂，沒有「不太懂」這回事。
:::
第三點<s>看不懂</s> 為何可以如此操作
>To minimize the effect
of environmental changes in the results, each measurement
corresponds to a randomly chosen class.1 The class assignment
and input preparation tasks are performed prior to the
measurement phase.
##### 2.資料預處理（Apply post-processing）
* 為了避免程式執行的時候受到作業系統本身或其他外在因素干擾而造成測量錯誤，因此在開始統計前會去掉一些極端值
* High-order preprocessing （我不知道這是幹嘛的）
##### 3.進行統計分析（Apply statistical test）
>參考 [2024-03-{19,21} 討論簡記
](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ)
```graphviz
digraph ele_list {
//rankdir=LR
node[shape=record]
head [label="計算 test statistic ", style="bold"]
node4 [label="決定自由度（degrees of freedom）", style="bold"]
node3 [label="選擇顯著水準 (α)", style="bold"]
node7 [label="決定是否拒絕虛無假說", style="bold"]
head->node4
node4->node3
node3->node7
}
```
## 改進 dudect 實作
>參考 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h), [marvin0102](https://hackmd.io/@MpDQFnRmRl2viw8YhUt5Ww/r10UUW83p#percentile-implement), [cheezad](https://hackmd.io/@cheezad/linux2024-homework1#dudect-%E8%AB%96%E6%96%87%E8%88%87%E7%A8%8B%E5%BC%8F%E5%B8%B8%E6%95%B8%E6%99%82%E9%96%93%E7%9A%84%E9%81%94%E6%88%90), [HotMercury](https://github.com/HotMercury/lab0-c)
發現 lab0-c 中沒有做到 Apply post-processing ，因此在從 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中複製了三個函式到 fixture.c 裡面，分別是：
* `compare_int64`: 比較兩個 64 位元整數的大小。它是給快速排序函式 (qsort) 使用的，以決定排序順序。
* `percentile`: 計算並返回一個已排序陣列中指定百分位數的值。例如，如果你想找到中位數（即 50% 百分位數），該函式可找到陣列中恰好位於中間位置的值。它首先計算出陣列中對應於所需百分位數的索引位置，然後返回該位置的值。
* `prepare_percentiles`: 對執行時間進行排序，然後計算一系列特定的百分位數。
使用 qsort 進行排序。
利用特殊的公式計算計算每一個元素的百分位數值
1 - (pow(0.5, 10 * (double) (i + 1) / (double) N_MEASURES)), N_MEASURES);
:::danger
為何如此？
:::
（我不知道）
接著將每個元素替換成對應的百分位數值。
最後記得要在 `fixture.c` 裡面的 `doit` 中加入 `prepare_percentiles(exec_times)`
（為什麼？不知道）
---
## 亂數研究及 shuffle 實作
### 亂數研究
>參考 [亂數](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d)
#### 如何確認亂數夠亂？
### q_shuffle
>參考 [alanjian85](https://hackmd.io/@alanjian85/lab0-2023#%E5%AF%A6%E4%BD%9C-shuffle-%E5%91%BD%E4%BB%A4) 如何在 qtest 中新增 shuffle 實作、 參考 [HotMercury](https://github.com/HotMercury/lab0-c) 如何使用 extern 、[2024-03-19 討論簡記](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ?both)、[Pearson's chi-squared test
](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test)
在 queue.c 中新增 `q_shuffle`：
>[commit1030b5](https://github.com/devarajabc/lab0-c/commit/1030b5d4f20d6dce5d6692a51837121a668a6d02)
利用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm)演算法來實作洗牌（shuffle）
為什麼要用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) ？
:::danger
注意空白字元。
:::
### 實測與成果
使用 [Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 來驗證 `q_shuffle`
(為何不使用 [t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) )?
+ $H_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
+ $H_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同
:::danger
列出 `diff -u` 的結果，不用張貼完整程式碼。
:::
## 比較亂數產生器
>觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 qtest 切換不同的 PRNG 的實作
參考 [由大數法則理解訊息熵的數學意義](https://hackmd.io/@8dSak6oVTweMeAe9fXWCPA/ryoegPgw_) 、[yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-lab0#Linux-%E6%A0%B8%E5%BF%83-Linked-List-%E6%8E%92%E5%BA%8F%E7%A0%94%E7%A9%B6)
## 解釋 select 系統呼叫在本程式的使用方式
---
## 針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式
> 參考 [Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort#Timsort-%E5%B0%8D-Mergesort-%E7%9A%84%E6%94%B9%E5%96%84)、[Wikipedia: Timsort](https://en.wikipedia.org/wiki/Timsort)
:::danger
使用明確清晰且流暢的漢語表達。
:::
以下是我實作的幾個版本：
1. `Timsort_naive` [commit 103640d](https://github.com/devarajabc/lab0-c/commit/103640de08779abba3021449f98ccf5e88c9b83d)
> 參考 [第一週測驗](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) 中使用的版本 、 [yanjiew1](https://github.com/yanjiew1/lab0-c/blob/master/ksort.c) 、[HotMercury](https://hackmd.io/@NeedSleep/linux2024-homework1#%E6%95%B4%E5%90%88-timsort-mergesort-libsort)、[jimmylu890303](https://github.com/jimmylu890303/lab0-c/commit/45a04b7b43f3c6b6e06a17970a55b7ad4b49f201)
此版本使用逐對合併(one-pair-at-a-time) 而非 [Galloping mode](https://en.wikipedia.org/wiki/Timsort#Galloping_mode_during_merge) 且缺乏計算 minrun (最小運行長度)的機制。
此外我看不懂函式指標 `list_cmp_func_t cmp` 的用法，在
閱讀 [Function pointer](https://en.wikipedia.org/wiki/Function_pointer) 後才知道其正確的用法。
:::warning
參照 C 語言規格書。
:::
參考 [jimmylu890303](https://github.com/jimmylu890303/lab0-c/commit/45a04b7b43f3c6b6e06a17970a55b7ad4b49f201) 將 `q_tim_sort` 加入 `qtest` ，並使用 [jimmylu890303](https://github.com/jimmylu890303/lab0-c/commit/5412ca760c9828229ba56d007d2a073966d336a3) 的測資來測試 `q_tim_sort`
```shell
$ ./qtest < traces/trace-test_tim_sort.cmd
l = []
l = [jlojw ibobf wojsmiifc bqxdfxw tcqgbze ncfuuzqy ijvzbmtpk ddmwn ggkhinkmv lvvakzhbm zazpevqtq jnxhg vxclmor oaetwm jhrglvn qessrobxy ffdletlf oxzmevgpx yrlejf mxxuxk ftqpbyyxo lsstizr btxxe yfvjr nljrxoag aupsot rmgvx jxrwpyg mzubdze hoypriitx ... ]
l = [aaaatuqw aaabcbj aaabxaxkk aaabzdv aaadre aaadt aaadxb aaaed aaafbdz aaafen aaafofg aaafxxnff aaagdmf aaagfy aaagtibpi aaaguse aaahqwm aaahxzvmi aaaioytq aaaiuyo aaaiw aaaiwpc aaajpqey aaajscy aaakjhvx aaakuqts aaamjce aaanasm aaantzl aaanx ... ]
Delta time = 1.315
Freeing queue
```
不過在使用 valgrind cachegrind 分析 cache miss ratio 的時候會遇到錯誤，原因未知
```shell
valgrind --tool=cachegrind ./qtest -f traces/trace-test_tim_sort.cmd
--293068-- warning: L3 cache found, using its data for the LL simulation.
l = []
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of uzwwcvas failed (1 failures total)
l = [rdsrgsl ... ]
l = [aaaaob aaacxjy aaafv aaaigh aaammvz aaamwqgk aaaxieid aabbitjf aabbzzkd aabie aabjj aaboposi aabtcqhd aabxf aabxw aacajv aaccaz aacpcfed aacpgxxo aacpwe aacqnk aacqt aacvstpm aaczayj aaddhmo aadji aadqu aadshzupc aaduij aaduzhn ... ]
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated
```
:::danger
幻滅是成長的開始
:::
:::danger
使用明確清晰且流暢的漢語表達。
:::
## 分析 [lib/list_sort.c](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09)
> 參考 [Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh) 、 [csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework1#%E6%8E%A2%E8%A8%8E-liblib_sortc) 、[kdnvt](https://hackmd.io/byNYeoGvQv-a9TNDc2CKFQ?view#comparison-%E6%AC%A1%E6%95%B8) 、 [ blueskyson](https://hackmd.io/0oQNR91SSRKprDpLbObf6w?view#%E6%AF%94%E8%BC%83%E8%87%AA%E5%B7%B1%E7%9A%84-sort-%E8%88%87-list_sort-%E6%95%88%E8%83%BD%E8%90%BD%E5%B7%AE) 、 [yanjiew1 ](https://hackmd.io/@yanjiew/linux2023q1-lab0#Linux-%E6%A0%B8%E5%BF%83-Linked-List-%E6%8E%92%E5%BA%8F%E7%A0%94%E7%A9%B6) 、[bakudr18](https://hackmd.io/@bakudr18/BkvLMLkeq#Linux-Kernel-list_sort-%E5%AF%A6%E4%BD%9C)
（原本的版本有什麼問題？為何需要修改？怎麼修改？）
（merge sort vs. quicksort locality）
原先的版本已經用 DFS 來讓比較次數 $n*log_2(n) - K*n + O(1)$ 的領導係數降到理論的極限值（理由做法待補），因此作者著重在一次項的改進。
作者確保兩個子佇列在最糟情況下合併時的長度比為 $2:1$ ，因為當合併兩個**大小差異非常大**的子佇列的時候比較次數會大大上升（理由、數據待補充）
改進後的效果相當顯著：
>This achieves the same average K=1.207 as queue-mergesort, which is 0.2*n better then bottom-up, and only 0.04*n behind top-down mergesort.
### 引入至 lab0-c
>[commit 83a8434](https://github.com/devarajabc/lab0-c/commit/83a84347c7de996a5c445791bf4fa4b32fc79ad8)
u8 是啥？
unlikely 是啥 ？
```shell
struct list_head *head, **tail = &head;
^
Fail to pass static analysis.
```
### 該設計對應的排序測試實驗方案
> 參考 [用效能分析工具比較 list_sort.c 及自己實作的排序](https://hackmd.io/byNYeoGvQv-a9TNDc2CKFQ?view#comparison-%E6%AC%A1%E6%95%B8)、[排序測試和效能評估機制](https://hackmd.io/@sysprog/Hy5hmaKBh)、[listsort 的說明文件](https://github.com/python/cpython/blob/main/Objects/listsort.txt)
參考 [fennecJ](https://hackmd.io/@fennecJ/linux2024-q1q2#%E5%8F%83%E8%80%83-cpython-%E6%BA%96%E5%82%99%E8%B3%87%E6%96%99%E9%9B%86%E9%80%B2%E8%A1%8C%E5%AF%A6%E9%A9%97) 所使用的方法：
在 `q_test` 中新增 `test_config` 來將創造測資
將測試以下幾種情況：
1. random data
1. descending data
1. ascending data
1. ascending, then 3 random exchanges
1. ascending, then 10 random at the end
1. ascending, then randomly replace 1% of elements with random values
1. many duplicates
1. all equal
1. worst case scenario
---
## 整合 ttt
### 研讀Linux 核心的浮點數運算
### 研讀(MCTS) 演算法
### 針對 ttt 命令的「電腦 vs. 電腦」的對弈模式，引入若干 coroutine
### 嘗試引入其他快速的 PRNG 實作並比較 MCTS 實作獲得的效益
### 運用定點數來統計不同 AI 實作機制對系統負載的使用率
### 改寫既有的 `shannon_entropy.c` 和 `log2_lshift16.h`
Sign in with Wallet
