2024q1 Homework2 (quiz1+2)

contributed by < vax-r >

第一週測驗題

程式碼

測驗一

運作原理

程式碼實作非遞迴 quick sort ，並且是在 linked list 而非陣列上操作，此部分和 Optimized QuickSort — C Implementation (Non-Recursive) 不同，運作原理如下。

每一輪排序是利用 L 及 R 分別指向被排序之鍵結串列的第一個節點與最後一個節點，每次挑選最左邊之節點為 pivot ，利用節點 p, n 走訪整個串列。
p 會存取下一個要走訪的節點，避免因為 n 的移除而無法完成串列的走訪。
過程當中將若 n->value > pivot->value 則將節點 n 加入 right 串列，反之則加入 left 串列。

接下來將當前 begin[i], end[i] 分別設為 left 串列的頭與尾， begin[i+1], end[i+1] 則是直接放入 pivot 節點， begin[i+2], end[i+2] 則是將 right 串列的頭與尾放入。 下一次 iteration 就會對目前的 right 串列進行排序。 right 串列全部排列完成才會對 left 串列進行排序。過程如下圖。

假設原本的鍵結串列如下

digraph structs {
    node[shape=plaintext];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    p [fontcolor="black"];
    
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
    }
    pivot -> struct0;
    L -> struct0;
    R -> struct4;
    p -> struct1;
}

隨著 p 逐漸往右邊行進，將大於 pivot->value 的節點放入 right ，將其餘節點放入 left 。

digraph structs{
    node[shape=plaintext];
    left [fontcolor="blue"];
    pivot [fontcolor="red"];
    right [fontcolor="blue"];
    node[shape=box]
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    pivot -> struct0;
    left -> struct2;
    struct2 -> struct3;
    struct3 -> struct4;
    right -> struct1;
}

接著left 被放入了 beg[i], end[i] 中取代了原本的整個佇列的位置，right 頭尾被放入 beg[i+2], end[i+2] 在 i += 2 後會嘗試進行排序，而此時 beg[i] == end[i] 會成立，代表此串列只有一個節點，此時就將該節點加入 result 。接著 i-- 後會將上圖 pivot 節點加入 result ，接著對上圖 left 串列進行排序直到整個串列排序完成。

由以上分析可以發現此排序演算法的幾個特質

• 總是拿串列最左邊之元素當 pivot
• 跟 pivot->value 比較後將串列分為 left, right ，總是優先選擇 right 來持續進行排序

quick sort 在 pivot 的選擇上非常重要，若挑選適當的 pivot 能夠使串列平均的分割，從而避免 worst case 的發生。
而選擇優先排序哪一邊的串列也對效率有衝擊，若每次都選則較短長度的串列進行排序則會比較慢， 詳細可參閱 Optimized QuickSort — C Implementation (Non-Recursive) 。

改進方法

我認為可以改之處有數點

• max_level 是否真的需要 \(2 \times n\) 這麼大？何時會讓 begin, end 真的用到這麼多空間？ 能否進一步縮減甚至達到 \(O(1)\) 的空間複雜度？
• 目前實作的鍵結串列是單向鍵結串列，修改成雙向鍵結串列
• pivot 的挑選不該總是挑選開頭的節點，若試圖將一個已排序成 descending order 的鍵結串列重新排序成 ascending order ，這種挑選 pivot 的方式會造成 worst case 的產生。但考慮到鍵結串列為非連續記憶體的特性，若希望不犧牲效能的方法達到隨機挑選 pivot 該怎麼做？

題目中 quicksort 實作為 begin, end 配置 \(2 \times n\) 的連續記憶體空間，若將 count 設置成更大的數字會造成 Segmentation fault ，我在 quicksort() 函式當中以變數 reach_i 紀錄每次進行 quicksort() 時 i 最大會到多少，在 count 固定為 100000 的情況下 reach_i 執行 10 次的結果皆是 46 ，也就是 begin, end 陣列各自配置 20000 * sizeof(node_t) 個 bytes 卻只用到其中 46 個 bytes !

我設計小實驗分別計算 count 從 10 變化到 100000 時每次 reach_i 的數目，將 main() 函式改寫如下

int main(int argc, char **argv)
{
    node_t *list = NULL;

    for (int i = 10; i < 1000000; i *= 10) {
        size_t count = i;

        int *test_arr = malloc(sizeof(int) * count);

        for (int i = 0; i < count; i++)
            test_arr[i] = i;
        shuffle(test_arr, count);
        while (count--)
            list = list_construct(list, test_arr[count]);

        quick_sort(&list);
        assert(list_is_ordered(list));
        list_free(&list);

        free(test_arr);
    }

    return 0;
}

進行五次 quicksort 之後得出以下結果

$ ./main
size : 10, deepest level : 4
size : 100, deepest level : 14
size : 1000, deepest level : 26
size : 10000, deepest level : 38
size : 100000, deepest level : 48

隨著 size 每次成長 10 倍的變化，排序使用到的堆疊最大深度成長只有多 10 個左右，排序的節點越多，為堆疊配置 2 * n * sizeof(node_t) 的方式顯得越浪費。我作出改進的方法是計算該 list 的節點數目以十進位表示有幾個位元，並將位元數乘以十作為堆疊空間。

