從Chrome源碼看JS Array的實現
本篇將步介紹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還是有優勢，但是若能夠很快定位到刪除元素的位置，鏈表毫無疑問是更合適的。
來自：https://zhuanlan.zhihu.com/p/26388217