Javascript

V8 內的排序演算法 — Timsort

Timsort 廣泛應用在 Python / Android，現在 V8 JS Engine 也改用 Timsort 當作預設的排序法，此篇分享 Timsort實作的細節

在最新的一期 Javascript Weekly 中看到 V8 部落格 2019/07/09 的文章，裡頭提到 ECMAScript Spec 將 Sorting 改成 Stable，也就是如果排序上兩個元素順序相同，則最終排序完成的陣列中的相同順序元素，會依照原本的順序排列，例如

1

[{name: 'a', value: 2}, {name: 'b', value: 2}, {name: 'c', value: 1}]

依照 value 排序 ===>

1
2
3

[{name: 'c', value: 1}, {name: 'a', value: 2}, {name: 'b', value: 2}]

// a 跟 b 順序相同，而 a 維持在 b 之前

先前的 Spec 沒有特別定義，所以各平台的實作不同，之後Chrome 70+ 與 Nodejs 12+ 開始支援 Stable Sorting，其餘的平台還不確定。

TimSort

Timsort

作者原文

http://svn.python.org/projects/python/trunk/Objects/listsort.txt

參考自維基，Tim Sort 原理是由 Tim Peter 基於 Merge Sort 與 Insertion Sort所設計的排序演算法，Tim 觀察到實際世界的陣列多半是由多個部分排序的數列所組成，所以 Tim Sort 會先找出陣列中排序好的子陣列(稱為 run)，不斷的合併 run 直到整體排序結束，基於這樣的原理可以設計出更好的排序演算法。

作者提到，random array 最佳的排序法被 bound 在 O(nlog n) (文中是用 O(n!)，兩者等價)，但是不同的 O(nlog n)等級的 sorting 演算法離 O(log n) 的極限值還是有差距，Timsort 大概距離極限值 1%，而一般的 quick sort 則是 39% 之遠；
與原本 Python native 的 sample sort 相比兩者差異不大，random array Timsort 較差，但是 Timsort 針對部分排序的陣列表現更佳。

目前 Python、Android SDK、Java SDK、Chrome 、Swift 內部的 sort() 都採用 Tim Sort，應用非常廣泛。

基本觀念

Understanding timsort, Part 1: Adaptive Mergesort

直接死磕 Wiki有點看不懂，每個英文句子都懂但就是無法理解背後設計的含義，網路上看到這篇最淺顯易懂的解釋，以下簡單摘錄重點幫助理解。

Tim Sort 脫胎於 Merge Sort，試著用這三個方向去優化 Merge Sort

  1. 讓 merge 過程更快
  2. 讓 merge 次數變少
  3. 在特殊條件下用更好的方式取代 Merge Sort

試想有個陣列

{5, 6, 7, 8, 9, 10, 1, 2, 3}

用怎樣的方式可以用最少的 merge 完成排序？

直覺來看，把陣列拆成兩個已經按照升序排序的陣列 {5,6,7,8,9,10} 與 {1,2,3} 然後合併，只需要一次 merge 就可以完成

假使我們先提出一個演算法：找到陣列開頭最長的連續升序排序的陣列，其餘當作第二子陣列，以遞迴方式持續處理

這個演算法利用了已排序的陣列去減少 merge 的次數，但有個問題 如果陣列剛好是倒序，就會落入 worst case O(n²) ，稱不上是個理想的排序演算法，所以實作時會補上如果發現連續的子陣列是降序，則 in memory 反序。

先退回最基本的 Merge Sort

1
2
3

{{1}, {2}, {3}, {4}}  
{{1, 2}, {3, 4}}  
{{1, 2, 3, 4}}

這是 Merge Sort 的流程，將陣列分拆到為一然後在逐步 merge，我們將第一步分拆的過程改為已排序好的區間(稱為 Run)，然後進行 merge。

Tim Sort 在 merge 時會盡量 Balance，所以會設定 minrun，如果這次的 RUN 長度小於 minrun，則會補足到 minrun長度後，接著使用 binary insertion sort，如何選擇 minrun 是個學問，作者提到一個實務上的設定是

take the first 6 bits of N, and add 1 if any of the remaining bits are set

N 是陣列長度，最主要是希望如果遇到 random array，則N 盡可能被 minrun 切成 2 次方倍 RUN，在 merge 時可以最平衡。

