摘要：我關(guān)注的賀老賀師俊前輩最近發(fā)表個(gè)這樣一條微博雖然這條微博沒有引起大范圍的關(guān)注和討論，但是作為新人，我陷入了思考。通過賀老的微博，對一個(gè)問題進(jìn)行探究，最終找到核心成員的一文，進(jìn)行參考并翻譯。

我關(guān)注的賀老—賀師俊前輩@johnhax 最近發(fā)表個(gè)這樣一條微博：

雖然這條微博沒有引起大范圍的關(guān)注和討論，但是作為新人，我陷入了思考。究竟 V8 引擎做了哪些魔法，達(dá)到了極大限度的優(yōu)化呢？

這篇文章，將會深入淺出分析這些優(yōu)化背后的奧秘。希望大神給予斧正和引導(dǎo)，同時(shí)對讀者有所啟發(fā)和幫助。

ECMAScript 2015 語言標(biāo)準(zhǔn)規(guī)格介紹了幾種新的數(shù)據(jù)結(jié)構(gòu)：比如 Maps 和 Sets（當(dāng)然還有類似 WeakMaps 和 WeakSets等），而這幾個(gè)新引入的數(shù)據(jù)結(jié)構(gòu)有一個(gè)共性，那就是都可以根據(jù)同樣新引入的遍歷協(xié)議（iteration protocol）進(jìn)行遍歷。這就意味著你可以使用 for...of 循環(huán)或者擴(kuò)展運(yùn)算符進(jìn)行操作。舉一個(gè) Sets 簡單的例子：

const s = new Set([1, 2, 3, 4]);
console.log(...s);
// 1 2 3 4
for (const x of s) console.log(x);
// 1
// 2
// 3
// 4

同樣對于 Maps：

const m = new Map([[1, "1"], [2, "2"], [3, "3"], [4, "4"]]);
console.log(...m);
// (2) [1, "1"] (2) [2, "2"] (2) [3, "3"] (2) [4, "4"]
console.log(...m.keys());
// 1 2 3 4
console.log(...m.values());
//  1 2 3 4
for (const [x, y] of m) console.log(x, "is", y);
// 1 "is" "1"
// 2 "is" "2"
// 3 "is" "3"
// 4 "is" "4"

通過這兩個(gè)簡單的例子，展示了最基本的用法。感興趣的讀者可以參考 ECMA 規(guī)范： Map Iterator Objects 和 Set Iterator Objects。

然而不幸的是，這些可遍歷的數(shù)據(jù)結(jié)構(gòu)在 V8 引擎中并沒有很好的進(jìn)行優(yōu)化。或者說，對于這些實(shí)現(xiàn)細(xì)節(jié)優(yōu)化程度很差。包括 ECMAScript 成員 Brian Terlson 也曾在 Twitter 上抱怨，指出他使用 Sets 來實(shí)現(xiàn)一個(gè)正則引擎時(shí)遇到了惱人的性能問題。

所以，現(xiàn)在是時(shí)間來對他們進(jìn)行優(yōu)化了！但在著手優(yōu)化前，我們需要先徹底認(rèn)清一個(gè)問題：這些數(shù)據(jù)結(jié)構(gòu)處理慢的真實(shí)原因究竟是什么？性能瓶頸到底在哪里？
為了弄清這個(gè)問題，我們就需要理解底層實(shí)現(xiàn)上，迭代器究竟是如何工作的？

為此，我們先從一個(gè)簡單的 for...of 循環(huán)說起。

ES6 借鑒 C++、Java、C# 和 Python 語言，引入了 for...of 循環(huán)，作為遍歷所有數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一方法。

一個(gè)最簡單的使用：

function sum(iterable) {
  let x = 0;
  for (const y of iterable) x += y;
  return x;
}

將這段代碼使用 Babel 進(jìn)行編譯，我們得到：

