從 React 源碼談 v8 引擎對(duì)數(shù)組的內(nèi)部處理

前言

前段時(shí)間在看 Lane(以前叫做 expirationTime) 相關(guān)的代碼時(shí), 被 v8 引擎的這個(gè)注釋給吸引到了. 打開研究了一番, 發(fā)現(xiàn)創(chuàng)建數(shù)組的形式不同, v8 內(nèi)部的處理也不同, 因此適當(dāng)?shù)姆绞綍?huì)對(duì)性能大有裨益, 本文做一個(gè)記錄.

這篇文章翻譯自 Elements kinds in V8, 可配合 Mathias Bynens 的一篇演講視頻 V8 internals for JavaScript developers 一同觀看.

從 React 的源碼說(shuō)起

export function createLaneMap<T>(initial: T): LaneMap<T> {
  // Intentionally pushing one by one.
  // https://v8.dev/blog/elements-kinds#avoid-creating-holes
  const laneMap = [];
  for (let i = 0; i < TotalLanes; i++) {
    laneMap.push(initial);
  }
  return laneMap;
}

先簡(jiǎn)單介紹一下 createLaneMap 這個(gè)方法, 它是用來(lái)初始化 FiberRoot 對(duì)象中的 eventTimes, expirationTimes, entanglements 屬性, 其中 TotalLanes 是常量 31, 這是因?yàn)?Lane 是由 32 位二進(jìn)制來(lái)表示的, 去除二進(jìn)制的前導(dǎo) 0b, 正好是長(zhǎng)度是 31, 如 0b0000000000000000000000000000000.

正文

JavaScript 中對(duì)象的屬性可以是任意類型, 這意味著它們可以是 numeric, 可以是 Symbol, 甚至你用 undefined, null, Date 等等作為 key 都無(wú)所謂. 而對(duì)于 key 是 numeric 的情形, JavaScript 引擎是做了一些優(yōu)化的, 其中最典型的就是數(shù)組索引了.

在 V8 中, 具有整數(shù)名稱的屬性(最常見的形式是由 Array 構(gòu)造函數(shù)生成的對(duì)象, 也就是 new Array())會(huì)得到特別處理. 盡管在許多情況下這些數(shù)字索引屬性的行為與其他屬性一樣, 但是 V8 出于優(yōu)化目的選擇將它們與非數(shù)字屬性分開存儲(chǔ). 在內(nèi)部, V8 甚至給這些屬性一個(gè)特殊的名稱: 元素. 對(duì)象具有映射到值的屬性, 而數(shù)組具有映射到元素的索引.

雖然這些內(nèi)部代碼從未直接暴露給 JavaScript 開發(fā)人員, 但它們解釋了為什么某些代碼模式比其他代碼模式更快.

Common element kinds

在 JavaScript 代碼的運(yùn)行時(shí), V8 會(huì)對(duì)數(shù)組中的每個(gè) element kinds 保持跟蹤. 這些跟蹤信息允許 V8 來(lái)對(duì)數(shù)組中的指定類型做一些優(yōu)化. 舉個(gè)栗子, 在你調(diào)用 reduce, map 或者 forEach 的時(shí)候, V8 可以根據(jù)數(shù)組包含的 element kinds 優(yōu)化這些操作. 對(duì)于 JavaScript 來(lái)說(shuō), 它不會(huì)區(qū)分一個(gè)數(shù)字是 integers, floats, 亦或 doubles, 但在 V8 內(nèi)部會(huì)有一個(gè)精確的區(qū)分.

考察下面代碼: 數(shù)組一開始為 [1, 2, 3], 它的 element kinds(elements kind)在 v8 引擎內(nèi)部被定義成 PACKED_SMI_ELEMENTS; 我們追加一個(gè)浮點(diǎn)型數(shù)字, element kinds 變成了 PACKED_DOUBLE_ELEMENTS, 而當(dāng)我們?cè)僮芳舆M(jìn)一個(gè)字符串類型的元素時(shí), element kinds 變成了 PACKED_ELEMENTS.

const arr = [1, 2, 3]; // PACKED_SMI_ELEMENTS

arr.push(4.56); // PACKED_DOUBLE_ELEMENTS

arr.push("x"); // PACKED_ELEMENTS

