# 2020q1 Homework3 (quiz3)
contributed by < `nickyanggg` >
###### tags: `linux2020`
## [作業要求](https://hackmd.io/@sysprog/rJXs6hrHU)
- 重新回答[第 3 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz3)
- 細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。
## 測驗一
[XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list)
### 分析
```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;
}
}
```
`insert_node` 為新增 node 於 head。
第一次呼叫 `insert_node`，`tmp` = `A`，並且因為 `*l == NULL`，因此進入 `if` block。
```
A
data 100
addr NULL
```
第二次呼叫 `insert_node`，`tmp` = `B`，因為進入 `else` block，`A->addr` = `B` xor `NULL` = `B`，`B->addr` = `A`。
```
B A
data 777 100
addr A B
```
第三次呼叫 `insert_node`，`tmp` = `C`，因為進入 `else` block，`B->addr` = `C` xor `A`，`C->addr` = `B`。
```
C B A
data 999 777 100
addr B C^A B
```
可發現第一個節點的 `addr` 一定是第二個節點的地址，因為是由 (0 xor 第二個節點的地址) = (第二個節點的地址)。
- 因此新增的節點的 `addr` 才會直接 assign 成 `(*l)`。
- 因此新增節點時，原本的第一個節點的 `addr` 才會 assign 成 (自己的 `addr` xor 新增節點的地址) = (原本的第二個節點的地址 xor 新增節點的地址)，因此仍然保留整個 XOR linked list 的特性。
`delete_node` 為從頭開始刪到尾端，直到刪光為止。
可發現在每次的 `while` 迴圈中，`next` 的值都是直接取 `l->addr`，其實也就是 `0 ^ l->addr` = 第二個節點的地址，若 `next` = 0，就代表到底了並且會在下一次檢查跳出，否則會將 `next->addr` assign 成第三個節點的地址，並且最後將第一個節點使用空間釋放掉，並更改 `l` 的值為第二個節點的地址。
### sort
```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;
}
```
因為是遞迴所以就直接從 `for` 迴圈開始看，並且假定 `left`、`right` 都被 sort 好了，那這邊要注意因為 `left` 永遠都只有一個 node，因此 `sort` = $O(n^2)$。
`for` 迴圈中的 `merge` 可以當作一個新的 list，並且會比較 `left`、`right` 並將較小的推入 list 的尾端，因此第一個 `if` block，是 `left->data` < `right->data` 的狀況，所以 `LL1` 應為 `XOR(merge->addr, left)`，而 `LL2` 應為 `merge`。相對的當 `right->data` $\leq$ `left->data`，`RR1` 應為 `XOR(merge->addr, right)`，而 `RR2` 則為 `merge`。
### Improve
- 將 `left`、`right` 節點數平均分配。
- 複雜度 $O(n^2)$ => $O(nlogn)$。
```cpp
list *merge_sort(list *start)
{
if (!start || !start->addr)
return start;
list *left = start, *right = start->addr;
list *left_prev = NULL, *right_prev = left;
while (right && XOR(right_prev, right->addr)) {
list *tmp = left;
left = XOR(left_prev, left->addr);
left_prev = tmp;
right_prev = XOR(right_prev, right->addr);
right = XOR(right, right_prev->addr);
}
right = XOR(left_prev, left->addr);
right->addr = XOR(left, right->addr);
left->addr = left_prev;
left = merge_sort(start);
right = merge_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 = XOR(merge->addr, left);
left->addr = merge;
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 = XOR(merge->addr, right);
right->addr = merge;
merge = right;
}
right = next;
}
}
return start;
}
```
### 實際測試
- 比較 size 從 1 ~ 1000。
- 從下圖可以明顯地看出 `merge_sort` 優於 `sort`。
```cpp
int main(void)
{
struct timespec tt1, tt2;
for (int i = 1; i <= 1000; i++) {
list *mylist = NULL;
for (int j = 0; j < i; j++)
insert_node(&mylist, j);
clock_gettime(CLOCK_REALTIME, &tt1);
mylist = merge_sort(mylist);
clock_gettime(CLOCK_REALTIME, &tt2);
printf("%d, %ld, ", i, tt2.tv_nsec - tt1.tv_nsec);
delete_list(mylist);
mylist = NULL;
for (int j = 0; j < i; j++)
insert_node(&mylist, j);
clock_gettime(CLOCK_REALTIME, &tt1);
mylist = sort(mylist);
clock_gettime(CLOCK_REALTIME, &tt2);
printf("%ld\n", tt2.tv_nsec - tt1.tv_nsec);
}
return 0;
}
```
### [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort)
- 子序列大小達到 $S$ 時就不再繼續分割。
- $S$ 為可完整放進處理器 cache 中的元素數量。
- 小型子序列利用 bubble sort 排序。
- 透過實驗找出可能的 $S$。
#### `bubble sort`
- 為了實作方便只更動了 `data`，並未更動整個節點。
```cpp
list *bubble_sort(list *start)
{
list *tail = NULL;
while (start != tail) {
list *curr = start;
list *prev = NULL;
while (curr && XOR(prev, curr->addr) != tail) {
list *next = XOR(prev, curr->addr);
if (next->data < curr->data) {
int tmp = curr->data;
curr->data = next->data;
next->data = tmp;
}
prev = curr;
curr = next;
}
tail = curr;
}
return start;
}
```
#### `optimizing merge sort`
- 大部分和上面的 `merge_sort` 一樣。
- `size` 為實驗要找出的 $S$。
- 若子序列長度 $\leq S$，則呼叫 `bubble_sort`。
```cpp
list *merge_sort(list *start, int size)
{
if (!start || !start->addr)
return start;
list *left = start, *right = start->addr;
list *left_prev = NULL, *right_prev = left;
int count = 1;
while (right && XOR(right_prev, right->addr)) {
count++;
list *tmp = left;
left = XOR(left_prev, left->addr);
left_prev = tmp;
right_prev = XOR(right_prev, right->addr);
right = XOR(right, right_prev->addr);
}
if (count * 2 <= size)
return bubble_sort(start);
...
return start;
}
```
#### 實驗一
- 測試 size 代入 0 ~ 1000，並且排序 1000 個節點。
- 可發現 $S$ 於 50 內效能較好。
- $S$ 範圍取太廣，無法清楚辨識一般 merge sort ($S=0$) 的狀況。
#### 實驗二
- 測試 size 代入 0 ~ 50，並排序 10000 個節點。
- 可看出 $0<S\leq50$ 時，效能都比一般 merge sort 還來得好。
## 測驗二
### 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;
}
```
`insert` 會新增節點，並且依 `data` 由小到大排序。
### pointer to pointer
```cpp
void insert(struct node *newt)
{
struct node **link = &head;
while (*link && AA)
BB;
newt->next = *link;
*link = newt;
}
```
`link` 一開始 assign 成 `head` 的地址，那要跳出迴圈應該需要滿足 `*link` 為 `NULL` 或者是 `newt->data` $\leq$ 目前 traverse 到的節點的 `data`，因此 `AA` 應為 `(*link)->data < newt->data`，而 `BB` 應該要能夠使 `*link` 在下一圈指到下一個 node，並且不會更改到 head 的值，所以應該為 `link = &(*link)->next
`。
### [branch predictor](https://en.wikipedia.org/wiki/Branch_predictor)
由於前者多了一組 `if else`，因此 branch 的數量也會較多，因此執行時間也會相對較久一點。
Sign in with Wallet
Connect another wallet