# 2020q1 Homework3 (quiz3)
contributed by < `kylekylehaha` >
> [第三週測驗](https://hackmd.io/@sysprog/linux2020-quiz3)
> [作業要求](https://hackmd.io/@sysprog/rJXs6hrHU)
###### tags: `linux2020`
## 測驗 1
**XOR Linked list**
根據維基百科的描述 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list)
> An XOR linked list is a type of data structure used in computer programming. It takes advantage of the bitwise XOR operation to decrease storage requirements for doubly linked lists.
意思是說 `XOR linked list` 可以達到 `doubly linked list` 的效果：`可以在 O(1) 的時間複雜度下，取得前一項和後一項`，然而 `XOR linked list` 的空間雜度可以比 `doubly linked list` 低，因為只需要一個指標，而 `doubly linked list` 卻需要兩個指標 `prev` & `next`。
如何使用 `XOR linked list` 呢？
公式: `address of next node = address of perv node ^ pointer in the current node.` ，其中我們將 `address of next node` 記作 `addr(next) ` ; `address of perv node` 記作 `addr(prev)`
我們套入三種 case 來證明:
* Head to next node:
* 因為 head 的關係，故 addr(prev) 為 0
* 在 head 中，其element 為 `0 ^ addr(next)` = `addr(next)`
```
addr(next) = addr(prev) ^ pointer in the current node
= 0 ^ (0 ^ addr(next))
= addr(next)
```
* Node to next node:
```
addr(next) = addr(prev) ^ pointer in the current node
= addr(prev) ^ (addr(prev) ^ addr(next))
= 0 ^ addr(next)
= addr(next)
```
* Tail to next node:
* 由於 tail 即為最後一項，故其 next node = `NULL`
* 在 tail 中，其 element 為 `addr(prev) ^ 0` = `addr(prev)`
```
addr(next) = addr(prev) ^ pointer in the cuurent node
= addr(prev) ^ (addr(prev) ^ 0)
= addr(prev) ^ addr(prev)
= 0 (NULL)
```
測驗一題目:
```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;
}
```
可以發現，這題和[第一週題目](https://hackmd.io/@sysprog/linux2020-quiz1)相似，都是實做 `merge sort`。
`LL1` & `LL2`
* 在第一小段，由於 `left` 為 head，因此 `left->addr` 即為它的下一個 node
```cpp
...
list *next = left->addr;
if (next)
next->addr = XOR(left, next->addr);
...
```
* 我們已知 `merge` 為 merge list 的 tail，故我們要將 `left` 的 head 插在 `merge` 後面，並更新 `merge->addr`。在更新前， `merge->addr` = `addr(prev)`
* 在更新後，原本的 `merge` 所指的記憶體位置，我們用 `merge'` 代替。此時 `merge'->addr` 應為 `addr(prev) ^ addr(next)` = `addr(prev) ^ addr(left)`，在之前我們已知 `addr(prev)` = `merge->addr` ; `left` 插在 `merge'` 後面。
* 故由此可知 `LL1` = `XOR(merge->addr, left)`。
* 由於 `left` 為 tail ，故其 `left->addr` 存的是上一個 node，也就是 `merge`。故 `LL2` = `merge`
```cpp
if (!merge) {
start = merge = left;
merge->addr = NULL;
} else {
merge->addr = LL1;
left->addr = LL2;
merge = left;
}
left = next;
```
`RR1` & `RR2`
由於兩者對稱，因此我們可知 `RR1` = `XOR(merge->addr, right)`, `RR2 = merge`
### 延伸問題
#### 解釋上述 XOR linked list 排序實作的原理，並指出其中可改進之處
這邊的排序，基本上就是 [merge sort](https://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)。然而因為 `left` 只有一個節點，故 `merge sort` 效果不佳，會退化成 [insertion sort](http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html)，因此我們可以參考 [lab0](https://github.com/kylekylehaha/lab0-c/blob/master/queue.c) 的做法，將 `split` 加到 `sort`：從中間開始切。
#### 優化 XOR-merge sort
* 根據 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort)，為了滿足 locality of reference，當子序列小於 S 時，便不再切下去，而是利用 in-place algo. (e.g. insertion sort or bubble sort) 去做排序。(其中 S 的大小為 CPU cache 的大小。)
> For example, the tiled merge sort algorithm stops partitioning subarrays when subarrays of size S are reached, where S is the number of data items fitting into a CPU's cache
* 這次實驗，我們用 `insertion_sort` 來當作 optimizing merge sort 的 in-place algo.
* 因此，在這次實驗我們會製作 `print`, `insertion_sort` 和 `op_merge_sort`
**print()**
* 將 list 內的 `data` 印出來，方便 debug。
```cpp
void print(list *l)
{
if (!l) {
printf("list is not exist now\n");
return;
}
printf("list: ");
list *next = l->addr;
while(l) {
list *tmp;
printf("%2d", l->data);
if (next) {
tmp = XOR(next->addr, l);
}
l = next;
next = tmp;
}
printf("\n");
return;
}
```
* 測試一下:
```cpp
int main(){
list **start;
for(int i = 0;i < SIZE;i++){
insert_node(start, i);
}
print(*start);
return 0;
}
```
* 輸出:
```cpp
list: 9 8 7 6 5 4 3 2 1 0
```
**insertion_sort**
* 這邊我們會有兩個序列，分別是 `sorted` & 尚未排序的序列，每次都將尚未排序的序列取一個出來，和 `sorted` 一起丟入 `merge` 內做排序。
```cpp
list *merge(list *left, list *right)
{
list *start = NULL;
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(left, merge->addr);
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(right, merge->addr);
right->addr = merge;
merge = right;
}
right = next;
}
}
return start;
}
```
```cpp
list *insertion_sort(list *head)
{
if (!head || !head->addr)
return head;
list *sorted = head;
list *next = sorted->addr;
if (next)
next->addr = XOR(sorted, next->addr);
sorted->addr = NULL;
for (list *cur = next; cur;) {
next = cur->addr;
if (next)
next->addr = XOR(cur, next->addr);
cur->addr = NULL;
sorted = merge(sorted, cur);
cur = next;
}
return sorted;
}
```
* 測試一下：
```cpp
int main(){
list **start;
srand((unsigned)time(NULL));
for(int i = 0;i < SIZE;i++){
insert_node(start, rand()%100);
}
print(*start);
*start = insertion_sort(*start);
print(*start);
return 0;
}
```
* 輸出:
```cpp
list: 31 36 2 43 68 82 53 13 9 38
list: 2 9 13 31 36 38 43 53 68 82
```
**Optimizing merge sort**
* 在 optimizing merge sort，當序列小於 `S` 時，我們使用 `insertion_sort` ; 大於 `s` 時則繼續遞迴 `op_merge_sort`
* 基本上作法和一般的 merge sort 一樣，只差在需要判斷序列長度是否小於 threshold。
* 其中 `split` 用來平均切割序列，切割成兩個長度相同或是長度相差 1 的 子序列。
```cpp
list *op_merge_sort(list *start, int list_len, int thres)
{
if (!start || !start->addr)
return start;
if (list_len < thres) {
return insertion_sort(start);
}
list *head = start;
list *left, *right;
int left_len = 0, right_len = 0;
split(head, &left, &right, &left_len, &right_len, thres);
left = op_merge_sort(left, left_len, thres);
right = op_merge_sort(right, right_len, thres);
return merge(left, right);
}
```
```cpp
static void split(list *src, list **left,
list **right, int *left_len,
int *right_len, int thres)
{
list *fast = src, *prev_fast = NULL, *next_fast;
list *slow = src, *prev_slow = NULL, *next_slow;
int len = 0;
while (fast && XOR(fast->addr, prev_fast)) {
/* fast = fast->next->next */
next_fast = XOR(fast->addr, prev_fast);
fast = XOR(fast, next_fast->addr);
prev_fast = next_fast;
/* slow = slow->next */
next_slow = XOR(slow->addr, prev_slow);
prev_slow = slow;
slow = next_slow;
len++;
}
*left = src;
if (!src) {
*right = NULL;
} else if (fast) {
/* list is odd */
list *next = XOR(prev_slow, slow->addr);
next->addr = XOR(slow, next->addr);
*right = next;
slow->addr = XOR(slow->addr, next);
*left_len = len;
*right_len = len + 1;
} else {
/* list is even */
prev_slow->addr = XOR(prev_slow->addr, slow);
slow->addr = XOR(prev_slow, slow->addr);
*right = slow;
*left_len = *right_len = len;
}
return;
}
```
* 測試一下
```cpp
...
list **start ;
*start = NULL;
for (int j = 0;j < LIST_LEN; j++) {
insert_node(start, rand()%100);
}
printf("before sort\n");
print(*start);
*start = op_merge_sort(*start, LIST_LEN, 6);
print(*start);
...
```
* 輸出
```cpp
before sort
list: 23 75 71 6 29 71 20 47 17 51 64 66 47 40 22 34 61 94 24 31
list: 6 17 20 22 23 24 29 31 34 40 47 47 51 61 64 66 71 71 75 94
```
**利用實驗找出 threshold `S`**
* 我們將 `LIST_LEN` 長度拉長，可以比較明顯看出 `op_merge_sort` 的效果。
```cpp
#define LIST_LEN 10000
```
* 將程式固定在 CPU 0 上面，可以減少 context switch 的影響
```cpp
taskset 0x1 [execute]
```
* 我們將 `S` 的範圍從 0 ~ 1000 ，可以清楚發現有四個階段
* 實驗結果討論
* 我們可以利用 `lstopo` 命令來看出自己 cpu 的架構。
> 須先安裝套件: `$ sudo apt-get install hwloc`
* 
* 由此可知，cpu 內有四階 cache，分別對應上面實驗的四種階段。
* 因此根據實驗結果，可以得知當 `threshold` 小於 150 左右時，`op_merge_sort` 效果較佳。
**比較 `insertion_sort`, `merge_sort` 和 `op_merge_sort`**
* 分別呼叫 `insertion_sort`, `merge_sort` 和 `op_merge_sort`，比較三者的時間。
* 實驗結果討論
* 可以明顯看出 `op_merge_sort` 最佳，`insertion_sort` 最差，這和預期的結果符合。
* 由於是用 `rand()%100` ，也就是說在 random 的情況下，`insertion_sort` 不太會出現 worst case，也就是遞減的順序，因此其時間沒有差太多。
* [測驗一程式碼](https://github.com/kylekylehaha/self-practice/tree/master/c/xor_linked_list)
#### 修改 lab0-c 裡頭的 harness.c，將原本內部使用的 doubly-linked list 換為 XOR linked list，觀察記憶體佔用率的變化，可設計頻繁的 test_malloc / test_free 呼叫交錯情境。
---
## 測驗 2
基本上，這題就是 Linus Torvald 在 TED 演講所提到的「有品味的程式碼」，可以參照 [fcamel 的心得](https://medium.com/fcamels-notes/%E5%BE%9E%E5%88%AA%E9%99%A4-linked-list-node-%E7%9C%8B%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88%E7%9A%84%E5%93%81%E5%91%B3-b597cc5af785)。我們直接來看問題:
```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;
}
```
兩者差別
* 上面的程式碼需要考慮特殊情形，也就是插入的即為 head，因此需要條件式來判斷。
* 下面的程式碼直接考慮 target 的位置，因此不須特別用條件逝去判斷特殊情形。
==解題思路==
`AA`
* 由於 `link` 是 pointer to pointer，因此必須先 dereference 才會變成 pointer。故 `(*link)->data` 才能取到 data。須注意 `*` 與 `->` 的 [prioirty](https://en.cppreference.com/w/c/language/operator_precedence)，因為 `->` priority 比較高，因此要加括號。
* 此題答案為 `(*link)->data < newt->data`
`BB`
* 當 `(*link)->data < newt->data` 時， `*link` 要移動到下一項，但因為 c 只有 `call by value` ，因此要改變指標內的值需要傳入位置。
* 故本題答案為 `link = &(*link)->next
`
### 延伸問題
#### 解釋程式運作原理、對執行時間的影響 (考慮到 branch predictor 行為)，和指出其實作限制
* `insert_v1` 為第一個 insert。稱之為 **"ori insert"**
* `insert_v2` 為第二個 insert，也就是 pointer to pointer。稱之為 **"tasted insert"**
* `clear` 為清除 linked list
```cpp
struct timespec start, end;
clock_gettime(CLOCK_REALTIME, &start);
for (int i = 0;i < LEN;i++) {
insert_v2(create(i));
}
clock_gettime(CLOCK_REALTIME, &end);
printf("tasted insert time: %u ns\n", diff_in_ns(start, end));
clear();
/* test for insert_v2. i.e. tasted insert */
struct timespec t3, t4;
clock_gettime(CLOCK_REALTIME, &t3);
for (int i = 0;i < LEN;i++) {
insert_v1(create(i));
}
clock_gettime(CLOCK_REALTIME, &t4);
printf("ori time: %u ns\n", diff_in_ns(t3, t4));
clear();
```
* 輸出：和預期的相同， tasted insert 因為 branch 比較少，故執行時間較短。
```cpp
tasted insert time: 156140968 ns
ori time: 225535635 ns
```
* 利用 [perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 來確認 branch 的次數
```shell
$ gcc -o ll linked_list.c
$ sudo perf record -e branch-misses:u,branch-instructions:u ./ll
$ sudo perf report
```
**insert_v1**
```cpp
288 branch-misses:u
714 branch-instructions:u
```
* u 代表 userspace
**insert_v2 (tasted insert)**
```cpp
250 branch-misses:u
640 branch-instructins:u
```
* [測驗二程式碼](https://github.com/kylekylehaha/self-practice/blob/master/c/tasted_linked_list.c)
#### 在 Linux 核心找出運用類似的手法的程式碼並解說
## Reference
* [XOR linked list](http://www.tastones.com/zh-tw/stackoverflow/data-structures/linked-list/xor_linked_list/)
* [從刪除 linked-list node 看程式設計的品味](https://medium.com/fcamels-notes/%E5%BE%9E%E5%88%AA%E9%99%A4-linked-list-node-%E7%9C%8B%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88%E7%9A%84%E5%93%81%E5%91%B3-b597cc5af785)
Sign in with Wallet
Connect another wallet