Yuanchieh's Blog

Yuanchieh's Blog

生命是長期而持續的累積

09 Aug 2019

V8 內的排序演算法 — Timsort

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

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

依照 value 排序 ===>

[{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}, {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\.  A > B+C  
2\.  B > C

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

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

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的值

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\. runLen[i-2] > runLen[i-1] + runLen[i]  
2\. runLen[i-1] > runLen[i]

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

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

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

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 中比對次數相對重要,因為在比對的時候會使用到用戶寫的程式碼

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 操作等

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 ,強烈建議不要這樣寫程式,這裡僅作說明

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 了。

Categories