# 2024q1 Homework2 (quiz1+2)
contributed by < `aftuta85` >
## 第一週測驗題
### 測驗一
### 測驗二
#### Timsort 運作原理
##### 測驗題版本 Timsort
這小節介紹[測驗題版本](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) Timsort 為主。
```c
void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
stk_size = 0;
// ...
do {
/* Find next run */
struct pair result = find_run(priv, list, cmp);
result.head->prev = tp;
tp = result.head;
list = result.next;
stk_size++;
tp = merge_collapse(priv, cmp, tp);
} while (list);
// ...
}
```
首先，timsort() 在 `while` 迴圈中使用 `find_run()` 將序列切割成一個個獨立的 run，這些 run 是按照遞增或遞減的順序排列。舉例來說，如果序列是 {5, 4, 3, 6, 1, 7, 8}，它將被切割成 {5, 4, 3}、{6, 1}、{7, 8} 這樣的 run。每次切割出一個 run，`stk_size` 就會記錄目前 run 的總數。在每一輪 `find_run()` 後，都會呼叫 `merge_collapse()` 來進行 run 的合併。`merge_collapse()` 程式碼如下：
```c
static struct list_head *merge_collapse(void *priv,
list_cmp_func_t cmp,
struct list_head *tp)
{
int n;
while ((n = stk_size) >= 2) {
if ((n >= 3 &&
run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
(n >= 4 && run_size(tp->prev->prev->prev) <=
run_size(tp->prev->prev) + run_size(tp->prev))) {
if (run_size(tp->prev->prev) < run_size(tp)) {
tp->prev = merge_at(priv, cmp, tp->prev);
} else {
tp = merge_at(priv, cmp, tp);
}
} else if (run_size(tp->prev) <= run_size(tp)) {
tp = merge_at(priv, cmp, tp);
} else {
break;
}
}
return tp;
}
```
合併規則如下：
- stk_size >= 2
- 假設 stk_size == 2，有 A 與 B 兩個 run:
- 若 A'size <= B'size，則將 A、B 合併
- 假設 stk_size == 3, 有 A、B、C 三個 run:
- 若 A'size <= B'size + C'size
- 若 A'size < C'size，則將 A、C 合併
- 若 A'size >= C'size，則將 B、C 合併
- 假設 stk_size == 4, 有 A、B、C、D 四個 run:
- 若 A'size <= B'size + C'size
- 若 B'size < D'size，則將 B、C 合併
- 若 B'size >= D'size，則將 C、D 合併
持續進行上述步驟 (切 run、合併)，直到 `find_run()` 將整個序列切完為止。
接下來透過 `merge_force_collapse()` 將尚未合併的 run 合併：
```c
void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
stk_size = 0;
// ...
do {
/* Find next run */
struct pair result = find_run(priv, list, cmp);
// ...
} while (list);
/* End of input; merge together all the runs. */
tp = merge_force_collapse(priv, cmp, tp);
/* The final merge; rebuild prev links */
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
stk0 = stk0->prev, stk1 = stk1->prev;
if (stk_size <= 1) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
}
```
經過 `merge_force_collapse()` 合併後，可能會剩下 2 個以下的 run。若只剩下 1 個 run，則直接透過 `build_prev_link()` 將 head 與合併後的 list 接回，形成環狀雙向鏈結串列（在合併過程中 `prev` 可能會斷掉，或用來記錄當前 run 的大小）。
若在最後 `stk_size == 2`，則透過 `merge_final()` 將 2 個 run 依據大小合併為 1 個 run 後，在呼叫 `build_prev_link()` 將其回復為環狀雙向鏈結串列。
在 trace code 和補完程式碼的過程中，讓我學習到的是把 `prev` 指標拿來存 run 長度的用法：
```c
// store run size
head->next->prev = (struct list_head *) len;
// get size
static inline size_t run_size(struct list_head *head)
{
if (!head)
return 0;
if (!head->next)
return 1;
return (size_t) (head->next->prev);
}
```
:::info
下面程式碼部份有疑惑：
```c
// 這邊已經處理完 stk_size >= 3 的 case，代表函式結束後最多剩下 2 個 run
tp = merge_force_collapse(priv, cmp, tp);
struct list_head *stk0 = tp, *stk1 = stk0->prev;
// 這個 while 在兩個 run 情況下也最多執行一次，因此可以用 if 就好?
while (stk1 && stk1->prev)
stk0 = stk0->prev, stk1 = stk1->prev;
// ...
```
:::
目前測驗題版本的 Timsort 尚未考慮到 minrun 以及 Galloping mode 的實作，僅以遞增或遞減為分割 run 的依據。因此，應該改進兩個方面：
1. 實作 minrun 計算和分割規則
2. 實作 Galloping mode
> Galloping mode 用於 linked list 還沒有想到怎麼做，因為怎麼樣都要逐一訪問節點，那就直接用one-pair-at-a-time 模式即可。
#### 改善進度：
> 程式碼 [timsort.c](https://github.com/aftuta85/linux_lab_2024/commit/b7bb9765c2dae0af0aeed1dcd02bf9a0b18d11cf)
新增了 `minrun` 機制，並且在 `find_run()` 過程中，若 `run size` < `minrun`，則透過 binary insertion 將新節點插入當前 run。
在實作 binary insertion 時，在做插入時對於節點的 `next`、`prev` 操作上有一些混亂，目前的版本或許要在檢查一下。
目前的實作 (timsort) 與原始版本 (timsort_orig) 的比較:
> 這邊的 SAMPLES 是 100000
```shell
==== Testing timsort_orig ====
Comparisons: 1649746
Exection time: 0.011212 seconds
List is sorted
==== Testing timesort ====
Comparisons: 1533253
Exection time: 0.014868 seconds
List is sorted
```
目前以 `clock()` 計算執行時間，如下：
```c
/* Test */
count = 0;
start = clock();
test->impl(&count, &testdata_head, compare);
end = clock();
printf(" Comparisons: %d\n", count);
printf(" Exection time: %f seconds\n", ((double)(end - start))/CLOCKS_PER_SEC);
printf(" List is %s\n",
check_list(&testdata_head, nums) ? "sorted" : "not sorted");
```
:::info
有個疑惑是雖然改進版本的比較次數比原始版本少，但執行時間卻比較長一點，雖然用 clock() 有其他因素干擾，但對每次結果都是相同趨勢感覺疑惑
:::
> 排除實作差異，改進版本只多了計算 minrun 跟資料長度，試過把計算長度功能也在原始版本做，但依舊差不多結果。或許要再檢查一下目前實作部分有沒有問題。後續再使用其他工具來做測試。
## 第二週測驗題
### 測驗三
`find_nth_bit()` 函式的功能是在給定的 size 範圍內找到第 n 個設置為 1 的位元，流程如下：
1. 如果 `size` 小於或等於 `BITS_PER_LONG`，則使用 `fns()`` 函式找出第 n 個位元的位置。
2. 如果 `size` 大於 `BITS_PER_LONG`，則使用 `FIND_NTH_BIT` 巨集以每 `BITS_PER_LONG` 單位進行查找。
在 `fns()` 中，通過 `while` 迴圈，每次透過`__ffs()`找出第一個最低有效位。如果這個位元不是要找的第 n 個，則清除該位元並重複上述步驟。
```c
static inline unsigned long fns(unsigned long word, unsigned int n)
{
while (word) {
unsigned int bit = __ffs(word);
if (n-- == 0)
return bit;
__clear_bit(bit, &word);
}
return BITS_PER_LONG;
}
```
`__ffs()` 定義如下:
```c
#if BITS_PER_LONG == 64
if ((word & 0xffffffff) == 0) {
num += 32;
word >>= 32;
}
#endif
if ((word & 0xffff) == 0) {
num += 16;
word >>= 16;
}
if ((word & 0xff) == 0) {
num += 8;
word >>= 8;
}
if ((word & 0xf) == 0) {
num += 4;
word >>= 4;
}
if ((word & 0x3) == 0) {
num += 2;
word >>= 2;
}
if ((word & 0x1) == 0)
num += 1;
return num;
}
```
在假設為 64 位元環境下，`__ffs()` 依序檢查 `word` 的 32 個位元、16 個位元、8 個位元、4 個位元、2 個位元和 1 個位元中是否有 1。
下面以一個 16 位元環境為範例，所以會依序檢查8 個位元、4 個位元、2 個位元和 1 個位元:
word = 10001000==00000000== // (word & 0xff) == 0, num = 0 + 8 = 8
word = <font color=#DDDBDB>00000000</font>1000==1000== // (word & 0xf) != 0
word = <font color=#DDDBDB>00000000</font>100010==00== // (word & 0x3) == 0, num = 8 + 2 = 10
word = <font color=#DDDBDB>0000000000</font>10001==0== // num = 10 + 1 = 11
如果 `size` 大於 `BITS_PER_LONG`，則利用 `FIND_NTH_BIT` 巨集透過 `for` 迴圈以每 `BITS_PER_LONG` 為單位去找出累積的 bit 1 數量是否已達到要求。在這邊利用 `hweight_long()` 計算出當前資料段有多少個 bit 1。當確定到這段資料段已經達到數量要求後，跳到 `found`，在利用上述 `fns()` 找出實際位置。
`hweight_long()` 透過將 64 個位元拆分為 32 個位元 + 32 個位元、16 個位元 + 16 個位元，直到每 8 個位元一組，計算每組中有多少個 1，然後將這些數量加總回到 64 個位元。
下面以一個 32 bits 資料 `10000000000010000111000000000001` 為例：
// <font color=#32AA6A>__const_hweight16(w)</font> + <font color=#CC3BCC>__const_hweight16((w) >> 16)</font>
<font color=#32AA6A>0111000000000001</font> <font color=#CC3BCC>1000000000001000</font>
// <font color=#32AA6A>__const_hweight8(w)</font> + <font color=#32AA6A>__const_hweight8((w) >> 8)</font>
<font color=#32AA6A>00000001</font> <font color=#32AA6A>01110000</font>
// <font color=#CC3BCC>__const_hweight8(w)</font> + <font color=#CC3BCC>__const_hweight8((w) >> 8)</font>
<font color=#CC3BCC>00001000</font> <font color=#CC3BCC>10000000</font>
return <font color=#32AA6A>1</font> + <font color=#32AA6A>3</font> + <font color=#CC3BCC>1</font> + <font color=#CC3BCC>1</font> = 6
:::info
在 small_const_nbits(nbits) 使用 __builtin_constant_p() 的目的是?
:::
Sign in with Wallet
Connect another wallet