從V8引擎來看JS中這個(gè)"假數(shù)組"

作者：哈啰出行-共享團(tuán)隊(duì)-Allan

原文地址：https://juejin.cn/post/6847902222009925640

數(shù)組是前端日常開發(fā)中最常見的一種數(shù)據(jù)類型，但你真的了解數(shù)組嗎？JS中的數(shù)組又是怎么實(shí)現(xiàn)的呢？通過本文，你將了解：

• JS數(shù)組和傳統(tǒng)數(shù)組的區(qū)別

• V8引擎為“傳統(tǒng)”數(shù)組做了哪些優(yōu)化

• 快數(shù)組和慢數(shù)組

• ArrayBuffer

• 
  

什么是數(shù)組？

數(shù)組（Array）在維基百科上的解釋是：

數(shù)組是由相同類型的元素（element）的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)內(nèi)存來存儲(chǔ)。

注意，這里有兩個(gè)關(guān)鍵詞：相同類型、連續(xù)內(nèi)存，這是作為一個(gè)“真數(shù)組”的充分必要條件！好，重點(diǎn)來了：

let arr = [100, 'foo', 1.1, {a: 1}];

上面代碼表示JS中的一個(gè)常規(guī)的數(shù)組，那么數(shù)組元素為啥可以是多種類型共存？這就有意思了，維基百科對(duì)于數(shù)組的描述應(yīng)該是具有一定權(quán)威的，難道JS的數(shù)組不是真的“數(shù)組”？

這么來看，我們姑且推斷一個(gè)小結(jié)論：

∵ 不同數(shù)據(jù)類型存儲(chǔ)所需空間大小不同

∴ JS中用來存放數(shù)組的內(nèi)存地址一定不是連續(xù)的（除非類型相同）

因此我們大膽猜測(cè)，JS中的數(shù)組實(shí)現(xiàn)一定不是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的！所以JS中原本沒有“真正”的數(shù)組！這就引起了我的好奇心了，那么JS中是如何“實(shí)現(xiàn)”數(shù)組這個(gè)概念的呢？ 我們來一探究竟！

數(shù)組中概念一：連續(xù)內(nèi)存

在講連續(xù)內(nèi)存前，先來了解下什么是內(nèi)存，知道的本節(jié)直接繞過。

1）什么是內(nèi)存？

通俗理解，在計(jì)算機(jī)中，CPU用于數(shù)據(jù)的運(yùn)算，而數(shù)據(jù)來源于硬盤，但考慮到CPU直接從硬盤讀寫數(shù)據(jù)效率低，所以內(nèi)存在其中扮演了“搬運(yùn)工”的角色。

內(nèi)存是由DRAM（動(dòng)態(tài)隨機(jī)存儲(chǔ)器）芯片組成的。DRAM的內(nèi)部結(jié)構(gòu)可以說是PC芯片中最簡單的，是由許多重復(fù)的“單元”——cell組成，每一個(gè)cell由一個(gè)電容和一個(gè)晶體管（一般是N溝道MOSFET）構(gòu)成，電容可儲(chǔ)存1bit數(shù)據(jù)量，充放電后電荷的多少（電勢(shì)高低）分別對(duì)應(yīng)二進(jìn)制數(shù)據(jù)0和1。

DRAM由于結(jié)構(gòu)簡單，可以做到面積很小，存儲(chǔ)容量很大。用芯片短暫存儲(chǔ)數(shù)據(jù)，讀寫的效率要遠(yuǎn)高于磁盤。所以內(nèi)存的運(yùn)行也決定了計(jì)算機(jī)的穩(wěn)定運(yùn)行。

2）內(nèi)存和數(shù)組的故事

了解完什么是內(nèi)存后，回過頭再來看一下數(shù)組的概念：

數(shù)組是由相同類型的元素（element）的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)內(nèi)存來存儲(chǔ)。

那么數(shù)組中的連續(xù)內(nèi)存說的是，通過在內(nèi)存中劃出一串連續(xù)且長度固定的空間，用來于存放一組有限且數(shù)據(jù)類型相同的數(shù)據(jù)結(jié)構(gòu)。在C/C++、Java等編譯型語言中數(shù)組的實(shí)現(xiàn)都是這個(gè)。C++數(shù)組聲明示例代碼如下：

