# 2020q1 Homework3 (quiz3)
contributed by < `jeeeff` >

## 解釋上述 XOR linked list 排序實作的原理，並指出其中可改進之處
### XOR 為鍊結與一般指標的差別
一般指標只需要用 node.link 就可以直接指向下個節點，但 XOR 的 list 需要用 `next = XOR(prev, curr->addr);` 這種 XOR 的特性往前後移動

while (curr) {
    /*  ACTION  */
    next = XOR(prev, curr->addr);
    prev = curr;
    curr = next;
} 

* 在這次作業裡多次用到上面的 while 迴圈來移動
### sort

list *sort(list *start) // 傳 head 進副程式 sort，並回傳 head
{
    if (!start || !start->addr) // 若 list 為空或只有一項，直接回傳 head
        return start;

    list *left = start, *right = start->addr;
    left->addr = NULL;
    right->addr = XOR(right->addr, left); // 切割 list ，left 僅一項，其餘在 right ，所以 merge sort 退化為 insertion sort

    left = sort(left); //
    right = sort(right); // divide （Partition）

    for (list *merge = NULL; left || right;) { // conquer and then merge
        if (!right || (left && left->data < right->data)) { // 子序列（right）尚未為空
        // 或左項（left->data）小於右項（right->data）
        // merge 為最終要輸出的主序列（已排序）
            list *next = left->addr; // next 是暫存變數，負責插入的動作
            if (next) // 若 left 不為 list 的尾巴，用 XOR 紀錄 addr
                next->addr = XOR(left, next->addr);

            if (!merge) { // 這是剛開始 Sort 的情況，第一項的 addr 指向 NULL
                start = merge = left; // start 為 merge 的 head
                merge->addr = NULL;
            } else {
                merge->addr = XOR(merge->addr, left); // 用 XOR 紀錄 addr 指向的位置
                left->addr = merge; // left 這項為目前的尾巴， addr 只要 XOR(merge, NULL) 就好
                merge = left; // merge 項右移一格到尾巴（left）
            }
            left = next; // left 子序列往後移一格，繼續做下去
        } else { // 子序列為空或左項（left->data）不小於右項（right->data）
            list *next = right->addr;
            if (next)
                next->addr = XOR(right, next->addr);

            if (!merge) { // 這也是剛開始 Sort 的情況，第一項的 addr 指向 NULL
                start = merge = right;
                merge->addr = NULL;
            } else {
                merge->addr = XOR(merge->addr, right);
                right->addr = merge;
                merge = right;
            }
            right = next; // right 子序列往後移一格，繼續做下去
        }
    }
    return start;
}

### 可改進之處
* Insertion Sort 的時間複雜度平均是 O(n^2^)，如果在 Partition 的時候使 left 子序列盡量和 right 子序列一樣長，
* 預設如上，實際做過一次，發現速度上慢了許多，並沒有降到 Merge sort 的 O(nlogn)，先貼 code 再貼圖

list *merge_sort(list *start, int cut)
{
    if (!start || !start->addr)
        return start;

    list *left = start, *right = start->addr, *left_end = start;

    int mid = cut / 2;
    for (int i = 0; i < mid - 1; i++) {
        list *tmp;
        tmp = right;
        right = XOR(right->addr, left_end);
        left_end = tmp;
    }
    left_end->addr = XOR(right, left_end->addr);
    right->addr = XOR(right->addr, left_end);
    left = merge_sort(left, mid);
    right = merge_sort(right, cut - mid);

    left = merge_sort(left, mid);
    right = merge_sort(right, cut - mid);

...

* 可見這方式是失敗的

:::danger
用語該精確，什麼「失敗」？
:notes: jserv
:::

### main
* 附上目前 main 主程式

#define count 100 // for average
#define round 500 // for size

int main()
{
    int i, j, input;
    long long ts[round], tm[round];
    struct timespec start, stop;
    FILE *fp;
    if(!(fp = fopen("time.txt","w"))) {
        printf("Open file error\n");
        return -1;
    }
    for(j = 0; j < round; j++) {
        ts[j] = 0;
        tm[j] = 0;
    }
    for(j = 0; j < round; j++) {
       for(i = 0; i < count; i++) {
        struct __list *a = malloc(sizeof(struct __list));
        struct __list *b = malloc(sizeof(struct __list));
        a = NULL;
        b = NULL;
        
        for(int k = 0; k < j; k++) {
            input = rand();
            insert_node(&a, input);
            insert_node(&b, input);
        }

            clock_gettime(CLOCK_MONOTONIC, &start);
            a = sort(a);
            clock_gettime(CLOCK_MONOTONIC, &stop);
            ts[j] += stop.tv_nsec - start.tv_nsec;
            if (ts[j] < 0 && j > 0)
//                ts[j] = ts[j - 1];
            delete_list(a);

            printf("\n%dnd sorting-->\n",j);
//        print_list(b);
            clock_gettime(CLOCK_MONOTONIC, &start);
            b = merge_sort(b, j + 1);
            clock_gettime(CLOCK_MONOTONIC, &stop);
//            printf("%dn\t sorted\n", i + 1);
            tm[j] += stop.tv_nsec - start.tv_nsec;
//            print_list(b);
            if (tm[j] < 0 && j > 0)
//                tm[j] = tm[j - 1];
            delete_list(b); 
        }
        ts[j] /= count;
        tm[j] /= count;
        fprintf(fp,"%d\t%lld\t%lld\n", j+1, ts[j], tm[j]    );
//        printf("%d\t%ld\n", j+1, ts);
    }
    fclose(fp);
}

:::danger
附帶一提，這裡是做 100 次取平均，而且不知道為什麼輸出時間可能為負數，若不加上補救方式（如下），最終圖會有許多負的極端值
:::
* 補救方式：

if (ts[j] < 0 && j > 0)
    ts[j] = ts[j - 1];
...
if (tm[j] < 0 && j > 0)
    tm[j] = tm[j - 1];

* 許多負的極端值的圖：

:::danger
1. 不要只用平均值，用統計手法，去除 outlier。
2. 留意 timer 的精準度

:notes: jserv
:::

* 另一個改進策略是題目提到的，讓子序列大小$S$恰好為 Cahce 能容納的大小，減少 Paging 次數
## Optimizing merge sort

* 先搜尋 CPU 的 Cache size，使用指令

$ pico /proc/cpuinfo

* 找到的硬體資訊如下

processor       : 0
cache size      : 3072 KB
...
processor       : 1
cache size      : 3072 KB
...
processor       : 2
cache size      : 3072 KB
...
processor       : 3
cache size      : 3072 KB

* 然後修改 merge_sort 成 big_s_sort，蠻快的

list *big_s_sort(list *start, int cut, int s)
{
    if (!start || !start->addr)
        return start;

    list *left = start, *right = start->addr, *left_end = start;

    int mid = cut / 2;
    for (int i = 0; i < mid - 1; i++) {
        list *tmp;
        tmp = right;
        right = XOR(right->addr, left_end);
        left_end = tmp;
    }
    left_end->addr = XOR(right, left_end->addr);
    right->addr = XOR(right->addr, left_end);
    if(mid > s) {
        left = big_s_sort(left, mid, s);
        right = big_s_sort(right, cut - mid, s);
    } else {
        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 = 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;
}

* 先設定$S$為 5 測試三個演算法的速度，明顯快出許多
* 接下來就是單純測試 $S$ 與 list length 的關係
** 先固定 list 長度為 1~10000，S 為 100
** 先固定 list 長度為 1~10000，S 為 1000
** 先固定 list 長度為 1~10000，S 為 5000

## 修改 lab0-c 裡頭的 harness.c