探究JS V8引擎下的“數(shù)組”底層實現(xiàn)

本文首發(fā)于 vivo互聯(lián)網(wǎng)技術(shù) 微信公眾號?
鏈接：https://mp.weixin.qq.com/s/np9Yoo02pEv9n_LCusZn3Q
作者：李超

JavaScript 中的數(shù)組有很多特性：存放不同類型元素、數(shù)組長度可變等等，這與數(shù)據(jù)結(jié)構(gòu)中定義的數(shù)組結(jié)構(gòu)或者C++、Java等語言中的數(shù)組不太一樣，那么JS數(shù)組的這些特性底層是如何實現(xiàn)的呢，我們打開V8引擎的源碼，從中尋找到了答案。V8中對數(shù)組做了一層封裝，使其有兩種實現(xiàn)方式：快數(shù)組和慢數(shù)組，快數(shù)組底層是連續(xù)內(nèi)存，通過索引直接定位，慢數(shù)組底層是哈希表，通過計算哈希值來定位。兩種實現(xiàn)方式各有特點(diǎn)，有各自的使用情況，也會相互轉(zhuǎn)換。

一、背景

使用 JS 的數(shù)組時，發(fā)現(xiàn) JS 的數(shù)組可以存放不同類型的元素、并且數(shù)組長度是可變的。數(shù)據(jù)結(jié)構(gòu)中定義的數(shù)組是定長的、數(shù)據(jù)類型一致的存儲結(jié)構(gòu)。JS 中的數(shù)組竟然如此特殊，這也是為什么標(biāo)題中數(shù)組二字加上了“”的原因。帶著一臉的懵逼，打開V8源碼，一探究竟。

二、什么是數(shù)組

首先來看下什么是數(shù)組，下面的圖是維基百科上對于數(shù)組的定義：

圖中有兩個關(guān)鍵的點(diǎn)，相同類型、連續(xù)內(nèi)存。

這兩個關(guān)鍵點(diǎn)先不必深究，繼續(xù)往下看，下面來解釋。

看完數(shù)據(jù)結(jié)構(gòu)中的定義，再來看下具體語言中對數(shù)組的實現(xiàn)：

C、C++、Java、Scala 等語言中數(shù)組的實現(xiàn)，是通過在內(nèi)存中劃分一串連續(xù)的、固定長度的空間，來實現(xiàn)存放一組有限個相同數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)。這里面也涉及到了幾個重要的概念：連續(xù)、固定長度、相同數(shù)據(jù)類型，與數(shù)據(jù)結(jié)構(gòu)中的定義是類似的。

下面來分別解釋下這幾個概念：

1.連續(xù)

連續(xù)空間存儲是數(shù)組的特點(diǎn)，下圖是數(shù)組在內(nèi)存中的存儲示意圖。

可以明顯的看出各元素在內(nèi)存中是相鄰的，是一種線性的存儲結(jié)構(gòu)。

2.固定長度

因為數(shù)組的空間是連續(xù)的，這就意味著在內(nèi)存中會有一整塊空間來存放數(shù)組，如果不是固定長度，那么內(nèi)存中位于數(shù)組之后的區(qū)域會沒辦法分配，內(nèi)存不知道數(shù)組還要不要繼續(xù)存放，要使用多長的空間。長度固定，就界定了數(shù)組使用內(nèi)存的界限，數(shù)組之外的空間可以分配給別人使用。

3.相同數(shù)據(jù)類型

因為數(shù)組的長度是固定的，如果不是相同數(shù)據(jù)類型，一會存 int ，一會存String ，兩種不同長度的數(shù)據(jù)類型，不能保證各自存放幾個，這樣有悖固定長度的規(guī)定，所以也要是相同的數(shù)據(jù)類型。

看到這，想必大部分人應(yīng)該感覺：嗯，這跟我認(rèn)識的數(shù)組幾乎吻合吧。

那我們再來點(diǎn)刺激的，進(jìn)入正菜，JavaScript 中的數(shù)組。

三、JavaScript 中的數(shù)組

先來看段代碼：

let arr = [100, 12.3, "red", "blue", "green"];
arr[arr.length] = "black";
console.log(arr.length);    // 6
console.log(arr[arr.length-1]);  //black

這短短幾行代碼可以看出 JS 數(shù)組非同尋常的地方。

• 第一行代碼，數(shù)組中竟然存放了三種數(shù)據(jù)類型？

