2025q1 Homework2 (quiz1+2)

contributed by < weiso131 >

第一週測驗 1

填空

• AAAA : &l
• BBBB : before
• CCCC : &(*p)->next
• DDDD : item->next

程式運作原理

list_insert_before 運作原理

merge_sort 實作

list_item_t *merge(list_item_t *l, list_item_t *r, int descend) 
{
    list_item_t *head = NULL, **indir = &head;
    while (1) {
        if (l->value > r->value == descend) {
            *indir = l;
            indir = &l->next;
            l = l->next;
            if (!l) {
                *indir = r;
                break;
            }
        }
        else {
            *indir = r;
            indir = &r->next;
            r = r->next;
            if (!r) {
                *indir = l;
                break;
            }
        }
    }
    return head;
}

list_item_t *merge_sort(list_item_t *head, int descend)
{
    if (head->next == NULL)
        return head;
    list_item_t *l = head, *last_r = head, *r = head->next, *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        last_r = r;
        r = r->next;
        fast = fast->next->next;
    }
    last_r->next = NULL;
    l = merge_sort(l, descend), r = merge_sort(r, descend);

    return merge(l, r, descend);
}

第一週測驗 2

填空

• EEEE: (*pred_ptr)->r
• FFFF: &(*pred_ptr)->r

remove_free_tree 解讀

l == r == NULL

l != NULL || r != NULL

l != NULL && r != NULL

*pred_ptr != (*node_ptr)->l

*pred_ptr == (*node_ptr)->l

補完程式碼

find_free_tree

block_t **find_free_tree(block_t **root, block_t *target)
{
    block_t **node_ptr = root;
    while (*node_ptr != target && *node_ptr != NULL) {
        if (target->size > (*node_ptr)->size)
            node_ptr = &(*node_ptr)->r;
        else
            node_ptr = &(*node_ptr)->l;
    }
    return node_ptr;
}

解說

insert_free_tree

void insert_free_tree(block_t **root, block_t *target)
{
    block_t **node_ptr = find_free_tree(root, target);
    *node_ptr = target;
}

init_block

block_t *init_block(size_t size) 
{
    block_t *block = malloc(sizeof(block_t));
    block->size = size;
    block->l = block->r = NULL;
    return block;
}

測試程式

void block_test() 
{
    for (int i = 0;i < N;i++) {
        size_t size = rand() % 8192;
        blocks[i] = init_block(size);
        insert_free_tree(&root, blocks[i]);
    }
    for (int i = 0;i < N;i++) {
        remove_free_tree(&root, blocks[i]);
        block_t **find = find_free_tree(&root, blocks[i]);
        assert(*find == NULL);
        free(blocks[i]);
        blocks[i] = NULL;
    }
    printf("All test complete!!!\n");
}

解說

自訂記憶體配置器

github
參考 memory-allocators 的 free list allocator。
這種記憶體分配器屬於通用型分配器，利用一個資料結構(通常是鏈結串列或紅黑樹)紀錄可供使用的記憶體區塊，在使用者請求分配時，在這個資料結構尋找合適的區塊提供給使用者。
另外，若在釋放記憶體時，發現有相鄰的記憶體區塊是可用的，這種實作方法會將其合併。
要以時間複雜度

$O(1)$ 確認是否能合併，可以使用雙向鏈結串列維護其順序，以方便查詢。

文中提到可以用鍊結串列或是紅黑樹維護，我嘗試使用二元搜尋樹代替紅黑樹，實作這種記憶體分配器。在不發生樹嚴重傾斜的情況下，查詢的時間複雜度與紅黑樹相同，皆是

$O(log(n))$。 而在測驗題中也有提供相關實作，可直接使用。

至於雙向鏈結串列，在實作過程中發現，若是環狀的鏈結串列，在插入節點時就沒有判斷下一項是否為空指標的問題，因此我使用 list.h 的資料結構與 API 來維護這個雙向鏈結串列。

功能簡述

這些是這個分配器提供給使用者的主要功能
定義在 includes/free_list_alloc.h

• void init_fl(size_t size);
  根據使用者提供的size，設定這個記憶體分配器的總分配空間大小上限
• void *fl_alloc(size_t size)
  分配使用者需要的記憶體空間，分配成功則回傳該記憶體的位址
  分配失敗或是 size 為 0 則回傳 NULL
