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

前言

前段時間在看 Lane(以前叫做 expirationTime) 相關的代碼時, 被 v8 引擎的這個注釋給吸引到了. 打開研究了一番, 發(fā)現(xiàn)創(chuàng)建數(shù)組的形式不同, v8 內部的處理也不同, 因此適當?shù)姆绞綍π阅艽笥旭砸? 本文做一個記錄.

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

從 React 的源碼說起

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;
}

先簡單介紹一下 createLaneMap 這個方法, 它是用來初始化 FiberRoot 對象中的 eventTimes, expirationTimes, entanglements 屬性, 其中 TotalLanes 是常量 31, 這是因為 Lane 是由 32 位二進制來表示的, 去除二進制的前導 0b, 正好是長度是 31, 如 0b0000000000000000000000000000000.

正文

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

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

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

Common element kinds

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

考察下面代碼: 數(shù)組一開始為 [1, 2, 3], 它的 element kinds(elements kind)在 v8 引擎內部被定義成 PACKED_SMI_ELEMENTS; 我們追加一個浮點型數(shù)字, element kinds 變成了 PACKED_DOUBLE_ELEMENTS, 而當我們再追加進一個字符串類型的元素時, element kinds 變成了 PACKED_ELEMENTS.

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

arr.push(4.56); // PACKED_DOUBLE_ELEMENTS

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

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

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

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

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

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

PACKED vs. HOLEY kinds

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

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

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

v8 之所以做出這樣的區(qū)別, 是因為操作一個 packed array 會比 holey array 得到更多的優(yōu)化. 對于 packed array, 大多數(shù)操作可以高效的執(zhí)行, 而操作 holey array, 需要額外付出昂貴的代價來檢查原型鏈(這里后面會說到).

elements kind 轉化關系

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

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

Performance tips

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

Avoid reading beyond the length of the array

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

下面這個例子, 在讀取完數(shù)組中的所有元素后, 仍再讀取一個越界的元素, 才跳出循環(huán). 可能看到這段代碼你會嗤之以鼻, 因為我們幾乎 100% 不會這么寫, 但 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);
}

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

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 也是不錯的選擇. 而對于數(shù)組, 可以使用 forEach 等內建原型方法. 如今, 無論是 for...of 還是 forEach, 它們的性能跟傳統(tǒng)的 for 循環(huán)已經(jīng)不相上下了.

稍微擴展一下, Airbnb 的規(guī)則 no-restricted-syntax 屏蔽了 for...of, 理由如下. 不過我覺得 for...of 還是可以正常用, for...in 注意增加個 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

上面就講到了盡量不要進行 elements kind 的轉換, 因為一旦轉換了就是不可逆的. 這里有一些小知識, 盡管大家?guī)缀?100% 不會做, 還是貼一下. 如 NaN, Infinity, -0 都會導致純 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 中的對象 —— 尤其在 DOM 中, 有很多的類數(shù)組對象, 有時你自己也會創(chuàng)建類數(shù)組對象(嗯, 只在面試中見過).

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

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

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

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

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

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

另一個經(jīng)典的的類數(shù)組是 argument, 和上面的例子一樣, 同樣可以通過 call 或者 apply 來使用數(shù)組的原型方法. 但隨著 ES6 的普及, 我們更應該使用剩余參數(shù), 因為剩余參數(shù)是真正的數(shù)組.

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

Avoid polymorphism

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

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

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

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

這條就對應著開頭 React 源碼的考量了, 直接看代碼. 方式一你創(chuàng)建了數(shù)組長度為 3 的空數(shù)組, 那這個數(shù)組是稀疏的, 此時這個數(shù)組會被標記成 HOLEY_SMI_ELEMENTS, 即便最后我們填滿了數(shù)組, 他也不會是 packed 的, 仍然被標記成是 holey 的. 方式二是最優(yōu)雅的, 它被標記成了 PACKED_ELEMENTS. 當然如果你不知道到底有多少元素, 那么就使用方式三, 即將元素 push 到一個空數(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);

最后

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