即便我們此時(shí)并不知道以上三種 elements kinds 的區(qū)別, 但也能隱隱感受到, v8 肯定會(huì)對(duì)純 Int 類型元素的數(shù)組做些什么優(yōu)化. 下面來(lái)具體認(rèn)識(shí)一下這三種標(biāo)記:

• SMI 是 Small integers 的縮寫
• 如果有雙精度元素, 數(shù)組會(huì)被標(biāo)記成 PACKED_DOUBLE_ELEMENTS
• 對(duì)于有普通類型元素的, 數(shù)組會(huì)被標(biāo)記成 PACKED_ELEMENTS

需要注意的是, element kinds 的轉(zhuǎn)換是不可逆的, 并且方向只能從特殊到一般, 這就意味著從 PACKED_SMI_ELEMENTS 可以到 PACKED_DOUBLE_ELEMENTS, 但反之不行, 即便你后面再把 4.56 移除掉, 這個(gè)數(shù)組仍然會(huì)是 PACKED_DOUBLE_ELEMENTS.

稍作總結(jié), 我們可以看到 v8 為數(shù)組做了這些事:

• v8 會(huì)給每個(gè)數(shù)組指定 element kinds
• element kinds 不是一成不變的, 隨著我們對(duì)數(shù)組操作, 它會(huì)在運(yùn)行時(shí)發(fā)生變化
• element kinds 的轉(zhuǎn)換是不可逆的, 并且方向只能從特殊到一般

PACKED vs. HOLEY kinds

上面幾種標(biāo)記都是針對(duì)的密集數(shù)組. 什么是密集數(shù)組呢? 比如 [1, 2, 4.56, 'x'], 它的 length 是 4, 并且這四個(gè)位置在初始化的時(shí)候都有元素.

與此相反便是稀疏數(shù)組了, 比如下面這個(gè)例子: 原本數(shù)組為 PACKED_ELEMENTS, 但我們?cè)?nbsp;arr[8] 的位置設(shè)置了一個(gè)元素, 眾所周知數(shù)組內(nèi)存分配空間是按照長(zhǎng)度來(lái)的, 這就導(dǎo)致 arr[5] ~ arr[7] 什么都沒有, 對(duì)于這種數(shù)組, 它的 elements kind 被標(biāo)記成了 HOLEY_ELEMENTS.

// HOLEY_ELEMENTS
const arr = [1, 2, 4.56, "x"];
arr[8] = "hahaha";

v8 之所以做出這樣的區(qū)別, 是因?yàn)椴僮饕粋€(gè) packed array 會(huì)比 holey array 得到更多的優(yōu)化. 對(duì)于 packed array, 大多數(shù)操作可以高效的執(zhí)行, 而操作 holey array, 需要額外付出昂貴的代價(jià)來(lái)檢查原型鏈(這里后面會(huì)說(shuō)到).

elements kind 轉(zhuǎn)化關(guān)系

到此為止, 基本的 elements kind 的轉(zhuǎn)化關(guān)系我們就介紹完了. 當(dāng)然 v8 目前一共提供了 21 種不同的 elements kind, 都在 ElementsKind 這個(gè)枚舉類型中, 每種類型都有它不同的優(yōu)化方案.

通過(guò)這張圖, 我們看到轉(zhuǎn)化關(guān)系是不可逆的, 且只能從特殊類型到普遍類型. 更特定的元素類型支持更細(xì)粒度的優(yōu)化, 元素類型在越靠右下，對(duì)該數(shù)組的操作可能就越慢. 為了獲得最佳性能, 避免不必要地轉(zhuǎn)換到那些普遍類型, 堅(jiān)持使用最適合情況的特定類型.

Performance tips

在大多數(shù)情況下我們無(wú)需 care 這種細(xì)微的類型轉(zhuǎn)換. 但是, 你可以做以下幾件事來(lái)獲得最大的性能.

Avoid reading beyond the length of the array

這個(gè)很好理解, 比如一個(gè)數(shù)組 arr 的長(zhǎng)度是 5, 但你卻訪問(wèn)了 arr[42], 因?yàn)樵摂?shù)組沒有一個(gè)叫做 42 的屬性, 因此 JavaScript 引擎必須得到原型鏈上查找, 直到原型鏈的頂端 null 為止. 一旦負(fù)載遇到這種情況, V8 就會(huì)記住"此負(fù)載需要處理特殊情況", 并且它再也不會(huì)像讀取越界之前那樣快.

