# 2019q3 Homework4 (quiz4)
contributed by < `colinyoyo26` >

## 測驗 `1`

考慮一個單向 linked list:

typedef struct __list {
    int data;
    struct __list *next;
} list;

在不存在環狀結構的狀況下，以下函式能夠對 linked list 元素從小到大排序:

list *sort(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    LL0;

    left = sort(left);
    right = sort(right);

    for (list *merge = NULL; left || right; ) {
        if (!right || (left && left->data < right->data)) {
            if (!merge) {
                LL1;
            } else {
                LL2;
                merge = merge->next;
            }
            LL3;
        } else {
            if (!merge) {
                LL4;
            } else {
                LL5;
                merge = merge->next;
            }
            LL6;
        }
    }
    return start;
}

請補完程式碼。

:::success
延伸問題:
1. 解釋上述程式運作原理;
2. 指出程式改進空間，特別是考慮到 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort);
3. 將上述 singly-linked list 擴充為 circular doubly-linked list 並重新實作對應的 `sort`;
4. 依循 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 程式碼的方式，改寫上述排序程式;
5. 嘗試將原本遞迴的程式改寫為 iterative 版本;
6. 將 [2019q1 第 3 週測驗題 (下)](https://hackmd.io/@sysprog/SkrVSKiU4) 提及的 XOR linked list 列入考量，也實作對應的排序程式，並比較效能和記憶體開銷;
7. 比照 [List Sort](https://arxiv.org/pdf/1310.7890.pdf) 的手法來分析前述程式 (含擴充版本) 的效能表現;
:::

==解題==

- 一開始這邊的實作比較特別一點，每次 divide 的點為第一個元素，所以可以知道 LL0 為 `left->next = NULL`

list *left = start;
list *right = left->next;
LL0;

- 再來只有 merge 第一個元素時會進入 `if (!merge)` ，可以看出 LL1 為 `start = merge = left`
- start 指向 merge 後第一個元素
- 接者不是第一個的情況只要把尾端元素的 `next` 指下一個元素就好 `merge->next = left
- 最後 left 被選到所以要往後移`left = left->nex`
- 右邊和左邊同理

if (!right || (left && left->data < right->data)) {
    if (!merge) {
        LL1;
    } else {
        LL2;
        merge = merge->next;
    }
    LL3;
} 

### 程式改進空間

- 如同解題時提到的「每次 divide 的點為第一個元素」所以執行的情況其實會像 quick-sort 的 worst case 一樣( pivot 都選到極值)，時間複雜度為 $O(n^2)$
- `merge sort` 就是從中間切才有 $O(nlogn)$ 的穩定效能，但是這個實作沒做到這點
- 其時間開銷寫成遞迴式: $T(n) = T(n - 1) + n$
- 以下簡單圖例說明

- [ ] divide 過程

- [ ] merge 過程

:::warning
改用 GraphViz 重新製作上方 div/merge 圖例;
GraphViz 的描述內容可內嵌於 HackMD 頁面，請善用;
:notes: jserv
:::
- 用內嵌語法會有如下警告訊息跑出來，不知道是不是 bug

:::warning
TypeError: Y.renderString(...).then(...).catch(...).finally is not a function
:::
> 太好了，表示你可以提交錯誤回報: https://github.com/hackmdio/hackmd-io-issues/issues
> 之後 HackMD 改版就會有你的名字

- 為了驗證我的推論所以做了以下實驗 (擷取部份 code)
- merge.c

int main(int argc, char** argv){
    size_t size = atoi(argv[1]);
    list head;
    struct timespec start, end;
    head.next = NULL;
    for (size_t i = 0; i < size; i++){
        list *item = malloc(sizeof(list));
        item->data = random();
        item->next = head.next;
        head.next = item;
    }
    clock_gettime(CLOCK_REALTIME, &start);
    head.next = sort(head.next);
    clock_gettime(CLOCK_REALTIME, &end);
    printf("%lu %lu\n", size, end.tv_nsec - start.tv_nsec );

    return 0;
}

- test.sh

#!/bin/bash

rm *.txt
gcc  -o m m.c
for i in $(seq 1 50 2000)
do
    ./m $i >> out.txt
done
gnuplot ./plot.gp

- 結果
- 從數據及圖可以看出的確是 $O(n^2)$ 趨勢


- 部份實驗數據

|elments | time (ns)
|-----|-
| 1 | 119 |
| 101 | 28327 |
| 201 | 114818 |
| 301 | 221432 |
| 401 | 386574 |
| 501 | 598338 |
| 601 | 862473 |
| 701 | 1165719 |
| 801 | 1680010 |
| 901 | 1893432 |

- 為了更嚴謹一些，重新改寫了從中間 divide 的版本，看出效能確實有很大的差異

- 主要是多了這個迴圈，把 list 平均分到 left right

    for (size_t i = 0; start; i++){
        tem = start;
        start = start->next;
        if (i & 1){
            tem->next = left.next;
            left.next = tem;
        } else {
            tem->next = right.next;
            right.next = tem;
        }
    }

- [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort) 提到因為 memory hierarchy 的關係，所以用 Cache-aware versions of the merge sort algorithm 減少 cache 資料搬動的次數，其中一個作法為分割到剛好滿足 cache 大小時就用 `in-place sorting algorithm` 排序
:::warning
[skip list](https://en.wikipedia.org/wiki/Skip_list) 是種變形，之前修課的學生對此進行研究: [共筆](https://hackmd.io/@Vy_ZuZdnSo-Wv4jSWgNmLw/B1OZFDL1H)
:notes: jserv
:::

- 試著在 size <= 64 時使用 insertion sort 且為了善用 spatial locality 把 divide 的迴圈改成以下形式
- 差在 if 的條件，一開始沒注意到這點，所以實驗結果一直不如預期
- 雖然是 linked list 但是一開始插入節點時是循序的差入，每個節點的 virtual address 只相差 32 bytes
- 待更新

    for(size_t i = 0; start; i++){
        tem = start;
        start = start->next;
        if (i < size / 2){
            tem->next = left.next;
            left.next = tem;
        } else {
            tem->next = right.next;
            right.next = tem;
        }
    }

- 實驗結果
- insertion sort

list *insert_sort(list *start){
    list **prev, **cur = &start, *tem;
    while(*cur){
        cur = &(*cur)->next;
        prev = &start;
        while(*cur && *prev != *cur){
            if((*prev)->data > (*cur)->data){
                tem = *cur;
                *cur = (*cur)->next;
                tem->next = *prev;
                *prev = tem;
                prev = &start;
                continue;
            }
            prev = &(*prev)->next;
        }
    }
    return start;
}

### circular doubly-linked list
- 實作了邏輯相同的 doublly linked 版本
- 因為 `list` 的操作會一直用到，所以寫成 function
- `replace` function 內一開始忘記把左右 node 只到新的 head 找了很久
- sort.c

void sort(list *start) {
    /* empty or singular */
    if (start->next == start->prev)
        return;
    list left, right;
    init_list(&left);
    init_list(&right);  
    insert_tail(&left, pop_item(start->next));
    replace(start, &right);
    sort(&right);
    init_list(start);
    
    for (; !is_empty(&left) || !is_empty(&right); ) {
        if (is_empty(&right) || (!is_empty(&left) && first_data(&left) < first_data(&right))) 
            insert_tail(start, pop_item(left.next));
        else 
            insert_tail(start, pop_item(right.next));       
    }
}

- list.h

typedef struct __list {
    int data;
    struct __list *next;
    struct __list *prev;
} list;

static inline void init_list(list* head){
    head->next = head;
    head->prev = head;
}

/* insert to tail of linked list */
static inline void insert_tail(list* head, list* target){
    list *prev = head->prev;

    target->next = head;
    target->prev = prev;
    prev->next = target;
    head->prev = target;
}

/* pop the certain item and return it */
static inline list* pop_item(list* item){
    list *next = item->next,
        *prev = item->prev;
    
    next->prev = prev;
    prev->next = next;
    return item;
}

static inline bool is_empty(list* head){
    return head->next == head;
}

/* return data of first entry*/
static inline int first_data(list* head){
    return head->next->data;
}

/* replace the head of list */
static inline void replace(list* origin, list* new){
    list *next = origin->next,
        *prev = origin->prev;

    *new = *origin;
    next->prev = new;
    prev->next = new;
}

### iterative version
- 相同邏輯的 iterative版本，差在是從左邊 merge 時間複雜度也是 O($n^2$)

list *sort_iter(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    list *tem;
    left->next = NULL;

    do {
        tem = right->next;
        right->next = NULL;

        for (list *merge = NULL; left || right; ) {
            if (!right || (left && left->data < right->data)) {
                if (!merge) {
                    start = merge = left;
                } else {
                    merge->next = left;
                    merge = merge->next;
                }
                left = left->next;
            } else {
                if (!merge) {
                    start = merge = right;
                } else {
                    merge->next = right;
                    merge = merge->next;
                }
                right = right->next;
            }
        }
        left = start;
        right = tem;
    } while(tem);
    return start;
}

### XOR linked list
- sort.c

void sort(xlist* list) {
    if (!list || list->head == list->tail)
        return ;
    xlist left, right;
    xlist_init(&left);
    xlist_insert(&left, xlist_popfront(list));
    right = *list;
    sort(&right);
    xlist_init(list);
    
    for (; left.head || right.head; ) {
        if (!right.head || (left.head && first_data(&left) < first_data(&right)))
            xlist_insert(list, xlist_popfront(&left));
        else 
            xlist_insert(list, xlist_popfront(&right));
    }
}

- xlist.h

typedef struct xor_node {
    int data;
    uint64_t xptr;
} xnode; 

typedef struct xor_list {
    struct xor_node *head, *tail;
} xlist;

static inline void xlist_init(xlist* list){
    list->head = list->tail = NULL;
}
/* use to trace the list */
static inline void xlist_next(xnode** cur, xnode** prev){
    xnode* tem = *cur;
    *cur = (xnode*) ((uint64_t) (*cur)->xptr ^ (uint64_t) *prev);
    *prev = tem;
}
/* pop and retrun first item */
static inline xnode* xlist_popfront(xlist* list){
    xnode *tem, *next = (xnode *) (list->head->xptr ^ (uint64_t) NULL);

    /* originally, next->xptr == list.head ^ next->next */ 
    if(next)
        next->xptr = next->xptr ^ (uint64_t) list->head ^ (uint64_t) NULL;
    tem = list->head; 
    list->head = next;
    return tem;
}
/* retrun data in first entry */
static inline int first_data(xlist* list){
    return ((xnode *)((uint64_t) list->head ^ (uint64_t) NULL))->data; 
}

/* insert tail */
static inline void xlist_insert(xlist* list, xnode* node){
    node->xptr = (uint64_t) list->tail ^ (uint64_t) NULL;

    if(!list->head){
        list->tail = node;
        list->head = node;
        return;
    }

    list->tail->xptr = list->tail->xptr ^ (uint64_t) NULL ^ (uint64_t) node;
    list->tail = node;
}   

- 比較和 doubly linked list 記憶體開銷 (size 100)
- 用 valgrind 觀測 heap 使用率
- 看出用 doubly-linked list 每個 block 多了 8 bytes 也就是一個指標所佔的大小
- [ ] doubly-linked list

==5409== HEAP SUMMARY:
==5409==   in use at exit: 2,400 bytes in 100 blocks
==5409==   total heap usage: 101 allocs, 1 frees, 3,424 bytes allocated

- [ ] xor linked list

==5435== HEAP SUMMARY:
==5435==     in use at exit: 1,600 bytes in 100 blocks
==5435==   total heap usage: 101 allocs, 1 frees, 2,624 bytes allocated

### 效能分析
- 對結果不太意外， xor 的實做為了節省開銷需要更大的計算量，而 doubly linked list 原本就要比 sigle linked list 還需要更多的操作

:::danger
修正用語: (注意連字號)
* `singly-linked list (orig)`: 原本給定的程式碼
* `singly-linked list (fixed)`: 嘗試修正效能表現的程式碼
* `doubly-linked list`: 雙向鏈結串列
:::
- 已更正

## 參考資料
- [xor liked list](https://en.wikipedia.org/wiki/XOR_linked_list)
- [Merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort)