2025q1 Homework2 (quiz1+2)

contributed by <Max042004>

quiz 1

測驗 1

第一次測驗的時候不懂間接指標如何發揮作用，經過 lab0-c 的練習之後，現在搞懂了。
在原本品味不好的程式碼，需要使用兩個指向節點的指標走訪鏈結串列，但鏈結串列的 head 不是節點，所以會造成例外。使用間接指標的話，其實只是善用 dereference 。要做比對，只需要 dereference p ，就能取得指向節點的指標，也就是節點的地址，然後比對是否一致；要做插入，也是 dereference p ，就能更改節點指標的值，使其指向新的節點。
間接指標可以透過 dereference 讓操作對象從自己變成自己指向的指標，從而取得指標指向的對象或更改指標的指向。
用間接指標避開特例，實際上是看待操作對象的方式不同，品味不好的作法是操作節點，但 head 並不是節點，因此形成特例：

間接指標是操作指標， head 和節點的指標都是指標，因此避免了特例：

程式碼：

{
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    item->next = before;
}

運作原理：
首先初始化 p 指向 head

接著 *p 取得節點地址，比對是否等於 before ，若否，則 p = &(*p)->next 更新間接指標指向下一個指標。
當 *p ，也就是 node1->next ，等於 before ，則停止迴圈。

接著，藉由 *p 讓 node1->next 指向 node3

最後，item->next = before 把 node2 接回去

假如是碰到 before 是首個節點會發生什麼事？

這時比對第一個節點時， *p = before ，因此跳出迴圈，一樣藉由 *p 更改 head 去指向 node3

間接指標避免了特例的發生

所以下次如果遇到要操作多個指標，可以思考能否使用間接指標讓程式碼更簡潔。

延伸思考：撰寫合併排序操作
參考你所不知道的 C 語言: linked list 和非連續記憶體
在 mergeTwoLists 使用間接指標，可以免去分配記憶體空間給head，使用 node 這個間接指標可以減少重複的程式碼

list_item_t *mergeTwoLists(list_item_t *L1, list_item_t *L2) {
    list_item_t *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (L1->value < L2->value) ? &L1: &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (list_item_t *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}


static list_item_t *mergesort_list(list_item_t *head){
    if(!head || !head->next) return head;

    list_item_t *slow = head, *mid;
    for(list_item_t *fast = head; fast->next != NULL || fast->next->next != NULL; fast = fast->next->next){
        slow = slow->next;
    }
    mid = slow->next;
    slow->next = NULL;

    list_item_t *left = mergesort_list(head);
    list_item_t *right = mergesort_list(mid);

    return mergeTwoLists(left, right);
}

後續再閱讀你所不知道的 C 語言: linked list 和非連續記憶體案例探討: Leetcode 2095的部份，了解到 lab0-c 的 q_delete_mid 也可以使用間接指標簡化，於是著手改善程式碼

在閱讀的過程學習到三元運算子的使用，於是也改善 q_delete_dup 的程式碼

測驗 2

while ((*pred_ptr)->r)
    pred_ptr = &(*pred_ptr)->r;

尋找的是左樹中最右邊的節點，所以只要右子樹存在，就持續走訪，直到不存在右子樹為止

問題：

1. 為何要管理記憶體
2. 結構為何是二元樹
3. block 節點代表的是什麼
4. 何為 free list

對於記憶體配置器而言，需要 free block 的結構來紀錄 free block。為什麼使用二元搜尋樹，因為二元搜尋樹可以使得在結構中搜尋的時間複雜度在 O(logn) ，比起像雙向鏈結串列的搜尋時間複雜度為 O(n) 。二元搜尋樹在插入和移除也比較有效率。

這整段程式碼做的就是經典的二元搜尋樹的移除邏輯。先用 find_free_tree 找到指定大小的記憶體區塊，然後執行移除邏輯，如果它有子樹，則必須以左子樹中最右邊的節點，也就是左子樹最大的元素來取代自己，維持二元搜尋樹的順序性，若只有單邊子樹或沒有子樹，就直接把子樹指標往上遞補或設為 NULL，將該節點「從樹中抽離」。

對於相同大小的空閒記憶體，會被相對應的 free list 連接起來。但隨著程式進行，經過許多次的記憶體配置與釋放，可能造成相同大小的空閒記憶體位置分散，如：

這時如果要配置一個 8 byte 的鏈結串列，則它的空間區域性很差。
因此有分頁（pageing）的功能，確保每個分頁僅存放特定大小類別 (size-class) 的空間，藉此提升空間區域性。

我新增一個分支用來放 quiz 的可執行程式碼和測試程式碼。

commit 5d66640

測試結果：

Initial : 5 7 10 12 15 18 
after removing size=10: 5 7 12 15 18 
after removing size=7: 5 12 15 18

quiz 2

測驗 1

重新做這題，因為我不熟快速排序，所以先把實作理解一遍。
快速排序法的概念是，選取一個 pivot ，然後將所有元素跟 pivot 比大小後分成較大區與較小區。在教大區和較小區一樣再各自選取 pivot 比較並再切分，直到切分到僅含一個元素

這時將較小，pivot ，較大依序連接，這時保證這三個元素一定排序好了。接著就是持續把所有區塊同樣連接起來，最後完成排序

+   pivot = list_fist_entry(head, struct listitem, list);
+   list_del(&pivot->list);

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot->i) < 0)
            list_move_tail(&item->list, &list_less);
        else
            CCCC(&item->list, &list_greater);
    }

    list_quicksort(&list_less);
    list_quicksort(&list_greater);