下面這個(gè)例子, 在讀取完數(shù)組中的所有元素后, 仍再讀取一個(gè)越界的元素, 才跳出循環(huán). 可能看到這段代碼你會(huì)嗤之以鼻, 因?yàn)槲覀儙缀?100% 不會(huì)這么寫, 但 jQuery 里面極少代碼就用到了這種模式.

for (let i = 0, item; (item = items[i]) != null; i++) {
  doSomething(item);
}

取而代之, 我們用最樸素的 for 循環(huán)就夠了.

const n = items.length;
for (let index = 0; index < n; index += 1) {
  const item = items[index];
  doSomething(item);
}

下面是原作者真實(shí)測(cè)量過(guò)的例子, 該方法傳入 10000 個(gè)元素的數(shù)組, i <= array.length 要比 i < array.length 慢 6 倍(然而我測(cè)了好幾遍下面的代碼居然還快不少, 手動(dòng)狗頭).

function Maximum(array) {
  let max = 0;
  for (let i = 0; i <= array.length; i++) {
    // BAD COMPARISON!
    if (array[i] > max) max = array[i];
  }
  return max;
}

最后, 如果你的集合是可迭代的, 比如 NodeList, Map, Set, 使用 for...of 也是不錯(cuò)的選擇. 而對(duì)于數(shù)組, 可以使用 forEach 等內(nèi)建原型方法. 如今, 無(wú)論是 for...of 還是 forEach, 它們的性能跟傳統(tǒng)的 for 循環(huán)已經(jīng)不相上下了.

稍微擴(kuò)展一下, Airbnb 的規(guī)則 no-restricted-syntax 屏蔽了 for...of, 理由如下. 不過(guò)我覺得 for...of 還是可以正常用, for...in 注意增加個(gè) hasOwnProperty 限制就行.

iterators/generators require regenerator-runtime, which is too heavyweight for this guide to allow them. Separately, loops should be avoided in favor of array iterations.

Avoid elements kind transitions

上面就講到了盡量不要進(jìn)行 elements kind 的轉(zhuǎn)換, 因?yàn)橐坏┺D(zhuǎn)換了就是不可逆的. 這里有一些小知識(shí), 盡管大家?guī)缀?100% 不會(huì)做, 還是貼一下. 如 NaN, Infinity, -0 都會(huì)導(dǎo)致純 Int 類型的數(shù)組變成 PACKED_DOUBLE_ELEMENTS.

const arr = [1, 2, 3, +0]; // PACKED_SMI_ELEMENTS

arr.push(NaN, Infinity, -0); // PACKED_DOUBLE_ELEMENTS

Prefer arrays over array-like objects

一些在 JavaScript 中的對(duì)象 —— 尤其在 DOM 中, 有很多的類數(shù)組對(duì)象, 有時(shí)你自己也會(huì)創(chuàng)建類數(shù)組對(duì)象(嗯, 只在面試中見過(guò)).

const arrayLike = {};
arrayLike[0] = "a";
arrayLike[1] = "b";
arrayLike[2] = "c";
arrayLike.length = 3;

上面的代碼雖然有 index, 也有 length, 但它畢竟缺少真正數(shù)組的原型方法, 即便如此, 你也可以通過(guò) call 或者 apply 數(shù)組的語(yǔ)法來(lái)使用它.

Array.prototype.forEach.call(arrayLike, (value, index) => {
  console.log(`${index}: ${value}`);
});
// This logs '0: a', then '1: b', and finally '2: c'.

這段代碼使用起來(lái)沒啥問(wèn)題, 但它仍然比真正的數(shù)組去調(diào)用 forEach 要慢, 因此如果有必要(比如要對(duì)該類數(shù)組進(jìn)行大量的操作), 你可以先將該類數(shù)組對(duì)象轉(zhuǎn)換為真正的數(shù)組, 再去做后續(xù)的操作, 也許這種犧牲空間換時(shí)間的方法是值得的.

const actualArray = Array.prototype.slice.call(arrayLike, 0); // 先轉(zhuǎn)換為真正的數(shù)組

actualArray.forEach((value, index) => {
  console.log(`${index}: ${value}`);
});
// This logs '0: a', then '1: b', and finally '2: c'.

另一個(gè)經(jīng)典的的類數(shù)組是 argument, 和上面的例子一樣, 同樣可以通過(guò) call 或者 apply 來(lái)使用數(shù)組的原型方法. 但隨著 ES6 的普及, 我們更應(yīng)該使用剩余參數(shù), 因?yàn)槭Ｓ鄥?shù)是真正的數(shù)組.

