# lab0-c link list sorting 實作
## 開發工具

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

## 針對佇列排序的程式碼實作
### q_sort
實作方式基於buttom up merge sort，一共寫了三個版本和改動linux kernel的list_sort.c來比較有無避免cache thrashing，由於要使用descend去決定遞增遞減，所以我將`q_sort`寫成:

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return;
    if (descend)
        _q_sort(head, q_descend_cmp);
    else
        _q_sort(head, q_ascend_cmp);
}

`_q_sort`定義如下，並實作對應遞增遞減的排序邏輯，可以藉此簡化排序中判斷遞增遞減的邏輯
`static void _q_sort(struct list_head *head, list_cmp_func_t qcmp);`

### 第一版

> Commit: [ad4d266](https://github.com/sysprog21/lab0-c/commit/ad4d266d95f274282e6f5252d172e3235627c105)
>
我每次都從頭跑完整個`link list`，第一次走訪整個`link list`時，將兩兩相鄰的node合併，第 n 次走訪時將`2^n`個相鄰node合併，直到`2^n`大於`link list`的`size`即完成排序
* 可以發現這版使用大量的int去計算位置與大小，十分的低效，cache thrashing的問題也很嚴重

void _q_sort(struct list_head *head, list_cmp_func_t qcmp)
{
    if (!head || list_empty(head))
        return;
    struct list_head *tmp, *l = head, *r = head;
    for (int t = 1, len = 2, size = q_size(head); t < size;
         t <<= 1, len <<= 1, l = r = head) {
        for (int k = 0, i = 0, j = 0; k < size; k += len, i = 0, j = 0) {
            for (j = 0; j < t; j++)
                r = r->next;
            while (i < t && j < len && j + k < size) {
                if (qcmp(l->next, r->next)) {
                    tmp = r->next;
                    r->next = tmp->next;
                    tmp->next = l->next;
                    l->next = tmp;
                    j++;
                } else
                    i++;
                l = l->next;
            }
            for (; j < len; j++)
                r = r->next;
            l = r;
        }
    }
    for (l = head->next, l->prev = head; l != head; l = l->next)
        l->next->prev = l;
}

### 第二版
> Commit: [4b59d29](https://github.com/sysprog21/lab0-c/commit/4b59d2993f0c83fefae7b158360567b154395f82)
>
我參考list_sort.c的操作流程，實作成比較看得懂的版本

### 重點解釋
方便理解可以將整個array視為一顆binary tree的leaves，整個sorting的過程就是Postorder Traversal整個binary tree。
binary tree的內點所代表的位置會是該點子樹最前面的位置，畫出來會像是:

                    [0]
        [0]                     [4]
   [0]        [2]         [4]        [6]
[0]   [1]  [2]   [3]   [4]   [5]  [6]   [7]

Postorder Traversal:

0->1->0->2->3->2->0->4->5->4->6->7->6->4->0

* 過程中第一次出現的0單純指的就是第0個元素的位置，第二次出現則是代表第0跟第1個元素排序的結果，第三次則是第0,1,2,3個元素排序的結果，依此類推。
* 既然知道要處理的index我們可以存下那些位置的pointers避免花時間去找它們，然而另外開memory去記錄這些pointers實在太浪費，透過觀察合併的操作不需要使用到node的prev指標，所以使用每個node裡面的prev去存這些位置會很大姆指。排序完成要記得把prev補回來。

void _q_sort(struct list_head *head, list_cmp_func_t qcmp)
{
    if (!head || list_empty(head))
        return;
    struct list_head *tmp, *l, *r = head, *cur = head, *nxt = head->next;
    for (int t = 0; cur->next != head; t++) {
        nxt = nxt->next;
        int bits = (nxt == head) ? end_bits(t) : t;
        for (; bits & 1; bits >>= 1) {
            r = cur;
            cur = l = cur->prev;
            while (l != r && r->next != nxt) {
                if (qcmp(l->next, r->next)) {
                    tmp = r->next;
                    r->next = tmp->next;
                    tmp->next = l->next;
                    l->next = tmp;
                }
                l = l->next;
            }
            nxt->prev = (r->next == nxt) ? r : nxt->prev;
        }
        nxt->prev->prev = cur;
        cur = nxt->prev;
    }
    for (cur = head->next, cur->prev = head; cur != head; cur = cur->next)
        cur->next->prev = cur;
}

* struct list_head *cur 是用來指向接下來要處理的list_head，*nxt則是記錄尚未處理過的第一個node，`l->next`和`r->next`則是當前做比較的node。
* 這邊的 `end_bits` 目的是將剩餘的link list合併，因為當link list長度不是2^n，我的postorder traversal會在完成前停下所以要將沒完成的一併處理。經過計算可知最後一個位置在處理時會剩下和t二進制裡面1的次數一樣多的link list，故用以下計算處理此例外。

int end_bits(int t)
{
    int res = 0;
    for (; t; t >>= 1)
        if (t & 1)
            res = (res << 1) | 1;
    return res;
}

### 第三版
> Commit: [31539a9](https://github.com/sysprog21/lab0-c/commit/31539a9d806aec4c36de2957160ae64e123e2ef4)
>
這版主要是做一點小優化，假設當前比較的l->next比r的後面很多個都大，這樣我們可以把這些要搬到l->next的nodes一次搬過去就可以減少一些搬動的操作。

 while (l != r && r->next != nxt) {
-     if (qcmp(l->next, r->next)) {
-         tmp = r->next;
+     for (tmp = r; tmp->next != nxt && qcmp(l->next, tmp->next);
+          tmp = tmp->next)
+         ;
+     if (tmp != r) {
+         r->prev = r->next;
         r->next = tmp->next;
         tmp->next = l->next;
-         l->next = tmp;
+         l->next = r->prev;
+         l = tmp;
     }
     l = l->next;
 }

## 修改 lib/list_sort.c 並比較

### 將 `list_sort.c` 加入 `lab0-c` 專案
> Commit: [82f45ec](https://github.com/sysprog21/lab0-c/commit/82f45ec799be0007685dbe3caf4d88a7a6a26f31)

將 Linux 核心原始程式碼的 `list_sort.c` 複製到 `lab0-c` 專案中，並且為了成功編譯做了以下修改：

* 刪掉 `EXPORT_SYMBOL(list_sort)`
* 將 `u8` 改成 `uint8_t` 作為 `count`，並加入 `#include <stdint.h>`
* 移除不必要的 `#include`，手動加入 `likely` ,`unlikely`和`list_cmp_func_t` 的定義。

### 效能分析
為了測大數據下的表現，停止超時的功能，[參考](https://hackmd.io/@yanjiew/linux2023q1-lab0)改動執行檔如下:

make
cp qtest nolimit_qtest
chmod u+x nolimit_qtest
sed -i "s/alarm/isnan/g" nolimit_qtest

執行 `./nolimit_qtest` 並使用以下的命令來分析排序效能:

new
ih RAND 1000000
time sort        

不同版本都測試十次，執行結果如下：
| | q_sort v1 | q_sort v2 | q_sort v3 | linux list_sort |
|-----------| -------- | -------- | -------- | -------- |
|0 | 2.147 | 1.296 | 1.319 | 1.254 |
|1 | 2.243 | 1.530 | 1.337 | 1.418 |
|2 | 2.023 | 1.468 | 1.354 | 1.282 |
|3 | 2.059 | 1.403 | 1.255 | 1.286 |
|4 | 2.034 | 1.415 | 1.290 | 1.325 |
|5 | 2.076 | 1.444 | 1.273 | 1.335 |
|6 | 2.080 | 1.539 | 1.386 | 1.442 |
|7 | 2.061 | 1.414 | 1.301 | 1.285 |
|8 | 2.143 | 1.377 | 1.301 | 1.328 |
|9 | 2.008 | 1.507 | 1.260 | 1.468 |
|avg. | 2.087 | 1.439 | 1.307 | 1.342 |

可以發現每次改動，q_sort的表現都有所進步，也可以從v1到v2大幅的進步表現可以了解到cache thrashing對程式的執行效率有嚴重的影響，另外透過小小的觀察改動可以再擠出一點效能，甚至和linux kernel的list_sort相當的執行效率。另外自認為linux kernel的list_sort即便有註解也還是反人類的難讀。