+int count_level (int n) {
+    int i = 0;
+    while (n /= 10)
+        i++;
+    return i ? (i+1) * 10 : 10;
+}

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
-    int max_level = 2 * n;
+    int max_level = count_level(n);

如此一來不僅節省記憶體用量，配置的記憶體空間被使用到的比例也更大，對節點數量超過 1000000 以上的鍵結串列也能順利進行排序，不會因為陣列空間過大無法分配造成 Segmentation fault。以下為節點個數從 10 到 10000000 的運行結果。

$ ./main
size : 10, max_level : 20, deepest level : 4, cpu clock : 2
size : 100, max_level : 30, deepest level : 14, cpu clock : 9
size : 1000, max_level : 40, deepest level : 26, cpu clock : 113
size : 10000, max_level : 50, deepest level : 38, cpu clock : 1958
size : 100000, max_level : 60, deepest level : 48, cpu clock : 27733
size : 1000000, max_level : 70, deepest level : 66, cpu clock : 658785
size : 10000000, max_level : 80, deepest level : 76, cpu clock : 11872240

能否更進一步，縮減排序使用到的 deepest level ? 切割平均的 quick sort 應該較能使 deepest level 降低，而切割是否平均重點就在 pivot 的挑選。如果是在陣列上運作，因為有 indexing 的協助，我們可以輕易的隨機選擇 pivot ，不過這是在鍵結串列上進行的 quick sort ，我想到可以利用 shuffle 來避免 worst case ， main 函式中一開始就是利用 shuffle 來將數列打亂，一開始我認為可以在 quick_sort 每次進行排序的時候對要排序的串列進行 shuffle ，如此一來就算挑選的 pivot 永遠都是最左邊的節點，事實上因為先打亂後再拿 pivot ，就可以看成是隨機挑選 pivot ，但這樣做的成本太高，例如 Fisher-Yates shuffle algorithm 的時間複雜度可能達到 \(O(n^2)\) ，引進這方法的結果會讓每次排序都是 worst case 的時間複雜度，因此我想到的替代方案是隨機挑選一個節點並和 head 做交換，如此一來最糟糕的時間複雜度也是 \(O(n)\) 。實際方法如下。

void random_pivot(node_t **head) {
    int r = rand() % list_length(head);
    node_t **cur = head;
    for (int i = 0; i < r - 1 && (*cur)->next; i++)
        cur = &((*cur)->next);

    node_t *tmp = (*cur)->next;
    (*cur)->next = (*head);
    (*head) = tmp;
}

引入此方法進行排序，同樣也是從節點個數 10 開始每次乘以 10 一直到一千萬。

$ ./main
size : 10, max_level : 20, deepest level : 4, cpu clock : 4
size : 100, max_level : 30, deepest level : 8, cpu clock : 7
size : 1000, max_level : 40, deepest level : 8, cpu clock : 30
size : 10000, max_level : 50, deepest level : 10, cpu clock : 224
size : 100000, max_level : 60, deepest level : 14, cpu clock : 4003
size : 1000000, max_level : 70, deepest level : 22, cpu clock : 90759
size : 10000000, max_level : 80, deepest level : 30, cpu clock : 900976

可以看到使用到的堆疊深度進一步的縮減，並且 cpu clock 在節點數量越多的情況，相比沒有進行 random_pivot 的版本，縮減許多，若讓測資固定是已排序成 descending order 的鍵結串列，也就是會引發 worst case 情況的測資，這兩個方法又有何不同呢？
我們將 main 函式進行以下改寫，使得每次送進 quick_sort 的測資都是已排序成 descending order 的鍵結串列，並且 count_level 函式暫時取消並改回配置 2 * n 的記憶體空間。

        for (int i = 0; i < count; i++)
-            test_arr[i] = i;
+            test_arr[i] = (count - i);
-        shuffle(test_arr, count);

結果如下:

size : 10, max_level : 20, deepest level : 10, cpu clock : 4
size : 100, max_level : 200, deepest level : 100, cpu clock : 35
size : 1000, max_level : 2000, deepest level : 1000, cpu clock : 2598
size : 10000, max_level : 20000, deepest level : 10000, cpu clock : 241023
size : 100000, max_level : 200000, deepest level : 100000, cpu clock : 26872526
Segmentation fault (core dumped)

原本的 quick_sort 實作在 worst case 情況下每次都需要使用到 n 的堆疊深度， cpu clock 的數量也相較 average case 成長了約 2 倍。
此時我們重新引入 random_pivot 函式，並且也不再為堆疊配置 2 * n 大小的記憶體空間，觀察執行結果。

size : 10, max_level : 20, deepest level : 2, cpu clock : 6
size : 100, max_level : 30, deepest level : 6, cpu clock : 3
size : 1000, max_level : 40, deepest level : 10, cpu clock : 22
size : 10000, max_level : 50, deepest level : 12, cpu clock : 329
size : 100000, max_level : 60, deepest level : 14, cpu clock : 1985
size : 1000000, max_level : 70, deepest level : 12, cpu clock : 57822
size : 10000000, max_level : 80, deepest level : 14, cpu clock : 597349

在原本會造成 quick_sort 產生 worst case 的測試案例底下，引入 random_pivot()函式不僅讓使用到的堆疊深度大幅縮減， cpu clock 數量更是呈現可觀的縮減，成功避免 worst case 情形發生。

