從Chrome源碼看JS Array的實現

01-23

我們在上一篇介紹了JS Object的實現，這一篇將進一步介紹JS Array的實現。

在此之前，筆者將Chromium升級到了最新版本60，上一次是在元旦的時候下的57，而當前最新發布的穩定版本是57。57是三月上旬發布的，所以Chrome發布一個大版本至少用了兩、三個月的時間。Chrome 60的devTool增加了很多有趣的功能，這裡順便提一下：

例如把沒有用到的CSS/JS按比例標紅，增加了全頁的截屏功能，和一個本地代碼的編輯器：

回到正文。

JS的Array是一個萬能的數據結構，為什麼這麼說呢？因為首先它可以當作一個普通的數組來使用，即通過下標找到數組的元素：

var array = [19, 50, 99];console.log(array[0]);

然後它可以當作一個棧來使用，我們知道棧的特點是先進後出，棧的基本操作是出棧和入棧：

var stack = [1, 2, 3];stack.push(4); //入棧var top = stack.pop(); //出棧

同時它還可以當作一個隊列，隊列的特點是先進先出，基本操作是出隊和入隊：

var queue = [1, 2, 3];queue.push(4); //入隊var head = queue.shift(); //出隊

甚至它還可以當作一個哈希表來使用(但是不推薦這麼用)：

var map = [];map["id"] = 1234;map["name"] = "yin";console.log(map["name"]);

另外，它還可以隨時隨地增刪數組中任意位置的元素：

var array = [1, 2, 3, 4];//從第3個元素開始，刪掉1個元素，並插入-1，-2這兩個元素array.splice(2, 1, -1, -2);//再來個2000的索引array[2000] = 10;

JS Array一方面提供了很大的便利，只要用一個數據結構就可以做很多事情，使用者不需要關心各者的區別，使得JS很容易入門。另一方面它屏蔽了數據結構的概念，不少寫前端的都不知道什麼是棧、隊列、哈希、樹，特別是那些不是學計算機，中途轉過來的。然而這往往是不可取的。

另外一點是，即使是一些前端的老司機，他們也很難說清楚，這些數組函數操作的效率怎麼樣，例如說隨意地往數組中間增加一個元素不會有性能問題么。所以就很有必要從源碼的角度看一下數組是怎麼實現的。

1. JS Array的實現

先看源碼注釋：

// The JSArray describes JavaScript Arrays// Such an array can be in one of two modes:// - fast, backing storage is a FixedArray and length <= elements.length();// Please note: push and pop can be used to grow and shrink the array.// - slow, backing storage is a HashTable with numbers as keys.class JSArray: public JSObject { public: // [length]: The length property. DECL_ACCESSORS(length, Object) // Number of element slots to pre-allocate for an empty array. static const int kPreallocatedArrayElements = 4;};

這裡說明一下，如果不熟悉C/C++的，那把它成偽碼就好了。

源碼裡面說了，JSArray有兩種模式，一種是快速的，一種是慢速的，快速的用的是索引直接定位，慢速的使用用哈希查找，這個在上一篇《從Chrome源碼看JS Object的實現》就已經提及，由於JSArray是繼承於JSObject，所以它也是同樣的處理方式，如下面的：

var array = [1, 2, 3]array[2000] = 10;

增加一個2000的索引時，array就會被轉成慢元素。

如下的數組：

var a = [8, 1, 2];

把a列印出來：

- map = 0x939ebe04359 [FastProperties]
- prototype = 0x27e86e126289
- elements = 0xe70c791d4e9 <FixedArray[3]> [FAST_SMI_ELEMENTS (COW)]
- length = 3
- properties = 0x2b609d202241 <FixedArray[0]> {
#length: 0x2019c3e58da9 <AccessorInfo> (const accessor descriptor)

}
- elements= 0xe70c791d4e9 <FixedArray[3]> {
0: 8
1: 1
2: 2
}

它有一個length的屬性，它的elements有3個元素，按索引排列。當給它加一個2000的索引時：

var a = [8, 1, 2];a[2000] = 10;

列印出來的array變成：

- map = 0x333c83f9dbb9 [FastProperties]
- prototype = 0xdcc53ba6289
- elements = 0x21a208a1d541 <FixedArray[29]> [DICTIONARY_ELEMENTS]