minRun 是希望剩餘的數再分minrun的時候能盡可能是2的冪次，後續再做merge的時候才能兩兩合併效率較高；
實作上會不斷將n除以二 直到n<MIN_MERGE，而中間只要有任何一次不能被2整除，最終結果就加一，這樣取的minRun會讓分組最接近2冪
(感謝公司同事 Frank 補充)

例如 N = 2112，minrun = 32 會切成 66個RUN，則合併時最後會變成 2048 + 64，兩者非常不平衡；
但如果 minrun 是 33，則會被切成 64個RUN，切割成 2的 n 次方個數合併起來就很平衡 (perfect balanced)。

決定何時 merge?

Tim Sort 會用一個 Stack 暫存 RUN，並不是一開始就輪詢整個陣列產生RUN，而是逐步進行，避免要用掉過多的記憶體。

基於這兩個原則，Tim Sort 實作上有個函式 merge_collapse ，這個函式主要判斷目前 Stack 最上層的三個 RUN 是否符合以下規則

1
2

1\.  A > B+C  
2\.  B > C

如果符合，則將下一個 RUN push 到 Stack上，反之則比較 A跟Ｃ，較小者與 B merge，例如

1
2

A:30  B:20  C:10  
A <= B + C 所以不符合 merge_collapse，又因為 C < A，所以 C 跟 B merge 變成 A:30 BC: 30

透過這樣的方式，讓保留在 Stack 上的 RUN 長度平衡，另一個重點是合併只能是 A+(B+C) 或是 (A+B)+C，因為要保持 Stable，所以 merge 一定要相鄰兩個 RUN。

如何 merge

要將兩個相鄰子陣列，用 in memory 方式 merge 在實作上會有困難，實務上因為要造成大量的 memory 操作其實也不會比較快，所以 Tim Sort 使用一塊暫存記憶區，大小為 (A,B) 陣列的最小長度

如果 A < B，則先將 A 放進暫存記憶區，最直覺的方式是 A 跟 B 從頭開始比對，小的放進 A 的位置，直到 A 跟 B 排序完成，如同一般 merge sort 的做法，又稱為 one-pair-at-a-time。

但因為 A 跟 B 都已經是排序好的陣列，所以有個優化的方式是找出 B[0] 在 A陣列排序的位置，然後A該位置之前都是小於 B[0]，所以可以整段放進去，接著找剩餘A[0]在 B的位置，不斷輾轉直到排列結束，也就是 gollaping mode。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

A: [1,2,3,7,8,9] B: [4,5,6,8,9,10,11]  
A < B，所以 A 放入暫存區 temp

先找 B[0] 在 A 的位置，也就是在 A[2]、A[3]之間，因為 B[0] > A[2]，也就是 A[0]~A[2] 可以直接放回去，變成  
A: [1,2,3] B: [4,5,6,8,9,10,11]  
temp: [7,8,9]

接著找 temp[0] 在 B的位置，也就是 B[2]、B[3] 之間，變成  
A: [1,2,3,4,5,6] B: [9,10,1]  
temp: [7,8,9]

接著找 B[0] 在 temp 的位置，持續反覆

這優化的方式大多數是有正向的效果，但如果遇到 random array，可能會比原本的 one-pair-at-a-time 還要慢，但作者提及

It’s generally true in this algorithm that we’re willing to gamble a little to win a lot, even though the net expectation is negative for random data

風險與收益評估後，整體還是正向的，所以就決定採用。

實務上有一個固定參數 MIN_GALLOP =7 與變動參數 minGallop，一開始採用 one-pair-at-a-time mode，一直到某個陣列的首位元素持續大於另一陣列，才切換到 galloping mode；
如果 galloping search(看後續)找到的元素位置小於MIN_GALLOP 則退回 one-pair-at-a-time mode，反之則持續用 galloping mode；
如果一直在 galloping search，會下修 minGallop，也就是更容易進入 galloping mode 的意思。

反覆執行到兩個陣列合併完成

找出某數在已排序陣列中的位置

進入 galloping mode 時，會需要不斷的查找某數在已排序陣列的位置，假設 A 是較短的陣列，一開始找 A[0] 在 B陣列應排序的位置，最直覺的方式是用 binary search，但這邊作者改採用另一個演算法 galloping search(又稱 expotential search)