利用 Linux Kernel API 改寫

引入 list.h 之後，將 node_t 結構體改寫為以下形式

typedef struct __node {
-    struct __node *left, *right;
-    struct __node *next;
    long value;
+    struct list_head list;
}

同時改寫對應的鍵結串列操作方式，並注意現在處理的都是雙向鍵結串列而非原本的單向鍵結串列。重點的 quick sort 改寫為以下

void quick_sort(struct list_head **head)
{
    clock_t time = clock();

    if (!(*head) || list_empty(*head))
        return;

    int n = list_length(*head);
    int i = 0;
    int max_level = count_level(n);

    struct list_head *begin[max_level];
    begin[0] = *head;
    for (int i = 1; i < max_level; i++)
        begin[i] = list_new();
    struct list_head *result = list_new();
    struct list_head *left = list_new(), *right = list_new();

    int deepest_level = i;
    while (i >= 0) {
        struct list_head *L = begin[i]->next, *R = begin[i]->prev;
        if (L != R) {
            random_pivot(begin[i]);
            node_t *pivot = list_remove_head(begin[i]);

            node_t *entry, *safe;
            list_for_each_entry_safe (entry, safe, begin[i], list) {
                list_del(&entry->list);
                if (entry->value > pivot->value) {
                    list_add(&entry->list, right);
                } else {
                    list_add(&entry->list, left);
                }
            }

            list_splice_init(left, begin[i]);
            list_add(&pivot->list, begin[i + 1]);
            list_splice_init(right, begin[i + 2]);

            i += 2;
            deepest_level = deepest_level < i ? i : deepest_level;
        } else {
            if (list_is_singular(begin[i]))
                list_splice_init(begin[i], result);
            i--;
        }
    }

    for (int i = 0; i < max_level; i++)
        list_free(begin[i]);
    list_free(left);
    list_free(right);

    *head = result;

    time = clock() - time;
    printf("size : %d, max_level : %d, deepest level : %d, cpu clock : %ld\n",
           n, max_level, deepest_level, time);
}

重點變更是不再配置 end 堆疊，因為 linux kernel 風格的鍵結串列為雙向鍵結串列，因此直接使用 head->prev 即可找到鍵結串列的最後一個節點。
完整變更在 Introduce linux kernel list API in quick sort

測驗二

閱讀測驗二 的題目敘述，嘗試解析 Timsort 的運作原理與重點

運作原理

Timsort 有以下幾個重點需要注意

• run 代表的是連續單調遞增的一段子串列， 程式碼當中由 find_run 來尋找這樣的子串列，值得注意的是 find_run 若找到一個單調遞減的子串列，則將結果回傳的時候由 head 開始一直往 next 的方向行走的話反而是一個單調遞增的子串列。另外這個子串列的長度會存在 head->next->prev 當中 （參閱 C99 規格書當中關於 pointer to integar 的轉型）。
• 每次 find_run 後回傳一個 struct pair 結構體 head 指向此 run 的開頭， next 則指向剩餘鍵結串列的開頭。不同 run 的開頭 head 會彼此串接在一起，新的 run 會接在已經組織好的 run 串列尾端。
• merge_collapse 當中檢查 tp 前三個 run 是否滿足以下條件，若不滿足則挑選其中兩個進行合併
  • tp->prev->prev 長度大於 tp->prev 和 tp 長度總和
  • tp->prev 長度大於 tp
• 此處使用的 merge 和 /lib/list_sort.c 使用的相同，合併的時候不需要額外配置空間，此部分比起 測驗二 的題目敘述解說之 timsort 合併更好
• 此實作當中並未實作 Galloping mode 的合併方法，而是每次合併時按照傳統 merge sort 方法一個個元素檢查合併。

改進方法

實作 Galloping mode
我將 Galloping mode 用以下的方式實作，不過結果卻讓排序過程的比較次數不減反增，應探討實作當中哪裡有問題，並且 Galloping mode 在尋找 \(B_0\) (或 \(A_0\)) 應該插入在 \(A\) 當中何處時還是得經過比較，應思考是否有不須比較就能找到位置的方法。

static struct list_head *merge_galloping(void *priv,
                                         list_cmp_func_t cmp,
                                         struct list_head *a,
                                         struct list_head *b)
{
    struct list_head *head;
    struct list_head **tail = &head;

    for (; a && b;) {
        if (cmp(priv, a, b) <= 0) {
            while (a && cmp(priv, a, b) <= 0) {
                *tail = a;
                tail = &a->next;
                a = a->next;
            }
            *tail = b;
            tail = &b->next;
            b = b->next;
        } else {
            while (b && cmp(priv, a, b) > 0) {
                *tail = b;
                tail = &b->next;
                b = b->next;
            }
            *tail = a;
            tail = &a->next;
            a = a->next;
        }
    }

    *tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
    return head;
}

我本來不解為何 Galloping mode 會表現的比普通的 merge 還要差，原本認為兩個準備被合併的 run 他們的資料分布都是單調遞增，但仔細閱讀 Galloping mode during merge 後，文中提到要進行 Galloping mode 需要設定一個 Galloping threshold ，而某個 run 的大小如果達到該 threshold 則隱含著該 run 存在許多連續的數字 ，不只是遞增，而是數字必須連續，如此一來才能做到不比較就找到 \(B_0\) 在 \(A\) 當中該放入的位置。