• void fl_free(void *ptr)
  將使用者傳入的指標對應的空間釋放
  若傳入空指標則不做任何事情
  若傳入已經釋放過，或是不屬於 init_fl 初始化的記憶體，則屬於 undefine behavior
  與 C 語言原生的 free 類似(參考: C standard (ISO/IEC 9899:2011 §7.20.3.2))

init_fl

步驟

1. 利用 init_block 建立一個初始 block (root_block)。
2. 把這個 block 設定為 tree_root（BST 根節點）。
3. 建立一個 root_head，為雙向鏈結串列的頭節點。
4. 將 root_block 加入雙向鏈結串列（使用 list_add）。

說明

1. 這個新的 block 是一個全新可用的區塊，所以直接加入二元搜尋樹
2. 先使用 root_block 儲存這個分配器全部的可用區塊，再將 tree_root 設定成 root_block ，可以在最後方便使用者一次釋放所有空間，不會因為二元搜尋樹根節點的改變而無法一次釋放

fl_alloc

步驟

1. 使用 find_block_by_size() 找一個合適的 block
2. 從 BST 移除該 block ， 代表這個 block 不再是未使用空間
3. 分割多餘空間：
   • 若剩餘空間足夠放一個 block 結構和額外資料 ➜ 建立新 block (unuse)。
   • 重新設定兩個區塊所持有的空間
   • 將 unuse 插入鏈結串列(在原本的 block 後方)，並加入二元搜尋樹。
4. 標記分配的 block 為已使用

說明

1. 若剩餘空間小於等於 block 結構的大小，則無法正常成為一個可使用的 block，此時儘管超出使用者要求的記憶體一些，仍會一次將這些記憶體都提供給使用者

find_block_by_size

• 找到最小大於等於使用者要求大小的區塊
• 在迴圈中，若最後找不到相同大小的區塊時， find 會變成 NULL
• 為了確保找到的區塊絕對大於使用者要求大小，利用 last_bigger 儲存最後一個往左，也就是最後一個發現比目標大的區塊的指標

  dded92d

• find 為 NULL 的時候會將其設為 last_bigger ， 若 size 大於所有可用區塊， 就會因為尋找過程中一直向右， last_bigger 仍為 NULL ， 符合需求

fl_free

步驟

1. 檢查時否未使用
2. 標記 block 為未使用
3. 插入二元搜尋樹
4. 呼叫 try_merge() 嘗試合併周圍未使用區塊

try_merge

1. 檢查 block 的 list.next 和 list.prev 是否是未使用。
2. 若是 ➜ 呼叫 merge_b_to_a()

merge_b_to_a

1. 將 b 從 BST 和 linked list 移除。
2. 將 a 從 BST 移除。
3. 計算合併後新大小 ➜ a->size = a->size + b->size + sizeof(block_t)。
4. 將合併後的 a 插回 BST

說明

• 因為合併大小時，可能會改變二元搜尋樹的性質，所以要先將 a 從樹上移除

  5c0da11

效能測試

測試程式

• 圖為隨機執行 alloc / free 1000000 次所花費的時間累積圖
• 如圖，目前的分配器效能明顯比 malloc 差

使用 perf 尋找效能瓶頸

• 可以發現 find_free_tree 佔用了非常大量的時間
• 查看組合語言可以看到 cmp 前最後一個 dereference 非常花時間，這可能對應到原始碼的 (*node_ptr)->size

  0.07 │25:   mov     -0x20(%rbp),%rax                                                                                                                                                                 ▒
  0.71 │      mov     (%rax),%rax                                                                                                                                                                      ▒
  0.13 │      mov     -0x8(%rbp),%rdx                                                                                                                                                                  ▒
 53.47 │      mov     (%rdx),%rdx  

• 似乎與太多的 cache miss 發生有關
  

嘗試減少 find_free_tree 使用

• 參考 rota1001 開發紀錄
  

效能或許有些微提昇，使用 t 檢定驗證

def calculate_cohens_d(x1, x2):
    # Pooled standard deviation
    nx = len(x1)
    ny = len(x2)
    pooled_std = np.sqrt(((nx - 1)*np.var(x1, ddof=1) + (ny - 1)*np.var(x2, ddof=1)) / (nx + ny - 2))
    d = (np.mean(x1) - np.mean(x2)) / pooled_std
    return d

