# 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
* $S$ := 1~100，list 長度為 10000
* 來看一下比 merger sort 還快的區間 $S$ := 1~25，list 長度為 10000
做了一連串實驗發現:
* 當 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)$ 的差異顯現出來
* $S = 10$, list 長度為 100
* optimized merge sort 有稍微快一點，但優化的程度沒有想像中多
Sign in with Wallet
Connect another wallet