相較於 binary search 不斷對半切查找，galloping search 是比對 (2^k)th 元素，也就是找 1, 3, 5, 7, 15 這樣的方式，當找到 (2^(j-i)) < x < (2^j) 時，在改用 binary search。

比較這兩者， galloping search 的時間複雜度是 O(i)，i 指的是 x 在查詢陣列的位置，如果 i 很前面那效率就會很高；
binary search 時間複雜度為 O(n)，n 是查詢陣列的長度。
而 n ≥ i ，所以從時間複雜度來看 galloping search 會比 binary search 還要快一些。

但實際上，因為陣列是隨機的，採用 galloping search 可能會比 linear search 慢，作者列出 galloping search 對比 linear search 的計算花費，可以看到在 i=7 之前 galloping search 會需要更多的比較次數，而比較是很花計算資源的，所以 MIN_GALLOP預設是 7。

總結演算法

稍微總結一下，Timsort 維護一個 Stack，Stack 上會 push 已排序的連續子陣列，並透過 merge_collapse 判斷是否先 merge Stack 上的陣列，盡量保持子陣列的長度接近；

merge 過程，則是動態在 one-pair-at-a-time 與 galloping mode 中切換，用有效率的方式合併兩個已排序好的陣列；

進入程式碼

最終還是要看一下代碼，原作者是用 C寫，因為 java code 比較好閱讀參考 android TimSort 實作

luni/src/main/java/java/util/TimSort.java - platform/libcore - Git at Google

也有 js 版，但是註解較少

mziccard/node-timsort

minRunLength() 定義如何決定 minrun的值

1
2
3
4
5

int r = 0;      // Becomes 1 if any 1 bits are shifted off        while (n >= MIN_MERGE) {              
    r |= (n & 1);              
    n >>= 1;          
}          
return n + r;

gallopLeft() 用 galloping search 找出最左 ≤ element 的位置，因為是 pass 整個 array 的 reference，所以會有 base / hint 去定位元素，看起來稍微複雜

mergeLo()、mergeHi() 分別對應 (A+B)+C / A+(B+C) 兩種情況，邏輯類似， outer 段落就是在 one-pair-at-a-time mode，只有任一邊陣列連續大於 minGallop 才會切到 galloping mode；
接著再 galloping mode，找到的元素必須位置大於 MIN_GALLOP，否則就會跳出 galloping mode，同時 minGallop會 +=2，也就是下次待在 one-pair-at-a-time mode 會更久。

透過 minGallop 與 MIN_GALLOP，確保 merge 在兩種模式中取得較佳的效率。

BUG

如果再查 TimSort，你可能會找到這一篇文章

Envisage: Engineering Virtualized Services

主要在講 java 版的實作，可能會出現 OutMemeroyBound 的問題，主要是因為在 allocate Stack 的長度時，會有以下極端狀況導致 Stack 長度預設過短而記憶體不夠用

問題出在timsort本身的約束條件

1
2

1\. runLen[i-2] > runLen[i-1] + runLen[i]  
2\. runLen[i-1] > runLen[i]

在runLen為以下情況時，120, 80, 25, 20, 30，25<20+30所以進行run[3]，run[4]合併，變為，120, 80, 45, 30
這時候由於 80>45+30, 45>30 條件滿足了，merge就終止了

但此時120<80+45是不滿足約束條件的，但我們只對上層進行判斷
如果（精心策劃）一些特殊數組造成大量這樣的情況，而在原始碼中 空間是這樣申請的

1
2
3
4
5

int stackLen = (len < 120 ? 5 :  
 len < 1542 ? 10 :  
 len < 119151 ? 19 : 40);  
runBase = new int[stackLen];  
runLen = new int[stackLen];

上面stackLen,是滿足上面提到的約束條件跟MIN_MERGE情況下去估計的最大可能數量，但剛也說了，只對上層進行判斷，會有例外狀況導致所需要的大小可能超出原本預想的，至於修復的方式是把檢查最後三個runLen變成檢查最後四個runLen

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

private void newMergeCollapse() { 
 while (stackSize > 1) {  
  int n = stackSize - 2;**  
  if (   (n >= 1 && runLen[n-1] <= runLen[n] + runLen[n+1]) || (n >= 2 && runLen[n-2] <= runLen[n] + runLen[n-1])) {  
  if (runLen[n - 1] < runLen[n + 1]) n--;
  } else if (runLen[n] > runLen[n + 1]) { 
    break; // Invariant is  established
  }
  mergeAt(n);  
 } 
}