- length = 2001
- properties = 0x885d1402241 <FixedArray[0]> {
#length: 0x1f564a958da9 <AccessorInfo> (const accessor descriptor)
}
- elements= 0x21a208a1d541 <FixedArray[29]> {
2: 2 (data, dict_index: 0, attrs: [WEC])
0: 8 (data, dict_index: 0, attrs: [WEC])
2000: 10 (data, dict_index: 0, attrs: [WEC])
1: 1 (data, dict_index: 0, attrs: [WEC])
}

elements變成了一個慢元素哈希表，哈希表的容量為29。

由於快元素和慢元素上一節已經有詳細討論，這一節將不再重複。我們重點討論數組的操作函數的實現。

2. Push和擴容

數組初始化大小為4：

// Number of element slots to pre-allocate for an empty array. static const int kPreallocatedArrayElements = 4;

執行push的時候會在數組的末尾添加新的元素，而一旦空間不足時，將進行擴容。

在源碼裡面push是用彙編實現的，在C++裡面嵌入的彙編。這個應該是考慮到push是一個最為常用的操作，所以用彙編實現提高執行速度。在彙編的上面封裝了一層，用C++調的封裝的彙編的函數，在編譯組裝的時候，將把這些C++代碼轉成彙編代碼。

計算新容量的函數：

Node* CodeStubAssembler::CalculateNewElementsCapacity(Node* old_capacity, ParameterMode mode) { Node* half_old_capacity = WordOrSmiShr(old_capacity, 1, mode); Node* new_capacity = IntPtrOrSmiAdd(half_old_capacity, old_capacity, mode); Node* padding = IntPtrOrSmiConstant(16, mode); return IntPtrOrSmiAdd(new_capacity, padding, mode);}

如上代碼新容量等於：

new_capacity = old_capacity /2 + old_capacity + 16

即老的容量的1.5倍加上16。初始化為4個，當push第5個的時候，容量將會變成：

new_capacity = 4 / 2 + 4 + 16 = 22

接著申請一塊這麼大的內存，把老的數據拷過去：

Node* CodeStubAssembler::GrowElementsCapacity( Node* object, Node* elements, Node* capacity, Node* new_capacity) { // Allocate the new backing store. Node* new_elements = AllocateFixedArray(new_capacity, mode); // Copy the elements from the old elements store to the new. CopyFixedArrayElements(elements, new_elements, capacity, new_capacity); return new_elements;}

由於複製是用的memcopy，把整一段內存空間拷貝過去，所以這個操作還是比較快的。

再把新元素放到當前length的位置，再把length增加1：

StoreFixedArrayElement(elements, var_length.value());Increment(var_length, 1, mode);

可以來改點代碼玩玩，我們知道push執行後的返回結果是新數組的長度，嘗試把它改成返回老數組的長度：

Node *old_length = LoadJSArrayLength(receiver);Node *new_length = BuildAppendJSArray(/.../);//args.PopAndReturn(new_length);args.PopAndReturn(old_length);

重新編譯Chrome，在控制台上執行比較如下：

右邊的新Chrome返回了4，左邊正常的Chrome返回5.

3. Pop和減容

push是用彙編實現，而pop的邏輯是用C++寫的。在執行pop的時候，第一步，獲取到當前的length，用這個length - 1得到要刪除的元素，然後調用setLength調整容量，最後返回刪除的元素：

int new_length = length - 1;int remove_index = remove_position == AT_START ? 0 : new_length;Handle<Object> result = Subclass::GetImpl(isolate, *backing_store, remove_index);Subclass::SetLengthImpl(isolate, receiver, new_length, backing_store);return result;

我們重點看下這個減容的過程：

if (2 * length <= capacity) { // If more than half the elements won"t be used, trim the array. isolate->heap()->RightTrimFixedArray(*backing_store, capacity - length);} else { // Otherwise, fill the unused tail with holes. BackingStore::cast(*backing_store)->FillWithHoles(length, old_length);}

如果容量大於等於length的2倍，則進行容量調整，否則用holes對象填充。第三行的rightTrim函數，會算出需要釋放的空間大小，並做標記，並等待GC回收：

int bytes_to_trim = elements_to_trim * element_size;// Calculate location of new array end.Address old_end = object->address() + object->Size();Address new_end = old_end - bytes_to_trim;CreateFillerObjectAt(new_end, bytes_to_trim, ClearRecordedSlots::kYes);

也就是說，當數組的元素個數小於容量的一半時，就會進行減少的操作，將容量調整為實際的大小。

4. shift和splice數組中間的操作

push和pop都是在數組末尾操作，相對比較簡單，而shfit、unshfit、splice是在數組的開始或者中間進行操縱。我們來看一下，如果是這種情況的又是如何調整數組元素的。

（1）shift是出隊，即刪除並返回數組的第一個元素。shift和pop調的都是同樣的刪除函數，只不過shift傳的刪除的postion是AT_STRT，源碼裡面會判斷如果是AT_START的話，會把元素進行移動：

if (remove_position == AT_START) { Subclass::MoveElements(isolate, receiver, backing_store, 0, 1, new_length, 0, 0);}

從1的位置移到0的位置，如上面第2行的第4、5個參數，這個move將會調leftTrim，和上面的rightTrim相反：

*dst_elms.location() = BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index));receiver->set_elements(*dst_elms);

