---
# System prepended metadata

title: quiz3
tags: [NCKU Linux Kernel Internals]

---

---
tags: NCKU Linux Kernel Internals
---

# quiz3

[2020q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz3)

完整的程式內容請參考: [Github](https://github.com/RinHizakura/XOR-linked-list)

## XOR linked list
### 實作原理
[XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 是一種透過 bitwise XOR 操作，可以僅用一個 linked list 節點表現 doubly linked lists 的資料結構，範例的結構如下:

```c=
#include <stdint.h>

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

#define XOR(a, b) ((list *) ((uintptr_t) (a) ^ (uintptr_t) (b)))
```

其中 `addr` 所記錄的並不是上一個節點的位置，也不是下一個節點的位置，而是**上一個節點位址 XOR 下一個節點位址**。
```
...  A         B         C         D         E  ...
         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->
```

透過這種表示，就可以擅用 XOR 操作的特性，例如如果想從 `B` 得到 `C`，則只要有上一個的 `A`，`A ⊕ B = A ⊕ A ⊕ C = C`，可以得到 `C`，往反方向也同理。

#### Insert
```c=
void insert_node(list **l, int d) {
    list *tmp = malloc(sizeof(list));
    tmp->data = d;

    if (!(*l)) {
        tmp->addr = NULL;
    } else {
        (*l)->addr = XOR(tmp, (*l)->addr);
        tmp->addr = *l;
    }
    *l = tmp;
}
```
為了更容易理解，想像初始的 linked list 為空，並且依序插入 A、B、C 節點。
* 首先插入 A: 把 `tmp` 想成 A，因為最初 list 為空，所以走 `if (!(*l)` ，`tmp->addr = NULL`，`*l` 這時候指到 A


| NULL | A            | NULL |
| ---- |:------------: | ---- |
| NULL | <–> NULL <–> | NULL |


* 接著，插入 B: 把 `tmp` 想成 B，`*l` 指在 A，因此 `A->addr = XOR(B, A->addr)`，`B->addr = *l` 也就是 A，最後 `*l` 指到 B

| NULL |     B     |        A         | NULL |
| ---- |:---------:|:----------------:| ---- |
| NULL | <–> A <–> | <–> B ⊕ NULL <–> | NULL |
* 最後插入 C: 把 `tmp` 想成 C，`*l` 指在 B，因此 `B->addr = XOR(C,A)`，`C->addr = *l` 也就是 B，最後 `*l` 指到 C

| NULL |     C     |       B       |        A         | NULL |
| ---- |:---------:|:-------------:|:----------------:| ---- |
| NULL | <–> B <–> | <–> C ⊕ A <–> | <–> B ⊕ NULL <–> | NULL |

#### Delete
```c=
void delete_list(list *l) {
    while (l) {
        list *next = l->addr;
        if (next)
            next->addr = XOR(next->addr, l);
        free(l);
        l = next;
    }
}
```
延續上面的 linked list 案例，來看看刪除是怎麼完成的:
* `next` 會指到 `l->addr` 也就是 B，然後做 `if (next)` 裡的 `next->addr = XOR(C⊕A, C) = A`，最後把 `l` 指到的 C free 掉，再指到 next ，也就是 B。因此刪除後就變成:


| NULL |     B     |        A         | NULL |
| ---- |:---------:|:----------------:| ---- |
| NULL | <–> A <–> | <–> B ⊕ NULL <–> | NULL |

可以看到，其實就是插入 C 前的狀態，然後不斷重複，直到把所有節點都釋放。

#### Merge sort

有了上面的了解之後，其實答案就很容易理解了。LL1 和 LL2 其實就是把 left 放進 merge，因此其實就是 insert 的概念: 

LL1: ( h ) `XOR(merge->addr, left)`
LL2: ( c ) `merge`

同理 RR1 和 RR2 是把 right 放進 merge 因此是:

RR1: ( i ) `XOR(merge->addr, right)`
LL2: ( c ) `merge`

思考一下程式的運作：
```c=
list *sort(list *start)
{
    ...
    list *left = start, *right = start->addr;
    left->addr = NULL;
    right->addr = XOR(right->addr, left);

    left = sort(left);
    right = sort(right);
    ...
```

看到 left、right 和遞迴的呼叫，不難猜到其實這就是 merge sort。因此整個 sort 的流程就是把遞迴把最左邊的節點切出來，然後遞迴去做 merge 排序。從 `sort` 後回傳的會是一個已經排序好的子 linked list。
```c=
for (list *merge = NULL; left || right;) {
        if (!right || (left && left->data < right->data)) {
            ...
        } else {
           ...
        }
    }
```
在後面的 for loop 中，要做得就是把 left 和 right 合併成一個排序好的 linked list，因為 left 和 right 已經排序好了，因此要做的只是從 left 和 right 中挑出最小的，插入到 merge，直到把 left 和 right 的所有節點都歷經過。


### 改善 merge sort
原始的實作是從左到右一個個把節點切下來，因此如果有 n 個節點，就需要呼叫 n 次 merge sort。舉例來說 4 個節點的狀況是
```graphviz
digraph graphname{
    B[label="1"]
    C[label="1"]
    D[label="1"]
    4->3
    4->1
    3->B
    3->2
    2->C
    2->D
}
```


如果將其改成每次都從 list 的中間切，則只需要 $\log_{2}{n}$ 次：
```graphviz
digraph graphname{
    B[label="2"]
    C[label="2"]
    D[label="1"]
    E[label="1"]
    F[label="1"]
    4->B
    4->C
    B->1
    B->D
    C->E
    C->F
  
}
```

可以參考我們在 lab0 參考過的[方法](https://www.techiedelight.com/merge-sort-singly-linked-list/)調整，詳細的程式請參閱 Github。

從圖可以看到，調整後的方法在執行時間上帶來極大效益。
![](https://i.imgur.com/WtPgcuD.png)

### [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort)

在上面的 merge sort 中，會先把 linked list 切成單一個節點，再一個個合併，這會導致 locality 不佳。一種最佳化的方式是 tiled merge sort，當分割到 linked list 為 S 大小時便不再分割，S 是節點的資料結構可以納入 cache 的總量。先透過可以 in-place 的排序演算法（insertion sort / bubble sort）進行排序後，減少在記憶體內交換特定區域的次數，再以典型的 merge sort 完成剩下的部份。

為此，對 XOR linked list 實作 insertion sort，這裡有兩種實作方式:
* 原本是採用不重新更動節點，而是把裡面的儲存值換掉的方法，詳細請看[這裡](https://github.com/RinHizakura/XOR-linked-list/blob/1cf01e98d1685c65edbf8a916ca611ddc116d409/XOR_list.c#30)。不過這種作法明顯延展性會比較不好，而且使用了稍微有點多的指標。
* [調整後的作法](https://github.com/RinHizakura/XOR-linked-list/blob/master/XOR_list.c#32)，改成重新組織節點，使用比較少的變數。

#### cache locality 對執行的影響
首先透過 `lscpu` 可以看到 cache 的大小：

```
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            8192K
```

而一個 `list` 結構為 16 bytes，因此理想上可以 cache 可以放入 32k / 16 = 2k 個 `list`，但是也需要考慮到其他變數的使用也會佔用 cache 空間。

為了判斷分割到 S 為多少會有較佳的速度，因此修改程式，並透過統計方法分析得到以下的實驗結果(固定 5000 個節點的 linked list)。注意到圖形的階梯狀是因為 linked list 的大小固定，而 merge sort 總是把 linked list 對半分，因此 merge sort 中可能會出現的長度只會是 `5000 -> 2500 -> 1250 -> 625 -> 312 -> 156 -> 78 -> 49 ......` 。由此可以推斷在 `S = 49 ~ 78` 的區間是使用 insertion sort 較佳的地方。

:::warning
:warning: 為了撰寫程式的容易性，因此把 list 的長度以參數的形式遞迴傳遞。但考慮到函式的通用性，比較好的方法應該是把 list 長度封裝在資料結構中。這部份暫時保留未修改。
:::

![](https://i.imgur.com/aYDxKv3.png)

因此，經調整後將 S 設為 64，即當切割 list 到長度為 64 以下後會先用 insertion sort 排序，從下圖可以看到調整後的方法對執行時間的效益。

![](https://i.imgur.com/J9BbNh2.png)


### Doubly linked list 與 XOR linked list 的記憶體佔用率
- [ ] 修改 lab0-c 裡頭的 harness.c，將原本內部使用的 doubly-linked list 換為 XOR linked list，觀察記憶體佔用率的變化

## Pointer to pointer

### 實作原理
原本的 insert 方法需要額外維護 prev 的思考為： 一直尋找直到找到不滿足條件的第一個 node ，它的前一個位置和自己中間就是是插入的地方。

而透過 pointer to pointer，可以把問題思考為： 一直尋找直到找到不滿足條件的第一個 node，這個 node **所在的位置**是新節點的位置，而原本的這個 node 往後接。有了 pointer to pointer，**位置**就可以被追蹤。

AA = ( c ) `(*link)->data < newt->data`。因為 `link` 是 pointer to pointer，一層的 dereference 可以得到指標。


BB = ( a ) `link = &(*link)->next`。因為 `link` 是 pointer to pointer，因此需要用 `&` 對 pointer 取值。

### 執行時間的影響
![](https://i.imgur.com/DzErkMA.png)
從時間結果來看， poniter to pointer 的版本結果似乎稍好一些。

如果從 [perf-stat](https://man7.org/linux/man-pages/man1/perf-stat.1.html) 來觀察的話：
* simple 版本
```
sudo perf stat -e branch-instructions:u,branch-misses:u  ./a.out

 Performance counter stats for './a.out':

           588,130      branch-instructions:u                                       
             4,446      branch-misses:u           #    0.76% of all branches        

       0.003824609 seconds time elapsed

       0.003787000 seconds user
       0.000000000 seconds sys
```
* pointer to pointer 版本
```
sudo perf stat -e branch-instructions:u,branch-misses:u  ./a.out

 Performance counter stats for './a.out':

           587,114      branch-instructions:u                                       
             4,405      branch-misses:u           #    0.75% of all branches        

       0.001592976 seconds time elapsed

       0.001597000 seconds user
       0.000000000 seconds sys
```
看起來 pointer to pointer 整體的 branch instruction 確實比較少，但 branch miss 沒有顯著的少很多。這個數量級的 branch 的減少對於時間的差距是合理的嗎？或者有 branch 以外的其他原因讓時間得以變快？或許需要進一步去思考。


### 實作限制

還沒想到... :cry: 
### linux kernel code

- [ ] 研讀 [bfq_insert](https://elixir.bootlin.com/linux/v4.15/source/block/bfq-wf2q.c#L373) 在 linux kernel 中如何應用 pointer to pointer