contributed by < yanjiew1
>
Cache Miss 改善:
記憶體使用改善:
比較次數的改善:
設 Q 為一佇列,先把待排序的序列全部加入這個佇列中。(在實際程式可以重用原本的 Linked List 當佇列,不用真的建新佇列)。此佇列每次取出的元素都是從最開頭取出,例如: [20, 10, 1, 50] ,則取出的順序就會是 [20, 10, 1, 50] 。
故透過 Q ,我們可以定義一個函式 - NextRun ,它可以用來取得下一個 Run 。
在 Timsort 裡會有額外定義一個 Run 的最小長度。若建構出來的 Natural Run 不到最小長度,則會繼續從 Q 中取出新的元素,透過 Insertion sort 的方式排進要建構的 Run 中。 這也是為什麼 Timsort 是 Mergesort + Insertion sort 的結合。此外 Run 也可以是嚴格遞減排序(即遞減排序時沒有重複的元素,這是確保穩定排序的特性),嚴格遞減排序 Run 取出後再反轉即可使用。
Timsort 運作時,會往下取下一個 Run 直到 Q 為空。但在每取下一個 Run 時,會按照合併策略進行合併,避免未合併的 Run 超過 空間,此外也趁這些被走訪的元素還在 cache 或較上層的 Memory hierachy 時進行合併,效率較高。
因為每一個 Run 的長度都不一樣,要怎麼避免不平衡的合併就相當重要。試想,若我們將一個 2000 個元素的 Run 和一個只有 2 個元素的 Run 合併,那麼比較次數最高可以到達 但卻只讓我們排序好的元素只多 2 個。故合併時,二個 Runs 的大小愈一致愈好。
故需要設計 Merge 策略來避免不平衡的 Merge ,一來是確保時間複雜度不會變 ,另外也是降低比較次數。
此外我們也要限制 Run 數量。因為 Run 的 metadata 會存在堆疊中,故若能限制堆疊空間複雜度是 是最理想的。
Timsort 中,對任意三個相鄰的 Runs ,其長度分別為 A, B, C ,需維持下列三點 invariant:
原始 Timsort 合併的時機為,當加入新的 Run 或進行 Merge 後:
透過維持上述的 invariant ,可以知道 Runs 的大小會由大到小排列 (B > C) 。若從右往左看,則 Runs 大小的增長至少會是費氏數增長速度,且可以更快。
但上述合併策略在極端狀況下,可能會沒辦法維持 invariant ,可以參照這篇文章 Proving that Android’s, Java’s and Python’s sorting algorithm is broken 。
故在合併策略加入新的條件:
在這篇文章中舉了一個例子:
在 Run 大小是這樣子排列的情況:
因為 25 <= 20 + 30 ,故 25 和 20 合併,成為:
此時,若只考慮最後二個 Run , 80 > 45 + 30 且 45 > 30 ,符合 invariant 。但若往前看,會發現 120 <= 80 + 45 ,違反 invariant 規則。
前述文章使用 Formal verification 的方式去證明,只要每次考慮最後四個 Run ,即 A, B, C, D 中,多判斷 A <= B + C ,若此條件成立,也要進行合併。故加上此條件後,上述可再進行合併變為:
參考資料:
傳統的 Merge Sort 演算法,在合併二個 Runs 時,會比較二個 Runs 的最前面元素,把要排在前的取下來放在要輸出的 buffer 內,直到其中一個 Run 所有元素都取走了,再把另一個 Run 接在後面。而 Linux Kernel 也是使用此方法來實作的。
在 Timsort 裡,把這種方式叫做「 one pair at a time 」,是均勻分布時,會採用此方式。
在 Timsort 內,當發現資料非均勻分布,而是有叢集 (Clusters) 特性時,會改用 Galloping 演算法。但一開始合併時,不會知道資料分布的狀況,但是在使用傳統合併方式 「 one pair at a time 」 時,若發現連續好幾輪比較,資料都來自其中一個 Run 時,就會猜測資料具有叢集 (Clusters) 特性,就切換到 Galloping 模式。而要資料來自同一個 Run 才切換呢? 在 Timsort 裡有一個常數 MIN_GALLOP
,預設為 7 ,即當比較 7 次後,若都來自同一個 Run ,則切換到 Galloping 模式。
切換到 Galloping 模式後,若透過 Galloping 模式找到的連續資料來自同一個 Run 的次數小於 MIN_GALLOP
,則會回到「 one pair at a time 」。
實際上在 Python 的 Timsort 內有一個變數叫做 min_gallop
,初始值為 MIN_GALLOP
,存放要切換到 Galloping 模式前,要有幾次輸出 Buffer 資料連續來同一個 Run 的次數。每次 Galloping 模式離開時會讓 min_gallop
加 1 ,但是若 min_gallop
一直持續運作時,每運作一回合,則會讓 min_gallop
減 1 。
Galloping 運作方式如下
有二個 Runs 分別為 A 和 B 要合併,且 A Run 比 B Run 長度短。此時,要尋找 A[0] 在 B 的位置。會分別比較 B[0], B[1], B[3]… 直到找到 k 使得 B[ - 1] < A[0] <= B[ - 1] 成立。接下來會在 B[ - 1] 與 B[ - 1] 之間進行二分搜尋法,找到 A[0] 要放在 B 的哪一個位置後面。例如:找到 B[j] , 那麼就可以把 B[0] ~ B[j] 取下來放到輸出的 Buffer 。
找到 A[0] 在 B 的位置,並B[0] ~ B[j] 取下來放到輸出的 Buffer 後,就會繼續找 B[0] 在 A 的位置,其方式與上述相同,只是 A, B 交換。故就不再描述一次。
這個作法在 Linked list 會有個問題。因為 Linked list 不支援隨機存取。雖然此作法在資料配合的情況下,會降低比較次數,但可能會增加記憶體存取次數與時間,且每一次要判斷是否要進入 Galloping Mode ,也會增加分支指令。故仍然要實驗才能知道是否適用 Linux 核心的 Linked List 排序及是否能提升效能。
Powersort 需要預先知道序列的長度,故可能不太適合,因為一開始就要去走訪過整個序列。
不過雖然記憶體存取的成本變高,若能降低比較次數,也有可能還是會有比較好的效能,故還是可以嘗試看看。
參考資料:
這是 Vincent Jugé 提出的排序演算法。其改變 Timsort 中的合併策略,改為如下:
假設 X, Y, Z 為目前堆疊上的 Runs ,Z 為堆疊頂部 ,若 ,則將 X, Y 合併。 使用 bitwise 操作或 __builtin_clzl
可以快速實作此演算法。除了演算法簡單外,其時間複雜度可以比 Timsort 好,詳細資料可以看論文。
參考資料
我在研讀 lib/list_sort.c
的過程中,發現裡面的 merge
函式是用有分支的版本。我想試著貢獻沒有分支的版本給 Linux kernel 。
但最後發現這樣子的 merge
其實分支沒有減少,反而出現更多記憶體存取,故最後寄了一封信附上實驗數據解釋新的方法沒有比較好。
已送 patch
共筆記錄 https://hackmd.io/@yanjiew/linux2023q1-1st_contrib
實作和效能比較的程式都放在 GitHub 中。
為了方便實作和比較效能,我開了一個新的 Git repository 存放實作的內容。把 Linux Kernel 中的 list_sort.c
和 list_sort.h
拿出來使用。
list_sort.c
和 list_sort.h
list.h
struct list_head
結構和 container_of
巨集至 list.h
likely
和 unlikely
二個巨集至 list_sort.c
。效能比較程式已放在 GitHub ,共筆待補。初步測試 Adaptive Shivers Sort 、 list_sort 和 Timsort 三者中 Adaptive Shivers Sort 效能最好,比較次數最少。
目前我實作的 Timsort 和 Adaptive Shivers Sort ,尚未實作 Timsort 中 Insertion sort 和 Galloping ,但在隨機資料上,前二者演算法都已比 Linux 核心原有的 list_sort 快。
之後可以考慮一些非隨機分布的資料,來評測看看。另外也需要研究如何用 perf 測單一函式,來更了解 cache miss 、 branch mispredict 和 cycle 數的狀況。因為測試程式一開始會先用 malloc 來建立測資,這些準備測資的過程產生的效能資料不應被 perf 計入。