// 數(shù)據(jù)類型 數(shù)組名[元素?cái)?shù)量]

double balance[10];

上述代碼中，需要指定元素類型和數(shù)量，這非常重要。細(xì)細(xì)品味其中的蘊(yùn)含的內(nèi)容，將其聯(lián)系到內(nèi)存以及計(jì)算機(jī)運(yùn)行原理信息量很大！

數(shù)組中概念二：固定長度

從上面說的就很容易理解，計(jì)算機(jī)語言設(shè)計(jì)者為什么要讓C/C++、Java這類編譯型語言在數(shù)組的設(shè)計(jì)上要固定長度。因?yàn)閿?shù)組空間數(shù)連續(xù)的，所以這就意味著內(nèi)存中需要有一整塊的空間用來存放數(shù)組。如果長度不固定，那么內(nèi)存中位于數(shù)組之后的區(qū)域沒法繼續(xù)往下分配了！內(nèi)存不知道當(dāng)前數(shù)組還要不要繼續(xù)存放，要多少空間了。畢竟數(shù)組后面的空間得要留出來給別人去用，不可能讓你（數(shù)組）一直霸占著對(duì)吧。

數(shù)組中概念三：相同數(shù)據(jù)類型

為什么數(shù)組的定義需要每個(gè)元素?cái)?shù)據(jù)類型相同呢。其實(shí)比較容易理解了，如果數(shù)組允許各種類型的數(shù)據(jù)，那么每存入一個(gè)元素都要進(jìn)行裝箱操作，每讀取一個(gè)元素又要進(jìn)行拆箱操作。統(tǒng)一數(shù)據(jù)類型就可以省略裝箱和拆箱的步驟了，這樣能提高存儲(chǔ)和讀取的效率。

V8引擎下數(shù)組的實(shí)現(xiàn)

寫在前面

首先，我們要了解JS代碼是如何在計(jì)算機(jī)上被執(zhí)行的。和Python一樣，它作為一門解釋型語言，需要宿主環(huán)境去對(duì)它進(jìn)行“轉(zhuǎn)換”，然后再由機(jī)器運(yùn)行機(jī)器碼，也就是二進(jìn)制。我們平時(shí)對(duì)JS的討論很多都是（默認(rèn)）基于瀏覽器來講的，當(dāng)前大多主流瀏覽器底層都是基于C++開發(fā)的，并且Node底層也是基于Chrome V8引擎的JS運(yùn)行環(huán)境，而V8底層也是基于C++來開發(fā)的。所以會(huì)有開發(fā)者以為JavaScript是用C++寫的，這是不對(duì)的。

作為一門解釋型語言，JS并非只有C++才能去解析JS，其實(shí)還有：

• D：DMDScript

• Java：Rhino、Nashorn、DynJS、Truffle/JS 等

• C#：Managed JScript、SPUR 等等

還有最近熱度不減的Rust：deno（也是基于V8）。所以，我們要來研究JS中數(shù)組的實(shí)現(xiàn)就要依賴“解釋”他的JS引擎來講了。鑒于此，本文用V8引擎來進(jìn)行講解有關(guān)JS中的數(shù)組。

V8源碼中的JS數(shù)組

為了追蹤JS到底是如何實(shí)現(xiàn)數(shù)組的，我們追蹤到V8中看看它是如何去“解析”JS數(shù)組的。下面截圖來自V8源碼：

可以看到上面截圖1中可以得到兩個(gè)信息（V8源碼注釋寫的還是比較詳細(xì)的）：

• 1、JSArray數(shù)組繼承于JSObject對(duì)象

• 2、數(shù)組有快慢兩種模式

  
  

下面我們來具體講講。

JS數(shù)組就是“對(duì)象”

如果說JS中的數(shù)組底層是一個(gè)對(duì)象，那么我們就可以解釋為什么JS中數(shù)組可以放各種類型了。假設(shè)我們猜測(cè)是對(duì)的，那么如何來驗(yàn)證這一點(diǎn)呢？為此最近花了點(diǎn)時(shí)間探索了一番，在網(wǎng)上看了很多資料，也找了很多方法，最終鎖定使用通過觀察JS最終執(zhí)行生產(chǎn)的字節(jié)碼來看最終代碼的轉(zhuǎn)換。最后選用了GoogleChromeLabs的jsvu，他可以幫我們安裝各種JS引擎，也可以將JS轉(zhuǎn)為字節(jié)碼。