以上 Bug 部分也是由強者公司同事 Frank 補充，有興趣者可以點進去看原文，原文包含說明了如何用工具與方法找出問題的，但因為還沒有到非常理解就不多做說明。

這 Bug 已經被修復，在 Python 的 Bug回報討論中，Tim Peter 提到其實現有的機器沒有足夠的 Memory 去產生這樣的問題，Java 版實作也是有一些改動才有辦法復現，不過最終基於邏輯的完整性，還是先修復了此問題，避免未來有問題。

V8的實作

Getting things sorted in V8

前言

在評估排序演算法上，會考量比對次數跟記憶體用量，在動態語言包含 JS 中比對次數相對重要，因為在比對的時候會使用到用戶寫的程式碼

1
2
3
4
5
6
7
8

const array = [4, 2, 5, 3, 1];

function compare(a, b) {  // Arbitrary code goes here, e.g. `array.push(1);`. 
  return a - b;
}

// A “typical” sort 
call.array.sort(compare);

比對函式回傳 0 、1(或其他正值)、-1(或其他負值)分別代表 等於、大於、小於 ，在比對函式中用戶可能會有 Side-Effect 操作等

1
2
3
4
5
6
7
8

const array = [4, 2, 5, 3, 1];

array.push({  toString() {    // Arbitrary code goes here, e.g. `array.push(1);`.    
  return '42';  
}});

// Sort without a comparison 
function.array.sort();

預設的比對函式會先呼叫 toString() 轉成字串比對

接著把 Spec 先放在腦後，有一部分是 Implementation-defined ，在一些 Spec 保留實作彈性的部分，工程師有機會去自由發揮，做出理想中用戶會希望看到的行為，但這部分各個 JS Engine 行為差異很大，例如說遇上了 accessors(getter/setter) 或prototype-chain ，強烈建議不要這樣寫程式，這裡僅作說明

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

const array = [0, 1, 2];

Object.defineProperty(array, '0', {
    get() {
        console.log('get 0');
        return 0;
    },
    set(v) {
        console.log('set 0');
    }
});

Object.defineProperty(array, '1', {
    get() {
        console.log('get 1');
        return 1;
    },
    set(v) {
        console.log('set 1');
    }
});

array.sort();

const object = {
    1: 'd1',
    2: 'c1',
    3: 'b1',
    4: undefined,
    __proto__: {
        length: 10000,
        1: 'e2',
        10: 'a2',
        100: 'b2',
        1000: 'c2',
        2000: undefined,
        8000: 'd2',
        12000: 'XX',
        __proto__: {
            0: 'e3',
            1: 'd3',
            2: 'c3',
            6: undefined,
        },
    }
};

Array.prototype.sort.call(object);

V8 在排序前後的處理

在 Spec中，將排序的元素分成三部分

  1. non-undefined value，這部分會套用比對函式決定排序
  2. undefined value，放在排序的最後
  3. holes，不存在的值

V8 在實作上的步驟大概為

  1. 找出 Array 或是 Object 的 length
  2. 設變數 numberOfUndefineds 為 0
  3. 在範圍 [0, length) 中
    - 遇到 holes 不處理
    - 遇到 undefined 將 numberOfUndefineds++- 遇到 non-undefined value，放到暫存陣列上

接著用 TimSort 對暫存陣列做排序，之後將暫存暫列寫回原陣列或物件中，並在後面補足 numberOfUndefineds 數量的 undefined，刪除剩餘的長度(移除 hole)，這樣就完成排序了。

過去的實作

過去 V8 是小陣列(length < 10) 用 Insertion Sort 其餘採用 Quick Sort，而 Quick Sort 中分割的小陣列長度小於 10 也是用 Insertion Sort；
因為 Quick Sort 是採用遞迴的方式，小陣列改用 Insertion Sort 效率較好。

Quick Sort 在選擇 pivot 的點很重要，選不好就會跑到最差情況 O(n²)，V8 採用兩種策略：
1. 選擇子陣列中第一個、最後一個、第三個數的中位數
2. 對於大的陣列，選擇被排序過數列的中位數

Quick Sort 優點在於是 In-Place 排序，但缺點有可能會落到 O(n²)。

現行就改成 TimSort 了。

Licensed under CC BY-NC-SA 4.0
comments powered by Disqus