• 第二行代碼，竟然向數(shù)組中添加了一個值？

• 第三行和第四行代碼驗證了，數(shù)組的長度改變了，添加的值也生效了。

除了這些，JS的數(shù)組還有很多特殊的地方：

1. JS 數(shù)組中不止可以存放上面的三種數(shù)據(jù)類型，它可以存放數(shù)組、對象、函數(shù)、Number、Undefined、Null、String、Boolean 等等。

2. JS 數(shù)組可以動態(tài)的改變?nèi)萘浚鶕?jù)元素的數(shù)量來擴(kuò)容、收縮。

3. JS 數(shù)組可以表現(xiàn)的像棧一樣，為數(shù)組提供了push()和pop()方法。也可以表現(xiàn)的像隊列一樣，使用shift()和 push()方法，可以像使用隊列一樣使用數(shù)組。

4. JS 數(shù)組可以使用for-each遍歷，可以排序，可以倒置。

5. JS 提供了很多操作數(shù)組的方法，比如Array.concat()、Array.join()、Array.slice()。

看到這里，應(yīng)該可以看出一點(diǎn)端倪，大膽猜想，JS的數(shù)組不是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，應(yīng)該是在基礎(chǔ)上面做了一些封裝。

下面發(fā)車，一步一步地驗證我們的猜想。

四、刨根問底：從V8源碼上看數(shù)組的實現(xiàn)

Talk is cheap，show me the code.

下面一圖是 V8 中數(shù)組的源碼：

首先，我們看到JSArray 是繼承自JSObject，也就是說，數(shù)組是一個特殊的對象。

那這就好解釋為什么JS的數(shù)組可以存放不同的數(shù)據(jù)類型，它是個對象嘛，內(nèi)部也是key-value的存儲形式。

我們使用這段代碼來驗證一下：

let a = [1, "hello", true, function () {
  return 1;
}];

通過 jsvu 來看一下底層是如何實現(xiàn)的：

可以看到，底層就是個 Map ，key 為0，1，2，3這種索引，value 就是數(shù)組的元素。

其中，數(shù)組的index其實是字符串。

驗證完這個問題，我們再繼續(xù)看上面的V8源碼，摩拳擦掌，準(zhǔn)備見大招了！
從注釋上可以看出，JS 數(shù)組有兩種表現(xiàn)形式，fast 和 slow ，啥？英文看不懂？那我讓谷歌幫我們翻譯好了！

fast ：

快速的后備存儲結(jié)構(gòu)是 FixedArray ，并且數(shù)組長度 <= elements.length();

slow ：

緩慢的后備存儲結(jié)構(gòu)是一個以數(shù)字為鍵的 HashTable 。

HashTable，維基百科中解釋的很好：

散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

源碼注釋中的fast和slow，只是簡單的解釋了一下，其對應(yīng)的是快數(shù)組和慢數(shù)組，下面來具體的看一下兩種形式是如何實現(xiàn)的。

1、快數(shù)組（FAST ELEMENTS）

快數(shù)組是一種線性的存儲方式。新創(chuàng)建的空數(shù)組，默認(rèn)的存儲方式是快數(shù)組，快數(shù)組長度是可變的，可以根據(jù)元素的增加和刪除來動態(tài)調(diào)整存儲空間大小，內(nèi)部是通過擴(kuò)容和收縮機(jī)制實現(xiàn)，那來看下源碼中是怎么擴(kuò)容和收縮的。

源碼中擴(kuò)容的實現(xiàn)方法（C++）：

新容量的的計算方式：

即new_capacity = old_capacity /2 + old_capacity + 16

也就是，擴(kuò)容后的新容量 = 舊容量的1.5倍 + 16

擴(kuò)容后會將數(shù)組拷貝到新的內(nèi)存空間中，源碼：

看完了擴(kuò)容，再來看看當(dāng)空間多余時如何收縮數(shù)組空間。

源碼中收縮的實現(xiàn)方法（C++）:

可以看出收縮數(shù)組的判斷是：
如果容量 >= length的2倍 + 16，則進(jìn)行收縮容量調(diào)整，否則用holes對象（什么是holes對象？下面來解釋）填充未被初始化的位置。

如果收縮，那收縮到多大呢？

看上面圖中的這段代碼：

這個elements_to_trim就是需要收縮的大小，需要根據(jù) length + 1 和 old_length 進(jìn)行判斷，是將空出的空間全部收縮掉還是只收縮二分之一。

