owned this note
owned this note
Published
Linked with GitHub
# 2021q1 Homework5 (sort)
contributed by < `ccs100203` >
###### tags: `linux2021`
> [sort](https://hackmd.io/@sysprog/linux2021-sort)
> [@Uduru0522: Note of Bottom-up Heapsort (English Version)](https://hackmd.io/@Uduru0522/bottomup-heapsort-analyze)
## [sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 分析
> A fast, small, non-recursive O(n log n) sort for the Linux kernel
這是一個建立在連續記憶體上的 heapsort 實作。
而 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 是不連續記憶體上的排序實作。
## 時間複雜度
翻完演算法講義還是不太了解 sort.c 算出 $n*log2(n) + 0.37*n + o(n)$ 的方法
## 程式碼分析
### Swap
- line 50: Exchange the two objects in memory. This exploits base+index addressing, which basically all CPUs have, to minimize loop overhead computations.
不知道為什麼有這些優點
- aligned vs unaligned
(覺得他的 swap 好厲害，第一次看到這種寫法。除了這裡也看到作者很多為了加速跟優化的寫法，教科書上的東西實際使用感到很驚豔)
在對齊的情況下，藉由指標的特性，可以一次交換 4 或 8 bytes。
在不對齊時，就用原本讀取 array 的方式逐 byte 去做交換。
(TODO 把說明寫的更詳細)
### Parent
```cpp=
__attribute_const__ __always_inline static size_t parent(size_t i,
unsigned int lsbit,
size_t size)
{
i -= size;
i -= size & -(i & lsbit);
return i / 2;
}
```
此函式是為了找一個 node 的 parent。在一般的 heap 中，可以直接用 $(j-1)/2$ 得到 parent 的 index。但因為這裡的 `i` 並不是 index 而是 offset，所以不能直接用這種方式去處理。變成要判斷他是 left child 或 right child，藉此決定要減一次 `size` 或兩次 `size`，之後才進行除二。可以想成因為不能夠當成 index 那樣藉著整數除法的性質自動捨去小數，所以必須精確的減去正確數量的 `size` 才能夠做除二。
#### 用下面的圖例說明:
```
0
|
|-------|
1 2
| |
|-----| |-----|
3 4 5 6
```
- 如果只是一般的 index，只要 $(j-1)/2$ 就可以得到 parent
- 因為這邊是 offset 所以需要透過額外的計算才能找到 parent
- 先假設 size 是 4，如果要找 index 5 的 parent，那麼 $i = 5 * 4 = 20$，
- `lsbit = size & -size`，代表 `size` 的 least set bit。
- 第五行會先做一次減 `size`，再來第六行就是要不要做第二次減 `size` 的關鍵。
如果此時的 `(i & lsbit)` 不為 0，代表此數字需要減第二次 `size` ，反之則不用。可以想像成 odd 跟 even 的概念，這邊目的是要讓他在基於 `size` 的情況下屬於偶數，那 `size` 的 least set bit 的要是 0 才能代表是偶數，因為偶數除二才不會有小數點或餘數的問題。
- 此時的 $i=16_{10}=010000_2$，而 $lsbit=4_{10}=000100_2$，交集為 0，所以在第六行 BITWISE AND 的右半邊就會是 0，這樣 `i` 就不會做任何的運算，最後回傳 `i` 除二就是 $offset = 16/2=8$，換算回 $index = 8/4 = 2$。
- 那如果 index 是 6，$i = 6*4 = 24$, 第一次減 `size` 會變成 $i=20_{10}=010100$，則 `i & lsbit` 會得到 4，這樣第六行就會變成 `i -= 4 & -4`，這樣就會得到 16，回傳後就得到了 parent 的 offset。
#### 順帶一提，上述的程式用更直覺的寫法會寫成:
可以馬上看出來是用來判斷是否需要再減去一次 size
```cpp
i -= size;
if (i & lsbit) i -= size;
```
但是這有明顯缺陷，就是多了一個 branch 的 overhead，而作者利用 bitwise 將其省去了，這就是 bitwise 的魅力嗎
### Sort
> Sorting time is O(n log n) both on average and worst-case. While quicksort is slightly faster on average, it suffers from exploitable O(n*n) worst-case behavior and extra memory requirements that make it less suitable for kernel use.
一開始就寫明了使用 heapsort 而不是 quicksort 的原因，因為 $O(n*n)$ worst-case 是沒辦法被接受的。
作者利用 backtrack 的方法降低 compare 的次數，所以 heapsort 的方式不同於平時看到的 Top-down heapsort，而是 [Bottom-up heapsort](https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort)。
#### 先來解釋兩種 heapsort 的差別
這邊是一個 heapsort 的架構:
(假設要從小排到大)
**HEAPSORT(Array, n):**
```
// build max heap
for i <- floor(n/2) to 0:
siftdown(i, n)
// swap & sort
for i <- n downto root:
swap(A[0], A[i])
siftdown(0, i–1)
```
- 第一個迴圈用來將 heap 建立為 [MAX HEAP](https://en.wikipedia.org/wiki/Min-max_heap)，siftdown 是一個會不斷向 child 比較與交換的函式，後面會再解釋。
- 因為 MAX HEAP 的特性，藉由第二個迴圈會不斷的把 root 與當前的最後一個 node 交換，並利用 siftdown 維持其 MAX HEAP 的性質，就可以將此陣列由小到大排序完成。
**siftdown function:**
此函式的功能在於將傳進來的 node 與其 child 進行比較，將自身交換為三者 (假設有 left & reight child) 之中最大的值，並持續的向下交換以及比較。
而這個函式就是 Top-down 與 bottom-up 的差異所在，以下圖來說明:
假設我目前將 node 0 傳入函式 siftdown
```
0 2
| |
|-------| |-------|
1 2 ----> 1 6
| | | |
|-----| |-----| |-----| |-----|
3 4 5 6 3 4 5 0
```
- Top-down
parent, left child, right child 三者會透過兩次的 compare 找出最大值 2，將其與 parent 0 交換，此時會進行下一輪比較，在數值 0, 5, 6 之間比較出最大的點，就可以得到右圖。
- Bottom-up
與 Top-down 的差別在於，每一輪的 compare 中只先比較兩個 child，找出比較大的 child 就會由他繼續往下比，一直到 leaf 不能繼續向下比較時，會將傳進來的 node 沿著剛剛往下的 path，從 leaf 開始一路向上比較回去，一直到 input_node < current_node，代表找到了傳進來的 node 要放置的新位置。此時將此位置紀錄為 new，就會進行 swap(new, parent(new))，再來會繼續進行 swap(new, parent(parent(new))) 一直進行到 new 與 input_node 進行交換過後結束。
在這裡會進行第一次的 compare 找出 $2 > 1$，然後進行第二次的 compare 找出 $6>5$，此時因為已經到達 leaf，所以要開始向上 backtrack，於是透過 $0<6$ 找到 0 所應該放置的點，就可以開始進行 swap(2, 6)，以及 swap(2, 0)，最後也會得到右圖。
- compare 次數的比較
可以發現兩者會得到相同的結果，但是 Top-down 在每一輪都需要兩次的 compare，而 bottom-up 則是藉由一輪一次的 compare 到達 leaf，再一路向上 compare，雖然如果每一步都需要比較到最後的話都會是兩次，但是需要交換的 element 是傾向於靠近 leaf 的，代表了 compare 次數會隨之減少。
>根據 [Bottom-up heapsort](https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort) 的敘述
在 Top-down 中的 worst & average case 為 $2nlog_2n + O(n)$
而 bottom-up 的 average case 為 $nlog_2n+O(1)$，worst case 為 $1.5nlog_2n+O(n)$。
即便是在 worst case 都只有 Top-down 3/4 的比較次數，大大減少了 compare 的 overhead。
#### sort 的程式碼
以下是 sort.c 內的程式碼，每個部分都能夠與前面 heapsort 的敘述相呼應，藉此來做說明。
```cpp=
for (;;) {
size_t b, c, d;
if (a) /* Building heap: sift down --a */
a -= size;
else if (n -= size) /* Sorting: Extract root to --n */
do_swap(base, base + n, size, swap_func);
else /* Sort complete */
break;
for (b = a; c = 2*b + size, (d = c + size) < n;)
b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d;
if (d == n) /* Special case last leaf with no sibling */
b = c;
/* Now backtrack from "b" to the correct location for "a" */
while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0)
b = parent(b, lsbit, size);
c = b; /* Where "a" belongs */
while (b != a) { /* Shift it into place */
b = parent(b, lsbit, size);
do_swap(base + b, base + c, size, swap_func);
}
}
```
- 這裡的 `a` 是 $\lfloor{n/2}\rfloor$
- Line 4 的 if 將程式分為兩個階段
- 第一個是 a > 0 時，此階段對應到上面所說的 heapsort 架構中 build max heap 的部分
- 第二個階段就是 a = 0 且 n > 0 時，對應到上述的 swap & sort 階段
- Line 11 的 for 對應到的是前面 bottom-up 敘述中，不斷向下找比較大的 child 直到 leaf 的部分
- Line 17 的 while 對應到的是，從 leaf 開始向上尋找 `a` 所應該要放置的位置的階段。而 `c = b` 就是前面說的設定擺放位置 new 的操作。
- Line 20 的 while 對應到從 new location 開始，不斷的跟 parent 做 swap，一直到進行到 `a` 時的部分。
Google Drive
Gist
Clipboard
Sign in with Wallet
