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

contributed by < `yanjiew1` >

> [GitHub](https://github.com/yanjiew1/linux23q1-timsort)

## 名詞定義

- 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(\log N)$ 空間，此外也趁這些被走訪的元素還在 cache 或較上層的 Memory hierachy 時進行合併，效率較高。

因為每一個 Run 的長度都不一樣，要怎麼避免不平衡的合併就相當重要。試想，若我們將一個 2000 個元素的 Run 和一個只有 2 個元素的 Run 合併，那麼比較次數最高可以到達 $M+N-1=2001$ 但卻只讓我們排序好的元素只多 2 個。故合併時，二個 Runs 的大小愈一致愈好。

故需要設計 Merge 策略來避免不平衡的 Merge ，一來是確保時間複雜度不會變 $O(n^2)$，另外也是降低比較次數。

此外我們也要限制 Run 數量。因為 Run 的 metadata 會存在堆疊中，故若能限制堆疊空間複雜度是 $O(\log N)$ 是最理想的。

#### 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](http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/) 。

#### 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

參考資料：
* Python 程式碼中的 [listsort.txt](https://github.com/python/cpython/blob/24e5ad4689de9adc8e4a7d8c08fe400dcea668e6/Objects/listsort.txt) (最新版的 Python 已改用 Powersort ，這是改成 Powersort 之前的版本)
* [Proving that Android’s, Java’s and Python’s sorting algorithm is broken](http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/)

### 合併演算法

傳統的 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[$2^{k-1}$ - 1] < A[0] <= B[$2^k$ - 1]　成立。接下來會在 B[$2^{k-1}$ - 1] 與 B[$2^k$ - 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 需要預先知道序列的長度，故可能不太適合，因為一開始就要去走訪過整個序列。
不過雖然記憶體存取的成本變高，若能降低比較次數，也有可能還是會有比較好的效能，故還是可以嘗試看看。

參考資料：
* Python 程式碼中的 [listsort.txt](https://github.com/python/cpython/blob/6a1c49a7176f29435e71a326866d952b686bceb3/Objects/listsort.txt) (Powersort 版本)
* [Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs](https://arxiv.org/abs/1805.04154)

### Adaptive Shivers Sort

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

假設 X, Y, Z 為目前堆疊上的 Runs ，Z 為堆疊頂部 ，若 $\lfloor \log_2 X \rfloor \le \lfloor \log_2 (\max(Y, Z)) \rfloor$ ，則將 X, Y 合併。 使用 bitwise 操作或 `__builtin_clzl` 可以快速實作此演算法。除了演算法簡單外，其時間複雜度可以比 Timsort 好，詳細資料可以看論文。

參考資料
* [Adaptive Shivers Sort: An Alternative Sorting Algorithm](https://arxiv.org/abs/1809.08411)

## 實作

:::info
我在研讀 `lib/list_sort.c` 的過程中，發現裡面的 `merge` 函式是用有分支的版本。我想試著貢獻沒有分支的版本給 Linux kernel 。

但最後發現這樣子的 `merge` 其實分支沒有減少，反而出現更多記憶體存取，故最後[寄了一封信](https://lore.kernel.org/lkml/[e-mail]/)附上實驗數據解釋新的方法沒有比較好。

> 已送 [patch](https://lore.kernel.org/lkml/[e-mail]/)
> 共筆記錄 [https://hackmd.io/@yanjiew/linux2023q1-1st_contrib](https://hackmd.io/@yanjiew/linux2023q1-1st_contrib)
:::

實作和效能比較的程式都放在 [GitHub](https://github.com/yanjiew1/linux23q1-timsort) 中。

### 建新 Git 倉庫並引入 Linux 的 list_sort

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

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

### 實作 Timsort

### 實作 Adaptive Shivers Sort

### 實作 Powersort

### 實作效能測試程式

## 效能比較

效能比較程式已放在 [GitHub](https://github.com/yanjiew1/linux23q1-timsort) ，共筆待補。初步測試 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 計入。

## 參考資料

- [Wikipedia: Timsort](https://en.wikipedia.org/wiki/Timsort)
- [Engineering In-place (Shared-memory) Sorting Algorithms](https://arxiv.org/pdf/2009.13569.pdf)
- [Merge Strategies: from Merge Sort to TimSort](https://hal.science/hal-01212839v1/file/aunipi2016-merge-sorts.pdf)
- [Adaptive Shivers Sort: An Alternative Sorting Algorithm](https://arxiv.org/abs/1809.08411)