2020q1 Homework3 (quiz3)

contributed by < kylekylehaha >

第三週測驗
 作業要求

tags: `linux2020`

測驗 1

XOR Linked list
根據維基百科的描述 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)

測驗一題目:

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。

LL1 & LL2

在第一小段，由於 left 為 head，因此 left->addr 即為它的下一個 node

...
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

            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。然而因為 left 只有一個節點，故 merge sort 效果不佳，會退化成 insertion sort，因此我們可以參考 lab0 的做法，將 split 加到 sort：從中間開始切。

優化 XOR-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。

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

測試一下:

int main(){
    list **start;
    for(int i = 0;i < SIZE;i++){
        insert_node(start, i);
    }
    print(*start);
    return 0;
}

輸出:

list:  9 8 7 6 5 4 3 2 1 0

insertion_sort

這邊我們會有兩個序列，分別是 sorted & 尚未排序的序列，每次都將尚未排序的序列取一個出來，和 sorted 一起丟入 merge 內做排序。

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

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

測試一下：

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

輸出:

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 的子序列。

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

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

測試一下

...
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);
...

輸出

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 的效果。

#define LIST_LEN 10000

將程式固定在 CPU 0 上面，可以減少 context switch 的影響

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，也就是遞減的順序，因此其時間沒有差太多。
測驗一程式碼

修改 lab0-c 裡頭的 harness.c，將原本內部使用的 doubly-linked list 換為 XOR linked list，觀察記憶體佔用率的變化，可設計頻繁的 test_malloc / test_free 呼叫交錯情境。

測驗 2

基本上，這題就是 Linus Torvald 在 TED 演講所提到的「有品味的程式碼」，可以參照 fcamel 的心得。我們直接來看問題:

#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 函式，功能等價但更簡潔，如下:

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，因為 -> 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

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 比較少，故執行時間較短。

tasted insert time: 156140968 ns
ori time: 225535635 ns

利用 perf 來確認 branch 的次數

$ gcc -o ll linked_list.c
$ sudo perf record -e branch-misses:u,branch-instructions:u ./ll
$ sudo perf report

insert_v1

288 branch-misses:u
714 branch-instructions:u

u 代表 userspace

insert_v2 (tasted insert)

250 branch-misses:u
640 branch-instructins:u

測驗二程式碼

2020q1 Homework3 (quiz3)

tags: `linux2020`

測驗 1

延伸問題

解釋上述 XOR linked list 排序實作的原理，並指出其中可改進之處

優化 XOR-merge sort

修改 lab0-c 裡頭的 harness.c，將原本內部使用的 doubly-linked list 換為 XOR linked list，觀察記憶體佔用率的變化，可設計頻繁的 test_malloc / test_free 呼叫交錯情境。

測驗 2

延伸問題

解釋程式運作原理、對執行時間的影響 (考慮到 branch predictor 行為)，和指出其實作限制

在 Linux 核心找出運用類似的手法的程式碼並解說

Reference

2020q1 Homework3 (quiz3)

tags: linux2020

測驗 1

延伸問題

解釋上述 XOR linked list 排序實作的原理，並指出其中可改進之處

優化 XOR-merge sort

修改 lab0-c 裡頭的 harness.c，將原本內部使用的 doubly-linked list 換為 XOR linked list，觀察記憶體佔用率的變化，可設計頻繁的 test_malloc / test_free 呼叫交錯情境。

測驗 2

延伸問題

解釋程式運作原理、對執行時間的影響 (考慮到 branch predictor 行為)，和指出其實作限制

在 Linux 核心找出運用類似的手法的程式碼並解說

Reference

tags: `linux2020`