2023q1 Homework1 (quiz1)

contributed by < chiangkd >

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5599.85

測驗一

延伸問題

解釋程式碼運作原理
針對 Quick sort 提出程式碼的改進方案並實作
引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻

~~快速排序法原本並不是一個 stable sort ，而是 unstable sort~~
根據 Wikipedia，一般常見的 quicksort 並不是 stable sort，例如 Lomuto partition scheme，Hoare partition scheme，但是也可以透過進行 out-of-place，進行 stable 版本的 quick sort 實作，與一般需要

O (n l o g n)

空間複雜度的 in-place 版本不同，out-of-place 需要

O (n)

的空間來儲存資訊，文中也提到可以透過 linked list 實作 stable sort 版本的 quick sort，但是此時是否有 random access 就會非常重要。

Although quicksort can be implemented as a stable sort using linked lists, it will often suffer from poor pivot choices without random access.

這句不精準，其實不是演算法設計的問題，而是實作手段，可參照 Wikipedia (要看英文版，避免讀中文詞條，後者充斥許多錯誤) 的解釋。

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

Fix it, Thanks!

結構體

struct item {                         
    uint16_t i;
    struct list_head list;
};

struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);

考慮到結構體的定義、 list_first_entry 的用途以及變數的宣告，可知 AAA = item，BBB = list

CCC (itm, is, head, list) {
    if (cmpint(&itm->i, &pivot->i) < 0)
        DDD (&itm->list, &list_less);
    else
        EEE (&itm->list, &list_greater);
}

根據 list.h 中的定義，可以放入 4 個引數的僅有 list_for_each_entry_safe = CCC ，且 DDD、EEE 負責根據當前迭代到的值大於或是小於 pivot 來進行節點交換

當迭代到的值小於 pivot 的值 (if 條件滿足) 則將該節點移動至 list_less 節點後面，若否，則移動到 list_greater 節點後面
- DDD = EEE = list_move_tail

透過遞迴的方式繼續對 list_less、 list_greater 做一樣的處理，此時注意到最後兩行為

list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head)

代表每次回傳都是將已經排序好的 list 接在 head 後面，其中，首先將 pivot 放在 head 後，再將代表比 pivot 小的 list_less 放在 head 後面，最後一部將比 pivot 大的 list_greater 放在 pivot 右側，也就是目前由 head 開頭的 list 的最後面，故得知 list_splice_tail = FFF.

struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);

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

list_sort(&list_less);

以此類推最後透過

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

先把節點放進去，比節點大的放右邊，比節點小的放左邊，完成排序

測驗二

延伸問題

解釋程式碼運作原理，指出設計和實作的缺失
比較測驗 1 和測驗 2 的程式碼，設計實驗來分析二者效能，解釋為何非遞迴的實作未能總是比遞迴的實作快
提出效能改進方案，特別是避免依賴 MAX_DEPTH
引入 Introsort, 也就是 quick sort 和 heap sort (或其他可避免前者
$O (n^{2})$ 最差時間複雜度的演算法)。加入 heapsort 的原因為，當 quicksort 迭代
$2 \times \log n$ 次後還排序完成，那就很可能會得到
$O (n^{2})$ 時間複雜度。此時切換為 heap sort 能將其時間複雜度控制在
$O (n \log n)$

首先根據 Optimized QuickSort 的所提及的方法與原版(這裡原版指的是網站指出的 wikipeida 版本)比較，包含了以下幾個優點

避免使用 function call ，減少 CPU 花在進入 function、離開 function 的時間
不使用 stack 來儲存資料，文中提及雖然 recursive 版本的 quick sort 看起來直觀簡單，但是會使用大量的 private stack 來儲存資料，會比起直接使用 beg[]、 end[] arrau 來的慢，且有機會造成 stack overflow，而文中提及的方法透過設定 MAX_LEVELS 來回傳 NO 來避免產生 failure
在每一輪中，原版會 swap 非常多次，但文中版本僅 swap pivot 以及某個節點一次
其他像是多次移動同個物件、冗餘的移動、和自己進行 swap 都在文中新版本有所改善

