# 2020q2 Homework3 (quiz3)
contributed by < `eecheng87` >
###### tags: `linux2020`
## 題目 `1`
### XOR linked list

#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` 結構裡面存的東西到底是什麼。`data` 顧名思義就是存數字的地方，那 `addr` 在一般狀況下是存此節點前個一地址和下一個節點地址的 XOR 值。 舉例來說: 有個 list: A->B->C，則 `B->addr` 應該為 `XOR(&A, &C)`。那何謂非一般狀況，當準備要對節點操作時 (如: 刪除)，`addr` 就會改成下一個指向的節點，舉例來說: 若要得到 B 的下一個節點，只需要做 `XOR(&B->addr,&A)`。

接著探討上面程式碼的作用:
* 在 insert 時，分兩種情況:
1. 若目前 list 為空，節需要把 addr 填成 0 ( 因為 XOR(NULL, NULL) = NULL );
2. 把 `tmp` 插到 `l` 前面，所以 `l->addr` 的值應該為 address of previous node XOR address of next node ，即 `&tmp` 和 `l->addr` 的 XOR 值;
* 在 delete 時，位在頭 `node->addr` 會被改成 next node 的地址（透過X OR），假設有一個 list: A->B->C , `l` = `A`:
* `next = l->addr` ( $0 \oplus B = B$)　所以 next 正好指到下一個 node B
* `next->addr = XOR(next->addr, l)` : `B->addr` 原本是 $A \oplus C$ ，現在讓 `B->addr` 改成指向下一個節點C (透過 $((A \oplus C) \oplus A )\ = C$)
* 接著 free(l) 即 A
* 讓 l 變成 B

### XOR merge sort

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

由於 merge sort 的 linked list 實作已經在 quiz1 出現過，加上前面已經說明 XOR linked list 原理，所以接著只解釋部分程式碼:
* `right->addr = XOR(right->addr, left)` 把 right 指向下一個節點(e.g. list: A->B->C。A 是 left，B 是 right，則 XOR(right->addr, left) 即 $(A \oplus C) \oplus A = C$)，`right->addr` 最後指向下一個節點。
* `next->addr = XOR(left, next->addr)` 讓 `next` 指向下一個節點。
* `if (!right || (left && left->data < right->data))` 內表示要切 `left` 的頭到 `merge` 後。
* 若 `merge` 仍空
* 若非空，`merge->addr = LL1;left->addr = LL2;merge = left;`
* LL1應該為 `XOR( merge->addr,left )`，此時 `merge` 並非 `left` 的頭，為了讓此時 `merge` 的 `addr` 有正確的數值 (prev addr xor next addr)，所以要分別給 `merge->addr`，`XOR( merge->addr,0 )` (因為原本 merge->next = NULL，此結果為 merge 的 previous 節點) 和 `left` (原本 `merge` 的下一個節點會變成 `left` 的頭) 的 XOR 值
* LL2 應該為`merge`，因為 `left` 的頭會變成 merge list 的尾巴，所以此節點 `left` 的前面是`merge`，後面是 `NULL`。所以此節點 `left` 的 `addr` 應該為 `XOR(merge,0)` 即 `merge`。

## 延伸問題
### 優化 XOR-merge sort

在 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort) 中談及，現存版本的 merge sort 一開始在 top-down 的過程一定會走到只剩一個節點後，才開始做 bottom-up (merge) 的動作。這種方式很明顯可以看出缺點，因為 merge sort 不論是 worst, best 或 average case 的複雜度都是 $O(Nlog{N})$ ，反觀 insertion sort，在 N 沒有很大的時候，複雜度近似 $O(N)$。因此，我們有了最初優化的雛型，當目前分割的 sub-list 的長度小於 S 時，我們改用 insertion sort。

### 實做

用考題提供的 XOR-merge sort 修改，並額外實做一個 XOR-insertion sort 來給前者使用。