When this number reaches the minimum galloping threshold (min_gallop), Timsort considers that it is likely that many consecutive elements may still be selected from that run and switches into galloping mode.

但是文中也提到要找到該位置得進行 binary search ，這在我們原本實作的 linked list 版本 timsort 是難以做到的，因為非連續記憶體不支援 indexing 也就無法隨機存取，只能照順序走訪節點。
另外 Galloping threshold 的大小一開始會設定 7 ，若該次合併並未使用 Galloping mode 則會把 Galloping threshold 加一，這種行為在隨機資料分布的情況下會使得 Galloping threshold 變得很大從而不可能執行到 Galloping mode 的合併。

設定 min run
原先實作中的 find_run 並不會將 run 的長度進行控制，理論上要靠近2的冪或正好是2的冪，才能讓 merge 的過程最佳化。
我採用的方式是設定 MIN_SIZE 為 64 ，若 find_run 的長度 len 使得 MIN_SIZE - len >= 3 則利用 insertion sort 的方式將 next 的元素逐個插入原先的 run 當中直到 MIN_SIZE - len < 3 。不過結果是比較次數大增，效能也沒有改進。

整合 timsort 進入 lab0-c

Implementation of a novel version merge sort

第二週測驗題

測驗一

原理解釋

這個程式主要利用 dfs 方法來重建二元樹，並且一開始先在 buildTree 將 inorder 節點建立一個 hash table 。 而在 dfs 函式當中利用 find 尋找當前 preorder 節點在 inorder 陣列當中的位置。
再來就是將當前建立的節點的左子樹指派為
dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size)
右子樹指派為 dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder, idx + 1, in_high, in_heads, size)
以下解釋這兩個 expression 的原理。
首先我們知道 dfs 存取順序實際上就是 preorder 順序，因此當前存取節點就會是 preorder[pre_low] ，接著透過 find 找到 preorder[pre_low] 這個節點在 inorder 當中的位置 idx 後，我們知道在 inorder 當中位於 in_low ~ (idx-1) 的節點通通位在 idx 的左子樹當中， (idx+1) ~ in_high 全部位於 idx 的右子數當中，所以我們才會看見 tn->left 呼叫的 dfs 傳入的 in_low = in_low 且 in_high = (idx - 1) ， tn->right 呼叫的 dfs 傳入的 in_low = (idx + 1) 且 in_high = in_high 。

接著 dfs 過程中存取完當前節點，下一個就會存取當前節點的左子樹，假設左子數共有 left_size 個節點，右子數有 right_size 個節點，則在 preorder 當中， preorder[pre_low + 1] ~ preorder[pre_low + left_size] 就會是屬於左子樹節點， preorder[pre_high - right_size + 1] ~ preorder[pre_high] 就會是右子樹的節點，因此關鍵就在算出 left_size 和 right_size 。而這可以輕易透過 idx 從 inorder 當中得到，因為在 inorder 當中位於 idx 左側之節點全都屬於左子樹，因此 left_size = idx - in_low ，而同理可證 right_size = in_high - idx ，將這兩個值帶回式子中可得左子樹的 preorder 範圍是 (pre_low + 1) ~ (pre_low + idx - in_low) ，右子樹的 preorder 範圍則是 (pre_high - (in_high - idx - 1)) ~ pre_high 。

實作測試程式

Construct binary tree basic setup and test code

改進程式碼

我認為可改進之處有數點

• hlist 使用之必要性
  原本程式碼實作中使用 hlist 做為找到 preorder 走訪過程中的節點在 inorder sequence 中的 index 用，但此處涉及取餘數之運算並且此 hash function 在某些資料分布（例如都是 size 倍數）的情況下會導致大量碰撞，還不如捨棄 hlist 直接使用原先的 inorder 陣列直接找尋對應節點的 index 更快，還能節省 hlist 佔用的空間。

static int find(int num, int size, const int *inorder)
{
    for (int i = 0; i < size; i++) {
        if (inorder[i] == num)
            return i;
    }
    return -1;
}

• 遞迴 dfs 的實作可改進為非遞迴
  preorder sequence 即是 dfs seqeunce ，再利用遞迴走訪並建立二元樹是多此一舉，利用一個迴圈逐個走訪 preorder 陣列中的元素並進行對應的節點新增即可

針對上述想法進行實驗，首先比較在隨機產生高度為 100 之二元樹情形下，使用 hlist 或直接在 inorder 陣列中尋找 index 何者較優，比較方法為各自執行五次並取 cpu clock 之平均值。

hlist version : ( 2 + 3 + 2 + 2 + 4 ) / 5 = 2.6
non-hlist version : ( 2 + 3 + 3 + 2 + 2) / 5 = 2.4

就結果而言並沒有明顯差異，但在記憶體使用量上 hlist version 會因為要儲存 struct hlist_head 所以使用更多記憶體。

Linux 核心 cgroups 相關程式碼

閱讀 Control Groups 並記錄了解相關內容 。 cgroups 當中也有利用到 hash table 來加快找到對應 css_set 的速度，我認為目前使用的 hash 方式非常特別，可以在 /kernel/cgroup.c 找到。