+   list_add(&pivot->list, head);
+   list_splice(&list_less, head);
+   list_splice_tail(&list_greater, head);
}

在參考陳麒升的程式碼後，發現我原本在 lab0 實作的 shuffle 可以精簡程式碼：

Commit 85a2a23

然而在查詢規格書的過程，規格書在 7.20.1.4 談到 uintptr_t ：

The following type designates an unsigned integer type with the property that any valid pointer
to void can be converted to this type, then converted back to pointer to void, and the result will
compare equal to the original pointer

在 6-3 Conversions 也寫到：

Unless explicitly stated otherwise, conversion of an operand value to a compatible type causes no
change to the value or the representation.

規格書僅保證指標轉型成 uintptr_t 之後再轉回來不會改變其值。似乎沒有關於指向物件的指標轉型成 unsigned int type 之後的行為會不會符合預期，代表這有可能是編譯器自行定義的行為。因為這個問題暫時無法解答，因此我先使用 complier explorer 對比看看 swap 以及 xor 對於交換的差別，發現在 x86-64 gcc 10.5 ，都一樣是 6 個指令的操作

        //swap
        mov     rax, QWORD PTR [rbp-8]
        mov     QWORD PTR [rbp-24], rax
        mov     rax, QWORD PTR [rbp-16]
        mov     QWORD PTR [rbp-8], rax
        mov     rax, QWORD PTR [rbp-24]
        mov     QWORD PTR [rbp-16], rax
        
        //xor
        mov     rax, QWORD PTR [rbp-16]
        xor     QWORD PTR [rbp-8], rax
        mov     rax, QWORD PTR [rbp-8]
        xor     QWORD PTR [rbp-16], rax
        mov     rax, QWORD PTR [rbp-16]
        xor     QWORD PTR [rbp-8], rax

接下來我使用 massif 進行實際監測時間，發現時間和記憶體用量也幾乎一樣

test shuffle xor vs swap

xor:

peak: 3    131,425,898       30,403,856       26,002,620     4,401,236            0

end: 49  2,684,056,382        7,255,264        6,008,408     1,246,856            0

swap:

peak: 3    131,025,900       30,403,856       26,002,620     4,401,236            0

end: 49  2,643,656,561        7,535,088        6,240,124     1,294,964            0

這時我回去看你所不知道的 C 語言：數值系統談到 xor swap 的部份，提及適合的情境是：

1. 指令集允許 XOR swap 產生較短的編碼 (某些 DSP);
2. 考慮到暫存器數量在某些硬體架構 (如 ARM) 非常有限，register allocation 就變得非常棘手，這時透過 XOR swap 可降低這方面的衝擊;
3. 在微處理器中，記憶體是非常珍貴的資源，此舉可降低記憶體的使用量;
4. 在加解密的實作中，需要常數時間的執行時間，因此保證 swap 兩個數值的執行成本要固定 (取決於指令週期數量);

顯然在 shuffle 命令，不符合上述情況，所以我把程式碼改回用 tmp 變數執行交換。
再來我好奇 shuffle 命令中使用 array 紀錄記憶體位址對於效率提升有多少。

# Test performance of shuffle
option fail 0
option malloc 0
new
ih 1 5000
it 2 5000
shuffle 100

使用陣列紀錄記憶體位置

不使用陣列

可以看到不使用陣列的話，記憶體用量是 85% ，但執行時間卻變成 72.6 倍。
這邊體會到massif工具的方便性。