【深度】扒開V8引擎的源碼，我找到了你們想要的前端算法（下次面試官再問算法，用它懟回去?。?/h1>

發(fā)布時(shí)間：2020-07-04 17:16:19 來源：網(wǎng)絡(luò) 閱讀：1843 作者：亞里士朱徳 欄目：web開發(fā)

算法對于前端工程師來說總有一層神秘色彩，這篇文章通過解讀V8源碼，帶你探索Array.prototype.sort函數(shù)下的算法實(shí)現(xiàn)。

<!-- more -->

來，先把你用過的和聽說過的排序算法都列出來：

• 快速排序
• 冒泡排序
• 插入排序
• 歸并排序
• 堆排序
• 希爾排序
• 選擇排序
• 計(jì)數(shù)排序
• 桶排序
• 基數(shù)排序
• ...

答題環(huán)節(jié)到了， sort 函數(shù)使用的以上哪一種算法？

如果你在網(wǎng)上搜索過關(guān)于 sort 源碼的文章，可能會告訴你數(shù)組長度小于10用插入排序，否則用快速排序。

開始我也是這么認(rèn)為的，可當(dāng)我?guī)е鸢溉?GitHub 驗(yàn)證的時(shí)候發(fā)現(xiàn)并非如此。

首先我并沒有找到對應(yīng)的 js 源碼（文章說實(shí)現(xiàn)邏輯是用js寫的），因?yàn)榈掳姹镜腣8源碼已經(jīng)修改，改用V8 Torque。V8 Torque是專門用來開發(fā)V8而創(chuàng)造的語言，語法類似TypeScript（再一次證明TypeScript的價(jià)值），它的編譯器使用CodeStubAssembler轉(zhuǎn)換成高效的匯編代碼。
簡單理解起來就是創(chuàng)造了一個(gè)類似TypeScript的高效的高級語言，這個(gè)語言的文件后綴是tq。

這里需要感謝 justjavac 大神指點(diǎn)~

其次當(dāng)我開始閱讀源碼的時(shí)候，并沒有找到使用快速排序的代碼，也沒有找到判斷數(shù)組長度的常數(shù)值10。

所有的證據(jù)表明，之前的源碼解讀文章很可能已經(jīng)過時(shí)。

那么最新版本的 V8 用的是什么排序算法呢？

算法解讀

V8引擎在xx版本之后就舍棄了快速排序，因?yàn)樗皇欠€(wěn)定的排序算法，在最壞情況下，時(shí)間復(fù)雜度會降級到O(n^2)。
而是采用了一種混合排序的算法：TimSort。
這種功能算法最初用于Python語言中，嚴(yán)格地說它t不屬于以上10種排序算法中的任何一種，屬于一種混合排序算法：
在數(shù)據(jù)量小的子數(shù)組中使用插入排序，然后再使用歸并排序將有序的子數(shù)組進(jìn)行合并排序，時(shí)間復(fù)雜度為 O(nlogn) 。

結(jié)合V8源碼，具體實(shí)現(xiàn)步驟如下：

1. 判斷數(shù)組長度，小于2直接返回，不排序。
2. 開始循環(huán)。
3. 找出一個(gè)有序子數(shù)組，我們稱之為“run”，長度為 currentRunLength 。
4. 計(jì)算最小合并序列長度 minRunLength （這個(gè)值會根據(jù)數(shù)組長度動態(tài)變化，在32~64之間）。
5. 比較 currentRunLength 和 minRunLength ，如果 currentRunLength >= minRunLength ，否則采用插入排序補(bǔ)足數(shù)組長度至 minRunLength ，將 run 壓入棧 pendingRuns 中。
6. 每次有新的 run 被壓入 pendingRuns 時(shí)保證棧內(nèi)任意3個(gè)連續(xù)的 run（run0, run1, run2）從下至上滿足run0>run1+run2 && run1>run2 ，不滿足的話進(jìn)行調(diào)整直至滿足。
7. 如果剩余子數(shù)組為0，結(jié)束循環(huán)。
8. 合并棧中所有 run，排序結(jié)束。

源碼解讀

源碼路徑

/thrid_party/v8/builtins/array-sort.tq

調(diào)用棧

1386 ArrayPrototypeSort
1403 ArrayTimSort
1369 ArrayTimSortImpl
1260 ComputeMinRunLength // 計(jì)算 minRunLength
// while循環(huán) 
1262 CountAndMakeRun // 計(jì)算當(dāng)前 run 的長度
1267 BinaryInsertionSort // 用插入排序補(bǔ)足 run 長度
1274 MergeCollapse // 放入 pendingRuns 并根據(jù)需要進(jìn)行調(diào)整
// 循環(huán)結(jié)束 
1281 MergeForceCollapse // 合并 pendingRuns 中所有 run