測(cè)試代碼：const arr = [1, true, 'foo'];
復(fù)制代碼

然后使用V8-debug引擎去debug打印他轉(zhuǎn)譯的字節(jié)碼，如下圖所示：

那么這就可以得出結(jié)論，其實(shí)arr就是一個(gè)map，它有key，有value，而key就是數(shù)組的索引，value就是數(shù)組中的元素。

快數(shù)組和慢數(shù)組

細(xì)心的同學(xué)可能發(fā)現(xiàn)了，前面截圖的V8源碼注釋中有這樣一段描述：

Such an array can be in one of two modes:- fast, backing storage is a FixedArray and length <= elements.length();- slow, backing storage is a HashTable with numbers as keys.

翻譯一下，一個(gè)數(shù)組含有兩種模式：

• 快（模式）：后備存儲(chǔ)是一個(gè)FixedArray，長度 <= elements.length

• 慢（模式）：后備存儲(chǔ)是一個(gè)以數(shù)字為鍵的HashTable

  
  

那么來思考下為什么要V8要將數(shù)組這樣“設(shè)計(jì)”，動(dòng)機(jī)是什么？無非就是為了提升性能，一說到性能，就不得不提內(nèi)存，總之這一切無非就是：

犧牲性能節(jié)省內(nèi)存，犧牲內(nèi)存提高性能

這是時(shí)間換空間，空間換時(shí)間的博弈，最后看到底哪個(gè)“劃算”（合理）。

快數(shù)組

先看快數(shù)組，快數(shù)組是一種線性存儲(chǔ)，其長度是可變的，可以動(dòng)態(tài)調(diào)整存儲(chǔ)空間。其內(nèi)部有擴(kuò)容和收縮機(jī)制，來看一下V8中擴(kuò)容的實(shí)現(xiàn)。源碼（C++）：

./src/objects/js-objects.h

拓容時(shí)計(jì)算新容量是根據(jù)基于舊的容量來的:

新容量 = 舊容量 + 50% + 16

因?yàn)镴S數(shù)組是動(dòng)態(tài)可變的，所以這樣安排的固定空間勢(shì)必會(huì)造成內(nèi)存空間的損耗。然后擴(kuò)容后會(huì)將數(shù)組拷貝到新的內(nèi)存空間：

收縮的實(shí)現(xiàn)源碼（C++）:

它的判斷依據(jù)是：當(dāng)前容量是否大于等于當(dāng)前數(shù)組長度的2倍+16，此外的都填入Holes（空洞）對(duì)象。什么是Holes，簡單理解就是數(shù)組分配了空間但沒有存入元素，這里不展開?？鞌?shù)組就是空間換時(shí)間來提升JS數(shù)組在性能上的缺陷，也可以說這是參照編譯型語言的設(shè)計(jì)的一種“數(shù)組”。

一句話總結(jié)：V8用快數(shù)組來實(shí)現(xiàn)內(nèi)存空間的連續(xù)（增加內(nèi)存來提升性能），但由于JS是弱類型語言，空間無法固定，所以使用數(shù)組的length來作為依據(jù)，在底層進(jìn)行內(nèi)存的重新分配。

慢數(shù)組

慢數(shù)組底層實(shí)現(xiàn)使用的是 HashTable 哈希表，相比于快數(shù)組，他不用開辟大塊的連續(xù)空間，從而節(jié)省內(nèi)存，但無疑執(zhí)行效率是比快數(shù)組要低的（時(shí)間換空間）。相關(guān)代碼（C++）：

快慢數(shù)組之間的轉(zhuǎn)換

JS中長度不固定，類型不固定，所以我們?cè)谶m合的適合會(huì)做相應(yīng)的轉(zhuǎn)換，以期望它能以最適合當(dāng)前數(shù)組的方式去提升性能。對(duì)應(yīng)源碼：

上面截圖代碼中，返回true就表示應(yīng)該快數(shù)組轉(zhuǎn)慢數(shù)組。第一個(gè)紅框表示3*擴(kuò)容后容量*2 <= 新容量這個(gè)對(duì)象就改為慢數(shù)組。kPreferFastElementsSizeFactor 源碼中聲明如下：

  // 此處注釋翻譯：相比于快（模式）元素，如果字典元素能節(jié)省非常多的內(nèi)存空間，那JSObjects更傾向于字典`dictionary`。  static const uint32_t kPreferFastElementsSizeFactor = 3;

