---
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。
從圖可以看到，調整後的方法在執行時間上帶來極大效益。
### [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 長度封裝在資料結構中。這部份暫時保留未修改。
:::
因此，經調整後將 S 設為 64，即當切割 list 到長度為 64 以下後會先用 insertion sort 排序，從下圖可以看到調整後的方法對執行時間的效益。
### 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 取值。
### 執行時間的影響
從時間結果來看， 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
Sign in with Wallet
Connect another wallet