Try   HackMD

Timsort 研究與對 Linux 核心貢獻嘗試

contributed by < yanjiew1 >

GitHub

名詞定義

  • Runs:為在 Mergesort 和 Timsort 中已經排序好的子序列。
  • Natural Run: Natural Run 就是在未排序的序列中,裡面已經排序好的子序列。例如: [10, 20, 30, 25, 27, 31, 34] ,就可以形成 2 個 Natural Runs :[10, 20, 30] 和 [25, 27, 31, 34] 。
  • 合併樹:把 Timsort 和 Mergesort 合併的行為表示成一棵二元樹。此二元樹的葉節點,在 Mergesort 為個別元素,而在 Timsort 為 Natural Runs 。而內部節點代表其二個子節點的合併產生的 Run。
  • 比較次數估算: 把所有合併樹中的內部節點代表之 Run 元素個數加總,即可估算比較次數。

Timsort 對 Mergesort 的改善

  1. Cache Miss 改善:

    • 傳統 Mergesort 的問題:
      • 非遞迴版 Mergesort : 在傳統的 Mergesort 非遞迴版裡。會從合併樹的最底層開始合併,底層合併完才進行較上層的合併。這樣子的缺點是,每進行其中一層的合併時,就要掃過整個序列進行合併。因此對 cache 不友善。在 Linux 核心有對此進行改進,不會掃描整個序列才進行合併,而是把元素加入 Pending List 的過程中,趁這些元素還在 Memory hierachy 上層時,在適當時機就合併。
      • 遞迴版本 Mergesort : 我們仍用合併樹的概念來說明遞迴版本中。在合併樹上的每一個節點,可以代表在遞迴中一次函式呼叫。若去追綜合併順序時,會發現遞迴版本相較於非遞迴版本,會先處理完左子樹後,再去處理右子樹,最後在把二個子樹合併。故合併時,二個子樹的內容都可能還在上層的 Memory hierachy 中。在陣列的情境,其合併的順序相對於非遞迴版對 cache 較友善。但是對 Linked List 非連續性記憶體而言,進行分治(Divide) 的過程中,意即決定要切在哪一個點決定左右子樹,要走訪目前遞迴呼叫對應到合併樹中內部節點,所有待排序的元素,對 cache 不友善。
    • Timsort 的改進:
      • Timesort 是非遞迴版 Mergesort 的改進版本。它會儘量讓要排序的元素剛才存取過,還在 Memory hierachy 上層時,就進行合併。類似 Linux 核心 Mergesort 的作法。它不必走訪整個序列才能進行合併,而是一邊走訪,就一邊把序列的元素加進待合併的 Runs 當中,在適當時機就合併。
  2. 記憶體使用改善:

    • 傳統 Mergesort 在合併時,會配置一塊與待合併的二個 Runs 相同大小的記憶體空間,然後把合併的內容存放到新配置的空間中。故有 N 個元素時,最多需要額外 N 個元素的記憶體空間。
    • 在 Timsort 中,合併時,會以較複雜的演算法,只會對二個 Runs 中,其範圍重疊的部份進行合併。這裡的重疊,不是指二個 Runs 的元素一樣,而是在大小關係上重疊。例如 [2, 4, 6, 7, 8, 11] 和 [9, 10,11, 15, 17] ,則重疊的部份為 [8, 11] 和 [9, 10, 11] ,故只要對這二個部份進行合併就好,其他部份接上去即可。 額外空間的部份,會配置二個要合併的部份中跟較小的那一部份元素數量的記憶體。故以上述例子,只需要配置 2 個元素的空間即可合併。
  3. 比較次數的改善:

    • 一個待排序的序列中,裡面可能有部份元素已經排序好。 Timsort 利用這個特性,在尋找 Runs 時,會把已經排序好的元素加入同一個 Runs ,避免需要額外的時間排序。
    • 而在 Timsort 中,在合併二個 Runs 時,有一個特有的 Galloping mode ,它也是利用要合併的二個 Runs 元素,其分佈不均勻的特性,可以減少比較次數加速合併。(需再補上詳細運作原理)但是若是針對隨機產生的序列,就不太有用,此時用 Galloping mode 反而比較慢。故在 Timsort 會有一個機制決定是否要啟動 Galloping mode 。
    • 上述比較次數只是初步的評估,仍然需要去計算精確比較次數,來能判斷 Timsort 改善的程度。

Timsort 實作上的挑戰

  1. Linux kernel 的 list_sort 已經針對 cache 存取盡可能的最佳化。且其比較次數在最差情況已經算優良。故仍然不是很能確定 Timsort 是否可以比原本的 Linux kernel 快。而 Timsort 比較次數取決於資料分佈的型態(例如:若原本資料已排序好,只要最多 N 次比較),故若能得知 Linux kernel 實際排序的資料在未排序前的狀態,更能分析出改用 Timsort 效益。希望能實作出 Timsort 在最壞情況比較次數仍然能比 Linux kernel list_sort 好 ,即便不行,希望也不要差太多。
  2. Timsort 原始版本是實作在陣列上。實作在 Linked List 上的效能目前還不太確定好不好,因為它會有比陣列更多的額外記憶體存取。
  3. Timsort 比起 Linux kernel 的 list_sort 需要多一個 stack 存放每一個 Runs 的大小。在 Linux 的 doubly-linked list 實作 Timsort 有個優勢,不用建立合併二個 Runs 時的暫存空間。

