2021q1 Homework5 (sort)

# 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` 時的部分。

Read more

2022/08/23~24 OSSLA Records

So What Has RCU Done Lately? (2023)

RCU in the Linux Kernel

RCU Notes