位於 /include/linux/cgroup.h 當中的 css_next_descendant_pre 。
css_for_each_descendant_pre 此巨集會利用 css_next_descendant_pre 對指定的 css 進行 pre-order traversal walk ，註解當中有提到，若某個 css 呼叫 subsystem API css_online() ，則 pre-order walk 保證會走訪到此節點，如果某個 css 節點在整個走訪過程當中尚未完成 css_online() 或已經完成 css_offline() ，則該節點可能在走訪過程中突然出現。註解中提到此處保證親代節點的狀態更新對於 walking order 來說都是可見的且只要 inheriting operations 對於相同的節點是 atomic 的，則多個 racing 也保證會有對的結果，我不理解此處的意思。

#define css_for_each_descendant_pre(pos, css)				\
	for ((pos) = css_next_descendant_pre(NULL, (css)); (pos);	\
	     (pos) = css_next_descendant_pre((pos), (css)))

其中 css_next_descendant_pre 會回傳 pos 在 pre-order 順序中的下一個元素。同時觀察 css_next_descendant

struct cgroup_subsys_state *
css_next_descendant_pre(struct cgroup_subsys_state *pos,
			struct cgroup_subsys_state *root)
{
	struct cgroup_subsys_state *next;

	cgroup_assert_mutex_or_rcu_locked();

	/* if first iteration, visit @root */
	if (!pos)
		return root;

	/* visit the first child if exists */
	next = css_next_child(NULL, pos);
	if (next)
		return next;

	/* no child, visit my or the closest ancestor's next sibling */
	while (pos != root) {
		next = css_next_child(pos, pos->parent);
		if (next)
			return next;
		pos = pos->parent;
	}

	return NULL;
}

root 會是第一個存取的節點，接下來利用 css_next_child 來尋找接續存取的節點 。值得注意的是此處並沒有看到向 left 或 right 存取這類的函式呼叫，而是先走訪到後一個節點，之後再利用 pos = pos->parent 做 back track 並繼續尋找下一個子節點。此處應探討 css_next_child 如何區分已存取過的節點。

css_next_child 在 /kernel/cgroup/cgroup.c 實作，此部分實作和 RCU 有很大的關聯，但我目前尚不了解 RCU ，無法理解此處的註解。

css_for_each_descendant_pre() 被大量用在有使用到 cgroup 的各個程式碼當中，通常會定義另一個巨集並把它當成 callback 函式使用。

測驗二

原理解釋

這個 LRU cache 的實作利用 hlist 來加速讀取快取的時間成本，相較傳統實作 LRU 可能直接使用一個鍵結串列並在每次讀取或寫入時需要嘗試走訪整個鍵結串列 (造成 worst case 時間複雜度會達到 \(O(n)\)) ，此實作如果 hash function 的選擇恰當，能夠使讀取及寫入時間複雜度貼近 \(O(1)\) (尚需實驗證明，採用 lab0-c 的 dudect 或許是可行方法)。以下解說此快取設計構造以下讀取、寫入的方式。

LRUCache 結構體

• capacity : 紀錄此 cache 最多能記錄幾筆資料
• count : cache 當前紀錄的資料筆數
• dhead : 用來串接所有資料的雙向鍵結串列
• hhead : 處理碰撞使用的 hlist 結構體陣列

digraph structs{
    node [shape="record"];
    rankdir = "LR"
    subgraph cluster_a
    {
        label = "LRUCache";
        struct1 [label="capacity"];
        struct2 [label="count"];
        struct3 [label="dhead"];
        struct4 [label="<head>hhead[0]|hhead[1]|...|hhead[capacity - 1]"];
        struct3 -> struct3 [label="next"];
        struct3 -> struct3 [label="prev"];
        
    }
}

寫入 put
對快取進行寫入時，首先將 key 送入 hash function 當中得到一個 hash 值，並尋找對應 hhead 當中的欄位是否已經存在該 key ，若有則更新 value 值，若沒有則先檢查快取的容量是否已滿，如果是的話就刪除快取當中的 least used node ，也就是 dhead 鍵結串列的最後一個節點，同時把它從 hhead 當中移除。 若還沒滿則直接新增一個節點。
注意結果都是讓被更新、新增的節點被放置到 dhead 最前端，也放到對應 hhead column 的最前端。由此我們可以發現 dhead 當中節點放置順序就代表節點被更新的時間，擺放得越前面代表越近期進行操作，越後面則代表越久。

讀取 get
相較普通的 LRU cache 實作，引入 hlist 後，我們先將 key 丟入 hash function 進行計算得到對應的 hash 值，此時理想上我們要尋找的節點就會在 hhead[hash] 的第一個節點，但這取決於我們 hash function 選擇的好壞。
取得 hash 值後，我們在對應的 hhead[hash] 所指向的鍵結串列進行搜索，若找到該節點則回傳，找不到則回傳 -1 。此處正好體現使用 hlist 代表我們的優勢，若僅僅使用 dhead 一個雙向鍵結串列來儲存所有資料，每次讀取時都必須走訪此串列， worst case 甚至得走訪所有節點，時間複雜度來到 \(O(n)\) ，而引入 hlist 後，只要 hash function 挑選適當，可以很大程度避免 worst case 的發生。