第二個(gè)紅框表示索引-當(dāng)前容量 >= 1024(kMaxGap的值)時(shí)，也會(huì)從快數(shù)組轉(zhuǎn)為慢數(shù)組。其中 kMaxGap 是一個(gè)用于控制快慢數(shù)組轉(zhuǎn)換的試探性常量，源碼中聲明如下：

// 此處注釋翻譯：kMaxGap 是“試探法”常量，用于控制快慢數(shù)組的轉(zhuǎn)換

  static const uint32_t kMaxGap = 1024;

也就是說當(dāng)前數(shù)組在重新賦值要遠(yuǎn)超其所需的容量+1024的時(shí)候，就會(huì)造成內(nèi)從的浪費(fèi)，于是改為慢數(shù)組。我們來驗(yàn)證下：

示例代碼一：

let arr = [1];復(fù)制代碼

%DebugPrint(arr) 后截圖如下：

然后將arr數(shù)組重新賦值:

arr[1024] = 2;復(fù)制代碼

%DebugPrint(arr) 后截圖如下：

ok，驗(yàn)證成功。接下來我們來看如何從慢數(shù)組到快數(shù)組。

從上面源碼注釋可以知道，快數(shù)組到慢數(shù)組的條件就是：快數(shù)組節(jié)省僅為50％的空間時(shí)，就采用慢數(shù)組（Dictionary）。我們繼續(xù)來驗(yàn)證:

let arr = [1];arr[1025] = 1;復(fù)制代碼

上面代碼聲明的數(shù)組使用的是慢數(shù)組（Dictionary），截圖如下

接下來讓索引從500開始填充數(shù)字1，讓其滿足快數(shù)組節(jié)省空間小于50％：

for(let i=500;i<1024;i++){    arr[i]=1;}復(fù)制代碼

?

得到結(jié)果如下：

最終我們得到結(jié)果，讓arr數(shù)組從慢數(shù)組（Dictionary）轉(zhuǎn)為了快數(shù)組（HOLEY_SMI_ELEMENTS就是Fast Holey Elements）。以上就是快慢數(shù)組的相互轉(zhuǎn)換，核心還是本著合理用內(nèi)存來決定到底用哪種數(shù)組。

new ArrayBuffer

講了真么多，無非就是在說JS中由于語言“特色”而在數(shù)組的實(shí)現(xiàn)上有一些性能問題，那么為了解決這個(gè)問題V8引擎中引入了連續(xù)數(shù)組的概念，這是在JS代碼轉(zhuǎn)譯層做的優(yōu)化，那么還有其他方式嗎？

當(dāng)然有，那就是ES6中ArrayBuffer。ArrayBuffer 對(duì)象用來表示通用的、固定長度的原始二進(jìn)制數(shù)據(jù)緩沖區(qū)，它是一個(gè)字節(jié)數(shù)組。使用ArrayBuffer能在操作系統(tǒng)內(nèi)存中得到一塊連續(xù)的二進(jìn)制區(qū)域。然后這塊區(qū)域供JS去使用。

// create an ArrayBuffer with a size in bytesconst buffer = new ArrayBuffer(8); // 入?yún)?為length
console.log(buffer.byteLength);

但需要注意的是ArrayBuffer本身不具備操作字節(jié)能力，需要通過視圖去操作。比如：

let buffer = new ArrayBuffer(3);let view = new DataView(buffer);view.setInt8(0,?8)

更多細(xì)節(jié)本文不再展開，請(qǐng)讀者自行探索。

??愛心三連擊
1.看到這里了就點(diǎn)個(gè)在看支持下吧，你的「點(diǎn)贊，在看」是我創(chuàng)作的動(dòng)力。
2.關(guān)注公眾號(hào)程序員成長指北，回復(fù)「1」加入高級(jí)前端交流群！「在這里有好多 前端?開發(fā)者，會(huì)討論?前端 Node 知識(shí)，互相學(xué)習(xí)」！
3.也可添加微信【ikoala520】，一起成長。
“在看轉(zhuǎn)發(fā)”是最大的支持