解釋完了擴(kuò)容和減容，來看下剛剛提到的holes對象。

holes （空洞）對象指的是數(shù)組中分配了空間，但是沒有存放元素的位置。對于holes，快數(shù)組中有個專門的模式，在 Fast Elements 模式中有一個擴(kuò)展，是Fast Holey Elements模式。

Fast Holey Elements 模式適合于數(shù)組中的 holes （空洞）情況，即只有某些索引存有數(shù)據(jù)，而其他的索引都沒有賦值的情況。

那什么時候會是Fast Holey Elements 模式呢？

當(dāng)數(shù)組中有空洞，沒有賦值的數(shù)組索引將會存儲一個特殊的值，這樣在訪問這些位置時就可以得到 undefined。這種情況下就會是 Fast Holey Elements 模式。

Fast Holey Elements 模式與Fast Elements 模式一樣，會動態(tài)分配連續(xù)的存儲空間，分配空間的大小由最大的索引值決定。

新建數(shù)組時，如果沒有設(shè)置容量，V8會默認(rèn)使用 Fast Elements 模式實現(xiàn)。

如果要對數(shù)組設(shè)置容量，但并沒有進(jìn)行內(nèi)部元素的初始化，例如let a = new Array(10);，這樣的話數(shù)組內(nèi)部就存在了空洞，就會以Fast Holey Elements 模式實現(xiàn)。

使用jsvu調(diào)用v8-debug版本的底層實現(xiàn)來驗證一下：

一目了然，HOLEY_SMI_ELEMENTS?就是Fast Holey Elements 模式 。

如果對數(shù)組進(jìn)行了初始化，比如let a = new Array(1,2,3);，這種就不存在空洞，就是以Fast Elements 模式實現(xiàn)。

驗證：

這個PACKED_SMI_ELEMENTS就是Fast Elements 模式。

快數(shù)組先到這，再來看下慢數(shù)組：

2、慢數(shù)組（DICTIONARY ELEMENTS）

慢數(shù)組是一種字典的內(nèi)存形式。不用開辟大塊連續(xù)的存儲空間，節(jié)省了內(nèi)存，但是由于需要維護(hù)這樣一個 HashTable，其效率會比快數(shù)組低。

源碼中 Dictionary 的結(jié)構(gòu)

可以看到，內(nèi)部是一個HashTable，然后定義了一些操作方法，和 Java 的 HashMap類似，沒有什么特別之處。

了解了數(shù)組的兩種實現(xiàn)方式，我們來總結(jié)下兩者的區(qū)別。

3、快數(shù)組、慢數(shù)組的區(qū)別

1. 存儲方式方面：快數(shù)組內(nèi)存中是連續(xù)的，慢數(shù)組在內(nèi)存中是零散分配的。

2. 內(nèi)存使用方面：由于快數(shù)組內(nèi)存是連續(xù)的，可能需要開辟一大塊供其使用，其中還可能有很多空洞，是比較費(fèi)內(nèi)存的。慢數(shù)組不會有空洞的情況，且都是零散的內(nèi)存，比較節(jié)省內(nèi)存空間。

3. 遍歷效率方面：快數(shù)組由于是空間連續(xù)的，遍歷速度很快，而慢數(shù)組每次都要尋找 key 的位置，遍歷效率會差一些。

既然有快數(shù)組和慢數(shù)組，兩者的也有各自的特點(diǎn)，每個數(shù)組的存儲結(jié)構(gòu)不會是一成不變的，會有具體情況下的快慢數(shù)組轉(zhuǎn)換，下面來看一下什么情況下會發(fā)生轉(zhuǎn)換。

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

1、快 -> 慢

首先來看 V8 中判斷快數(shù)組是否應(yīng)該轉(zhuǎn)為慢數(shù)組的源碼：

關(guān)鍵代碼：

1. 新容量 >= 3 擴(kuò)容后的容量 2 ，會轉(zhuǎn)變?yōu)槁龜?shù)組。

2. 當(dāng)加入的 index- 當(dāng)前capacity >= kMaxGap（1024） 時（也就是至少有了 1024 個空洞），會轉(zhuǎn)變?yōu)槁龜?shù)組。

我們主要來看下第二種關(guān)鍵代碼的情況。

kMaxGap 是源碼中的一個常量，值為1024。