首先，為了在開發中能夠方便 debug，我們得先實做印出 list 的工具函式 `print()`

void print(list *l)
{
    printf("List: ");
    list *next = l->addr;
    while (l){
        list *tmp;
        printf("%3d  ", l->data);
        if (next)
            tmp = XOR(next->addr, l);
        l = next;
        next = tmp;
    }
    printf("\n");
}

在這邊要注意的是，其實 XOR-linked list 並沒有想像中的這麼神，只透過一個 XOR 值就能知道前後是誰。事實上，我們永遠需要記憶額外的一個節點，才能還原下一個或上一個節點。 秉持這個精神，上述程式碼就是記憶著 `l` ，透過 `next->addr` 來拿 `l->next->next`。

既然完成工具了，接著來實做 XOR-insertion sort

list *insert_sort(list* head,int ssize)
{
    // insertion sort
    if(!head)
        return NULL;
    list *pre_tmp;
    list *tmp;
    list *res; // this is global temorary variable
    int size = ssize;

    // curr is the next element of sorted list
    list *pre_curr = head;
    list *curr = head->addr;
    // prev->next == curr
    list *pre_prev = NULL;
    list *prev = head;
    // tail indicates the tail of sorted list
    list *pre_tail = NULL;
    list *tail = head;

    for(int i = 1; i < size; i++) {
        pre_tmp = NULL;
        tmp = head;
        pre_prev = NULL;
        prev = head;
        // find the location to be inserted
        for (int j = 0; j < i && tmp->data < curr->data; j++) {
            //tmp = tmp->next;
            res = tmp;
            tmp = XOR(tmp->addr,pre_tmp);
            pre_tmp = res;
            if(j != 0) {
                res = prev;
                prev = XOR(prev->addr,pre_prev);
                pre_prev = res;
            }
        }
        // insert
        if (tmp == head) {
            /*tail->next = curr->next;
            curr->next = head;
            head = curr;*/
            if (!pre_tail)
                pre_tail = curr;
            tail->addr = XOR(pre_tail,XOR(curr->addr,tail));
            curr->addr = tmp;
            if (tmp != tail)
                tmp->addr = XOR(curr,tmp->addr);
            head = curr;
        } else if (tmp == curr) {
            //tail = tail->next;
            res = XOR(pre_tail,tail->addr); // res is tail->next
            pre_tail = tail;
            tail = res;
        } else {
            /*prev->next = curr;
            tail->next = curr->next;
            curr->next = tmp;*/
            if (tail == tmp){
                tail->addr = XOR(curr,XOR(curr->addr,tail));
                pre_tail = curr;
            } else {
                tail->addr = XOR(XOR(tail->addr,curr),XOR(curr->addr,tail));
                tmp->addr = XOR(XOR(tmp->addr,pre_tmp),curr);
            }
            curr->addr = XOR(prev, tmp);
            prev->addr = XOR(pre_prev,curr);
        }
        //curr = tail->next;
        list *ttmp = curr;
        curr = XOR(pre_tail,tail->addr);
        if (curr)
            curr->addr = XOR(XOR(curr->addr,ttmp),tail);
    }

    return head;
}

事實上，XOR-linked list 雖然能節省記憶體，但是在實做上我個人認為十分累人，因為我們需要保證 list 中每個 node 的 addr 值的正確性。也就是說，當我們每對節點做一個操作，很有可能就有 1 個以上的 addr 值需要被修改。

接著稍微說明我的實做，若對用最初版本 linked list 實做 insertion sort 不清楚的同學可以參考 [Linked List Sort
](https://npes87184.github.io/2015-09-12-linkedListSort/)。我的 insertion sort 在插入的時候主要分成三種情況，分別是要插入的點在最前面，中間和 tail (指向已經 sort 好的 sub-list) 的後面。三種狀況對應該怎麽操做我有在註解附上相對應較善解人意的直覺版本 linked list，而我的 XOR 操作就是在做註解做的事。

補充說明兩件事，變數的命名意義：

tmp : 在 sorted list 上移動的點（類似c++ iterator)
pre_XXXX : XXX 的前一個點
cur : 目前準備要比較的點
tail : sorted list 的最尾端