核心源碼

tq語言雖然有些不一樣，但如果有TypeScript基礎(chǔ)的話閱讀起來應(yīng)該不成問題。
下面重點(diǎn)解讀3個(gè)函數(shù)的源碼：

// 在while循環(huán)之前調(diào)用，每次排序只調(diào)用一次，用來計(jì)算 minRunLength
macro ComputeMinRunLength(nArg: Smi): Smi {
  let n: Smi = nArg;
  let r: Smi = 0;

  assert(n >= 0);
  // 不斷除以2，得到結(jié)果在 32~64 之間
  while (n >= 64) {
    r = r | (n & 1);
    n = n >> 1;
  }

  const minRunLength: Smi = n + r;
  assert(nArg < 64 || (32 <= minRunLength && minRunLength <= 64));
  return minRunLength;
}

// 計(jì)算第一個(gè) run 的長度
macro CountAndMakeRun(implicit context: Context, sortState: SortState)(
    lowArg: Smi, high: Smi): Smi {
  assert(lowArg < high);
  // 這里保存的才是我們傳入的數(shù)組數(shù)據(jù)
  const workArray = sortState.workArray;

  const low: Smi = lowArg + 1;
  if (low == high) return 1;

  let runLength: Smi = 2;

  const elementLow = UnsafeCast<JSAny>(workArray.objects[low]);
  const elementLowPred = UnsafeCast<JSAny>(workArray.objects[low - 1]);
  // 調(diào)用比對函數(shù)來比對數(shù)據(jù)
  let order = sortState.Compare(elementLow, elementLowPred);

  const isDescending: bool = order < 0 ? true : false;

  let previousElement: JSAny = elementLow;
  // 遍歷子數(shù)組并計(jì)算 run 的長度
  for (let idx: Smi = low + 1; idx < high; ++idx) {
    const currentElement = UnsafeCast<JSAny>(workArray.objects[idx]);
    order = sortState.Compare(currentElement, previousElement);

    if (isDescending) {
      if (order >= 0) break;
    } else {
      if (order < 0) break;
    }

    previousElement = currentElement;
    ++runLength;
  }

  if (isDescending) {
    ReverseRange(workArray, lowArg, lowArg + runLength);
  }

  return runLength;
}

// 調(diào)整 pendingRuns ，使棧長度大于3時(shí)，所有 run 都滿足 run[n]>run[n+1]+run[n+2] 且 run[n+1]>run2[n+2]
transitioning macro MergeCollapse(context: Context, sortState: SortState) {
    const pendingRuns: FixedArray = sortState.pendingRuns;

    while (GetPendingRunsSize(sortState) > 1) {
      let n: Smi = GetPendingRunsSize(sortState) - 2;

      if (!RunInvariantEstablished(pendingRuns, n + 1) ||
          !RunInvariantEstablished(pendingRuns, n)) {
        if (GetPendingRunLength(pendingRuns, n - 1) <
            GetPendingRunLength(pendingRuns, n + 1)) {
          --n;
        }
        MergeAt(n); // 將第 n 個(gè) run 和第 n+1 個(gè) run 進(jìn)行合并
      } else if (
          GetPendingRunLength(pendingRuns, n) <=
          GetPendingRunLength(pendingRuns, n + 1)) {
        MergeAt(n); // 將第 n 個(gè) run 和第 n+1 個(gè) run 進(jìn)行合并
      } else {
        break;
      }
    }
  }

總結(jié)

下次面試前端崗位的時(shí)候，如果面試官問你算法題，你可以莞爾一笑地問他/她：

知道 Array 的 sort 函數(shù)使用了什么算法嗎？TimSort要不要了解一下？

當(dāng)然如果因此搞得面試官難堪而導(dǎo)致拿不到offer可別怪作者~

參考：

• V8源碼
• 《V8引擎中的排序》
• 《男科一夢（再續(xù)一集）-TimSort的實(shí)現(xiàn)》

一部由眾多技術(shù)專家推薦，幫你成為具有全面能力和全局視野工程師的進(jìn)階利器——《了不起的JavaScript工程師》已經(jīng)在京東、當(dāng)當(dāng)、淘寶各大平臺上架了~

點(diǎn)擊下方鏈接即刻踏上屬于你的進(jìn)階之路吧！

https://u.jd.com/nETVMh

向AI問一下細(xì)節(jié)