def compare_groups(free_list, new_free_list):
    # Welch's t-test（自動考慮變異數不等）
    t_value, p_value = ttest_ind(free_list, new_free_list, equal_var=False)

    # 自由度由 ttest_ind 自動處理（Welch 方法）
    cohen_d = calculate_cohens_d(free_list, new_free_list)

    print(f"✅ Welch's t-test 結果：")
    print(f"t 值：{t_value:.4f}")
    print(f"p 值：{p_value:.4f} {'（顯著）' if p_value < 0.05 else '（不顯著）'}")
    print(f"Cohen's d 效果量：{cohen_d:.4f}")
    print(f"效能提升倍率：{free_list.sum() / new_free_list.sum():.4f}")
compare_groups(free_list, new_free_list)

輸出：

✅ Welch's t-test 結果：
t 值：54.8427
p 值：0.0000 （顯著）
Cohen's d 效果量：0.0776
效能提升倍率：1.0997

8e833ec

第一週測驗 3

填空

• GGGG: head->prev=prev
• HHHH: list_entry(pivot,node_t,list)->value
• IIII: list_entry(n,node_t,list)->value
• JJJJ: pivot
• KKKK: right

rebuild_list_link 解說

node 不斷往 next
prev 緊跟在 node 後面
當 node 為 NULL 時，代表鍊結串列的最後一個節點找到了
此時 prev 就是最後一個節點

quick_sort 解說

稍微跳過幾個步驟

第二週 測驗 1

填空

• AAAA: list_first_entry
• BBBB: list_del
• CCCC: list_move_tail
• DDDD: list_add
• EEEE: list_splice
• FFFF: list_splice_tail

list_quicksort 解釋

1. 將 list 的第一項作為 pivot ， 並移出環狀鍊結串列
2. 比 pivot 小的節點加入 list_less ， 比 pivot 大的節點加入 list_greater ， 加入時使用 list_move_tail 維持環狀鍊結串列的特性， 同時滿足 stable sorting
3. list_less 與 list_greater 各自進行 list_quicksort
4. 將 pivot, list_less, list_greater 合併

修正 random_shuffle_array

測試程式

使用 4 個元素的陣列
執行 shuffle 1e6 次
紀錄每種排列的出現次數
再計算卡方值

static int index_form[4][4][4];

#define SHUFFLE_TIMES 1000000
#define FACTORIAL_4 24

void build_lookup_table()
{
    int index = 0;
    uint16_t perm[4] = {1, 2, 3, 4};

    // Generate all 4! permutations using stdlib's next_permutation
    for (int a = 1; a <= 4; ++a)
        for (int b = 1; b <= 4; ++b)
            if (b != a)
                for (int c = 1; c <= 4; ++c)
                    if (c != a && c != b)
                        for (int d = 1; d <= 4; ++d)
                            if (d != a && d != b && d != c)
                                index_form[a - 1][b - 1][c - 1] = index++;
}



int main()
{
    uint16_t array[4] = {0, 1, 2, 3};
    uint32_t count[FACTORIAL_4] = {0};
    build_lookup_table();
    for (int i = 0; i < SHUFFLE_TIMES; ++i) {
        random_shuffle_array(array, 4);
        int idx = index_form[(int)array[0]][(int)array[1]][(int)array[2]];
        count[idx]++;
    }
    double expected = (double)SHUFFLE_TIMES / FACTORIAL_4;
    double chi_squared = 0.0;

    for (int i = 0; i < FACTORIAL_4; ++i) {
        double diff = count[i] - expected;
        chi_squared += (diff * diff) / expected;
    }

    printf("Chi-squared value: %.4f\n", chi_squared);

    return 0;
}

原本的 random_shuffle_array

輸出：

Chi-squared value: 122688.7850

卡方值遠高於

${\chi }_{23,0.05}^2=35.1725$

使用 fisher_yates_shuffle

參考 lab0 提供的 shuffle 演算法

static inline void fisher_yates_shuffle(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0;i < len;i++) {
        uint16_t new = len - i - 1;
        uint16_t old = get_unsigned16() % (new + 1);
        uint16_t save = operations[new];
        operations[new] = operations[old];
        operations[old] = save;

    }
}

輸出：

Chi-squared value: 21748.5402

雖然有減少，但其卡方值仍遠高於

${\chi }_{23,0.05}^2=35.1725$

使用 rand 代替 get_unsigned16

        uint16_t new = len - i - 1;
-       uint16_t old = get_unsigned16() % (new + 1);
+       uint16_t old = rand() % (new + 1);
        uint16_t save = operations[new];

輸出：

