我關(guān)注的賀老—賀師俊前輩@johnhax 最近發(fā)表個這樣一條微博：
雖然這條微博沒有引起大范圍的關(guān)注和討論，但是作為新人巧鸭，我陷入了思考。究竟 V8 引擎做了哪些魔法，達(dá)到了極大限度的優(yōu)化呢瓶埋？
這篇文章，將會深入淺出分析這些優(yōu)化背后的奧秘诊沪。希望大神給予斧正和引導(dǎo)养筒，同時對讀者有所啟發(fā)和幫助。
我們到底在討論什么端姚？
ECMAScript 2015 語言標(biāo)準(zhǔn)規(guī)格介紹了幾種新的數(shù)據(jù)結(jié)構(gòu)：比如 Maps 和 Sets（當(dāng)然還有類似 WeakMaps 和 WeakSets等）晕粪，而這幾個新引入的數(shù)據(jù)結(jié)構(gòu)有一個共性，那就是都可以根據(jù)同樣新引入的遍歷協(xié)議（iteration protocol）進(jìn)行遍歷渐裸。這就意味著你可以使用 for...of 循環(huán)或者擴展運算符進(jìn)行操作巫湘。舉一個 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"
通過這兩個簡單的例子，展示了最基本的用法昏鹃。感興趣的讀者可以參考 ECMA 規(guī)范： Map Iterator Objects 和 Set Iterator Objects尚氛。
然而不幸的是，這些可遍歷的數(shù)據(jù)結(jié)構(gòu)在 V8 引擎中并沒有很好的進(jìn)行優(yōu)化盆顾〉『郑或者說，對于這些實現(xiàn)細(xì)節(jié)優(yōu)化程度很差您宪。包括 ECMAScript 成員 Brian Terlson 也曾在 Twitter 上抱怨奈懒，指出他使用 Sets 來實現(xiàn)一個正則引擎時遇到了惱人的性能問題。
所以宪巨，現(xiàn)在是時間來對他們進(jìn)行優(yōu)化了磷杏！但在著手優(yōu)化前，我們需要先徹底認(rèn)清一個問題：這些數(shù)據(jù)結(jié)構(gòu)處理慢的真實原因究竟是什么捏卓？性能瓶頸到底在哪里极祸？
為了弄清這個問題，我們就需要理解底層實現(xiàn)上怠晴，迭代器究竟是如何工作的遥金？
深入主題探索究竟
為此，我們先從一個簡單的 for...of 循環(huán)說起蒜田。
ES6 借鑒 C++稿械、Java、C# 和 Python 語言冲粤，引入了 for...of 循環(huán)美莫，作為遍歷所有數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一方法页眯。
一個最簡單的使用：
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;
}
需要告訴大家的一個事實是：目前現(xiàn)代 JavaScript 引擎在本質(zhì)上和 Babel 對 for...of 的去語法糖化處理是相同的厢呵，僅僅是在具體一些細(xì)節(jié)上有差別窝撵。
這個事實出處：
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)系：
一個數(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)化，同時章钾，最理想的情況是完全避免對 iterResult 的內(nèi)存分配墙贱。能夠達(dá)到這種目的的幾個手段便是使用類似 store-load propagation， escape analysis 和 scalar replacement of aggregates 先進(jìn)的編譯處理技術(shù)贱傀。
同時惨撇，優(yōu)化后的編譯還需要完全消除迭代器本身 —— iterable[Symbol.iterator] 的調(diào)用分配，而直接在迭代器 backing-store 上直接操作府寒。
事實上魁衙，在數(shù)組和字符串迭代器的優(yōu)化過程中，就是使用了這樣的技術(shù)和理念株搔。具體的實施文檔可以參考這里剖淀。
那么具體到 Set 迭代器的性能問題，其實關(guān)鍵原因在與：其實現(xiàn)上混合了 JavaScript 和 C++ 環(huán)境纤房。比如祷蝌，我們看 %SetIteratorPrototype%.next() 的實現(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;
}
這段代碼實際上按部就班做了這么幾件事情：
- 定義分配了 value_array 數(shù)組，初始化時為兩項 undefined帆卓；
- 定義分配了 result 對象巨朦，其格式為 {value: value_array, done: false}；
- 調(diào)用 C++ %SetIteratorNext runtime 函數(shù)剑令，將迭代器的 this 和 value_array 作為參數(shù)傳遞糊啡。
- 根據(jù) C++ %SetIteratorNext runtime 函數(shù)返回結(jié)果，將 result 正確賦值
這就造成什么樣的后果呢吁津？遍歷的每一步我們都在不斷地分配兩個對象：value_array 和 result棚蓄。不管是 V8 的 TurboFan 還是 Crankshaft （V8的優(yōu)化編譯器） 我們都無法消除這樣的操作。更糟糕的是碍脏，每一步遍歷我們都要在 JavaScript 和 C++ 之間進(jìn)行切換梭依。下面的圖，簡要表示了一個簡單的 SUM 函數(shù)在底層的運行流程：
在 V8 執(zhí)行時典尾，總處在兩個狀態(tài)（事實上更多）：執(zhí)行 C++ 代碼和執(zhí)行 JavaScript 當(dāng)中役拴。這兩個狀態(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() 實現(xiàn)正是切中要害髓考，做了這個“關(guān)鍵”的處理部念。我們想要執(zhí)行的代碼在調(diào)用之前就會變得 hot （熱處理），TurboFan 進(jìn)而最終得以熱處理優(yōu)化氨菇。借助所謂的 CodeStubAssembler儡炼，baseline implementation，現(xiàn)在已經(jīng)完全在 JavaScript 層面實現(xiàn)接入门驾。這樣我們僅僅只需要調(diào)用 C++ 來做垃圾回收（在可用內(nèi)存耗盡時）以及異常處理的工作射赛。
基于回調(diào)函數(shù)的遍歷
在遍歷協(xié)議中，JavaScript 同樣提供 Set.prototype.forEach 和 Map.prototype.forEach 方法奶是，來接收一個回調(diào)函數(shù)楣责。這些同樣依賴于 C++ 的處理邏輯，這樣不僅僅需要我們將 JavaScript 轉(zhuǎn)換為 C++聂沙，還要處理回調(diào)函數(shù)轉(zhuǎn)換為 Javascript秆麸，這樣的工作模式如下圖：
所以，上面使用 CodeStubAssembler 的方式只能處理簡單的非回調(diào)函數(shù)場景及汉。真正完全意義上的優(yōu)化沮趣，包括 forEach 方法的 TurboFan 化還需要一些待開發(fā)的魔法。
優(yōu)化提升 Benchmark
我們使用下面的 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ìn)行處理翁狐。
總結(jié)
這篇文章只是在大面上介紹了遍歷器性能所面臨的瓶頸和現(xiàn)有的解決方案。通過賀老的微博凌蔬，對一個問題進(jìn)行探究露懒，最終找到 V8 核心成員 Benedikt Meurer 的 Faster Collection Iterators一文，進(jìn)行參考并翻譯砂心。想要完全透徹理解原文章中內(nèi)容懈词，還需要扎實的計算機基礎(chǔ)、v8
引擎工作方式以及編譯原理方面的知識儲備辩诞。
因我才疏學(xué)淺坎弯，入行也不到兩年，更不算計算機科班出身躁倒，拾人牙慧的同時難免理解有偏差和疏漏荞怒。更多 V8 引擎方面的知識，建議大家更多關(guān)注@justjavac秧秉，編譯方面的知識關(guān)注 Vue 作者@尤雨溪 以及他在 JS Conf 上的演講內(nèi)容： 前端工程中的編譯時優(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)鍵织中。
我同樣不知道什么是海，
赤腳站在沙灘上衷戈，
急切地等待著黎明的到來狭吼。
