2024q1 Homework2 (quiz1+2)

contributed by < aftuta85 >

第一週測驗題

測驗一

測驗二

Timsort 運作原理

測驗題版本 Timsort

這小節介紹測驗題版本 Timsort 為主。

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() 程式碼如下：

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 合併：

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 長度的用法：

// 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);
}

下面程式碼部份有疑惑：

    // 這邊已經處理完 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

新增了 minrun 機制，並且在 find_run() 過程中，若 run size < minrun，則透過 binary insertion 將新節點插入當前 run。

在實作 binary insertion 時，在做插入時對於節點的 next、prev 操作上有一些混亂，目前的版本或許要在檢查一下。

目前的實作 (timsort) 與原始版本 (timsort_orig) 的比較:

這邊的 SAMPLES 是 100000

==== 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() 計算執行時間，如下：

/* 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");

有個疑惑是雖然改進版本的比較次數比原始版本少，但執行時間卻比較長一點，雖然用 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 個，則清除該位元並重複上述步驟。

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() 定義如下:

#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 = 1000100000000000   // (word & 0xff) == 0, num = 0 + 8 = 8
word = 0000000010001000   // (word & 0xf) != 0
word = 0000000010001000   // (word & 0x3) == 0, num = 8 + 2 = 10
word = 0000000000100010   // 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 為例：
// __const_hweight16(w) + __const_hweight16((w) >> 16)
0111000000000001   1000000000001000   

// __const_hweight8(w) + __const_hweight8((w) >> 8)
00000001   01110000   
// __const_hweight8(w) + __const_hweight8((w) >> 8)
00001000   10000000   

return 1 + 3 + 1 + 1 = 6

在 small_const_nbits(nbits) 使用 __builtin_constant_p() 的目的是?