# 2024q1 Homework2 (quiz1+2)
contributed by <`csotaku0926`>
> [程式碼](https://github.com/csotaku0926/Linux_Hw2_Lab)
## 第一週測驗題
### 測驗一
#### 解釋程式碼原理
先就現有的[參考資料](https://alienryderflex.com/quicksort/)觀察
從原先作者的圖解，可以知道這段程式是在實現非遞迴的快速排序:
首先 L 會指向陣列的開頭 (從 begin 按照 LIFO 選取)，R 會指向陣列結尾 (從 end 按照 LIFO 選取)
在圖示的初始狀況中，L, R 指向的點不同，因此 pivot 選用陣列的開頭
利用指標 (上圖中的 p ) 走訪整個串列後 (pivot 除外)，將數值較 pivot->value 小的節點放到 left, 反之放到 right。
最後，begin, end 這兩個陣列會新增紀錄三個子串列的開頭與結尾： left, pivot 與 right
也就是說，`begin[i] = left` `begin[i+1] = pivot` `begin[i+2] = right`, end 堆疊同理
(end 存放串列的結尾)
接著下一個 partition 處理位於 i+2 位置的串列 (也就是上圖的 right )，重複上述動作
如果 L, R 指向同個位置，表示已經處理完畢，可以把這個節點放入已排序陣列中
::: info
思路：
測驗一中的 `quick_sort` 函式，並沒有使用到 `swap` ，反而是利用 `begin` `end` 這兩個 stack 達成遞迴的目的。所以 begin 裡面存放的應該是每次遞迴的子串列開頭, end 同理應是存放子串列的結尾。
:::
#### 改進方案
我觀察到的可能改進點如下：
- `max_length` 的大小
- `pivot` 的選取
首先討論 `max_length` 的大小
原先程式使用 `2 * list_legnth(list)` 作為 begin, end 的大小，這顯得不合理
理論上最多也只會放入 `list_legnth(list)` 這麼多的節點
為驗證以上說法，來實際測量begin, end 最大使用的長度為何
在 `quick_sort` 迴圈加入 `count_i` 變數紀錄最大長度
```diff
left = right = NULL;
i += 2;
+ count_i = MAX(count_i, i);
```
並且利用 lab0 裡面的 `cpucycles()` 測量執行時間
```diff
+ int64_t before = cpucycles();
quick_sort(&list);
+ int64_t after = cpucycles();
```
以下為以不同長度的串列測試的結果輸出：
```shell
Size: 10
Max length: 4
elasped cycles: 22876
Size: 100
Max length: 14
elasped cycles: 93627
Size: 1000
Max length: 22
elasped cycles: 809319
Size: 10000
Max length: 34
elasped cycles: 14269767
Size: 100000
Max length: 60
elasped cycles: 77046564
Size: 1000000
Segmentation fault (core dumped)
```
可以發現使用到的長度遠小於預期，原先的實作甚至會導致 Segmentation fault
於是將程式改為：
```c
int n = list_length(list);
int max_level = n * 0.25 + 20;
```
這時分配 1000000 個節點，也不會出現 Segmentation fault 了
談到 pivot 的選取，可以發現原先程式選用開頭作為 pivot
這麼做有個問題，若是輸入陣列節點數值是完全遞增或是遞減的狀況，會導致 worst case 的發生
因為每次都會將陣列分割成一個只包含 pivot 節點，以及另一個包含所有其他節點的子串列
顯然，這會讓時間複雜度退化為 $O(n^2)$
其中一個常見的作法是隨機選取 pivot。我的作法是利用 `rand()` 選取隨機節點後，將其移動到開頭。
```c
// swap the random value with head
void swap_random_pivot(node_t **list) {
if (!list)
return;
int len = list_length(list);
srand(time(NULL));
int r = rand() % len;
node_t **rand_node = list;
while (r > 1) {
rand_node = &(*rand_node)->next;
r--;
}
node_t *tmp = (*rand_node)->next;
(*rand_node)->next = tmp->next;
list_add(list, tmp);
}
```
以下是原來程式，對於每個長度 (10, 100, ..., 100000) 執行十次後取執行時間與最大堆疊長度的中位數
```shell
Size: 10
Max length: 8
Elapsed Cycles: 5611
Size: 100
Max length: 16
Elapsed Cycles: 69692
Size: 1000
Max length: 26
Elapsed Cycles: 916829
Size: 10000
Max length: 38
Elapsed Cycles: 2481397
Size: 100000
Max length: 48
Elapsed Cycles: 50033392
```
以下是我在加入 `swap_random_pivot` 後取得的數值
```diff
if (L != R) {
+ swap_random_pivot(&L);
node_t *pivot = L;
value = pivot->value;
...
```
可以看到最大的深度確實有所減少，但整體花費 cycle 反而上升不少
```shell
Size: 10
Max length: 4
Elapsed Cycles: 100035
Size: 100
Max length: 14
Elapsed Cycles: 814267
Size: 1000
Max length: 26
Elapsed Cycles: 3605319
Size: 10000
Max length: 38
Elapsed Cycles: 18732945
Size: 100000
Max length: 48
Elapsed Cycles: 222897390
```
#### 結合 [List API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)
本項實作使用 lab0-c 中的 `list.h`
由於是雙向鍊結串列，因此在 `quick_sort` 中不再需要以 `end` 紀錄結尾，可以進一步節省空間使用量
修改過的 `quick_sort` 初始版本會有陷入迴圈的問題
要留意 list API 與單向鍊結中的節點的型態差異，並且注意正確的函式呼叫
[quick_sort 程式碼](https://github.com/csotaku0926/Linux_Hw2_Lab/blob/main/1-1/qsort.c#L72C1-L116)
#### 避免最差狀況的實作
根據 [StackOverflow](https://stackoverflow.com/a/7560859) 的討論，PRNG 的選取不僅會影響執行速度，有時在安全性的考量也是個問題 (e.g. 如果使用顯著的PRNG，可能被有心人士更改節點順序，導致一直選到「不好的」 pivot )
一個常見的作法是 median-of-three ，考慮以下程式碼 ([原著](https://stackoverflow.com/a/55242934))
```c
int medianThree(int a, int b, int c) {
if ((a > b) ^ (a > c))
return a;
else if ((b < a) ^ (b < c))
return b;
else
return c;
}
```
我們比較三個數值： 開頭，中間點，以及尾端
這麼一來，可以優化遞增或遞減串列的最差狀況
但是排序的對象是鍊結串列，如果要找中間點需要耗費 $O(n)$ 的時間搜尋。這種策略用在鍊結串列上還能勝過隨機指定嗎？
### 測驗二
#### 解釋程式碼原理
在 `timsort` 函式中，先將給定的循環串列拆解成 null-terminated 的串列
接著透過 `find_run` 找尋當前串列的下一個 run ，處理規則如下
- 如果下個節點的數值比當前的小，回傳反轉後的序列
- 反之，回傳由當前節點開始，數值遞增的序列
考慮以下狀況
由於 list 指向的節點數值比 next 還要大，適用於狀況一
原始程式碼：
```c
do {
len++;
list->next = prev;
prev = list;
list = next;
next = list->next;
head = list;
} while (next && cmp(priv, list, next) > 0);
list->next = prev;
```
我想了很久才逐漸了解其中邏輯
新增一個暫時指標 prev ，指向 NULL
在這個迴圈中，next 指向下一個 run 開始的節點，head 指向這個反向序列的開頭
list 指向單調遞增的子串列，迴圈中 list->next 指向 prev 代表 list 中的順序和原先的遞減串列是反向的
也就是最後的結果會像這樣
不論哪種狀況，回傳的 pair 中 head 都會指向一個遞增子串列的開頭，next 則是下一個 run 的開頭，並將子串列的長度存在 `head->next->prev` 當中
處理好 run 之後，進行 `merge_collapse`
此函式的目的是合併 run 至兩個以下，並根據堆疊前三個 run 長度的大小關係決定要合併的點：
- 若 tp->prev->prev 長度小於 tp 以及 tp->prev 的長度總和，選取後兩者較小的串列合併
- 若 tp->prev 長度小於 tp，選取長度較小的 tp 合併
直到所剩的堆疊小於三個，或是長度不滿足上述關係後，才進行統一融合
最後，由於原先的串列被拆解成一個個堆疊的架構，需要透過 `build_prev_link` 恢復成雙向串列
#### 嘗試改進
作業說明中至少提到兩點可以改進的地方：
- 設計 minrun 使得串列分割成 2 的冪
- Galloping mode 的實作
參考 Tim 在 [github](https://github.com/python/cpython/blob/3fe9117779f0c75f7a0c3d7748c5bf281fbc1e4c/Objects/listsort.txt#L267-L283) 的解釋:
> This is easier to do than it may sound: take the first 6 bits of N, and add 1 if any of the remaining bits are set.
In fact, that rule covers every case in this section, including small N and exact powers of 2; merge_compute_minrun() is a deceptively simple function.
以 N = 2112 而言
2112 化成二進位是 `0b100001000000`
取前六位: `0b100001` --> 33
剩餘的 bit 沒有被設置的，所以 33 就是預期的 minrun
對應程式碼:
```c
static size_t find_minrun (struct list_head *head)
{
size_t len = list_length(head);
// find first 6 bit & add up remain bits
size_t minrun = 0;
while(len >> 6) {
minrun += (len & 1);
len >>= 1;
}
minrun += len;
return minrun;
}
```
目前這方面卡在 `insertion sort` 的部份有實作錯誤，一直無法跳出迴圈，待修正
[有 bug 的程式碼](https://github.com/csotaku0926/Linux_Hw2_Lab/blob/main/1-2/timsort.c#L134-L160)
另外，我發現 `main.c` 沒有將動態分配的記憶體釋放
```c
free(samples);
free(warmdata);
free(testdata);
```
## 第二週測驗題
### 測驗一
#### 解釋程式碼原理
初始化和二元樹節點一樣多的 `hlist_head`
給定 inorder 以及 preorder 序列，將每個 inorder 節點放入 `order_node` 這個架構後，
利用 `node_add` 將節點插入 `hlist_head` 鍊結中
以題目舉的範例而言：
每個 hlist_head 都有個稱為 first 的指標，用來指向已經在這個鍊結的頂端節點 (初始指向 NULL)
`next` 指向下一個節點，`pprev` 較為特別，指向上一個節點指向自己的指標
以上述案例，假設節點0和節點1被分配到同一個 `hlist` ，數值 9 的節點會先進入，再來是數值 3
只有第一個進入的節點的 next ，也就是數值 9，會指向 NULL
而建立 inorder 雜湊表的目的，是要在 preorder 序列中找到對應的 inorder 元素
引用題目的[圖表](https://hackmd.io/@sysprog/linux2024-quiz2)：
第一個 preorder 元素是樹根，而我們在 inorder 序列的第二個元素找到它
這代表在第二個元素之前的屬於左半邊樹，反之則是右半邊樹。這種問題很適合以遞迴解決
#### 嘗試改進
顯然，在 `find` 函式中並未實現 hash function，而是單純以 `hlist_for_each` 搜索
完整的檢測程式碼可以參考我的 [github](https://github.com/csotaku0926/Linux_Hw2_Lab/tree/main/2-1)
```c
for (int i=0; i<test_time; i++) {
start = clock();
struct TreeNode *test_root = buildTree(preorder_list, Tree_size(depth),
inorder_list, Tree_size(depth));
end = clock();
if (!checkTree(root, test_root)) {
printf("Check tree failed :(\n");
success = false;
break;
}
total_time_used += (end - start);
}
if (success)
printf("elapsed avg time: %f\n",
(double)(total_time_used) / CLOCKS_PER_SEC / test_time);
```
作為測試資料，我建立一顆長度為 d 的完整二元樹
就原始的程式碼而言，當 d = 10，耗費時間約為 0.0012 秒
由於原先程式中已經宣告足夠數量 (等同於節點數量) 的 `hlist_head` ，直接使用簡潔的雜湊函數
```c
static int find(int num, int size, const struct hlist_head *heads)
{
struct hlist_node *p;
int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, &heads[hash]) {
// ...
}
```
執行時間來到 0.000137 秒，顯然這是空間換取時間的策略
有沒有可能使用少一點空間，時間效能上又不會影響太多？
#### Linux 核心的 cgroups 相關原始程式碼
什麼是 cgroup ？ 和樹有什麼關係？
根據官方 [github](https://github.com/torvalds/linux/blob/master/Documentation/admin-guide/cgroup-v2.rst):
> cgroup is a mechanism to organize processes hierarchically and
distribute system resources along the hierarchy in a controlled and
configurable manner.
而 cgroups 是一個樹狀的架構，每個系統行程都屬於一個且唯一的 cgroup
cgroup 可分為兩個部份 -- 核心 (core) 以及控制器 (controller)
控制器的作用是分配一種特定類型的系統資源給階層架構
查閱 linux kernel
```c
struct cgroup_subsys_state *
css_next_descendant_pre(struct cgroup_subsys_state *pos,
struct cgroup_subsys_state *root)
{
struct cgroup_subsys_state *next;
// ...
/* no child, visit my or the closest ancestor's next sibling */
while (pos != root) {
next = css_next_child(pos, pos->parent);
if (next)
return next;
pos = pos->parent;
}
return NULL;
}
```
雖然說是 preorder-walk ，卻沒有看到類似 left, right 的子節點架構
其利用 `css_next_child` 尋找下一個子節點，若不存在，則返回到上一層重新搜索
### 測驗二
#### 解釋程式碼
首先透過 `lruCacheCreate` 建立需要的架構
初始化一個 `LRUcache` ，這個架構有以下成員:
- 一個 `list_head` dhead，是存放節點的架構。當節點被存取時，會重新放到 dhead 的開頭，這時若要移除 least recent 的節點，移除其中排位最後的節點
- 數量為 capacity 的 `hlist_hea hhead[]`, 是用來查找節點的雜湊表
- capacity，代表 LRUcache 可容納的節點數量
- count, 代表目前 cahce 已存放的節點數量
而 `LRUNode` 則是節點架構，正如圖上方指向 hlist_head, dhead 的架構
#### 嘗試改進
注意到 `Get` `Put` 所使用的雜湊函式
```c
int hash = key % obj->capacity;
```
十分簡潔易懂，但相對碰撞的機率很高
我嘗試使用 [linux核心](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 引進的 multiplication-based 雜湊函式實作
```c
unsigned int hash_32(unsigned int key, unsigned int bits)
{
return (key * GOLDEN_RATIO_32) >> (32 - bits);
}
```
初步使用 clock() 進行測試時間
```c
start = clock();
for (int i=0; i<100; i++)
lRUCachePut(lru_cache, rand(), 111);
for (int i=0; i<10; i++)
lRUCacheGet(lru_cache, rand());
end = clock();
```
[leetcode](https://leetcode.com/problems/lru-cache/description/) 的要求
> The functions get and put must each run in O(1) average time complexity.
提到常數時間，可以使用 lab0-c 的 dudect 測試程式來檢驗
### 測驗三
### 雜記
關於 `hlist_del` 利用間接指標完成操作的部份，確實讓我思考了很久，於是在這裡紀錄
以下是節錄自 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable) 的擷圖，我覺得這張圖很好的解釋了原理
```c
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}
```
假設今天要移除 node 2，有兩件事情需要完成，那如何完成？
- 將 node 1->next 指向 node 3 (node 1 的下一個節點改為 node 3)
- 這時 `**prev = n->pprev` 是指向 node 1->next
- next 指向 node 3
- `*prev = next` : 更改 prev 間接指標指向的指標。這麼一來，不需要存取 prev->next 也能修改其值。同時，也不需以特例考慮 prev 是否為 NULL
- 將 node 3->pprev 指向 node 1 「指向 node 2」 的 next 指標 ( node 3 的前一個節點改為 node 1)
- next 有可能指向 NULL (如 node 3)
Sign in with Wallet
Connect another wallet