---
# System prepended metadata

title: 2024q1 Homework2 (quiz1+2)
tags: [Linux 核心設計/實作 (2024)]

---

# 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==&nbsp;&nbsp;&nbsp;// (word & 0xff) == 0, num = 0 + 8 = 8
word = <font color=#DDDBDB>00000000</font>1000==1000==&nbsp;&nbsp;&nbsp;// (word & 0xf) != 0
word = <font color=#DDDBDB>00000000</font>100010==00==&nbsp;&nbsp;&nbsp;// (word & 0x3) == 0, num = 8 + 2 = 10
word = <font color=#DDDBDB>0000000000</font>10001==0==&nbsp;&nbsp;&nbsp;// 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>&nbsp;&nbsp;&nbsp;<font color=#CC3BCC>1000000000001000</font>&nbsp;&nbsp;&nbsp;

// <font color=#32AA6A>__const_hweight8(w)</font> + <font color=#32AA6A>__const_hweight8((w) >> 8)</font>
<font color=#32AA6A>00000001</font>&nbsp;&nbsp;&nbsp;<font color=#32AA6A>01110000</font>&nbsp;&nbsp;&nbsp;
// <font color=#CC3BCC>__const_hweight8(w)</font> + <font color=#CC3BCC>__const_hweight8((w) >> 8)</font>
<font color=#CC3BCC>00001000</font>&nbsp;&nbsp;&nbsp;<font color=#CC3BCC>10000000</font>&nbsp;&nbsp;&nbsp;

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() 的目的是?
:::