# [2020q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 3 週測驗題
###### tags: `linux2020`
:::info
目的: 檢驗學員對 **[linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list)**, **[bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)**, **[指標操作](https://hackmd.io/@sysprog/c-pointer)** 的認知
:::
==[作答表單](https://forms.gle/puNw7kvhDwtzhwcV9)==
---
### 測驗 `1`
XOR 運算特性:
* $A \oplus A = 0$
* $A \oplus 0 = A$
* $A \oplus 1 = \neg A$
* $(A \oplus B) \oplus B = A$
以下程式碼是個 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 的實作，在這樣的資料結構可表示為:
```
1 2 3 4
data HAT CAT EAT BAT
link 2 2 6 3
```
要往下一格移動時，我們需要前一格在哪和這一格的位置。例如我們現在在 `HAT` (1), 已知前一格是 (0)，那麼下一格就是 `link(1) XOR 0` = `2 XOR 0` = 2，也就是 `CAT`。繼續，現在位於 `CAT` (2)，前一格在 (1)，於是下一格就是 `link(2) XOR 1` = `2 XOR 1` = 3，亦即 `EAT`，依此類推。只要當找出來的下一格是 (0) 就結束。
```cpp
#include <stdint.h>
typedef struct __list list;
struct __list {
int data;
struct __list *addr;
};
#define XOR(a, b) ((list *) ((uintptr_t) (a) ^ (uintptr_t) (b)))
void insert_node(list **l, int d) {
list *tmp = malloc(sizeof(list));
tmp->data = d;
if (!(*l)) {
tmp->addr = NULL;
} else {
(*l)->addr = XOR(tmp, (*l)->addr);
tmp->addr = *l;
}
*l = tmp;
}
void delete_list(list *l) {
while (l) {
list *next = l->addr;
if (next)
next->addr = XOR(next->addr, l);
free(l);
l = next;
}
}
```
在 `__list` 結構體內雖僅有一個 `struct __list *addr` 指標型態的物件，但卻可實作雙向的 linked list，就是憑藉著上述的實作技巧。[XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 的優勢很顯著，對空間的佔用更為精簡:
隨著資料處理量的增長，效益更明顯:
與尋常作法相比，佔用的儲存空間比值會趨近 $67\%$。
接著我們嘗試撰寫針對 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 的排序程式，採用遞增順序:
```cpp
list *sort(list *start)
{
if (!start || !start->addr)
return start;
list *left = start, *right = start->addr;
left->addr = NULL;
right->addr = XOR(right->addr, left);
left = sort(left);
right = sort(right);
for (list *merge = NULL; left || right;) {
if (!right || (left && left->data < right->data)) {
list *next = left->addr;
if (next)
next->addr = XOR(left, next->addr);
if (!merge) {
start = merge = left;
merge->addr = NULL;
} else {
merge->addr = LL1;
left->addr = LL2;
merge = left;
}
left = next;
} else {
list *next = right->addr;
if (next)
next->addr = XOR(right, next->addr);
if (!merge) {
start = merge = right;
merge->addr = NULL;
} else {
merge->addr = RR1;
right->addr = RR2;
merge = right;
}
right = next;
}
}
return start;
}
```
請補完上述排序程式碼。
==作答區==
LL1 = ?
* `(a)` `right`
* `(b)` `left`
* `(c)` `merge`
* `(d)` `XOR(merge, left)`
* `(e)` `XOR(merge, right)`
* `(f)` `XOR(merge, left->addr)`
* `(g)` `XOR(merge, right->addr)`
* `(h)` `XOR(merge->addr, left)`
* `(i)` `XOR(merge->addr, right)`
LL2 = ?
* `(a)` `right`
* `(b)` `left`
* `(c)` `merge`
* `(d)` `XOR(merge, left)`
* `(e)` `XOR(merge, right)`
* `(f)` `XOR(merge, left->addr)`
* `(g)` `XOR(merge, right->addr)`
* `(h)` `XOR(merge->addr, left)`
* `(i)` `XOR(merge->addr, right)`
RR1 = ?
* `(a)` `right`
* `(b)` `left`
* `(c)` `merge`
* `(d)` `XOR(merge, left)`
* `(e)` `XOR(merge, right)`
* `(f)` `XOR(merge, left->addr)`
* `(g)` `XOR(merge, right->addr)`
* `(h)` `XOR(merge->addr, left)`
* `(i)` `XOR(merge->addr, right)`
RR2 = ?
* `(a)` `right`
* `(b)` `left`
* `(c)` `merge`
* `(d)` `XOR(merge, left)`
* `(e)` `XOR(merge, right)`
* `(f)` `XOR(merge, left->addr)`
* `(g)` `XOR(merge, right->addr)`
* `(h)` `XOR(merge->addr, left)`
* `(i)` `XOR(merge->addr, right)`
:::success
延伸問題:
1. 解釋上述 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 排序實作的原理，並指出其中可改進之處;
2. 在 Wikipedia 關於合併排序的詞目中，談及 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort)，我們可知道一種最佳化策略是：在子序列大小達到 $S$ 時就不再繼續分割，此時這個 $S$ 為可完整放進處理器 cache 中的元素數量。每個大小為 $S$ 的子序列，都透過適用於小規模 in-place (即不需要額外配置記憶體) 排序演算法（如插入排序或泡沫排序）進行排序，以減少在記憶體內交換特定區域的次數。在小型子序列排序完畢後，再以典型的遞迴型合併排序完剩下的部份。
若可找到一個恰當的 $S$， 便能有效的同時利用到插入排序和合併排序的優點，並減少原始的合併排序當中 locality 不好的影響。請觀察你的硬體組態 (如 L1 data cache 的容量和行為)，以上述策略實作效率更好的 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 排序程式。過程中應該充分量化數據並進行視覺化處理。
3. 修改 [lab0-c](https://github.com/sysprog21/lab0-c) 裡頭的 [harness.c](https://github.com/sysprog21/lab0-c/blob/master/harness.c)，將原本內部使用的 doubly-linked list 換為 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list)，觀察記憶體佔用率的變化，可設計頻繁的 `test_malloc` / `test_free` 呼叫交錯情境。
:::
---
### 測驗 `2`
考慮以下 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;
}
```
請補完程式碼。
==作答區==
AA = ?
* `(a)` `(link)->data < newt->data`
* `(b)` `*link->data < newt->data`
* `(c)` `(*link)->data < newt->data`
* `(d)` `**link->data < newt->data`
BB = ?
* `(a)` `link = &(*link)->next`
* `(b)` `*link = *link->next`
* `(c)` `(*link) = (*link)->next`
* `(d)` `link = (*link)->next`
:::success
延伸問題:
1. 解釋程式運作原理、對執行時間的影響 (考慮到 [branch predictor](https://en.wikipedia.org/wiki/Branch_predictor) 行為)，和指出其實作限制;
2. 在 Linux 核心找出運用類似的手法的程式碼並解說
* 提示: 可參見 [bfq_insert](https://elixir.bootlin.com/linux/v4.15/source/block/bfq-wf2q.c#L373) 和 [rb_link_node](https://elixir.bootlin.com/linux/v4.15/source/include/linux/rbtree.h#L105) 操作 [red-black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) 的手法
:::
---
Sign in with Wallet
Connect another wallet