實作測試程式

LRU basic set up and testing program

測試的概念建立在每次對 LRU cache 當中某個欄位進行操作後，代表該欄位的節點都應該移動到鍵結串列最前端，如此一來維持鍵結串列節點順序也代表何時被操作。

改進方法

在測試過程中發現進行 get 操作後，並不會將對應的 hhead 串列當中的節點移動到該串列最前方，於是我更正此部分實作。不過也應該思考， hhead 每個欄位所代表之節點是否也有必要嚴格遵守此規範，我推論在 hash function 選擇恰當時，碰撞發生的機會很少， hhead 當中每個串列的節點數量理應也很少，故進行走訪的成本很低，或許不必遵守此規範 （further experiments are needed) 。

int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each(pos, &obj->hhead[hash])
    {
        LRUNode *cache = list_entry(pos, LRUNode, node);
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead);
+            hlist_del(&cache->node);
+            hlist_add_head(&cache->node, &obj->hhead[hash]);

另外在進行 put 操作時，若發現想寫入的 key 已經存在，除了更新 value 並且把節點移動到 dhead 最前端，也應該把節點移動到 hhead[hash] 最前端，所以我進行以下更動。

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *cache = NULL;
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each(pos, &obj->hhead[hash])
    {
        LRUNode *c = list_entry(pos, LRUNode, node);
        if (c->key == key) {
+            hlist_del(&c->node);
+            hlist_add_head(&c->node, &obj->hhead[hash]);

另外 hash function 目前是選擇寫死在程式當中，透過 function hook 或者 callback function 的形式達到更好的隔離與封裝性，對於維護與可讀性都能做更好的提升，如下。

static struct hlist_head *lRU_hash_slot(LRUCache *obj, int key)
{
    return obj->hhead + (key % obj->capacity);
}

commit a7f4984

Linux 核心 LRU 相關程式碼

drivers/md/dm-bufio.c

Clock Algorithm
Page Replacement Algorithm
Clock algorithm 會利用一個 circular list 來代表記憶體，而 hand 這個指標會指向最近一個操作的 page frame 。當 page fault 發生時，第 R 個 reference bit 會被檢查，如果 R == 0 則 new page 會被放入 hand 指向的位置，然後 hand 會往下一個位置移動，若 R == 1 則 R 會被重新設置為 0 ，然後 hand 會往下一個位置移動並檢查對應的 R bit 是否為 0 ，重複此過程直到某個 page 被替換。

程式碼解析
主要的結構體有三個，此處主要介紹 struct lru

struct lru {
	struct list_head *cursor;
	unsigned long count;

	struct list_head iterators;
};

接下來是 insertion 的部分，首先我疑問的點是為何新增的 entry 不是將 reference bit 設為 1 ？

/*
 * Insert a new entry into the lru.
 */
static void lru_insert(struct lru *lru, struct lru_entry *le)
{
	/*
	 * Don't be tempted to set to 1, makes the lru aspect
	 * perform poorly.
	 */
	atomic_set(&le->referenced, 0);

	if (lru->cursor) {
		list_add_tail(&le->list, lru->cursor);
	} else {
		INIT_LIST_HEAD(&le->list);
		lru->cursor = &le->list;
	}
	lru->count++;
}

我在此處認為有一個可以改進的空間，也就是它在處理 lru->cursor 是否為空的部分把 lru->cursor == NULL 視為 special case 處理。我認為有可行的改進方案也就是在 lru_init 時將 lru->cursor 事先利用 INIT_LIST_HEAD 初始化，並把它視為環狀鍵結串列的 head （和 lab0-c 的雙向佇列類似的設計， head 僅是用來指向該串列的指標，和成員節點不同）。

(TODO: 將剩餘函式理解並嘗試提出改進)

另外我在 lib/lru_cache.c 當中發現和此測驗 cache 設計十分相似的 struct lru_cache 。並且在函式 lc_create 當中發現該程式碼並未對新配置的 struct hlist_head 進行初始化，若在不同編譯器或硬體架構底下可能會因沒有初始化而出錯，因此我向維護者發送了一個 patch 連結如下。

patch

探討 LRU cache 在 Linux 核心當中的實作 linux_lru，這個 LRU cache 實作被運用在 DRBD 當中。注意到 Linux 核心 使用的 hash function 如下

static struct hlist_head *lc_hash_slot(struct lru_cache *lc, unsigned int enr)
{
	return  lc->lc_slot + (enr % lc->nr_elements);
}

hash function 的挑選、還有此處用到 % operator ，或許有更好的替代方案。

測驗三

原理解釋

我對於 bitwise operation 的理解非常低落，首先我參閱 Other Built-in Functions Provided by GCC 來理解一些 gcc 提供的內建 bitwise 操作函式。

• __builtin_constant_p
  可以判斷給入的參數 (一個 expression) 是否為 compile-time constant ，如果是的話此函式會回傳 1 ，編譯器可以對該 expression 做 constant-folding 。並且該 expression 的 side-effects 會被丟棄，應該說具有 side-effects 的 expression 就會使此函式回傳 0 ，代表 gcc 無法判斷此 expression 是否為 compile-time constant 。

GENMASK(h, l) 巨集作用可以拆解如下，首先 ((~0UL) - (1UL << (l)) + 1) 是讓 64 位元當中由右數來前 l 個位元為 0 ，剩下皆為 1 。後半部的 (~0UL >> (BITS_PER_LONG - 1 - (h))) 是讓 64 個位元全為 1 的 ~0UL 向右位移 BITS_PER_LONG - (1 + h) 個位元，結果會是從右數 h + 1 個位元都為 1 ，剩下高位皆為 0 ，所以若 l + 1 + h + 1 <= 64 則此巨集會是 0 ，若大於 64 則在交集處的位元為 1 ，其他為 0 。
因此 GENMASK(size - 1, 0) 的結果會是由右數來 size 個位元皆為 1 ，剩下 64 - size 個位元為 0 。

__ffs(word) 尋找該 word 由右數來第一個 set bit 。

hweight_long(w) 利用 __const_hweight8 每 8 個 bits 檢查 w 當中總共有幾個 set bits

若給進 find_nth_bit 的 size 能使 small_const_nbits(size) 成立，則利用 GENMASK(size - 1, 0) 尋找該 addr 前 size 個 bit 。若有值則利用 fns(val, n) 尋找 val 當中第 n 個 set bit 。如果 size 並非 compile-time constant 則利用 FIND_NTH_BIT 每 64 bits 檢查有幾個 set bits ，如果 FETCH 當中的 set bits 總數 (經由 hweight_long 計算) 大於 nr 則利用 fns(tmp, nr) 尋找在這 64 bits 區塊當中第 nr 個 set bit 是在第幾個位元，並加上 idx * BITS_PER_LONG 也就是前面有幾個位元，加總的總數要是小於 size 則成功找到，若大於 size 則回傳 size 表示失敗。注意到如果 size 並非 BITS_PER_LONG 的整數倍，則利用 BITMAP_LAST_WORD_MASK 來過濾出 FETCH 最後一個區塊像以上做法送入 fns 尋找這個資料區塊的第 nr 個 set bit 。

Linux kernel 應用案例

位於 include/linux/cpumask.h 的 cpumask_nth 可以用來取得 cpumask 當中第 n 個 CPU

/**
 * cpumask_nth - get the Nth cpu in a cpumask
 * @srcp: the cpumask pointer
 * @cpu: the Nth cpu to find, starting from 0
 *
 * Return: >= nr_cpu_ids if such cpu doesn't exist.
 */
static inline unsigned int cpumask_nth(unsigned int cpu, const struct cpumask *srcp)
{
	return find_nth_bit(cpumask_bits(srcp), small_cpumask_bits, cpumask_check(cpu));
}

在 Linux kernel 當中利用 struct cpumask 這個 bitmap 來代表系統當中 CPU 的集合，每個 bit 代表一個 CPU ，只有 nr_cpu_ids 個位元是有效的。

不過我沒有找到該函式應用在 CPU affinity 相關例子，只有找到他在 kernel/trace/trace_events_filter.c
當中的應用。

CPU affinity 則是在 kernel/sched/core.c 中有找到 sched_getaffinity() 與 sched_setaffinity 當中利用到 cpumask_and() 。

bitwise operation 補強

Integer Division by Constant

摘錄自 Hacker's Delight
首先以無號數除法為例，我們想要在不使用 /, % 甚至 * 等 operators 的前提下進行除法，其中一種做法是先計算除數的倒數的估計值 ( the reciprocal of the divisor ) 。但倒數有可能會是無窮小數，還有 >> operator 會造成被除數位元流失，所以這僅僅是一個估計值 (例如 \(1/3, 1/9\) ) 。
另外餘數與商數的計算也較為特別，會先計算出一個商數的估計值，接著再用該商數算出一個餘數，接著再使用該餘數除以除數得到一個修正值，把該修正值加回原本估計的商數就可以得到確切的商數。

以下以整數除以 3 為例，首先計算 3 的倒數 1/3 ，以 binary representation 來表示會是 0.01010101010101010101010101010101 。
則 \(\cfrac{n}{3} = n * \cfrac{1}{3}\) 也可以表示成
(n >> 2) + (n >> 4) + (n >> 6) + ... + (n >> 30) + (n >> 32) 並且 n >> 32 一定為零，所以商數即是
q = (n >> 2) + (n >> 4) + (n >> 6) + ... + (n >> 30)
又可以進一步化簡為以下形式

q = (n >> 2) + (n >> 4);
q = q + (n >> 4);
q = q + (n >> 8);
q = q + (n >> 16);

餘數就可以很直觀的利用 r = n - q * 3 計算而得，並且由於此時的 q 只是估計值並且絕不會大於真正的商數，所以 r 不會是負數。另外在此處，若除數為 d ，商數 q 的最小可能值為 k 則 r 的可能範圍為 k * d ~ k * d + d - 1 。（為何不是 0 ~ d - 1 ? 原文是說 q too low by k ，我推測意思是 q 有 k 個位元被遺棄)
所以以上計算 q 的方法用到五個 >> 因此 q is too low by at most 5 ，所以 k == 5 ，因此餘數至多會是 5 * 3 + 2 = 17 。到此處我十分好奇餘數怎麼可能比除數大，於是我依照上述程式進行實驗

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

int main(void)
{
    unsigned q, r;
    unsigned min = UINT_MAX, max = 0;
    for (unsigned i = 0; i < 100000000; i++) {
        unsigned n = i;
        q = (n >> 2) + (n >> 4);
        q = q + (q >> 4);
        q = q + (q >> 8);
        q = q + (q >> 16);

        r = n - q * 3;

        max = max > r ? max : r;
        min = min < r ? min : r;
    }

    printf("the maximum of remainder is %u\n", max);
    printf("the minimum of remainder is %u\n", min);

    return 0;
}

執行輸出:

the maximum of remainder is 14
the minimum of remainder is 0

結果居然真的能使餘數大於除數。
並且我們需要利用此餘數計算商數的 correction ，因此需要進行 \(\cfrac{r}{3}\) 的運算。
本文在此處將 r 乘上某個 a/b 的值並且該 a/b 需要略大於 1/3 ，例如文中使用 11/32 ，所以最終確切的商數會是 q = q + (11 * r >> 5) 。
文中最後提及若想避免 11 * r >> 5 使用到的乘法運算，可以將該行換成 q + ((r + 5 + (r << 2)) >> 4) ，也就是 (5 * r + 5) / 16 (不理解這和 11 * r >> 5 哪裡一樣) 。

編譯器產生的指令序列不同。考慮以下程式碼:
int f1(int r) { return 11 * r >> 5; }
int f2(int r) { return (r + 5 + (r << 2)) >> 4; }
在 Arm64 平台抑制最佳化 (即 -O0)，對應的指令序列是:

• f1

	mov	w0, 11
	mul	w0, w1, w0
	asr	w0, w0, 5

• f2

	add	w1, w0, 5
	ldr	w0, [sp, 12]
	lsl	w0, w0, 2
	add	w0, w1, w0
	asr	w0, w0, 4

注意到 f1 指令序列中的 mul 指令。你可在 x86-64 進行類似的實驗並對照 Instruction tables，計算整體的延遲以及對 CPU 管線的影響。

Image Not Showing Possible Reasons

• The image file may be corrupted
• The server hosting the image is unavailable
• The image path is incorrect
• The image format is not supported

Learn More →

jserv

如果將以上程式進行以下改進

- n = (n >> 2) + (n >> 4);
+ q = (n >> 1) + (n >> 3);
  q = q + (q >> 4);
  q = q + (q >> 8);
  q = q + (q >> 16);
+ q = q >> 1;
  q = n - q * 3;

餘數的最大值會因此變小（依舊不解，甚至進行 6 次 shift ），進而能使 1 / 3 的估計值使用更小的值。

Remainder by Summing digits

如何不使用任何除法就算出某數除以另一個數的餘數呢？如果除數符合 \(2^k \pm 1\) 則可以利用以下的概念來達成這個目的。
首先複習一下基本數學定理
若 \(a \equiv b (mod \ \ m)\) 且 \(c \equiv d (mod \ \ m)\) ，則 \(a + c \equiv b + d (mod \ \ m )\) 且 \(ac \equiv bd (mod \ \ m )\)
證明方法很簡單只需要假設 \(a = q_a m + r_1, b = q_b m + r_1, c = q_c m + r_2, d = q_d m + r_2\) 再進行運算即可。
以除數為 3 為例， \(1 \equiv 1 (mod \ \ 3)\) 且 \(2 \equiv -1 (mod \ \ 3)\) ，將後者不斷的乘上前者可得
\(2^k \equiv \begin{cases} 1 (mod \ \ 3), \ \ k \ \ even\\ -1 (mod \ \ 3), \ \ k \ \ odd\\ \end{cases}\)

因此若 n 的二元表示法為 \(b_{n-1}b_{n-2}\cdots b_1 b_0\) ，則 \(n = \sum_{i=0}^{n-1} b_i\cdot 2^i\) ，由以上的推論可得 \(n \equiv \sum_{i=0}^{n-1} b_i\cdot (-1)^i \ \ (mod \ \ 3)\) 。
將每次得到的位元和遞迴的應用上式直到得到一個小於 3 的數即是餘數，若變成負數則要加上 3 的倍數。
位元和通常又可以利用 population count 這類的函式來得到，因此寫成程式的話可以將上式表示為 n = pop(n & 0x55555555) - pop(n & 0xAAAAAAAA) 。
利用以下定理可以進一步化簡。

\(pop(x \And \overline{m}) - pop(x \And m) = pop(x \bigoplus m) - pop(m)\)

於是 n = pop(n & 0x55555555) - pop(n & 0xAAAAAAAA) 可以寫為 n = pop(n ^ 0xAAAAAAAA) - 16 ，將此式重複應用於得到的 n 上直到 n 介於 0~2 ，但為了避免 n 變成負數，我們要將它加上一個足夠大的 3 的倍數，文中的例子是加上 39 。範例程式如下

int remu3(unsigned n) {
    n = pop(n ^ 0xAAAAAAAA) + 23;
    n = pop(n ^ 0x2A) - 3;
    return n + ((n >> 31) & 3);
}

另一種變形是利用 lookup table 。

int remu3(unsigned n) {
    static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 };
    n = pop(n ^ 0xAAAAAAAA);
    return table[n];
}