測驗 2 給定具有 MAX_DEPTH = 512 的 stack 來模擬遞迴的過程且使用 INIT_LIST_HEAD 來初始化 head (此處上端為 stack[0] 依次往下遞增為 stack[1], stack[2] ... stack[MAX_DEPTH-1])

struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
    INIT_LIST_HEAD(&stack[i]);

把尚未排序好的 list 放進 stack 中

int top = -1;
list_splice_init(head, &stack[++top]);

執行完上述程式碼時時 top 為 0，進入 while 迴圈

INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);

執行完上述程式碼時時 top 為 -1，且符合第一個 if 條件，進入 if 迴圈

struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot =
    list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);

首先把 head 當我 pivot ，從對 list 左邊開始找，找到小於 pivot 的值就會放入，(文中使用 beg[]， end[] 紀錄比較過程)， linked list 則透過與測驗 1 一樣的 list_less、list_greater 來儲存資訊。

GGGG (itm, is, &partition, list) {
    ...
    }

與測驗一相同， GGGG 為 list_for_each_entry_safe

將各個節點和 pivot 比大小並將對應結果分別放到 list_less 以及 list_greater

list_for_each_entry_safe(itm, is, &partition, list) {
    list_del(&itm->list);
    if (cmpint(&itm->i, &pivot->i) < 0)
        list_move(&itm->list, &list_less);
    else
        list_move(&itm->list, &list_greater);
}

接著將 pivot 如同測驗 1 一樣在將 less 和 greater 合併時 pivot 會在中間，所以根據題目是將 pivot 放在 less 的某處，應為 less 的尾端

HHHH (&pivot->list, &list_less);

故 HHHH 為 list_move_tail

再來就是和測驗 1 不同的部份，透過 stack 取代遞迴的過程，故將 less 以及 greater 放進去 stack (記得在此處 top 為 -1，為原本放未排序的 list 的地方，取出來做處理得時候有 -1)，在推進去 stack 時為 &stack[++top]

考試的時候寫成 &stack[top++]，不夠細心

if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
    list_splice_tail(&list_less, JJJJ);

IIII = JJJJ = &stack[++top]

因為 top 值在推送進 stack 時有增加，所以 while 迴圈會持續運作，接著會對 1 -> 3 -> 2 -> 5 這個 list 做上述一樣的動作，持續到第一個 if 條件不滿足，也就是不滿足

if (!list_empty(&partition) && !list_is_singular(&partition))

代表從 stack 取出的節點為空或者是只有一個節點，此時進入 else 條件，

在第一次進入 else 前的 stack 樣子為

偵測到 stack 的最頂端 (尚未從 stack 取出的圖中最下面)，僅有一個節點 1，取出後 (此時的 top 會在指向 3->2->4 的位置，因為在切出 partition 的時候有做 top-- 的動作)進入 else 條件首先要先 top++ push top 一格

top++;
list_splice_tail(&partition, &stack[top]);
while (top >= 0 && list_is_singular(&stack[top])) {
    struct item *tmp =
        list_first_entry(&stack[top], struct item, list);
    list_del(&tmp->list);
    INIT_LIST_HEAD(KKKK);
    list_add_tail(&tmp->list, head);
}

一進入後會將剛剛判斷為只有一個節點的 partition 放回 stack[top]，注意到題目中進行 list_del(&tmp->list) 且後面有 list_add_tail(&tmp->list, head)，代表已經將該節點放到 head 後面，以完成排序的部份，故 KKKK 必須對 stack pop 一格，KKKK = &stack[top--]

總結進入到 else 才會透過 list_add_tail(&tmp->list, head); 將排序好的節點放到 head 後面，且進入 else 的條件為此時 stack[top] 的位置僅有一個節點，且根據上述過程，stack[top] 必為未排序的 list 中最小的那個節點 (在推進去 stack 的時候是先推 greater 後再推 less，所以比較小的節點會在上面)，以此依序將最小的節點接在 head 後面完成排序。

測驗三

延伸問題