function sum(iterable) {
  var x = 0;
  var _iteratorNormalCompletion = true;
  var _didIteratorError = false;
  var _iteratorError = undefined;

  try {
    for (var _iterator = iterable[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
      var y = _step.value;
      x += y;
    }
  } catch (err) {
    _didIteratorError = true;
    _iteratorError = err;
  } finally {
    try {
      if (!_iteratorNormalCompletion && _iterator.return) {
        _iterator.return();
      }
    } finally {
      if (_didIteratorError) {
        throw _iteratorError;
      }
    }
  }

  return x;
}

需要告訴大家的一個(gè)事實(shí)是：目前現(xiàn)代 JavaScript 引擎在本質(zhì)上和 Babel 對 for...of 的去語法糖化處理是相同的，僅僅是在具體一些細(xì)節(jié)上有差別。

這個(gè)事實(shí)出處：

All modern JavaScript engines essentially perform the same desugaring that Babel does here to implement for-of (details vary)

上文引自 V8 核心成員，谷歌工程師 Benedikt Meurer。

可是上面經(jīng)過 Babel 編譯后的代碼不太好閱讀。別急，我刪去了煩人的異常處理，只保留了最核心的邏輯供大家參考，以便研究：

function sum(iterable) {
  var x = 0;
  var iterator = iterable[Symbol.iterator]();
  for (;;) {
    var iterResult = iterator.next();
    if (iterResult.done) break;
    x += iterResult.value;
  }
  return x;
}

理解這段代碼需要的預(yù)備知識需要清楚 for...of 和 Symbol.iterator 方法關(guān)系：

一個(gè)數(shù)據(jù)結(jié)構(gòu)只要部署了 Symbol.iterator 屬性，就被視為具有 iterator 接口，就可以用 for...of 循環(huán)遍歷它的成員。也就是說，for...of 循環(huán)內(nèi)部調(diào)用的是數(shù)據(jù)結(jié)構(gòu)的 Symbol.iterator 方法。

for...of 循環(huán)可以使用的范圍包括數(shù)組、Set 和 Map 結(jié)構(gòu)、某些類似數(shù)組的對象（比如 arguments 對象、DOM NodeList 對象）、Generator 對象，以及字符串。

我們仔細(xì)觀察上段段代碼，便可以發(fā)現(xiàn)迭代器性能優(yōu)化的關(guān)鍵是：保證在循環(huán)中多次重復(fù)調(diào)用的 iterator.next() 能得到最大限度的優(yōu)化，同時(shí)，最理想的情況是完全避免對 iterResult 的內(nèi)存分配。能夠達(dá)到這種目的的幾個(gè)手段便是使用類似 store-load propagation， escape analysis 和 scalar replacement of aggregates 先進(jìn)的編譯處理技術(shù)。

同時(shí)，優(yōu)化后的編譯還需要完全消除迭代器本身 —— iterable[Symbol.iterator] 的調(diào)用分配，而直接在迭代器 backing-store 上直接操作。

事實(shí)上，在數(shù)組和字符串迭代器的優(yōu)化過程中，就是使用了這樣的技術(shù)和理念。具體的實(shí)施文檔可以參考這里。

那么具體到 Set 迭代器的性能問題，其實(shí)關(guān)鍵原因在與：其實(shí)現(xiàn)上混合了 JavaScript 和 C++ 環(huán)境。比如，我們看 %SetIteratorPrototype%.next() 的實(shí)現(xiàn)：

function SetIteratorNextJS() {
  if (!IS_SET_ITERATOR(this)) {
    throw %make_type_error(kIncompatibleMethodReceiver,
                        "Set Iterator.prototype.next", this);
  }

  var value_array = [UNDEFINED, UNDEFINED];
  var result = %_CreateIterResultObject(value_array, false);
  switch (%SetIteratorNext(this, value_array)) {
    case 0:
      result.value = UNDEFINED;
      result.done = true;
      break;
    case ITERATOR_KIND_VALUES:
      result.value = value_array[0];
      break;
    case ITERATOR_KIND_ENTRIES:
      value_array[1] = value_array[0];
      break;
  }

  return result;
}

這段代碼實(shí)際上按部就班做了這么幾件事情：

定義分配了 value_array 數(shù)組，初始化時(shí)為兩項(xiàng) undefined；

定義分配了 result 對象，其格式為 {value: value_array, done: false}；

調(diào)用 C++ %SetIteratorNext runtime 函數(shù)，將迭代器的 this 和 value_array 作為參數(shù)傳遞。

根據(jù) C++ %SetIteratorNext runtime 函數(shù)返回結(jié)果，將 result 正確賦值

這就造成什么樣的后果呢？遍歷的每一步我們都在不斷地分配兩個(gè)對象：value_array 和 result。不管是 V8 的 TurboFan 還是 Crankshaft （V8的優(yōu)化編譯器） 我們都無法消除這樣的操作。更糟糕的是，每一步遍歷我們都要在 JavaScript 和 C++ 之間進(jìn)行切換。下面的圖，簡要表示了一個(gè)簡單的 SUM 函數(shù)在底層的運(yùn)行流程：

在 V8 執(zhí)行時(shí)，總處在兩個(gè)狀態(tài)（事實(shí)上更多）：執(zhí)行 C++ 代碼和執(zhí)行 JavaScript 當(dāng)中。這兩個(gè)狀態(tài)之間的轉(zhuǎn)換開銷巨大。從 JavaScript 到 C++，是依賴所謂的 CEntryStub 完成，CEntryStub 會觸發(fā) C++ 當(dāng)中指定的 Runtime_Something 函數(shù)（本例中為 Runtime_SetIteratorNext）。所以，是否可以避免這種轉(zhuǎn)換，以及避免 value_array 和 result 對象的分配又決定了性能的關(guān)鍵。

最新的 %SetIteratorPrototype%.next() 實(shí)現(xiàn)正是切中要害，做了這個(gè)“關(guān)鍵”的處理。我們想要執(zhí)行的代碼在調(diào)用之前就會變得 hot （熱處理），TurboFan 進(jìn)而最終得以熱處理優(yōu)化。借助所謂的 CodeStubAssembler，baseline implementation，現(xiàn)在已經(jīng)完全在 JavaScript 層面實(shí)現(xiàn)接入。這樣我們僅僅只需要調(diào)用 C++ 來做垃圾回收（在可用內(nèi)存耗盡時(shí)）以及異常處理的工作。

在遍歷協(xié)議中，JavaScript 同樣提供 Set.prototype.forEach 和 Map.prototype.forEach 方法，來接收一個(gè)回調(diào)函數(shù)。這些同樣依賴于 C++ 的處理邏輯，這樣不僅僅需要我們將 JavaScript 轉(zhuǎn)換為 C++，還要處理回調(diào)函數(shù)轉(zhuǎn)換為 Javascript，這樣的工作模式如下圖：

所以，上面使用 CodeStubAssembler 的方式只能處理簡單的非回調(diào)函數(shù)場景。真正完全意義上的優(yōu)化，包括 forEach 方法的 TurboFan 化還需要一些待開發(fā)的魔法。

我們使用下面的 benchmark 代碼進(jìn)行優(yōu)化程度的評測：

const s = new Set;
const m = new Map;
for (let i = 0; i < 1e7; ++i) {
  m.set(i, i);
  s.add(i);
}

function SetForOf() {
  for (const x of s) {}
}

function SetForOfEntries() {
  for (const x of s.entries()) {}
}

function SetForEach() {
  s.forEach(function(key, key, set) {});
}

function MapForOf() {
  for (const x of m) {}
}

function MapForOfKeys() {
  for (const x of m.keys()) {}
}

function MapForOfValues() {
  for (const x of m.values()) {}
}

function MapForEach() {
  m.forEach(function(val, key, map) {});
}

const TESTS = [
    SetForOf,
    SetForOfEntries,
    SetForEach,
    MapForOf,
    MapForOfKeys,
    MapForOfValues,
    MapForEach
];

// Warmup.
for (const test of TESTS) {
  for (let i = 0; i < 10; ++i) test();
}

// Actual tests.
for (const test of TESTS) {
  console.time(test.name);
  test();
  console.timeEnd(test.name);
}
    

在 Chrome60 和 Chrome61 版本的對比中，得到下面圖標(biāo)結(jié)論：

可見，雖然大幅提升，但是我們還是得到了一些不太理想的結(jié)果。尤其體現(xiàn)在 SetForOfEntries 和 MapForOf 上。但是這將會在更長遠(yuǎn)的計(jì)劃上進(jìn)行處理。

這篇文章只是在大面上介紹了遍歷器性能所面臨的瓶頸和現(xiàn)有的解決方案。通過賀老的微博，對一個(gè)問題進(jìn)行探究，最終找到 V8 核心成員 Benedikt Meurer 的 Faster Collection Iterators一文，進(jìn)行參考并翻譯。想要完全透徹理解原文章中內(nèi)容，還需要扎實(shí)的計(jì)算機(jī)基礎(chǔ)、v8
引擎工作方式以及編譯原理方面的知識儲備。

因我才疏學(xué)淺，入行也不到兩年，更不算計(jì)算機(jī)科班出身，拾人牙慧的同時(shí)難免理解有偏差和疏漏。更多 V8 引擎方面的知識，建議大家更多關(guān)注@justjavac，編譯方面的知識關(guān)注 Vue 作者@尤雨溪 以及他在 JS Conf 上的演講內(nèi)容： 前端工程中的編譯時(shí)優(yōu)化。畢竟，我們關(guān)注前端大 V、網(wǎng)紅的根本并不是為了看熱鬧、看撕 b，而是希望在前輩身上學(xué)習(xí)到更多知識、得到更多啟發(fā)。

最后，隨著 ECMAScript 的飛速發(fā)展，讓每一名前端開發(fā)者可能都會感覺到處在不斷地學(xué)習(xí)當(dāng)中，甚至有些疲于奔命。但是在學(xué)習(xí)新的特性和語法之外，理解更深層的內(nèi)容才是學(xué)習(xí)進(jìn)階的關(guān)鍵。

我同樣不知道什么是海，
赤腳站在沙灘上，
急切地等待著黎明的到來。

Happy Coding!

PS:
作者Github倉庫 和 知乎問答鏈接
歡迎各種形式交流。