Timsort 運作方式

Runs

設 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 取出後再反轉即可使用。

合併 (Merge) 策略

Timsort 運作時,會往下取下一個 Run 直到 Q 為空。但在每取下一個 Run 時,會按照合併策略進行合併,避免未合併的 Run 超過

O(logN) 空間,此外也趁這些被走訪的元素還在 cache 或較上層的 Memory hierachy 時進行合併,效率較高。

因為每一個 Run 的長度都不一樣,要怎麼避免不平衡的合併就相當重要。試想,若我們將一個 2000 個元素的 Run 和一個只有 2 個元素的 Run 合併,那麼比較次數最高可以到達

M+N1=2001 但卻只讓我們排序好的元素只多 2 個。故合併時,二個 Runs 的大小愈一致愈好。

故需要設計 Merge 策略來避免不平衡的 Merge ,一來是確保時間複雜度不會變

O(n2),另外也是降低比較次數。

此外我們也要限制 Run 數量。因為 Run 的 metadata 會存在堆疊中,故若能限制堆疊空間複雜度是

O(logN) 是最理想的。

Timsort 的合併策略

Timsort 中,對任意三個相鄰的 Runs ,其長度分別為 A, B, C ,需維持下列三點 invariant:

  • A > B + C
  • B > C

原始 Timsort 合併的時機為,當加入新的 Run 或進行 Merge 後:

  • 若未合併的 Run 有 3 個以上時,設 A, B, C 為最右邊三個 Runs ,若出現 A >= B + C 時,則 B 與 A 或 C 選長度小的合併。
  • 若未合併的 Run 只有 2 個時,設 A, B 為其大小,若 A >= B ,則 A 和 B 合併。

透過維持上述的 invariant ,可以知道 Runs 的大小會由大到小排列 (B > C) 。若從右往左看,則 Runs 大小的增長至少會是費氏數增長速度,且可以更快。

但上述合併策略在極端狀況下,可能會沒辦法維持 invariant ,可以參照這篇文章 Proving that Android’s, Java’s and Python’s sorting algorithm is broken

Timsort 的修正版

故在合併策略加入新的條件:

  • 當加入新的 Run 或進行 Merge 後,若未合併的 Run 有 4 個以上,設 A, B, C, D 為最右邊尚未合併的四個 Runs ,若 A <= B + C 或 B <= C + D 時,則 C 與 B 或 D 選長度小的合併

在這篇文章中舉了一個例子:

在 Run 大小是這樣子排列的情況:

120, 80, 25, 20, 30

因為 25 <= 20 + 30 ,故 25 和 20 合併,成為:

120, 80, 45, 30

此時,若只考慮最後二個 Run , 80 > 45 + 30 且 45 > 30 ,符合 invariant 。但若往前看,會發現 120 <= 80 + 45 ,違反 invariant 規則。

前述文章使用 Formal verification 的方式去證明,只要每次考慮最後四個 Run ,即 A, B, C, D 中,多判斷 A <= B + C ,若此條件成立,也要進行合併。故加上此條件後,上述可再進行合併變為:

120, 80, 75

參考資料:

合併演算法

傳統的 Merge Sort 演算法,在合併二個 Runs 時,會比較二個 Runs 的最前面元素,把要排在前的取下來放在要輸出的 buffer 內,直到其中一個 Run 所有元素都取走了,再把另一個 Run 接在後面。而 Linux Kernel 也是使用此方法來實作的。

在 Timsort 裡,把這種方式叫做「 one pair at a time 」,是均勻分布時,會採用此方式。

Galloping

在 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[

2k1 - 1] < A[0] <= B[
2k
- 1] 成立。接下來會在 B[
2k1
- 1] 與 B[
2k
- 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

Powersort 需要預先知道序列的長度,故可能不太適合,因為一開始就要去走訪過整個序列。
不過雖然記憶體存取的成本變高,若能降低比較次數,也有可能還是會有比較好的效能,故還是可以嘗試看看。

參考資料:

Adaptive Shivers Sort

這是 Vincent Jugé 提出的排序演算法。其改變 Timsort 中的合併策略,改為如下:

假設 X, Y, Z 為目前堆疊上的 Runs ,Z 為堆疊頂部 ,若

log2Xlog2(max(Y,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 倉庫並引入 Linux 的 list_sort

為了方便實作和比較效能,我開了一個新的 Git repository 存放實作的內容。把 Linux Kernel 中的 list_sort.clist_sort.h 拿出來使用。

  1. 拷貝 list_sort.clist_sort.h
  2. 拷貝 list.h
  3. 加入 struct list_head 結構和 container_of 巨集至 list.h
  4. 加入 likelyunlikely 二個巨集至 list_sort.c

實作 Timsort

實作 Adaptive Shivers Sort

實作 Powersort

實作效能測試程式

效能比較

效能比較程式已放在 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 計入。

參考資料