此外當要插入 sorted-list 中間時還可以分成兩種情況，即是否是插在 `pre_tail` 和 `tail` 之間，如果是則需要額外維護 `pre_tail` 的 addr 值。

最後，修改 XOR-merge sort，讓它能夠判斷小於某個 threshold，就會改執行 insertion sort。

原本測驗提供的 merge sort 是用由左到右，一次切一個節點。這和我們原本認知的，第一次先切一半，再來切那一半的一半，有所不同。所以我們要先把原本切節點的地方改成：

int mid = (end - begin + 1) / 2;
int it = 0;
list *right = start;
list *left = start;

list *pre_right = NULL;
list *tmpr = right;
list *tmpp;
while (it < mid) {
    tmpr = right;
    right = XOR(pre_right,right->addr);
    pre_right = tmpr;
    it++;
}
// cut two list
pre_right->addr = XOR(pre_right->addr,right);
right->addr = XOR(right->addr,pre_right);

left = opt_sort(left,begin,begin + mid-1);
right = opt_sort(right,begin + mid, end);

這裡迴圈在做的是找到中間的點 `right`，找到後接著透過 `pre_right` 和 `right` 來切斷左右兩條 list。最後得到真正意義上的平分兩條 list。

而在這之前，我們還要透過 `begin` 和 `end` 來判斷目前傳入的 sub-list 是否小於 threshold。

if (end - begin + 1 < threshold)
    return insert_sort(start, end - begin + 1);

### 實驗

#### 找出 S (threshold)
我想到的實驗方式很簡單，把 S 從 0~1000 帶進 threshold 做 sorting。再觀察哪個 S 使 sort 速度快，就選那個當作是我們判斷呼叫 insertion sort 的基準。

int main()
{
    for (int j = 0; j < EXP_TIME; j++) {
        threshold = j;
        head = NULL;
        // generate random list
        srand((unsigned) time(&t));
        for (int i = 0; i < LIST_SIZE; i++)
            insert_node(&head,rand()%1000);
        
        // get elapse of sorting
        clock_gettime(CLOCK_REALTIME, &t1);
        head = opt_sort(head,0,LIST_SIZE-1);
        clock_gettime(CLOCK_REALTIME, &t2);
        
        printf("%d %lf\n",j,elapse(t1, t2));
        delete_list(head);
    }
}

接著把輸出做成 gnuplot：( 有將 task 固定在 cpu 1 以減少干擾 )

這張圖的描述很明顯就是，S 在某個區間會有差不多的速度，然後分四個區間。我聯想到的是，我在裝置管理員監控我的電腦發現也是剛好有 L1, L2 和 L3 cache。這時候我做出了一個假設，**或許**在 S 小於 200 時呼叫 insertion sort 時，L1 cache 能夠放的下常用的變數，所以自然很快。若 200~400，放不下的就會放到 L2 cache，而速度自然會慢下來，因為在 L1 層級發生 miss。接著我對為什麼 800 前後的 gap 這麼大做出猜測。 S 大於 800 之後，對應到的是 L3 cache 的下一個層級的暫存器( 或許是 disk，所以效能的差距才會比前三級 cache 彼此間的差異還大 )。

#### 比較三種版本 sort 的效能　

延續上述實驗，S 選 400以內應該都很快，所以我隨便選了 10。

