---
# System prepended metadata

title: 2020q1 Homework3 (quiz3)
tags: [linux2020]

---

# 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;
}
```

![](https://i.imgur.com/n7LOhci.png)

### [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$) 的狀況。 
![](https://i.imgur.com/A1bPKF4.png)
#### 實驗二
- 測試 size 代入 0 ~ 50，並排序 10000 個節點。
- 可看出 $0<S\leq50$ 時，效能都比一般 merge sort 還來得好。
![](https://i.imgur.com/KmrYuwK.png)

## 測驗二
### 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 的數量也會較多，因此執行時間也會相對較久一點。