Chi-squared value: 10.5795

卡方值小於

${\chi }_{23,0.05}^2=35.1725$
無證據說明這個 shuffle 是不公平的

list_move_tail 換為 list_move 無法滿足 stable sorting

第二週 測驗 2

填空

• GGGG: 14
• HHHH: 2
• IIII: 0
• JJJJ: 3
• KKKK: 2
• LLLL: 1
• MMMM: ~1
• NNNN: 1
• PPPP: 2

clz32

解說

1. 先將一個數字藉由 bit mask 切分成 upper 與 lower
2. 檢查 upper 是否為 0 ， 若不是 0 ，代表 leading zero 在 upper 裡面，對 upper 執行 clz32。反之， leading zero 在 lower ， 此時加上 (16 >> c) 正是前方的位元數量。
3. 重複執行直到 c == 3 ， 此時 upper 與 lower 都只剩兩個 bits 的長度，若 upper 不為 0 ， 將 upper 帶入 magic 可做最後的計算。反之， +2 然後對 lower 最類似的事情。

mask 補充

最後只剩 2 bits ， 代表會有四種可能

• 00: 前方累計位元數 +2 即是 leading zero 的位置
• 01: 前方累計位元數 +1 即是 leading zero 的位置
• 10: 前方累計位元數即是 leading zero 的位置
• 11: 前方累計位元數即是 leading zero 的位置

sqrti

解說

題目中的 sqrti 其實就是 Digit-by-digit Method 的實作，但直接從原本的函式實作解釋它有些困難，我將會提供從最直觀的實作，一步一步優化到現在狀態的過程。

最直觀實作

    int shift = (total_bits - 1 - clz64(x)) & ~1;

    while (shift >= 0) {
        m = 1ULL << shift;
        uint64_t m_2 = 1ULL << (shift >> 1);
        uint64_t b = ((y * m_2) << 1) + m;
        if (x >= b) {
            x -= b;
            y += m_2;
        }
        shift -= 2;
    }

這個實作方法基本上是照著演算法的描述一步一步實現，可以看到他會存在一個乘法運算

移除乘法運算

    int shift = (total_bits - 1 - clz64(x)) & ~1;
    uint64_t last = 0;

    while (shift >= 0) {
        m = 1ULL << shift;
        uint64_t m_2 = 1ULL << (shift >> 1);
        uint64_t b = last + m;
        last >>= 1;
        if (x >= b) {
            x -= b;
            y += m_2;
            last += m;
        }
        shift -= 2;
    }

這個方法由一個 last 儲存每一次 y 更新時的 m
並在進入判斷式前右移一格

這個調整仍是有效的原因，是因為所有 m 都是 2 的次方
以此改寫公式

$$(2^{i+k}+...+2^i+2^{i-j}{)}^2=(2^i{)}^2+(2(2^{i+k}+...+2^i)+2^{i-j})\cdot 2^{i-j}$$
再展開

$$(2^i{)}^2+(2^{i-j}{)}^2+2^{2i+k-j+1}+...+2^{2i-j+1}$$

觀察到

$2^{2i-j+1}$ 可以發現只要對

$2^{2i}$ 右移

$j-1$ ，就能得到現在做計算所需的值
這正是 last 在做的事情

合併 last 與 y

    int shift = (total_bits - 1 - clz64(x)) & ~1;

    while (shift >= 0) {
        m = 1ULL << shift;
        uint64_t b = y + m;
        y >>= 1;
        if (x >= b) {
            x -= b;
            y += m;
        }
        shift -= 2;
    }

在 shift 為

$2i$ 加上一個 m:

$2^{2i}$
由於到迴圈結束時會被右移

$i$ 格，對最後的 last 而言相當於每次都加上

$2^i$
這與 y 的功能完全相同

到了這步基本上已經跟原本的 sqrti 相同，只差把每次重新計算的 m 放在迴圈外， 每次 m 往右移兩格的調整

向上取整

x 在計算過程會被減去 y 的平方
若最後 x 不是 0 ，就代表 x 原本不是完全平方數，需要向上取整，也就是額外 +1
因此，可以對最後的 return 做修改

return y + (x && 1);

即可在只使用加減法與位元操作的情況下，完成向上取整的平方根

第二週 測驗 3

填空

• AAAA: map->bits
• BBBB: map->bits
• CCCC: first->pprev
• DDDD: n->pprev
• EEEE: n->pprev

程式碼解釋