---
# System prepended metadata

title: 2020q1 Homework3 (quiz3)

---

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

> [測驗題目描述](https://hackmd.io/@sysprog/linux2020-quiz3)
> [GitHub](https://github.com/ryanwang522/linked-list-sorting)

## 測驗 1
這題是探討 XOR linked list 的操作，其實主要就是利用 XOR 的運算特性:
* $A \oplus A = 0$
* $A \oplus 0 = A$
* $A \oplus 1 = \neg A$
* $(A \oplus B) \oplus B = A$

簡單來說，假設串列 `1->2->3` 以 XOR list 表的結構如下：
```
addr     A        B        C
data     1        2        3
link  0 xor B  A xor C  B xor 0
```
所以假設我們現在有一個指向 `B` 的指標，以及一個指向 `A` 的指標 ，則可以透過 `XOR(B->link, A) = C` 得到 `C` 的位址 。

### 解釋 XOR linked list 排序實作的原理，並指出其中可改進之處
主要的概念跟 [quiz1](https://hackmd.io/@sysprog/linux2020-quiz1) 類似，排序邏輯可以參考我之的 [解題思路](https://hackmd.io/@Ryspon/HJVH8B0XU)。

要看懂這次測驗，首先要先知道大量使用的一段程式碼的作用為何
```cpp
xor_list *next = left->addr;
if (next)
    next->addr = XOR(left, next->addr);
merge = left;
left = next;
```
* `left` 一開始指向一串串列的開頭，`left->addr` 為下一節點的位址和 `0` 做 XOR 的結果。
* `next->addr = XOR(left, next->addr);` 把下一個節點和當前的節點切開，以下圖為例，就是把 `A` 跟 `B` 切開，讓 `B->addr = XOR(left, B->addr) = C` (A xor A xor C = C = 0 xor C)
```
addr     A        B        C            A     |    B        C
data     1        2        3     --->   1     |    2        3
link  0 xor B  A xor C  B xor 0      0 xor B  | 0 xor C  B xor 0
```
* `left` 再指到 `next`，也就是說這段程式碼是在**把一串 list 的起點切出來給 `merge`，讓 `left` 指到剩下的 list 開頭**。

接著，就看 `left` 和 `right` 誰的開頭的值比較小，把它切出來連接在 `merge` 的後面（**`merge` 永遠指向 sorted list 的最後一個節點**）。左右的部分邏輯都一樣，這裡以 *`right` 的開頭比較小*的情況為例說明：

```cpp
// 將 `right` 的起點切出來，`next` 指向剩下的 list 的開頭
xor_list *next = right->addr;
if (next)
    next->addr = XOR(right, next->addr);

if (!merge) {
    // merge 為空，代表最終的 sorted list 還沒有東西
    // 將 sorted list 記錄在 `start`
    // 由於目前只有一個節點，因次 merge 也指向他
    // 加上前後都還沒有節點，`merge->addr` = NULL
    start = merge = right;
    merge->addr = NULL;
} else {
    // merge 不為空， merge 同時代表 sorted list 最後一個節點
    // 將 merge 和切出來的 right 接起來
    // 現在換成 right 是最後一個節點了
    merge->addr = XOR(merge->addr, right);
    // 因為 right 的前一個是 merge，因此 `right->addr` = XOR(merge, NULL)
    right->addr = merge;
    // merge 持續指向最後的節點
    merge = right;
}
// right 指向剩下的 right-list 的開頭
right = next;

```

根據以上分析 
* RR1 = `XOR(merge->addr, right)`
* RR2 = `merge`

同理
* LL1 = `XOR(merge->addr, left)`
* LL2 = `merge`

懂了之後發現其實整個 for-loop 就是在把 `left` `right` 兩個排序好的串列進行合併，跟先前作業的 `sorted_merge()` 是在做一樣的事情，只是這裡的 `left` 只有一個節點，因此就退化成了 insertion sort。

### 優化 merge sort
根據 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort) 提到的策略，在子序列大小達到 $S$ 時就不再繼續分割，此時這個 $S$ 為可完整放進處理器 cache 中的元素數量。每個大小為 $S$ 的子序列，都透過適用於小規模 in-place (即不需要額外配置記憶體) 排序演算法（如插入排序或泡沫排序）進行排序，以減少在記憶體內交換特定區域的次數。

> 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. [name=Wikipedia]

這裡目標為設計一個實驗，來找出最佳的 $S$ 為多少。

首先先看一下硬體組成
* OS : Ubuntu 16.04 LTS
* L1d cache : 32K
* L1i cache : 32K
* L2 cache : 256K
* L3 cache : 12288K
* CPU(s) : 12
* Model name : Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz

實作 `insertion_sort` 不難，即使是 XOR linked list，我改寫測驗中的 for-loop 部分為 `sorted_merge()`，每次取還沒排序好的串列中的第一個出來，插入到排序好的串列裡面（i.e. 等同於合併兩個排序好的 list，但其中一個 list 只有一個節點）。

```cpp
static void *insertion_sort(void *start)
{
    if (!start || !((xor_list *)start)->addr)
        return start;

    xor_list *sorted = (xor_list *)start;
    xor_list *next = sorted->addr;
    if (next)
        next->addr = XOR(sorted, next->addr);
    sorted->addr = NULL;

    for (xor_list *curr = next; curr;) {
        next = curr->addr;
        if (next)
            next->addr = XOR(curr, next->addr);
        curr->addr = NULL;
        sorted = sorted_merge(curr, sorted);
        curr = next;
    }
    return sorted;
}
```

#### Experiments

接著是實驗的部分，主要的概念就是令測試的 list 長度為 10000，我把 $S$ 從 1 跑到 1000，繪圖紀錄不同的 $S$ 排序完成所花的時間，並且跟 naive merge sort 比較。

* Optimize merge sort 實作
  * 首先先實作 `front_back_split()` 將陣列切分成前後長度各半的兩個 sublist，並且得到左右 sublist 長度 ( 若輸入長度為奇數，則右 sublist 長度會多 1 )。
  * 概念很簡單，當 sublist 的長度小於 $S$ 時，就使用 `insertion_sort()`，反之則繼續遞迴呼叫 `opt_merge_sort()`
* 另外我這裡也延續 quiz1，把 singly linked list 、 kernel list.h  的 optimized sort 實作也補上，請參考 [GitHub](https://github.com/ryanwang522/linked-list-sorting)。

XOR linked list 實作程式碼如下
```cpp
static void front_back_split(xor_list* src, xor_list **front, xor_list **back, int *front_len, int *back_len)
{
    int len = 0;
    xor_list *fast = src, *fast_prev = NULL, *fast_next;
    xor_list *slow = src, *slow_prev = NULL, *slow_next;
    while (fast && XOR(fast->addr, fast_prev)) {
        // fast = fast->next->next
        fast_next = XOR(fast->addr, fast_prev);
        fast = XOR(fast_next->addr, fast);
        fast_prev = fast_next;
        // slow = slow->next
        slow_next = XOR(slow->addr, slow_prev);
        slow_prev = slow;
        slow = slow_next;
        len++;
    }

    *front = src;
    if (!src) {
        *back = NULL;
    } else if (fast != NULL) {
        // odd
        xor_list *next = XOR(slow->addr, slow_prev);
        next->addr = XOR(next->addr, slow);
        *back = next;
        slow->addr = XOR(slow->addr, next);
        *front_len = len; *back_len = len + 1;
    } else {
        // even
        slow_prev->addr = XOR(slow_prev->addr, slow);
        slow->addr = XOR(slow->addr, slow_prev);
        *back = slow;
        *front_len = *back_len = len;
    }
}

static void *opt_merge_sort(void *start, int list_len, int split_thres)
{
    xor_list *hd = (xor_list *)start;
    if (hd == NULL || hd->addr == NULL)
        return hd;
    if (list_len <= split_thres)
        return insertion_sort(start);

    xor_list *left, *right;
    int left_len = 0, right_len = 0;
    front_back_split(hd, &left, &right, &left_len, &right_len);
    left = opt_merge_sort(left, left_len, split_thres);
    right = opt_merge_sort(right, right_len, split_thres);
    return sorted_merge(left, right);
}
```

實驗的程式碼如下，由於有不同版本(singly、list.h、XOR)的實作，我把各自版本的實作封裝在 `Sorting` 的結構介面中
```cpp
typedef struct __INTERFACE {
    void *(*initialize)();
    void (*push)(void **head_ref, int data);
    void (*print)(void *head, bool new_line);
    void *(*sort)(void *start);
    void *(*opt_sort)(void *start, int list_len, int split_thres);
    bool (*test)(void **head_ref, int *ans, int len, bool verbose, struct __INTERFACE *sorting);
    void (*list_free)(void **head);
} Sorting;
```

```cpp
// find optial split size
int testcase_len = 10000;
for (int thres = 1; thres < MAX_SPLIT_SIZE; thres++) {
    int *testcase = malloc(sizeof(int) * testcase_len);
    for (int j = 0; j < testcase_len; j++)
        testcase[j] = rand() % testcase_len;
    void *head = sorting_impl->initialize();
    for (int i = testcase_len - 1; i >= 0; i--)
        sorting_impl->push((void **)&head, testcase[i]);

    // optimized sorting
    struct timespec start, end;
    clock_gettime(CLOCK_REALTIME, &start);
    head = sorting_impl->opt_sort(head, testcase_len, thres);
    clock_gettime(CLOCK_REALTIME, &end);
    printf("%lf", diff_in_second(start, end));
    sorting_impl->list_free(&head);

    head = sorting_impl->initialize();
    for (int i = testcase_len - 1; i >= 0; i--)
        sorting_impl->push((void **)&head, testcase[i]);

    // naive mergesort
    clock_gettime(CLOCK_REALTIME, &start);
    head = sorting_impl->sort(head);
    clock_gettime(CLOCK_REALTIME, &end);
    printf(" %lf\n", diff_in_second(start, end));
    sorting_impl->list_free(&head);
    free(testcase);
}
```
依據結果製圖，在跑實驗的過程中有使用`taskset`，將 process 固定在 `cpu1` 上跑。

```
$ make expr 2
```
* $S$ := 1~1000，list 長度為 10000
![](https://i.imgur.com/WXjmLkJ.png)

* $S$ := 1~100，list 長度為 10000
![](https://i.imgur.com/g6jS7ks.png)

* 來看一下比 merger sort 還快的區間 $S$ := 1~25，list 長度為 10000
![](https://i.imgur.com/HLAYEMC.png)


做了一連串實驗發現:
* 當 list 長度越長，且 $S$ 大小選擇適當時，optimize merge sort 的優化就越顯著。
* 隨著 $S$ 越大，插入排序跟合併排序在時間複雜度的差距就明顯影響了排序時間。 
* 也可以看到 sorting time 反應出了 memory hierarchy 的概念。

接著固定 $S$ 來比較不同 sorting algo. 的時間:
* $S = 10$, list 長度為 10000
  * insertion sort $O(n^2)$ 跟 merge sort $O(nlogn)$ 的差異顯現出來 
![](https://i.imgur.com/SzJBdJ9.png)
* $S = 10$, list 長度為 100
  * optimized merge sort 有稍微快一點，但優化的程度沒有想像中多
![](https://i.imgur.com/C0jhkj2.png)

