# 2023q1 Homework1 (lab0)
contributed by < `Korin777` >
## 開發環境
```shell
$ 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): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 14
Socket(s): 1
Stepping: 3
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 5376.00
Caches (sum of all):
L1d: 544 KiB (14 instances)
L1i: 704 KiB (14 instances)
L2: 11.5 MiB (8 instances)
L3: 24 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-19
```
## 開發過程
### `q_new`
```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;
}
```
建立一個新的佇列， 透過 `INIT_LIST_HEAD` 巨集來初始化佇列的 `head` ， 這個 `head` 不儲存值且在新增及移除時不會改變 ， 它用來對應到 `queue_contex_t` 的 `q`
### q_free
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *itr, *safe;
list_for_each_entry_safe (itr, safe, l, list) {
q_release_element(itr);
}
free(l);
}
```
* 透過 `list_for_each_entry_safe` 來走訪佇列並釋放 memory ， 最後在釋放 `head`
* `list_for_each_entry_safe` 透過 `save` pointer 來事先存好要被釋放的 element 的下一個 element ， 讓我們可以釋放記憶體
### q_insert_head
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = strdup(s);
if (!ele->value) {
free(ele);
return false;
}
list_add(&ele->list, head);
return true;
}
```
* 配置 `element_t` 及 `value` 的記憶體，透過 `list_add` 將它插入佇列的開頭(head->next)
### q_insert_tail
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = strdup(s);
if (!ele->value) {
free(ele);
return false;
}
list_add_tail(&ele->list, head);
return true;
}
```
* 配置 `element_t` 及 `value` 的記憶體，透過 `list_add_tail` 將它插入佇列的尾端(head->prev)
### q_remove_head
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_first_entry(head, element_t, list);
list_del(&ele->list);
if (sp) {
size_t n = strlen(ele->value) + 1;
n = bufsize < n ? bufsize : n;
strncpy(sp, ele->value, n);
sp[n - 1] = '\0';
}
return ele;
}
```
* 透過 `list_first_entry` 取出開頭的值並複製到 `sp` ，在透過 `list_del` 移除開頭
* `n` 用來決定要複製多少字元，並確保包含結束字元
### q_remove_tail
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_last_entry(head, element_t, list);
list_del(&ele->list);
if (sp) {
size_t n = strlen(ele->value) + 1;
n = bufsize < n ? bufsize : n;
strncpy(sp, ele->value, n);
sp[n - 1] = '\0';
}
return ele;
}
```
* 與 `q_remove_head` 類似 ， 這裡用 `list_last_entry` 取出尾端
### q_size
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
size_t n = 0;
struct list_head *itr;
list_for_each (itr, head)
++n;
return n;
}
```
* 走訪整個佇列來記錄經過的節點數
### q_descend
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
int count = 1;
struct list_head *itr = head->prev, *safe;
char *cur_max = list_entry(itr, element_t, list)->value;
for (itr = itr->prev, safe = itr->prev; itr != head;
itr = safe, safe = itr->prev) {
char *tmp = list_entry(itr, element_t, list)->value;
if (strcmp(tmp, cur_max) >= 0) {
cur_max = tmp;
++count;
} else {
list_del(itr);
q_release_element(list_entry(itr, element_t, list));
}
}
return count;
}
```
* 透過 prev 從佇列尾端開始走訪，記下當前的最大值並把後續遇到比它小的節點刪除，確保佇列是遞減的
### q_delete_mid
```c
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 *ahead = head->next, *back = head->prev;
while (ahead != back && ahead != back->prev) {
ahead = ahead->next;
back = back->prev;
}
list_del(ahead);
element_t *ele = list_entry(ahead, element_t, list);
q_release_element(ele);
return true;
}
```
* 透過一個從開頭一直往後走的 pointer 及從尾端一直往前走的 pointer 找出 middle node
*節點數為奇數時 ， middle節點就是相遇的 node
*節點數為偶數時 ， middle節點是在兩 pointer 相鄰時往前的 pointer
### q_merge
:::warning
避免張貼完整程式碼，你只要列出值得討論以及後續可改進的部分即可。
:notes: jserv
:::
```c
struct list_head *itr, *safe, *q_finalhead = list_entry(head->next,queue_contex_t,chain)->q;
struct list_head *tmp = q_finalhead->next;
while(head-> next != head->prev) {
if(tmp != q_finalhead) {
char *cur_min = list_entry(tmp,element_t,list)->value;
struct list_head *cur_q = q_finalhead, *cur_chain = NULL;
for (itr = head->next->next, safe = itr->next; itr != head;
itr = safe, safe = itr->next) {
struct list_head *q_head = list_entry(itr,queue_contex_t,chain)->q;
char *q_min = list_entry(q_head->next,element_t,list)->value;
if(strcmp(q_min,cur_min) < 0) {
cur_min = q_min;
cur_q = q_head;
cur_chain = itr;
}
}
if(q_finalhead != cur_q) {
list_move(cur_q->next,tmp);
if(list_empty(cur_q))
list_del(cur_chain);
}
else {
tmp = tmp->next;
}
}
else {
char *cur_min = NULL;
struct list_head *cur_q= NULL, *cur_chain = NULL;
for (itr = head->next->next, safe = itr->next; itr != head;
itr = safe, safe = itr->next) {
struct list_head *q_head = list_entry(itr,queue_contex_t,chain)->q;
char *q_min = list_entry(q_head->next,element_t,list)->value;
if(!cur_min) {
cur_min = q_min;
cur_q = q_head;
cur_chain = itr;
}
else if(strcmp(q_min,cur_min) < 0) {
cur_min = q_min;
cur_q = q_head;
cur_chain = itr;
}
}
list_move_tail(cur_q->next,tmp);
if(list_empty(cur_q)) {
list_del(cur_chain);
}
}
}
```
* 每次找出所有佇列中最小值 `cur_min` ，若 `cur_min` 不再第一個佇列中，就把它所在的節點移到 `tmp(第一個佇列尚未 merge 完成的 node)` 前面，否則將 `tmp` 移動到下一個節點。當 `tmp` 回到開頭表示第一個佇列的值都 merge 完成，之後 `cur_min` 所在的節點都改為移到 `tmp` 的尾端。
* 測試時發現會因為 `queue_contex_t` 的 size 沒有被改到而產生錯誤，沒被改到的原因為我將第一個以外的佇列都移除，所以 chain 的 size 剩 1，導致 `do_merge` 無法更新 merge 後的 size 也無法釋放被我移除的佇列的 head 記憶體
```c
struct list_head *q_merge =
list_entry(head->next, queue_contex_t, chain)->q;
for (struct list_head *c_itr = head->next->next; c_itr != head;
c_itr = c_itr->next) {
struct list_head *q_itr, *safe,
*q_other = list_entry(c_itr, queue_contex_t, chain)->q,
*node_merge = q_merge->next;
list_for_each_safe (q_itr, safe, q_other) {
while (node_merge != q_merge) {
if (strcmp(list_entry(q_itr, element_t, list)->value,
list_entry(node_merge, element_t, list)->value) <=
0) {
break;
} else
node_merge = node_merge->next;
}
list_add_tail(q_itr, node_merge);
}
INIT_LIST_HEAD(q_other);
}
```
* 改為將其他的佇列依序跟第一個佇列merge，由於其他佇列的節點最後都會被移除，所以直接用 `INIT_LIST_HEAD` 來讓佇列不再與任何節點連接
### q_sort
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || head->next == head->prev)
return;
struct list_head less, greater;
INIT_LIST_HEAD(&less);
INIT_LIST_HEAD(&greater);
struct list_head *pivot = head->next;
char *pivot_val = list_entry(pivot, element_t, list)->value;
list_del(pivot);
struct list_head *itr, *safe;
list_for_each_safe (itr, safe, head) {
if (strcmp(list_entry(itr, element_t, list)->value, pivot_val) <= 0)
list_add(itr, &less);
else
list_add(itr, &greater);
}
q_sort(&less);
q_sort(&greater);
INIT_LIST_HEAD(head);
list_add(pivot, head);
list_splice(&less, head);
list_splice_tail(&greater, head);
}
```
* 參考[第 1 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz1)實作的 quick sort ， 將佇列的第一個節點當作 pivot ， 其餘的節點分別放入 `greater`(value 比 pivot 大)、`less`(value 比 pivot 小) 這兩個佇列， 遞迴去繼續將這兩個佇列分割直到佇列不超過一個節點，最後將 `less` 、 `pivot` 、 `greater` 接起來的佇列就會是排序好的
* 這裡使用到 `list_for_each_safe` 是由於 `list_add` 會更換 `itr` 的下一個節點， 所以先將它儲存在 `safe` 。在測驗題中最後連接排序好的佇列之前漏掉了 `INIT_LIST_HEAD` ， 由於 `head` 連接的節點已經被連接到排序好的 `less` 及 `greater` 中，所以要先斷開原本的連接。
* 這個實作在跑測試案例 `trace14` 、 `trace15` 會產生 `ERROR: Time limit exceeded` 。在 `trace14` 中，插入了許多相同的資料，因此在分割時會集中在其中一個 queue; 在 `trace15` 中，經過 sort 後資料就已經被排序完成， 因為這裡 pivot 固定選擇第一個節點， 所以資料也會集中在其中一個佇列。 當分割的資料幾乎都在其中一個佇列中，就使 quick sort 的時間複雜度從 $O(nlogn)$ 變成 $O(n^2)$
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || head->next == head->prev)
return;
struct list_head less, greater, middle;
INIT_LIST_HEAD(&less);
INIT_LIST_HEAD(&greater);
INIT_LIST_HEAD(&middle);
struct list_head *pivot = head->next;
char *pivot_val = list_entry(pivot, element_t, list)->value;
list_del(pivot);
struct list_head *itr, *safe;
list_for_each_safe (itr, safe, head) {
int result = strcmp(list_entry(itr, element_t, list)->value, pivot_val);
if (result < 0)
list_add(itr, &less);
else if(result > 0)
list_add(itr, &greater);
else {
list_add(itr,&middle);
}
}
q_sort(&less);
q_sort(&greater);
INIT_LIST_HEAD(head);
list_add(pivot, head);
list_splice(&middle,head);
list_splice(&less, head);
list_splice_tail(&greater, head);
}
```
* 為了解決大量相同資料的問題，新增一個佇列 `middle` 用來儲存與 pivot 相同的節點， middle 後續不在進行 quick sort ， 測試後可以通過 `trace14`
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || head->next == head->prev)
return;
struct list_head less, greater, middle;
INIT_LIST_HEAD(&less);
INIT_LIST_HEAD(&greater);
INIT_LIST_HEAD(&middle);
struct list_head *pivot = head->next;
char *pivot_val = list_entry(pivot, element_t, list)->value;
list_del(pivot);
struct list_head *itr, *safe;
bool less_change = true, greater_change = true;
list_for_each_safe (itr, safe, head) {
int result = strcmp(list_entry(itr, element_t, list)->value, pivot_val);
if (result < 0) {
if (less_change)
list_add(itr, &less);
else
list_add_tail(itr, &less);
less_change = !less_change;
} else if (result > 0) {
if (greater_change)
list_add(itr, &greater);
else
list_add_tail(itr, &greater);
greater_change = !greater_change;
} else {
list_add(itr, &middle);
}
}
q_sort(&less);
q_sort(&greater);
INIT_LIST_HEAD(head);
list_add(pivot, head);
list_splice(&middle, head);
list_splice(&less, head);
list_splice_tail(&greater, head);
}
```
* 因為選的 pivot 固定是第一個節點， 當佇列接近排序好的狀態(遞增或遞減) 就會使目前及後續的分割高度集中於其中一個 queue
* 透過交互插入開頭及尾端的方式來打亂佇列中的節點， 使得下次選擇 pivot 時不會固定是佇列中最大或最小的來避來避免分割不平均的問題。測試後可以通過 `trace15`
> [commit e7a6b70](https://github.com/Korin777/lab0-c/commit/e7a6b70cca766e02cf67b2d2c00dd2fba6d7bcd2) 參考 [linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)，新增 merge sort 的實作，並在 `qtest` 新增 `do_sortOption` 命令來切換排序的演算法
:::warning
若要改寫為非遞迴的排序，你打算如何進行？
:notes: jserv
:::
#### 非遞迴 buttom-up mergesort
[commit c44b1f4](https://github.com/Korin777/lab0-c/commit/c44b1f4daf1b7f64015ea41821be3d2add3ac895)
我的第一個想法是改用 buttom-up 去實作，去年[實作](https://hackmd.io/ae7DfZuiRW6wyn83y4UjNw?view#q_sort)的結果會因為 linked list 無法像陣列那樣直接取得某個位置的值，而產生許多不必要的走訪。
現在想想其實可以先不要將 `prev` 節點連接好，因為除了最後一次 merge ， 前面連接好的節點都可能會被重連 ， 所以可以等到最後再去重連 `prev` 節點 ， 有了 `prev` 節點我們就可以拿他來直接連到下一個要 merge 的區塊，來避免原本要經過多個節點才能到達下一個 merge 區塊
| bottom-up | time | cycles | instructions | cache-misses | cache-refrences | strcmp call |
|--|--|--|--|--|--|--|
| 改進前 |1.43996s|54,3498,5237|20,3342,1308|3180,7854|6983,8528|18715660|
| 改進後 |1.09312s|43,7429,6136|17,7845,9395|2541,9759|4210,4296|18715660|
上面是排序一百萬資料的結果，執行時間降低了不少，但比遞迴 top-down merge sort 還慢
#### 非遞迴 top-down mergesort
[commit fff99f4](https://github.com/Korin777/lab0-c/commit/fff99f4d2dab3c9b1764b7ce2722f17af7f93164)
這裡試著實現非遞迴的 top-down mergesort ， 想法也是跟上面一樣透過 `prev` 節點來連接合併好的區塊，並且額外在利用合併好的區塊的第二個節點的 `prev` 來紀錄這個區塊的大小，每次合併完就去看前面有沒有大小相同的區塊，有的話就繼續合併下去，主要是想模擬 top-down merge sort 會跟前一個區塊合併的行為
| top-down | time | cycles | instructions | cache-misses | cache-refrences | strcmp call |
|--|--|--|--|--|--|--|
| 遞迴 |0.71662s |29,7889,3727|18,9145,7316|1373,0805|3967,0762|18673584|
| 非遞迴 |0.69153s|29,2025,8297|17,8725,7508|1306,4755|3145,8093|18715660|
可以觀察到 `strcmp` 的次數不一樣，想想當節點有奇數個時，這個方法最後一個孤立的節點會跟 buttom-up 一樣固定在最後，但 top-down 的位置卻不一定，顯然我的方法只是一個會額外先合併相同大小的 buttom-up merge sort ， 而跟原本遞迴的實作相比有好一些
不過若跟上面改進後的 buttom-up 實作相比，這裡的實作執行時間又降低了不少，可以觀察到 cache-misses 低了不少，我覺得應該跟先去合併相同大小的區塊這點有關
---
### 引入 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
[commit 471ded9](https://github.com/Korin777/lab0-c/commit/471ded9a390aa75591110937848758df3d1e9754)
一開始 git commit 時無法成功，錯誤訊息如下：
```
list_sort.c:15:19: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
return strcmp(list_entry(a, element_t, list)->value,
^
list_sort.c:16:19: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
list_entry(b, element_t, list)->value);
```
上面的 `(struct element_t*)0` 對應到 `container_of` 巨集的 `(((type *) 0))` ，而 cppcheck 所檢測出來的問題就是我們對 0 dereference `(((type *) 0)->member)`，不過之前在 queue.c 也有用到 `list_entry` 卻還是可以 commit 成功，看了 `scripts/pre-commit.hook` 可以發現裡面有一行 `--suppress=nullPointer:qtest.c` ， 參閱 [Cppcheck manual](https://cppcheck.sourceforge.io/manual.pdf) 了解到他的用途是過濾掉產生的錯誤 ， 而透過 `--inline-suppr` 我們也可以透過 `suppression comment` 過濾掉 cppcheck 偵測出來的錯誤，最後也透過 Inline suppressions 的方式成功將 `list_sort` 引入，另外也在 `qtest.c` 中新增 `list_sort` 命令來使用它
#### 效能比較
[commit e87aba6](https://github.com/Korin777/lab0-c/commit/e87aba629e912497cde69ee91935d02d08a70cc4)
參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#%E6%AF%94%E8%BC%83-liblist_sortc-%E5%92%8C%E8%87%AA%E5%B7%B1%E5%AF%A6%E4%BD%9C%E7%9A%84-merge-sort) 撰寫測試程式產生排序用的資料，確保比較時排序的資料是相同的，並透過 perf 工具比較效能，排序一百萬筆隨幾產生的字串(每個字串為 5~10 個小寫字母組成)之結果如下
| 排序方式 | time | cycles | instructions | cache-misses | cache-refrences | strcmp call |
|--|--|--|--|--|--|--|
|my quicksort|0.73528s|30,5216,0933|21,6207,6539|3036,8419|6249,1175|24880386|
| linux list_sort |0.43839s|18,5576,2153|18,6235,4913|1262,4588|3827,9864|18686563|
| my_mergesort |0.71662s |29,7889,3727|18,9145,7316|1373,0805|3967,0762|18673584|
| my_mergesort 更改後 |0.52061s |21,2301,7352|17,8158,6690|1591,8822|5125,5537|18673584|
可以發現雖然 instructions 差不多，但我的實作 cycles 卻高出 `list_sort` 許多，顯然我的實作未考慮現代處理器特性，而在 cache-misses 的變現在我的實作偏高，至於排序過程中比較的次數，兩者都相當接近於 $O(n \ log n)$
```diff
static struct list_head *merge(struct list_head *a, struct list_head *b)
{
- // ptr : Update list_head->next to link node
- // node : Each comparison will advance one either a or b
- struct list_head *head = NULL, **ptr = &head, **node;
- for (; a && b; *node = (*node)->next) {
- node = strcmp(list_entry(a, element_t, list)->value,
- list_entry(b, element_t, list)->value) <= 0
- ? &a
- : &b;
- *ptr = *node;
- ptr = &(*ptr)->next;
+ struct list_head head;
+ struct list_head *h = &head;
+
+ while(a && b) {
+ if(strcmp(list_entry(a, element_t, list)->value,
+ list_entry(b, element_t, list)->value) <= 0) {
+ h->next = a;
+ a = a->next;
+ a = a->next;
+ } else {
+ h->next = b;
+ b = b->next;
+ }
+ h = h->next;
}
- *ptr = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
- return head;
+
+ h->next = (struct list_head *) ((uintptr_t)a | (uintptr_t)b);
+ return head.next;
}
```
觀摩 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_sort) 的開發紀錄，發現他 merge sort 的實作執行時間跟 cycle 與 linux `list_sort` 相當接近，而他跟我 merge sort 的不同主要在 `merge` 的實作，這裡也改進了最後 `h->next` 所造成的分支
從上面的表格可以發現，執行時間與 cycles 確實降低了，但 cache-misses 卻增加了，不知道是什麼原因造成的
我也發現如果透過 `-O3` 最佳化來編譯，運用指標得指標就不會比更改後的 merge sort 差了，同時又能精簡程式碼
Sign in with Wallet
Connect another wallet