# 2020q1 Homework3 (quiz3)
contributed by < `StevenChen8759` >
:::danger
注意共筆書寫格式規範！
:notes: jserv
:::
###### tags: `linux2020`
> [quiz3內容說明](https://hackmd.io/@sysprog/linux2020-quiz3)
## :Camera: 測驗一 - XOR Linked List
### :camera_with_flash: `XOR Linked List` 之排序實作填答與原理
* 程式碼實作敬請參閱我的github -> [list_xor.c](https://github.com/StevenChen8759/linklist_lkd2020q3/blob/master/list_xor.c)
* 串列是如何透過XOR的運算找到上一節點 or 下一節點的位址？
* 欲找到串列中某一節點 A 的上一節點，必須先知道 A 之下一節點的位址，並將該位址與 A->addr 內之值做XOR運算，所得結果即是上一節點的位址。尋找下一節點的方式相同，但其方向相反。即：A之下一節點位址 = XOR( A之上一節點位址, A->addr )，如下列範例所示：
:::danger
用 GraphViz 重新製圖
:notes: jserv
:::
* [list_xor.c](https://github.com/StevenChen8759/linklist_lkd2020q3/blob/master/list_xor.c) 中的填答如下：
```cpp=
#define LL1 XOR(merge->addr, left) // LL1 Select (h)
#define LL2 merge // LL2 Select (c)
#define RR1 XOR(merge->addr, right) // RR1 Select (i)
#define RR2 merge // RR2 Select (c)
```
* 參考此處實現的分割方法，會將 `list` 分割成下圖之格式，並逐一合併：
![Divide_and_merge]()
* 在每一次合併的第一個 `for iteration` 中，因為串列頭的 `addr` 欄位之位址必恰為該節點之下一節點的位址 (此處以 `right` 為例子， `left` 亦同)，因為 `right->addr` = XOR( 0, `right->next`) = `right->next`，故我們可直接讀取 `right->addr` 的值得知 `right->next` 的位址，並利用指標 `next` 指向下一節點的位址。此時我們可透過 XOR(`right`, `right->addr`) 取得 `right` 之後二節點的位址，並暫存在 `next->addr` 欄位。
```cpp=81
list *next = right->addr;
if (next)
next->addr = XOR(right, next->addr);
```
* 因為此時 `merge` 指向 `NULL` ，故將指標 `start` 以及 `merge` 指向 `right` ， 又因 `right` 之前一節點位址為空，故指派 `right->addr` 為 `NULL`，在完成以上串列走訪之後，將 `right` 移動至串列的下一個位置，即 `next` 所指向之節點。
```cpp=85
if (!merge) {
start = merge = right;
merge->addr = NULL;
}
```
```cpp=93
right = next;
```
* 在每一次合併的第二個 `for iteration` 起， `right` 會恆指向子串列尚未走訪的第一個節點，而 `merge` 恆指向此時 `right` 指向節點的前一節點，這樣才能在串列進行合併時， 修改 `right` 前一節點的 `addr` 欄位，使其可透過 XOR 操作找到合併的節點。
```cpp=89
/* 修改 merge 節點的 addr 欄位，由前一節點位址 XOR 下一節點位址得到 */
merge->addr = XOR(merge->addr, right);
/* 將前一節點的位址暫存在 right 之 addr 欄位內 */
right->addr = merge;
/* 修改 merge 指標以供下一次的 addr 計算 */
merge = right;
```
* 在此處我們利用了 `right` 的欄位 `addr` 暫存前一節點的位址，待下一輪的 `for iteration` 決定下一個合併的節點後，再計算實際的 `addr` 值。
* 在最後一個 `for iteration` 中，`left` 與 `right` 皆指向 `NULL`，因此只要直接指派合併串列尾端節點的 `addr` 欄位為其前一節點的位址即可。
* 綜合以上分析，最終的程式碼實作如下：
```cpp=43
list *sort(list *start)
{
/* Return while input is equal or less than 1 element */
if (!start || !start->addr)
return start;
/* Divide -> Cut to two sublist */
list *left = start, *right = start->addr;
left->addr = NULL; // Left sublist with 1 element only
right->addr = XOR(right->addr, left); // Right sublist with n-1 elements
/* Conquer -> Sort each sublist */
left = sort(left); // Sort left list
right = sort(right); // Sort right list
/* Combine - List Merging */
// loop: merge start with NULL, repeat until left and right are both NULL
for (list *merge = NULL; left || right;) {
// [Right is NULL] OR [left is not NULL and left data is smaller than right data]
if (!right || (left && left->data < right->data)) {
list *next = left->addr; // Let next points to addr field of left (Fetch next node address of right)
// Next is not NULL, Calculate next two node after right, and store in the addr field of next
if (next)
next->addr = XOR(left, next->addr);
// Merge pointer is initially NULL, assign merged list start pointer and store the previous node address of the node which merge points to
if (!merge) {
start = merge = left;
merge->addr = NULL;
// Merge is not null, calculate merge->addr and do pointer assignment
} else {
merge->addr = XOR(merge->addr, left); // Calculte real bit mask, with previous value of merge and current node which left points to
left->addr = merge; // Store previous node address to left->addr for merge calculation in the next run
merge = left; // Pointer assignment for element to do merge in the next run
}
left = next; // Current node in the leftlist is traversed, move to next position
// [Right is NOT NULL] AND [left is NULL OR left data is bigger than or equal to right data]
} else {
list *next = right->addr;
if (next)
next->addr = XOR(right, next->addr);
if (!merge) {
start = merge = right;
merge->addr = NULL;
} else {
merge->addr = XOR(merge->addr, right);
right->addr = merge;
merge = right;
}
right = next;
}
}
return start;
}
```
### :camera_with_flash: `XOR Linked List` 之實作可改進之處
* 觀察我們在 `insert` 的實作，可發現函式會操作傳入指標指向新增插入的元素。如下圖所示：
* 但若要在串列中間之某節點後方插入資料，則我們必須對範例串列做以下修改：
* 因此我們必須讓 `insert` 函式能夠知道插入節點的前一節點或後一節點，才能計算出正確的 `addr` (如同 `sort` 函式內的指標操作技巧)，但目前的實現僅允許在串列的頭或尾插入元素，因為我們並無法透過傳入單一指標至 `insert` 函式，計算出前一節點的位址。
* 解決方法：利用兩個指標操作 `XOR Linked List` ，這兩個指標必須同時指向兩個相鄰的節點，透過兩個指標的協同操作，即可克服上述的操作障礙，如同上述 `sort` 函式內，以 `merge` 與 `left` 或 `right` 指標之實作。
### :camera_with_flash: `XOR Linked List` 針對 `Merge Sort` 的效能改善 - 子串列分割
* 觀察 [list_xor.c](https://github.com/StevenChen8759/linklist_lkd2020q3/blob/master/list_xor.c) 中函式 `sort` 的實現，可以發現在 `sublist` 的分割上，左邊的 `list` 永遠只有一個元素，而右邊的 `list` 恆分割到 $n-1$ 個元素，假設每一次的 `Merge` 耗費 $O(n)$，則可基於此分割方式做下列複雜度分析：
* $T(n) = T(n-1) + O(n)$
* $T(n) = n + (n - 1) + ... + 1$
* $T(n) = \dfrac{n\cdot(n+1)}{2} = O(n^2)$
* 透過上列分析，我們可以發現這樣的分割方式並無法得到 `Merge Sort` 原有的 $O(n\log{n})$ 時間複雜度。故我們需在串列的分治策略上做一些調整。
* 改善的 `Merge Sort` 分治策略如下：
* 將 `list` 之 `head` 與 `tail` 額外記錄，並同時傳入 `sort` 函式內。
* 同時由 `head` 與 `tail` 出發，同時往中間移動，直到兩指標相碰時停止，由相碰之位址分割成左右子串列。
* 遞迴呼叫 `sort` 函式，以完成左右子串列之排序。
* 最後透過指標操作，將左右子串列合併成已排序的串列。
* 透過上述方法，可保證兩個分割出來的子串列是平均分割的，此處同樣假設每一次的 `Merge` 耗費 $O(n)$，可得以下時間複雜度分析：
* $T(n) = 2 \cdot T(\dfrac{n}{2}) + O(n)$
* $T(n) = O(n\log{n})$ <By **`Master Theorem`**>
### :camera_with_flash: `XOR Linked List` 針對 `Merge Sort` 的效能改善 - Locality 優化
* 首先，我們先回顧 `XOR Linked list` 的結構宣告：
```cpp=12
typedef struct __list list;
struct __list {
int data;
struct __list *addr;
};
```
* `XOR Linked list` 的一個節點的大小為 `8 Bytes`
* `int` 佔用 4 Bytes
* `addr` 佔用 4 Bytes
* 透過 `lscpu` 查看 `Cache` 的配置 (註: CPU 為 `Intel Core i5-5200u @ 2.20GHz`)
```shell
$ lscpu | grep cache
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
```
* 在此 CPU 中 `L1 data cache` 配置了 $32 KB$，假設忽略快取碰撞、指標存取與其他程序造成的影響，則在串列長度在 $\dfrac{32768}{8} = 4096$ 個以下時，可使用 `in-place` 排序方法進行排序，因為善用了元素存取上的 `空間區域性 (Spatial Locality)`，除了加速排序實際所需時間以外，亦可減少 `Merge sort` 重複遞迴呼叫所造成的效能負擔。
* 但在實際的配置上並不會這麼理想，故我們仍需在考量實際執行情形後，向下調整串列的實際最小長度，並不會恰等於 $4096$。
### :camera_with_flash: 透過 `XOR Linked List` 改善 [lab0-c](https://github.com/sysprog21/lab0-c) 中 [harness.c](https://github.com/sysprog21/lab0-c/blob/master/harness.c) 之實作效能
* 觀察 [harness.c](https://github.com/sysprog21/lab0-c/blob/master/harness.c) 中的 `link list` 結構，每一個節點皆使用了兩個指標，分別指向該節點的前一元素與後一元素。
```cpp=36
typedef struct BELE {
struct BELE *next, *prev;
size_t payload_size;
size_t magic_header; /* Marker to see if block seems legitimate */
unsigned char payload[0];
/* Also place magic number at tail of every block */
} block_ele_t;
```
* 我們可透過 `XOR linked list` 節省節點內的一個指標存放空間，但需同時修改 `insert` 、 `delete` 與 `traverse` 等操作以符合原有功能，且執行上述操作時，需兩個指標協同操作，才能讓指標正確地指向串列內各個節點的元素。
## :Camera: 測驗二 - Linked List with Insertion Sort via Pointer to Pointer
### :camera_with_flash: 實作分析與填答
* 考慮以下 singly-linked list 程式:
```cpp
#include <stddef.h>
struct node {
int data;
struct node *next;
} *head;
void insert(struct node *newt) {
struct node *node = head, *prev = NULL;
while (node != NULL && node->data < newt->data) {
prev = node;
node = node->next;
}
newt->next = node;
if (prev == NULL)
head = newt;
else
prev->next = newt;
}
```
* 可透過以下 pointer to pointer 改寫 `insert` 函式，功能等價但更簡潔，如下:
```cpp
void insert(struct node *newt)
{
struct node **link = &head;
while (*link && AA)
BB;
newt->next = *link;
*link = newt;
}
```
請補完程式碼。
* 參考上列程式碼，我們先分析 `Insert via Pointer to Pointer` 的實作中「指標的指標」`link` 的特性，如下所示：
* `link` 將會指向一個「指向 list 節點的指標」
* `*link` 即是代表存取上述「指向 list 節點的指標」
* `*link->data` 則代表存取「指標 `*link` 所指向的 list 節點中」，該「list 節點的 data 欄位值」。
* 觀察上述程式中的 `insert` 函式，可發現最開始從 `head` 開始走訪，直到 list 中某節點之值不小於欲插入 list 的節點之值跳離，或是 list 走訪到終點時跳離。
* 在向下一個節點走訪時，應將 `Pointer to Pointer` 指向現時節點的 `next` 指標，才能正確地存取下一個節點。
* 最後，操作該節點的相關指標，完成 list 節點之插入。
* 除此之外，考量編譯器的設計機制上的不同 (如: 最佳化機制、**運算子優先權**...等) ，在基於 `Pointer to Pointer` 之 list 存取順序上，應嚴格遵守下列順序：
1. 對 `Pointer to Pointer` 做取值運算，取得其所指向的 `Pointer`
2. 取出的 `Pointer` 指向 `list` 中之某一 `node` ，透過 `Arrow Operator` 取出所需欄位值進行相關操作。
* 故根據上述分析與考量，填答AA與BB之值：
* AA 應選 ==\<C\> (\*link)->data \< newt-\>data==
* BB 應選 ==\<A\> link = &(\*link)-\>next==
### :camera_with_flash: 兩種實現的效能分析與實作限制
* 首先，我們實作時間的量測機制，由函式 `insert` 呼叫前起算，至返回值為止。
```cpp=70
int ins_count;
struct node *ptr = NULL;
```
```cpp=99
trun = clock();
insert(ptr);
trun = clock() - trun;
```
```cpp=123
trun = clock();
insert_ptp(ptr);
trun = clock() - trun;
```
* 透過檔案操作輸出 `clk_normal.csv` 與 `clk_ptp.csv` 兩檔案，並透過 `gnuplot` 繪製成圖。
* 插入100個元素的效能比較:
* 插入1000個元素的效能比較:
* 插入10000個元素的效能比較:
* 在插入元素時，我們可以觀察到有幾次插入所耗的 clock cycle 特別地高，可以合理推論這是受到了 `快取失誤 (Cache Miss)` 的影響。
* 除此之外，因為操作 `Pointer to Pointer`，因此在插入10000個的元素時，其執行所需 `Clock Cycle` 較傳統方法略少一些；在插入100000個的元素時，其差異更加顯著，如下圖所示：
### :camera_with_flash: 在 `Linux Kernel` 中之應用 - 紅黑樹操作
* 在 [bfq-wf2q.c](https://elixir.bootlin.com/linux/v4.15/source/block/bfq-wf2q.c#L373) 的函式 `bfq_insert` ，以及 [rbtree.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/rbtree.h#L105) 中的 `rb_link_node` 函式中使用了 `Pointer to Pointer` 進行紅黑樹操作，其目的在於利用存取 `Pointer to Pointer` 的 `時間區域性 (temporal locality)`，因為存放 `Pointer to Pointer` 的位址是固定的，因此得以讓我們在大量的節點元素操作下，使更改 `Pointer to Pointer` 所指向的指標時產生的讀寫操作能夠透過快取記憶體增速。
* 在此紅黑樹的實作中，以演算法分析的角度而言，紅黑樹因為具有 `自平衡 (Self Balancing)` 的特性，因此其效能已優於一般的二元搜尋樹，但在此處的設計中，更善用快取加速的優勢，使大量資料的操作下有更佳的效能。
Sign in with Wallet
Connect another wallet