探究JS V8引擎下的“數組”底層實現

本文首發于 vivo互聯網技術 微信公眾號?
鏈接：https://mp.weixin.qq.com/s/np9Yoo02pEv9n_LCusZn3Q
作者：李超

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

一、背景

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

二、什么是數組

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

圖中有兩個關鍵的點，相同類型、連續內存。

這兩個關鍵點先不必深究，繼續往下看，下面來解釋。

看完數據結構中的定義，再來看下具體語言中對數組的實現：

C、C++、Java、Scala 等語言中數組的實現，是通過在內存中劃分一串連續的、固定長度的空間，來實現存放一組有限個相同數據類型的數據結構。這里面也涉及到了幾個重要的概念：連續、固定長度、相同數據類型，與數據結構中的定義是類似的。

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

1.連續

連續空間存儲是數組的特點，下圖是數組在內存中的存儲示意圖。

可以明顯的看出各元素在內存中是相鄰的，是一種線性的存儲結構。

2.固定長度

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

3.相同數據類型

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

看到這，想必大部分人應該感覺：嗯，這跟我認識的數組幾乎吻合吧。

那我們再來點刺激的，進入正菜，JavaScript 中的數組。

三、JavaScript 中的數組

先來看段代碼：

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 數組非同尋常的地方。

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

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

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

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

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

2. JS 數組可以動態的改變容量，根據元素的數量來擴容、收縮。

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

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

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

看到這里，應該可以看出一點端倪，大膽猜想，JS的數組不是基礎的數據結構實現的，應該是在基礎上面做了一些封裝。

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

四、刨根問底：從V8源碼上看數組的實現

Talk is cheap，show me the code.

下面一圖是 V8 中數組的源碼：

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

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

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

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

通過 jsvu 來看一下底層是如何實現的：

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

其中，數組的index其實是字符串。

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

fast ：

快速的后備存儲結構是 FixedArray ，并且數組長度 <= elements.length();

slow ：

緩慢的后備存儲結構是一個以數字為鍵的 HashTable 。

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

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

源碼注釋中的fast和slow，只是簡單的解釋了一下，其對應的是快數組和慢數組，下面來具體的看一下兩種形式是如何實現的。

1、快數組（FAST ELEMENTS）

快數組是一種線性的存儲方式。新創建的空數組，默認的存儲方式是快數組，快數組長度是可變的，可以根據元素的增加和刪除來動態調整存儲空間大小，內部是通過擴容和收縮機制實現，那來看下源碼中是怎么擴容和收縮的。

源碼中擴容的實現方法（C++）：

新容量的的計算方式：

即new_capacity = old_capacity /2 + old_capacity + 16

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

擴容后會將數組拷貝到新的內存空間中，源碼：

看完了擴容，再來看看當空間多余時如何收縮數組空間。

源碼中收縮的實現方法（C++）:

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

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

看上面圖中的這段代碼：

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

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

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

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

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

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

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

新建數組時，如果沒有設置容量，V8會默認使用 Fast Elements 模式實現。

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

使用jsvu調用v8-debug版本的底層實現來驗證一下：

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

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

驗證：

這個PACKED_SMI_ELEMENTS就是Fast Elements 模式。

快數組先到這，再來看下慢數組：

2、慢數組（DICTIONARY ELEMENTS）

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

源碼中 Dictionary 的結構

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

了解了數組的兩種實現方式，我們來總結下兩者的區別。

3、快數組、慢數組的區別

1. 存儲方式方面：快數組內存中是連續的，慢數組在內存中是零散分配的。

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

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

既然有快數組和慢數組，兩者的也有各自的特點，每個數組的存儲結構不會是一成不變的，會有具體情況下的快慢數組轉換，下面來看一下什么情況下會發生轉換。

五、快數組慢數組之間的轉換

1、快 -> 慢

首先來看 V8 中判斷快數組是否應該轉為慢數組的源碼：

關鍵代碼：

1. 新容量 >= 3 擴容后的容量 2 ，會轉變為慢數組。

2. 當加入的 index- 當前capacity >= kMaxGap（1024） 時（也就是至少有了 1024 個空洞），會轉變為慢數組。

我們主要來看下第二種關鍵代碼的情況。

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

也就是說，當對數組賦值時使用遠超當前數組的容量+ 1024時（這樣出現了大于等于 1024 個空洞，這時候要對數組分配大量空間則將可能造成存儲空間的浪費，為了空間的優化，會轉化為慢數組。

代碼實錘：

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

數組中只有三個元素，但是卻在 1030 的位置存放了一個值，那么中間會有多于1024個空洞，這時就會變為慢數組。

來驗證一下：

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

好了，看完了快數組轉慢數組，再反過來看下慢數組轉換為快數組。

2、慢 -> 快

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

V8中是否應該轉為快數組的判斷源碼：

關鍵代碼：

當慢數組的元素可存放在快數組中且長度在 smi 之間且僅節省了50%的空間,則會轉變為快數組

來寫代碼驗證一下：

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

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

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

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

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

3、各有優勢

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

六、擴展：ArrayBuffer

JS在ES6也推出了可以按照需要分配連續內存的數組，這就是ArrayBuffer。

ArrayBuffer會從內存中申請設定的二進制大小的空間，但是并不能直接操作它，需要通過ArrayBuffer構建一個視圖，通過視圖來操作這個內存。

let buffer = new ArrayBuffer(1024);

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

let intArray = new Int32Array(bf);

這行代碼創建了有符號的32位的整數數組，每個數占 4 字節，長度也就是 1024 / 4 = 256 個。

代碼驗證：

七、總結

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

1. 傳統意義上的數組是怎么樣的

2. JavaScript 中的數組有哪些特別之處

3. 從V8源碼下研究 JS 數組的底層實現

4. JS 數組的兩種模式是如何轉換的

5. ArrayBuffer

總的來說，JS 的數組看似與傳統數組不一樣，其實只是 V8 在底層實現上做了一層封裝，使用兩種數據結構實現數組，通過時間和空間緯度的取舍，優化數組的性能。

了解數組的底層實現，可以幫助我們寫出執行效率更高的代碼。