而這個部份的實驗也很簡單，在每一次迭代中，做三種不同的 sort。分別是：`ori_sort`,`opt_sort`和`insert_sort`，對應到的分別是沒優化過的 merge sort, 優化過的 merge sort 和 insertion sort。

    for (int j = 0; j < EXP_TIME; j++) {
        double time_ori;
        double time_opt;
        double time_insert;
        threshold = 10;
        // measuring optimize merge sort (+insertion sort)
        head = NULL;
        srand((unsigned) time(&t));
        for (int i = 0; i < LIST_SIZE; i++)
            insert_node(&head,rand()%1000);
        clock_gettime(CLOCK_REALTIME, &t1);
        head = opt_sort(head,0,LIST_SIZE-1);
        clock_gettime(CLOCK_REALTIME, &t2);
        time_opt = elapse(t1, t2);
        delete_list(head);
        
        // measuring original merge sort
        head = NULL;
        ..
        time_ori = elapse(t1, t2);
        delete_list(head);

        printf("%d %lf %lf %lf\n",j,time_opt,time_ori,time_insert);
    }

篇幅關係，省略部份實驗程式碼。大體上照著實驗說明實做。

接著透過 gnuplot 得到：

很明顯可以看出，把 insertion sort 融合到 merge sort 可以快上數百倍（實際上的數字是，優化的 merge sort 排序十萬個點只需要 1~2 ms）。這個結果的確驚人，沒想到快這麼多。
還有一個額外的亮點是 average case $O(N^2)$ 的 insertion sort 其實也沒那麼糟麻！表現明顯比 average case $O(Nlog{N})$ 的 merge sort 還要好。這其實也說明了一件事，在**隨機**的情況下，很少出現類似整個顛倒的序列 (insertion sort 的 worst case) 讓你排序。

最後附上[完整程式碼](https://github.com/eecheng87/data-structure-implementation/tree/master/xor-linked-list)。

---

## 題目 `2`
### 改寫 insert

void insert(struct node *newt)
{
    struct node **link = &head;
    while (*link && (*link)->data < newt->data)
        link = &(*link)->next;
    newt->next = *link;
    *link = newt;
}

這個函式的功能是依照大小插入節點，舉例：

insert(&(struct node){.data = 10, .next = NULL});
print();
insert(&(struct node){.data = 20, .next = NULL});
print();
insert(&(struct node){.data = 5, .next = NULL});
print();

你可以得到

10->
10->20->
5->10->20->

`(*link)->data < newt->data` 之所以要這樣寫是因為 link 是 pointer to pointer ，若是 pointer，只須 `link->data` 就可以拿到資料，但是前者的 `*link` 值才是節點的地址，對址做 de-reference，`*(*link).data` 即 `(*link)->data`。

而我們非得使用 pointer to pointer 的原因在 `*link = newt`，若只是 pointer 的操作 `link = newt` 這樣只有函數裡區域變數複製的那份 `struct node *link` 會拿到值，而非 `head`。

## 延伸問題

比較兩種版本的
* 速度：pointer to pointer 版本比較快

    clock_gettime(CLOCK_REALTIME, &t1);
    for(int i = 1; i < 10000; i++){
        struct node *tmp= (struct node*)malloc(sizeof(struct node));
        tmp->data = i;
        tmp->next = NULL;
        insert(tmp);
    }
    clock_gettime(CLOCK_REALTIME, &t2);
    printf("Time insert : %ld\n", elapse(t1, t2));

實驗方法是盡量讓 `tmp` 在 list 中移動越多次越好，這樣才能測出差距。所以每次新增的點一定會跑完整條 list 才插入到最後。

參考輸出：(單位奈秒) / [實驗程式碼](https://gist.github.com/eecheng87/1bbb77c62dedb097125941804df19978)

    Time insert : 200441303
    Time good insert : 163583162 

* branch 數量
若直接觀察的話，可以發現 `insert` 的 branch 數會略多，因為有最後的 if-else 判斷。

    $ sudo perf record -e branch-misses:u,branch-instructions:u ./insert
    $ sudo perf report

用 `perf` 觀察 `insert` 和 `good_insert` 的差異，發現前者的 branch instruction 有 677 個，後者為 654個。和預期一樣，後者略少。但是 branch miss 的數目後者就比較大了。