# 2024q1 Homework1 (lab0)
contributed by < `yutingshih` >
### Reviewed by `164253`
佇列相關函式實作複雜度都很好
除了 `list_find_mid` 的快慢指針可改為兩個指針從頭尾向中間靠近
其他部分目前沒見過其他可改進於此的實作
q_sort 效能測試部分採用我先前給出的第二種交錯方法
後來我有再更新第四種，新的構造法複雜度介於 $n$ 到 $n+\log_2n$ 之間
傳入任何一種最差排序，便可模擬原先的 dfs 過程
並在 $n$ 到 $n+\log_2n$ 間給出下一個最差排序
初始狀態也可以 $n+\log_2n$ 得出
能夠得到更大量的最差情況
## 開發環境
```shell
$ uname -a
Linux east 6.5.0-26-generic #26~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Tue Mar 12 10:22:43 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-10500 CPU @ 3.10GHz
CPU family: 6
Model: 165
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 3
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 6199.99
```
## 專案架構
`lab0-c` 專案中有數個原始碼檔案，以下說明每個檔案的用途，以方便後續實作與改進。首先用以下指令篩選出 C 語言的原始檔及標頭檔：
```shell
ls -l *[ch]
```
- `console.[ch]`：提供簡單的命令列介面 (command line interface)。若未來需要在 `qtest` 新增功能，可以使用 `console.h` 中的 API 在 `qtest.c` 的 `console_init` 函式中註冊新的命令或參數
- `harness.[ch]`：實作用於常見記憶體配置相關錯誤的保護機制
- `linenoise.[ch]`：第三方的 line-editing 函式庫，用於互動式的命令列使用者介面，可以讓 `qtest` 程式具有自動補全 (auto complete) 的功能，與網頁伺服器共用時會有問題需要修正
- `list.h`：Linux 風格的雙向環狀鏈結串列，包含介面與實作
- `log2_lshift16.h`：以查表方式實作的 `log2`，避免了浮點數操作，但其實作方式難以維護，有改進空間
- `qtest.c`：具有命令列使用者介面的測試程式
- `queue.[ch]`：利用 `list.h` 定義的雙向鏈結串列 API 實現指定的佇列操作實作
- `random.[ch]`：
- `report.[ch]`：用於輸出程式執行的資訊，分成不同的等級，包含 warning、error、fatal error 及 message
- `shannon_entropy.c`：計算 Shannon entropy 的函式
- `web.[ch]`：網頁伺服器，與 linenoise 共用時會有問題需要修正
## 佇列操作實作
### `q_new`
使用 `malloc` 函式配置記憶體給新建立的 `struct list_head`，並用 Linux 核心風格的 List API 所提供的函式 `INIT_LIST_HEAD` 將 `head` 初始化 (把 `prev` 和 `next` 設為自身) 後回傳。在對新建立的節點初始化前，先檢查是否有成功配置記憶體，若失敗，則提早回傳 `NULL`。
```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;
}
```
根據 [ISO/IEC 9899](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) (簡稱 C99) 規格書 [7.20.3] 關於記憶體配置函數 `calloc`、`malloc` 及 `realloc` 的行為描述：
> If the space cannot be allocated, a null pointer is
returned.
可知 `malloc` 配置失敗時，`head` 的值為 `NULL`，因此們可以改用更加簡潔的寫法來合併配置成功與失敗兩種狀況的 return 述句。
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
### `q_free`
`q_free` 釋放所有在佇列中使用到的記憶體，包含每個節點中內嵌的 `list_head` 結構體及字串 `value`，因此需要走訪每個節點，而 `list.h` 中有提供了一個巨集 `list_for_each_safe`，可以用兩個 `list_head` 指標來進行走訪，一個用來指向目前要刪除的節點，另一個指向目前還「安全」的節點，正好符合我們的需求
```c
/**
* list_for_each_safe - Iterate over list nodes and allow deletions
* @node: list_head pointer used as iterator
* @safe: list_head pointer used to store info for next entry in list
* @head: pointer to the head of the list
*
* The current node (iterator) is allowed to be removed from the list. Any
* other modifications to the the list will cause undefined behavior.
*/
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
因此我的 `q_free` 實作如下：利用 `list_for_each_safe` 巨集從 `head` 開始循序走訪每個 list 節點，再用 `list_entry` 巨集取得包含 `list_head` 的資料結構的起始位址，再依序釋放 `element_t` 結構體中手動配置的記憶體 (先釋放 `value` 字串再釋放 `elem` 物件本身)，為了避免釋放後的記憶體被存取所帶來的安全性議題，當記憶體空間被釋放後就馬上將指向該空間的指標歸零。
由於`list_for_each_safe` 是從標頭節點 `head` 的下個節點開始走訪，因此走訪結束後，還要記得釋放 `head` 指向的記憶體，並將 `head` 指標歸零。
```c
void q_free(struct list_head *head) {
if (!head)
return;
struct list_head *node, *safe;
list_for_each_safe(node, safe, head) {
element_t *elem = list_entry(node, element_t, list);
if (elem->value)
free(elem->value), elem->value = NULL;
free(elem), elem = NULL;
}
free(head), head = NULL;
}
```
此外，[C99](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 規格書 [7.20.3.2] 提到：
> The `free` function causes the space pointed to by `ptr` to be deallocated, that is, made available for further allocation. If `ptr` is a null pointer, no action occurs.
對一個 NULL pointer 進行記憶體釋放將不會有任何事發生，因此在釋放記憶體時不需要檢查指標是否指向 `NULL`。
```c
void q_free(struct list_head *head) {
if (!head)
return;
element_t *entry, *safe;
list_for_each_entry_safe(entry, safe, head, list) {
free(entry->value), entry->value = NULL;
free(entry), entry = NULL;
}
free(head), head = NULL;
}
```
### `q_insert_head` / `q_insert_tail`
### `q_remove_head` / `q_remove_tail`
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *entry = list_entry(head->next, element_t, list);
list_del_init(head->next);
if (sp && bufsize) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return entry;
}
```
第 6 行可以改用 `list.h` 中提供的 `list_first_entry` 和 `list_last_entry` 巨集
```c
/**
* list_first_entry() - Get first entry of the list
* @head: pointer to the head of the list
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*
* Return: @type pointer of first entry in list
*/
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
/**
* list_last_entry() - Get last entry of the list
* @head: pointer to the head of the list
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*
* Return: @type pointer of last entry in list
*/
#define list_last_entry(head, type, member) \
list_entry((head)->prev, type, member)
```
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *entry = list_first_entry(head, element_t, list);
list_del_init(head->next);
if (sp && bufsize) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return entry;
}
```
### `q_swap`
`list_move(node, head)`：將 `node` 移動到 `head` 的**後面**，成為鏈結串列的第一個節點
`list_move_tail(node, head)`：將 `node` 移動到 `head` 的**前面**，成為鏈結串列的最後一個節點
```c
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 *node;
list_for_each(node, head) {
if (node->next == head)
break;
list_move_tail(node->next, node);
}
}
```
### `q_reverse` / `q_reverseK`
`q_reverse` 將整個鏈結串列做反轉，作法是從頭到尾依序將每個節點移動到 `head` 的後面 (`head->next`) 成為串列的首個節點，即可完成反轉的操作
```graphviz
digraph {
rankdir=LR
node[shape=box]
curr[shape=none]
safe[shape=none]
node0[label="..."]
node4[label="..."]
curr->node1
safe->node2
subgraph cluster {
color=none
head->node0->node1->node2->node3->node4
}
}
```
```graphviz
digraph {
rankdir=LR
node[shape=box]
curr[shape=none]
safe[shape=none]
node0[label="..."]
node4[label="..."]
curr->node1
safe->node2
subgraph cluster {
color=none
head->node1->node0->node2->node3->node4
}
}
```
```graphviz
digraph {
rankdir=LR
node[shape=box]
curr[shape=none]
safe[shape=none]
node0[label="..."]
node4[label="..."]
curr->node2
safe->node3
subgraph cluster {
color=none
head->node1->node0->node2->node3->node4
}
}
```
`q_reverseK` 則是每 K 個一組將串列做反轉 (最後面不足 K 個時也是自成一組)，作法是利用 `list.h` 中的 `list_cut_position`，每 K 個一組切成獨立的串列，各自反轉後再依序連接起來。
```graphviz
digraph {
rankdir=LR
node[shape=box]
head
node1[label="node 1"]
node2[label="..."]
node3[label="node k"]
node4[label="node k+1"]
node5[label="..."]
safe[shape=none]
curr[shape=none]
curr->node1
safe->node2
subgraph cluster {
color=none
head->node1
subgraph cluster2 {
color=block
node1->node2->node3
}
node3->node4
subgraph cluster3 {
color=block
node4->node5
}
}
}
```
```graphviz
digraph {
rankdir=LR
node[shape=box]
head
node1[label="node 1"]
node2[label="..."]
node3[label="node k"]
node4[label="node k+1"]
node5[label="..."]
safe[shape=none]
curr[shape=none]
curr->node3
safe->node4
subgraph cluster {
color=none
head->node1
subgraph cluster2 {
color=block
node1->node2->node3
}
node3->node4
subgraph cluster3 {
color=block
node4->node5
}
}
}
```
```graphviz
digraph {
rankdir=LR
node[shape=box]
head
node1[label="node 1"]
node2[label="..."]
node3[label="node k"]
node4[label="node k+1"]
node5[label="..."]
safe[shape=none]
curr[shape=none]
curr->node3
safe->node4
subgraph cluster {
color=none
head->node3
subgraph cluster2 {
color=block
node3->node2->node1
}
node1->node4
subgraph cluster3 {
color=block
node4->node5
}
}
}
```
```graphviz
digraph {
rankdir=LR
node[shape=box]
head
node1[label="node 1"]
node2[label="..."]
node3[label="node k"]
node4[label="node k+1"]
node5[label="..."]
safe[shape=none]
curr[shape=none]
curr->node4
safe->node5
subgraph cluster {
color=none
head->node3
subgraph cluster2 {
color=block
node3->node2->node1
}
node1->node4
subgraph cluster3 {
color=block
node4->node5
}
}
}
```
### `q_sort`
參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C) 實作遞迴版本的合併排序法，先使用 `list_find_mid` 和 `list_cut_position` 將串列分割成 `head` 和 `left` 兩半 (第 7、8 行)，分別排序兩者 (第 9、10 行)，最後用 `list_merge` 合併至 `head` (第 11 行)。
若串列中的實際帶有資料的節點數量是奇數，則 `mid` 會位於正中央的的節點，若節點數量節點數量為偶數，則 `mid` 會偏向左邊。這兩種狀況 `mid` 指向的節點都會被移動到 `left`。也就是說當節點數量為是奇數，切割後 `left` 會比 `head` 多一個節點，偶數時則兩條串列擁有的節點數量一樣。
```c=
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head left, *mid = list_find_mid(head);
list_cut_position(&left, head, mid);
q_sort(&left, descend);
q_sort(head, descend);
list_merge(head, &left, descend);
}
```
其中 `list_merge` 函式利用 `list.h` 提供的 API 進行實作，功能是將兩條已排序好的的串列合併成一條排序好的串列。排序完成後 `l2` 所有的節點將會被移至 `l1`，而 `l2` 會變成一條空的串列 (會剩下 head 節點，而非整個串列被刪除)。
使用 `cur` 在 `l1` 上進行走訪，在迭代過程中，`cur` 之前的所有節點 (不含 `cur` 本身) 代表已經合併好的節點，`cur` 之後 (包含 `cur` 本身) 則代表 `l1` 上尚未與 `l2` 合併的節點。程式碼實作如下：
```c=
/* Merge list l2 into list l1 in ascending/descending order */
void list_merge(struct list_head *l1, struct list_head *l2, bool descend)
{
if (list_empty(l1)) {
list_splice_init(l2, l1);
return;
}
element_t *cur;
list_for_each_entry(cur, l1, list) {
while (true) {
if (list_empty(l2))
return;
element_t *tmp = list_first_entry(l2, element_t, list);
if (elem_compare(cur, tmp, descend) > 0)
list_move_tail(tmp, cur);
}
}
}
```
上述程式碼實現合併的關鍵在 15~17 行：若發現 `l2` 的首個節點 (`tmp`) 應該排在 `cur` 之前，則使用 `list_move_tail` 將 `tmp` 移動到 `cur` 之前，反之則更新 `cur` 繼續下一輪的比較。
而 `cur` 和 `tmp` 兩個節點的相對順序則藉由 `elem_compare` 來確定，其回傳值為一個有號整數，負值代表 `cur` 應該排在 `tmp` 的前面，正值則代表 `cur` 應該排在 `tmp` 的後面，0 則代表 `cur` 和 `tmp` 有相同的「順序」，何者在前則由使用者決定。
這樣的定義對使用者來說更加方便，不需要再考慮 `descend` 的值來決定順序，並且與 C 語言函式庫中的 `strcmp` 行為一致，根據 Linux manual，[strcmp](https://man7.org/linux/man-pages/man3/strcmp.3.html) 的回傳值代表的三種狀況：
> - `0`, if the `s1` and `s2` are equal;
> - a negative value if `s1` is less than `s2`;
> - a positive value if `s1` is greater than `s2`.
```c
/**
* elem_compare - Compare two elements in ascending/descending order
* @a: first element to be compared
* @b: second element to be compared
* @descend: whether or not to sort in descending order
*
* Return: negative number if @a is former than @b
* positive number if @a is latter than @b
* zero if @a is equal to @b
*/
int elem_compare(const element_t *a, const element_t *b, bool descend)
{
int res = strcmp(a->value, b->value);
return descend ? -res : res;
}
```
:::danger
如何確保目前的測試已涵蓋排序演算法的最差狀況？
- [name=yutingshih] 下面新增[效能分析](#效能分析)與[效能測試](#效能測試)的段落來探討
:::
#### 效能分析
上述 `list_sort` 以 top-down merge sort 的方式進行實作，參考 `164253` 同學於 [2024-03-{19,21} 討論簡記](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ#164253) 的分析，對於 merge sort 而言，最佳狀況的輸入資料是已經排序好的串列 (不論是正向或反向)，最差狀況則是交錯排列。
假設串列中有 $n$ 個具有資料的節點 (不包含 head)，則使用 merge sort 排列這 $n$ 個節點需要先將串列切分成兩條子串列，分別擁有 $\lceil n/2 \rceil$ 個節點和 $\lfloor n/2 \rfloor$ 個節點，兩者各自排序好後再將兩者合併，總共需要的比較次數為 $T(n)$， $T(1) = T(0) = 0$。
最佳狀況是串列已經是排序好的狀態，合併時僅需走訪完其中一條子串列，即可完成排序：
$$
T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \lfloor n/2 \rfloor
$$
最差狀況則是串列依序交錯位於兩條子串列當中，合併時需要交錯走訪兩條子串列才能完成排序：
$$
\begin{align}
T(n) &= T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + (\lceil n/2 \rceil + \lfloor n/2 \rfloor - 1) \\
&= T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + (n - 1)
\end{align}
$$
假設 $n$ 是 2 的非負整數次冪 ($n = 2^m \text{, where } m = \lg(n) \in \mathbb{N} \cup \{0\}$)，則最佳情況的比較次數為：
$$
\begin{align}
T(n) &= 2T(\frac{n}{2}) + \frac{n}{2} = 4T(\frac{n}{4}) + 2\frac{n}{2} = \text{ ... } \\
&= 2^{m}T(\frac{n}{2^m}) + m\frac{n}{2} \\
&= \frac{1}{2}nm \\
&= \frac{1}{2}n\lg(n)
\end{align}
$$
最差情況的比較次數為：
$$
\begin{align}
T(n) &= 2T(\frac{n}{2}) + (n-1) = 4T(\frac{n}{4}) + (n-2) + (n-1) = \text{ ... } \\
&= 2^m\ T(\frac{n}{2^m}) + mn - \sum_{i=0}^{m-1}{2^i} \\
&= mn - (2^m - 1) \\
&= n\lg(n) - n + 1
\end{align}
$$
#### 效能測試
目前 `qtest` 中使用隨機的方式產生測試資料 (參考 [`trace-15-perf.cmd`](https://github.com/yutingshih/lab0-c/blob/master/traces/trace-15-perf.cmd))，若希望產生 merge sort 最差情況的測試資料，有以下方法 (參考 [2024-03-{19,21} 討論簡記](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ#164253))：
1. 將排序好的奇數項放一邊、偶數項放另一邊，再分別對兩個子串列進行一樣的操作
2. 前兩項放最大和最小，接著放次大和次小，以此類推，由於每一對中的兩項可以交換不影響比較的次數，因此長度 $n$ 的串列會有 $2^{n/2}$ 種排列
3. 上述第二種方法不同對之間的相對順序不影響排序的比較次數，因此可以再把不同對之間打亂，總共可以有 $2^{n/2} \times \frac{n}{2}!$ 種排列
<!-- 4. -->
上述方式都需要先產生出排序好的資料再把資料整理成最差狀況，但若要
1. 第一種方法，整理一層的時間複雜度為 $O(n)$，共有 $n\lg(n)$ 層，所以整體的時間複雜度為 $O(n\lg(n))$
2. 第二種方法只需整理一次，所以實驗複雜度為 $O(n)$
3. 第三種方法則是需要使用第二種方法後再做排列，時間複雜度也比第二種差
因此我決定使用第二種方法來產生交錯排列的資料。至於如何產生排序好的測試資料，手刻顯然不可行 (尤其需要如 [`trace-15-perf.cmd`](https://github.com/yutingshih/lab0-c/blob/master/traces/trace-15-perf.cmd) 上萬筆資料時)，先產生隨機資料再排序也行不通，因為 `sort` 本身就是待測項目，不能假設其實作是正確的，因此需要有另一個方法來產生遞增或遞減的測試資料，其作法可以參考 `Vincent550102` 同學在 [2024-03-{19,21} 討論簡記](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ?view#Vincent550102) 中貢獻的程式碼，其核心思想是透過累加先前產生的資料來確保新產生的隨機資料一定是遞增的。
我們可以使用同樣的想法來產生我們所需的測試資料，只是需要做一些修改
在 `qtest` 中插入資料的操作是藉由 `queue_insert` 函式來達成，其中定義了 `RAND` 關鍵字來讓使用者產生隨機字串，字串的長度上限為 `MAX_RANDSTR_LEN`，其值為 `10`，若輸入的字串為 `RAND` 則會呼叫 `fill_rand_string` 來產生隨機字串。
`fill_rand_string` 會先隨機決定字串長度，下限為 `MIN_RANDSTR_LEN = 5`，上限為 `MAX_RANDSTR_LEN = 10`，然後再呼叫 `randombytes`，`randombytes` 再透過系統呼叫依照指定的長度產生隨機字串填寫至 buffer 當中。
```c
if (!strcmp(inserts, "RAND")) {
need_rand = true;
inserts = randstr_buf;
}
```
## Linux 核心 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 效能分析與改進
[Linux 核心專題: 改進 `lib/list_sort.c`](https://hackmd.io/@sysprog/Hy5hmaKBh)
> This mergesort is as eager as possible while always performing at least 2:1 balanced merges. Given two pending sublists of size 2^k, they are merged to a size-2^(k+1) list as soon as we have 2^k following elements.
>
> Thus, it will avoid cache thrashing as long as 3*2^k elements can fit into the cache. Not quite as good as a fully-eager bottom-up mergesort, but it does use 0.2\*n fewer comparisons, so is faster in the common case that everything fits into L1.
## 參考資料
- [vax-r](https://hackmd.io/@vax-r/linux2024-homework1)
## 檢查清單
:::info
#### Homework 3 Code Review Checklist
- [ ] 確認分析 Linux 核心的 lib/list_sort.c 實作並評估其效益、針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式，該設計對應的排序測試實驗方案
- [ ] 閱讀指定的論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉及列於 `lib/list_sort.c` 修改紀錄 (即 commit [b5c56e](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09))中的 3 篇論文，闡述你的洞見，需要指出論文和現有 Linux 核心原始程式碼不同的地方，並予以討論，過程中該有對應的效能分析實驗。參考 CPython 的 [listsort 的說明文件](https://github.com/python/cpython/blob/main/Objects/listsort.txt)，對不同的資料分佈進行測試
- [x] 使用 git 命令的 `fetch` 操作取得最新的 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) 變更，並用 `rebase` 操作讓自己提交的 commit 得以在 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) 最新的變革之上
- [x] 確保符合指定的書寫規範，技術用語依循〈[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)〉，並針對授課教師的要求，以清晰、明確，和流暢的漢語書寫
- [ ] 針對現有 (及自己的) 程式碼，提出可重用程度更高、效能更好，且更安全的實作，過程中應有對應的實驗及分析。過程中，應查閱 C 語言規格書 (原文) [ISO/IEC 9899:1999 (C99)](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 及 [The Linux Programming Interface](https://man7.org/tlpi/)
- [ ] 研讀 [select(2)](https://man7.org/linux/man-pages/man2/select.2.html) 並探討 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) 如何偵測程式執行的超時、現有的網頁伺服器如何與 linenoise 並存，以及相關的 [signal(7)](https://man7.org/linux/man-pages/man7/signal.7.html) 使用方式
- [ ] 使用 valgrind, massif, gdb, perf 等課程提及的開發量化程式碼執行時期的資訊，應分析記憶體開銷、執行的指令 (instruction) 數量、cache 表現，和程式熱點 (hotspot)，並予以改進，過程中應有充分的實驗紀錄及討論
- [ ] 紀錄研讀第 1 到第 3 週課程教材的發現和疑惑，描述於上述開發紀錄，之後授課教師和其他學員會參與討論
- [ ] 詳閱〈[Teach Yourself Programming in Ten Years](https://norvig.com/21-days.html)〉，闡述你的認知和發現，並描述你在本課程發現可對應到該文章的觀點
:::
Sign in with Wallet
Connect another wallet