（2）unshfit在數組的開始位置插入元素，首先要判斷容量是否足夠存放，如果不夠，將容量擴展為老容量的1.5倍加16，然後把老元素移到新的內存空間偏移為unshift元素個數的位置，也就是說要騰出起始的空間放unshfit傳進來的元素，如果空間足夠了，則直接執行memmove移動內存空間，最後再把unshif傳進來的參數copy到開始的位置：

int insertion_index = add_position == AT_START ? 0 : length;// Copy the arguments to the start.Subclass::CopyArguments(args, backing_store, add_size, 1, insertion_index);// Set the length.receiver->set_length(Smi::FromInt(new_length));

並更新array的length。

（3）splice的操作已經幾乎不用去看源碼了，通過shift和unshift的操作是怎麼樣的，就可以想像到它的執行過程是怎樣的，只是shift/unshfit操作的index是0，而splice可以指定index。具體代碼如下：

// Delete and move elements to make space for add_count new elements.if (add_count < delete_count) { Subclass::SpliceShrinkStep(isolate, receiver, backing_store, start, delete_count, add_count, length, new_length);} else if (add_count > delete_count) { backing_store = Subclass::SpliceGrowStep(isolate, receiver, backing_store, start, delete_count, add_count, length, new_length);}// Copy over the arguments.Subclass::CopyArguments(args, backing_store, add_count, 3, start);

它需要先shrink或者grow中間元素的空間，以適應增加元素比刪除元素少或者多的情況，然後進行容量調整和移動元素。

接著再來看下兩個「小清新」的函數

5. Join和Sort

說它們是小清新，是因為它們是用JS實現的，然後再用wasm打包成native code。不過，join的實現邏輯並不簡單，因為array的元素本身具有多樣化，可能為慢元素或者快元素，還可能帶有循環引用，對於慢元素，需要先排下序：

var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, length));

預處理完之後，最後創建一個字元串數組，用連接符連起來：

// Construct an array for the elements.var elements = new InternalArray(length);for (var i = 0; i < length; i++) { elements[i] = ConvertToString(use_locale, array[i]);}if (separator === "") { return %StringBuilderConcat(elements, length, "");} else { return %StringBuilderJoin(elements, length, separator);}

而sort函數是用的快速排序：