也就是說，當(dāng)對數(shù)組賦值時使用遠(yuǎn)超當(dāng)前數(shù)組的容量+ 1024時（這樣出現(xiàn)了大于等于 1024 個空洞，這時候要對數(shù)組分配大量空間則將可能造成存儲空間的浪費(fèi)，為了空間的優(yōu)化，會轉(zhuǎn)化為慢數(shù)組。

代碼實錘：

let a = [1, 2]
a[1030] = 1;

數(shù)組中只有三個元素，但是卻在 1030 的位置存放了一個值，那么中間會有多于1024個空洞，這時就會變?yōu)槁龜?shù)組。

來驗證一下：

可以看到，此時的數(shù)組確實是字典類型了，成功！

好了，看完了快數(shù)組轉(zhuǎn)慢數(shù)組，再反過來看下慢數(shù)組轉(zhuǎn)換為快數(shù)組。

2、慢 -> 快

處于哈希表實現(xiàn)的數(shù)組，在每次空間增長時， V8 的啟發(fā)式算法會檢查其空間占用量， 若其空洞元素減少到一定程度，則會將其轉(zhuǎn)化為快數(shù)組模式。

V8中是否應(yīng)該轉(zhuǎn)為快數(shù)組的判斷源碼：

關(guān)鍵代碼：

當(dāng)慢數(shù)組的元素可存放在快數(shù)組中且長度在 smi 之間且僅節(jié)省了50%的空間,則會轉(zhuǎn)變?yōu)榭鞌?shù)組

來寫代碼驗證一下：

let a = [1,2];
a[1030] = 1;
for (let i = 200; i < 1030; i++) {
    a[i] = i;
}

上面我們說過的，在 1030 的位置上面添加一個值，會造成多于 1024 個空洞，數(shù)組會使用為 Dictionary 模式來實現(xiàn)。

那么我們現(xiàn)在往這個數(shù)組中再添加幾個值來填補(bǔ)空洞，往 200-1029 這些位置上賦值，使慢數(shù)組不再比快數(shù)組節(jié)省 50% 的空間，會發(fā)生什么神奇的事情呢？

可以看到，數(shù)組變成了快數(shù)組的 Fast Holey Elements 模式，驗證成功。

那是不是快數(shù)組存儲空間連續(xù)，效率高，就一定更好呢？其實不然。

3、各有優(yōu)勢

快數(shù)組就是以空間換時間的方式，申請了大塊連續(xù)內(nèi)存，提高效率。
慢數(shù)組以時間換空間，不必申請連續(xù)的空間，節(jié)省了內(nèi)存，但需要付出效率變差的代價。

六、擴(kuò)展：ArrayBuffer

JS在ES6也推出了可以按照需要分配連續(xù)內(nèi)存的數(shù)組，這就是ArrayBuffer。

ArrayBuffer會從內(nèi)存中申請設(shè)定的二進(jìn)制大小的空間，但是并不能直接操作它，需要通過ArrayBuffer構(gòu)建一個視圖，通過視圖來操作這個內(nèi)存。

let buffer = new ArrayBuffer(1024);

這行代碼就申請了 1kb 的內(nèi)存區(qū)域。但是并不能對 arrayBuffer 直接操作，需要將它賦給一個視圖來操作內(nèi)存。

let intArray = new Int32Array(bf);

這行代碼創(chuàng)建了有符號的32位的整數(shù)數(shù)組，每個數(shù)占 4 字節(jié)，長度也就是 1024 / 4 = 256 個。

代碼驗證：

七、總結(jié)

看到這，腦瓜子是不是嗡嗡的？喘口氣，我們來回顧一下，這篇文章我們主要討論了這幾件事：

1. 傳統(tǒng)意義上的數(shù)組是怎么樣的

2. JavaScript 中的數(shù)組有哪些特別之處

3. 從V8源碼下研究 JS 數(shù)組的底層實現(xiàn)

4. JS 數(shù)組的兩種模式是如何轉(zhuǎn)換的

5. ArrayBuffer

總的來說，JS 的數(shù)組看似與傳統(tǒng)數(shù)組不一樣，其實只是 V8 在底層實現(xiàn)上做了一層封裝，使用兩種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)數(shù)組，通過時間和空間緯度的取舍，優(yōu)化數(shù)組的性能。

了解數(shù)組的底層實現(xiàn)，可以幫助我們寫出執(zhí)行效率更高的代碼。