2021q1 Homework5 (sort)

contributed by < ccs100203 >

tags: linux2021

sort
@Uduru0522: Note of Bottom-up Heapsort (English Version)

sort.c 分析

A fast, small, non-recursive O(n log n) sort for the Linux kernel

這是一個建立在連續記憶體上的 heapsort 實作。
而 list_sort.c 是不連續記憶體上的排序實作。

時間複雜度

翻完演算法講義還是不太了解 sort.c 算出

$n\ast log2(n)+0.37\ast 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

__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\ast 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\ast 4=24$, 第一次減 size 會變成
  $i={20}_{10}=010100$，則 i & lsbit 會得到 4，這樣第六行就會變成 i -= 4 & -4，這樣就會得到 16，回傳後就得到了 parent 的 offset。

順帶一提，上述的程式用更直覺的寫法會寫成:

可以馬上看出來是用來判斷是否需要再減去一次 size

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\ast n)$ worst-case 是沒辦法被接受的。

作者利用 backtrack 的方法降低 compare 的次數，所以 heapsort 的方式不同於平時看到的 Top-down 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，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 的敘述

  在 Top-down 中的 worst & average case 為

  $2nlo{g}_{2}n+O(n)$
  而 bottom-up 的 average case 為
  $nlo{g}_{2}n+O(1)$，worst case 為
  $1.5nlo{g}_{2}n+O(n)$。

  即便是在 worst case 都只有 Top-down 3/4 的比較次數，大大減少了 compare 的 overhead。

sort 的程式碼

以下是 sort.c 內的程式碼，每個部分都能夠與前面 heapsort 的敘述相呼應，藉此來做說明。

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