const logArgs = (...args) => {
  args.forEach((value, index) => {
    console.log(`${index}: ${value}`);
  });
};
logArgs("a", "b", "c");

Avoid polymorphism

如果你的一個(gè)方法會(huì)處理不同元素類型的數(shù)組, 它可能會(huì)導(dǎo)致多態(tài)操作, 這樣會(huì)比操作單一元素類型的代碼要慢. 舉個(gè)例子來(lái)講, 你自己寫了個(gè)數(shù)組迭代器, 這個(gè)迭代器可以傳入一個(gè)純數(shù)字類型的數(shù)組, 也可以是其他亂七八糟類型的數(shù)組, 這樣就是多態(tài)操作. 當(dāng)然需要注意的是, 數(shù)組內(nèi)建的原型方法在引擎內(nèi)部已經(jīng)做了優(yōu)化, 不在我們的考慮范圍.

下面這個(gè)例子中, each 方法先傳入了 PACKED_ELEMENTS 類型的數(shù)組, 于是 V8 使用內(nèi)聯(lián)緩存(inline cache, 簡(jiǎn)稱 IC) 來(lái)記住這個(gè)特定的類型. 此時(shí) V8 會(huì)"樂觀的"假定 array.length 和 array[index] 在 each 內(nèi)部訪問(wèn)函數(shù)是單調(diào)的(即只有一種類型的元素). 因此如果后續(xù)傳入該方法的數(shù)組仍是 PACKED_ELEMENTS, V8 可以復(fù)用這些先前生成的代碼.

但在后面分別傳入了 PACKED_DOUBLE_ELEMENTS, PACKED_SMI_ELEMENTS 類型的數(shù)組, 就會(huì)導(dǎo)致 array.length 和 array[index] 在 each 內(nèi)部訪問(wèn)函數(shù)被標(biāo)記為多態(tài)的. V8 在每次調(diào)用 each 時(shí)需要額外的檢查一次 PACKED_ELEMENTS, 并添加一個(gè)新的 PACKED_DOUBLE_ELEMENTS, 這就會(huì)造成潛在的性能問(wèn)題.

const each = (array, callback) => {
  for (let index = 0; index < array.length; ++index) {
    const item = array[index];
    callback(item);
  }
};
const doSomething = (item) => console.log(item);

each(["a", "b", "c"], doSomething); // PACKED_ELEMENTS

each([1.1, 2.2, 3.3], doSomething); // PACKED_DOUBLE_ELEMENTS

each([1, 2, 3], doSomething); // PACKED_SMI_ELEMENTS

Avoid creating holes

這條就對(duì)應(yīng)著開頭 React 源碼的考量了, 直接看代碼. 方式一你創(chuàng)建了數(shù)組長(zhǎng)度為 3 的空數(shù)組, 那這個(gè)數(shù)組是稀疏的, 此時(shí)這個(gè)數(shù)組會(huì)被標(biāo)記成 HOLEY_SMI_ELEMENTS, 即便最后我們填滿了數(shù)組, 他也不會(huì)是 packed 的, 仍然被標(biāo)記成是 holey 的. 方式二是最優(yōu)雅的, 它被標(biāo)記成了 PACKED_ELEMENTS. 當(dāng)然如果你不知道到底有多少元素, 那么就使用方式三, 即將元素 push 到一個(gè)空數(shù)組將是最好的選擇.

// 方式 1 (不推薦)
const arr = new Array(3);
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;

// 方式 2
const arr = ["a", "b", "c"];

// 方式 3
const arr = [];
arr.push(0);
arr.push(1);
arr.push(2);

最后

綜上來(lái)講, 這就是一篇爽文, 旨在漲漲見識(shí). 基本百分之九十以上, 后端返回給我們的數(shù)組就已經(jīng)是 PACKED_ELEMENTS 的類型了, 所以真正在乎這種內(nèi)核級(jí)別優(yōu)化的, 也就是如 React 這種牛逼的框架了. 當(dāng)然還有一種情況, 我們似乎可以優(yōu)化一番, 想想你刷動(dòng)態(tài)規(guī)劃的時(shí)候, 是不是初始化背包的時(shí)候就用了 new Array(n).fill(false) 這種代碼呢? (手動(dòng)狗頭.