解釋上述程式碼運作原理，指出其實作缺陷並改進
在上述 XOR linked list 的基礎，實作測驗 1 和 2 提及的快速排序演算法，注意要引入你改進效能的版本
修改 xorlist_destroy，使其不急著釋放記憶體，而搭配 atexit(3) 並在程式即將結束執行時，才批次處理資源釋放

在關鍵巨集中

#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))

根據函式名稱以及在程式內的用途知其為將 a 和 b 做 exclusive or 運算

LLLL = (uintptr_t)(a) ^ (uintptr_t)(b)

另一個常用函式為 address_of，在透過 assert 確認 n1、n2 都為非 0 值後搭配 XOR_COMP 巨集進行 exclusive or 運算回傳下一個節點地址。

static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
    assert(n1 && n2);
    return XOR_COMP(n1, n2);
}

XOR List 的迭代過程透過前一個的地址以及這一格的 link 進行 xor 運算來獲得下一格的位址，也就是說當前位置的 link 可以透過前後兩個點的地址進行 xor 運算得到

根據上述，程式內也定義了 xor_list_t 來代表 list 所需的資訊

typedef struct _xor_list_struct {
    xor_node_t head, tail;
    uint32_t count;
} xor_list_t;

根據前面敘述，要拿到當前節點的 link ，需要前後兩個點的地址，所以在這裡也直接定義了 head 以及 tail 代表 list 的頭尾

查看 xorlist_for_each 巨集

#define xorlist_for_each(node, rp, rn, list)                        \
    for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \
         rn = address_of(rp, node->cmp), rp = node, node = rn)

可以看到在迭代的過程中 rn 為下一個節點的地址，是透過 rp (前一個節點的地址) 和 node->cmp (當前節點的 link) 做 xor 運算得到。

在 main 中，先將 0~100 的值透過 xorlist_add 加入到 list 中，

xornode_init(&new->xornode);
new->value = i;
xorlist_add(&list, &new->xornode);

這裡的 cmp 若是要取得下一個節點的地址則需要與前一個節點地址做 xor

考慮題目及，題目給的參考執行輸出，

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;

    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
    if (node == &list->tail)
        real_next = MMMM;
    else
        real_next = node;
    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
    list->count++;

    return 0;
}

題目 MMMM 用以處理初始的條件，在進入 xorlist_add 之前已經呼叫過 XORLIST_INIT(h) 巨集，將 head 以及 tail 的 cmp 互相設定為對方，在初始條件下 real_next 即為 list_tail，故 MMMM = &list->tail，此時這個 if-else 條件似乎顯得沒必要? 可直接使用 real_next = node 做取代 (待驗證)

考慮到若 if 條件滿足，則代表 node = real_prev->cmp 為 &list->tail，此時 node 等價於 &list_tail ，因為是將新的節點 n 插入至 list 的第一個節點，且 node 指向 real_prev 的壓縮地址 (cmp)，因為是 head 的關係所以壓縮地址必為下一個節點地址，同時 node 也會是，故直接省略 if 條件也可以正常執行

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;

    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
-    if (node == &list->tail)
-        real_next = MMMM;
-    else
-        real_next = node;
+   real_next = node;
    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
    list->count++;

    return 0;
}

根據題目顯示，list_add 是新增節點在 list 的頭

進入 list_add 初始狀態如圖 A、B 為該節點地址

在初始狀態新增一個節點地址為 C 後的結果應為

而 PPPP 用以更新 real_next->cmp 的值，從 xor-list 的方法知道該節點的 cmp 為前後節點地址做 xor 運算

real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));

此時要讓 real_next->cmp 從 A 更新為 C，進行運算

C \oplus (A \oplus P P P P)

，此時 PPPP 應為 A ，用以消除 A (因為

A \oplus A = 0

)，故 PPPP 為 real_next->cmp

2023q1 Homework1 (quiz1)

開發環境

測驗一

測驗二

測驗三

Read more

面試紀錄 & 練習 (聯發科)

2023q1 Homework1 (lab0)

將現有的 Raspberry PI 系統備份

Run FreeRTOS on VexRiscv and Measure/Tweak context switch overhead