function ArraySort(comparefn) { CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort"); %Log("js/array.js execute ArraySort"); //手動添加的log列印，確保執行的是這裡 var array = TO_OBJECT(this); var length = TO_LENGTH(array.length); return InnerArraySort(array, length, comparefn);}

當數組元素的個數不超過10個時，是用的插入排序：

function InnerArraySort(array, length, comparefn) { // In-place QuickSort algorithm. // For short (length <= 10) arrays, insertion sort is used for efficiency. function QuickSort(a, from, to) { var third_index = 0; while (true) { // Insertion sort is faster for short arrays. if (to - from <= 10) { InsertionSort(a, from, to); return; } //other code ... } }}

快速排序演算法裡面有一個比較重要的地方是選擇樞紐元素，最簡單的是每次都是選取第一個元素，或者中間的元素，在源碼裡面是這樣選擇的：

if (to - from > 1000) { third_index = GetThirdIndex(a, from, to);} else { third_index = from + ((to - from) >> 1);}

如果元素個數在1000以內，則使用它們的中間元素，否則要算一下，這個演算法比較有趣：

function GetThirdIndex(a, from, to) { var t_array = new InternalArray(); // Use both "from" and "to" to determine the pivot candidates. var increment = 200 + ((to - from) & 15); var j = 0; from += 1; to -= 1; for (var i = from; i < to; i += increment) { t_array[j] = [i, a[i]]; j++; } t_array.sort(function(a, b) { return comparefn(a[1], b[1]); }); var third_index = t_array[t_array.length >> 1][0]; return third_index;}

先取一個遞增間距200~215之間，再循環取出原元素裡面落到這個間距的元素，放到一個新的數組裡面（這個數組是C++裡面的數組），然後排下序，取中間的元素。因為樞紐元素的剛好是所有元素的中位數時，排序的效果最好，而這裡是取出少數元素的中位數，類似於抽樣模擬，缺點是它得再藉助另外的排序演算法。

最後再比較一下Array和線性鏈接的速度。

6. Array和線性鏈接的速度

線性鏈接是一種非連續存儲的數據結構，每個元素都有一個指針指向它的下一個元素，所以它刪除元素的時候不需要移動其它元素，也不需要考慮擴容的事情，但是它的查找比較慢。我們實現一個簡單的List和Array進行比較。

List的每個節點用一個Node表示：

class Node{ constructor(value, next){ this.value = value; this.next = next; }}

每個List都有一個頭指針指向第一個元素，和一個length記錄它的長度：

class List{ constructor(){ this.head = null; this.tail = null; this.length = 0; }}

然後實現它的push和unshift函數：

class List{ unshift(value){ return this.insert(0, value); } push(value){ if(this.head === null){ this.head = new Node(value, this.tail); this.length++; } else { this.insert(this.length, value); } return this.length; }}

兩個函數都會調一個通用的insert函數：

insert(index, value){ var insertPos = this.head; //找到需要插入的位置的節點 for(var i = 0; i < index - 1; i++){ insertPos = insertPos.next; } var node = null; if(index === 0){ node = new Node(value, this.head); this.head = node; } else { node = new Node(value, insertPos.next); insertPos.next = node; } this.length++; return value;}

有了這個List之後，就可以初始化一個list和array：

var list = new List();var arr = [];for(var i = 0; i < 100; i++){ list.push(i); arr.push(i);}

可以來比較這個List和Array的存儲方式，非連續和連續的區別：

然後用下面的代碼比較List和Array在數組起始位置插入元素的操作時間：

var count = 10000;console.time("list unshfit");for(var i = 0; i < count; i++){ list.unshift(i);}console.timeEnd("list unshfit");console.time("array unshfit");for(var i = 0; i < count; i++){ arr.unshift(i);}console.timeEnd("array unshfit");

再比較從正中間位置插入元素的時間：

console.time("list insert middle with index");for(var i = 0; i < count; i++){ insertPos = list.insert(list.length >> 1, i);}console.timeEnd("list insert middle with index");console.time("array insert middle");for(var i = 0; i < count; i++){ arr.splice(arr.length >> 1, 0, i);}console.timeEnd("array insert middle");

運行可以得到以下表格：

可以看到在隊首插入元素，使用線性鏈接List的時間將會數量級的優於Array。如果是在中間位置插入的話，由於 List的查找花費了很多時間，導致總時間明顯高於Array。但是如果在插入的時候，記住上一次的位置，那麼List又會明顯快於Array。如下換成記錄插入的位置：

console.time("list insert middle with pos");var insertPos = list.getNode(list.length >> 1);for(var i = 0; i < count; i++){ insertPos = list.insertFromNode(insertPos, i);}console.timeEnd("list insert middle with pos");

時間比較List又快於Array：

綜上，本文介紹了JS Array的實現，特別是它的操作函數，分析了它是怎麼調整容量和移動元素的，並用了一個線性鏈接進行比較。Array的實現用了三種語言：彙編、C++和JS，最常用的如push用了彙編實現，比較常用的如pop/splice等用了C++，較為少用的如join/sort用了JS。

Array為快元素即普通的數組時，增刪元素操作需要不斷的擴容、減容和調整元素的位置。特別是當不斷地在起始位置插入元素時，和鏈表相比，這種時間效率還是比較低下的。如果使用的場景是要根據index刪除元素，使用Array還是有優勢，但是若能夠很快定位到刪除元素的位置，鏈表毫無疑問是更合適的。