接上一篇掘金 V8 中的快慢屬性，本篇分析V8 中的快慢陣列，了解陣列全填充還是帶孔、快慢陣列、快慢轉化、動態擴縮容等等，其實很多語言底層都采用類似的處理方式，比如：Golang中切片的append操作就涉及擴容處理，

?? D8除錯工具使用請來掘金 D8除錯工具——jsvu的使用細則

1、全填充 or 帶孔

通過一個小李子，看一下什么是全填充陣列(Paked-Array)，什么是帶孔陣列(Holey-Array)

前面還寫了稀疏陣列，稀疏陣列更加具有業務應用性，清洗的是無意義的資料，可以對比帶孔陣列來分析一下，有興趣請看掘金?? 稀疏陣列——實作五子棋存盤和續上盤功能

const o = ['a', 'b', 'c']
console.log(o[1])          // 'b'

delete o[1]
console.log(o[1])          // undefined
o.__proto__ = { 1: 'B' }
console.log(o[0])          // 'a'
console.log(o[1])          // 'B'   但如何確定要訪問原型鏈？？??
console.log(o[2])          // 'c'
console.log(o[3])          // undefined

如果一個陣列中所有位置均有值，我們稱之為全填充（Packed）陣列；

若某些位置在初始化時未定義（如 const arr = [1, , 3] 中的 arr[1]），或定義后被洗掉（delete，如上述例子），稱之為帶孔（Holey）陣列，

該例子在 V8 的訪問可以通過下圖解釋：

一開始陣列 o 是 packed 的，所以訪問 o[1] 時可以直接獲取值，而不需要訪問原型，

而行 4：delete o[1] 為陣列引入了一個孔洞（the_hole），用于標記不存在的屬性，同時又行 6 為 o 定義了原型上的 1 屬性，當再次獲取 o[1] 時會穿孔進而繼續往原型鏈上查詢，原型鏈上的查詢是昂貴的，可以根據是否有 the_hole 來降低這部分查詢開銷，

2、快慢陣列

const arr = [1, 2, 3]
arr[1999] = 1999
// arr 會如何存盤？

這個例子中，在行 1 宣告完畢后 arr 是一個全填充的陣列，但在行 2 馬上又定義索引 1999 處值為 1999，此時如果為 arr 創建一個長度為 2000 的完整陣列來存盤這樣的稀疏資料將會非常占用記憶體，為了應對這種情況，V8 會將陣列降級為慢陣列，創建一個字典來存盤「鍵、值、描述符」（key、value、descriptor）三元組，這就是 Object.defineProperty(object, key, descriptor) API 同樣會做的事情，

鑒于我們沒有辦法在 JavaScript 的 API 層面讓 V8 找到 HiddenClass 并存盤對應的 descriptor 資訊，所以當使用 Object.defineProperty 自定義 key、value、descriptor 時，V8 都會使用慢屬性，對應到陣列中就是慢陣列，

Object.defineProperty 是 Vue 2 的核心 API，當物件或陣列很龐大時，不可避免地導致訪問速度下降，這是底層原理決定的，

那究竟什么是快陣列和慢陣列呢？我們看下V8底層對于陣列的定義：?? 源代碼：v8/src/objects/js-array.h

快模式：陣列實作的是 V8 里一個叫 FixedArray 的類，它在記憶體中是連續的空間，直接通過索引讀寫值，非常快，如果有 push 或 pop 操作，它會動態地擴容或收縮，
慢模式：如前文所介紹，V8 創建了一個字典（HashTable）來記錄映射關系，其中索引的整數值即是字典的鍵，

為什么陣列也是物件型別的？

在 V8 原始碼中清晰地表明，JSArray 繼承自 JSObject，即陣列是一個特殊的物件，而 JS 中所有非原始型別都是物件的實體，所以 JS 中陣列可以存盤多種型別的值，

陣列內部也是用key-value的存盤形式

const testArr = [1, "hello", true, function () {
  return 1;
}];

2.1、快陣列何時轉換為慢陣列

(1)、看一下原始碼先??

path:v8/src/objects/js-objects-inl.h

快慢模式轉化： ShouldConvertToSlowElements

// path:v8/src/objects/js-objects-inl.h

// If the fast-case backing storage takes up much more memory than a dictionary
// backing storage would, the object should have slow elements.
// static
static inline bool ShouldConvertToSlowElements(uint32_t used_elements,
                                               uint32_t new_capacity) {
  uint32_t size_threshold = NumberDictionary::kPreferFastElementsSizeFactor *
                            NumberDictionary::ComputeCapacity(used_elements) *
                            NumberDictionary::kEntrySize;
  return size_threshold <= new_capacity;
}

static inline bool ShouldConvertToSlowElements(JSObject object,
                                               uint32_t capacity,
                                               uint32_t index,
                                               uint32_t* new_capacity) {
  STATIC_ASSERT(JSObject::kMaxUncheckedOldFastElementsLength <=
                JSObject::kMaxUncheckedFastElementsLength);
  if (index < capacity) {
    *new_capacity = capacity;
    return false;
  }
  if (index - capacity >= JSObject::kMaxGap) return true;
  *new_capacity = JSObject::NewElementsCapacity(index + 1);
  DCHECK_LT(index, *new_capacity);
  if (*new_capacity <= JSObject::kMaxUncheckedOldFastElementsLength ||
      (*new_capacity <= JSObject::kMaxUncheckedFastElementsLength &&
       ObjectInYoungGeneration(object))) {
    return false;
  }
  return ShouldConvertToSlowElements(object.GetFastElementsUsage(),
                                     *new_capacity);
}

(2)、分析

如果快陣列擴容后的容量是原來的 3 倍以上，意味著它比 HashTable 形式存盤占用更大的記憶體，快陣列會轉換為慢陣列
如果快陣列新增的索引與原來最大索引的差值大于 1024，快陣列會被轉換會慢陣列

所以，前面的例子：

const arr = [1, 2, 3];
arr[1999] = 1999;
%DebugPrint(arr);

1999 - 2 > 1024，arr 從快陣列轉換為哈希形式存盤的慢陣列，

下面看一下詳細運行資訊??

修改arr之前:

修改arr之后：

2.2、慢陣列何時轉換為快陣列

(1)、看一下原始碼先??

path:v8/src/objects/js-objects.cc

// path:v8/src/objects/js-objects.cc

// line:4932
static bool ShouldConvertToFastElements(JSObject object,
                                        NumberDictionary dictionary,
                                        uint32_t index,
                                        uint32_t* new_capacity) {
  // If properties with non-standard attributes or accessors were added, we
  // cannot go back to fast elements.
  if (dictionary.requires_slow_elements()) return false;

  // Adding a property with this index will require slow elements.
  if (index >= static_cast<uint32_t>(Smi::kMaxValue)) return false;

  if (object.IsJSArray()) {
    Object length = JSArray::cast(object).length();
    if (!length.IsSmi()) return false;
    *new_capacity = static_cast<uint32_t>(Smi::ToInt(length));
  } else if (object.IsJSArgumentsObject()) {
    return false;
  } else {
    *new_capacity = dictionary.max_number_key() + 1;
  }
  *new_capacity = std::max(index + 1, *new_capacity);

  uint32_t dictionary_size = static_cast<uint32_t>(dictionary.Capacity()) *
                             NumberDictionary::kEntrySize;

  // 看這里??， 當慢陣列轉換成快陣列能節省 不少于 50% 的空間時，才會將其轉換
  // Turn fast if the dictionary only saves 50% space.
  return 2 * dictionary_size >= *new_capacity;
}

(2)、分析

元素能存放在快陣列中并且長度不在smi之間（64位-2^31到232-1），并且當前慢陣列空間相比快陣列節省值小于等于50%，則轉變成為快陣列，

快慢轉換總結

快陣列就是以空間換時間的方式，申請了大塊連續記憶體，提高了執行效率，
慢陣列以時間換空間，不必申請連續的空間，節省了記憶體，但需要付出效率變差的代價，

3、動態擴容與收縮

3.1、擴容

看下原始碼??

path:v8/src/objects/js-array.h

空陣列預分配的大小: 4

// path:v8/src/objects/js-array.h

// Dispatched behavior.
DECL_PRINTER(JSArray)
DECL_VERIFIER(JSArray)

// Number of element slots to pre-allocate for an empty array.
// 空陣列預分配的大小為4
static const int kPreallocatedArrayElements = 4;

static const int kLengthDescriptorIndex = 0;

上面代碼表明，當宣告一個空陣列時，已預分配好 4 個位元組的存盤空間，

所以 [] 與 [1, 2, 3, 4] 占用一樣多的記憶體，前面說過，JSArray 繼承自 JSObject，我們可以在 js-objects.h 中找到如下代碼：

path:v8/src/objects/js-objects.h

擴容公式

// path:v8/src/objects/js-objects.h

// line:551??
static const uint32_t kMinAddedElementsCapacity = 16;

// Computes the new capacity when expanding the elements of a JSObject.
static uint32_t NewElementsCapacity(uint32_t old_capacity) {
  // (old_capacity + 50%) + kMinAddedElementsCapacity
  // 擴容公式:原有記憶體容量（1.5倍）+ 16
  return old_capacity + (old_capacity >> 1) + kMinAddedElementsCapacity;
}

這是對 JSObject elements 擴容和對 JSArray 擴容的通用方法，擴容后容量的計算邏輯是：在原占用空間 old_capacity 的基礎上增加一半（old_capacity >> 1 右移 1 位表示除 2，再相加得原空間 1.5 倍），再加上 16，

舉例：

const arr = [1, 2, 3, 4];
arr.push(5);
%DebugPrint(arr);

arr.push 之前：
arr.push 后：

具體分析如下：
??

向陣列 [1, 2, 3, 4] push 5 時，首先判斷到當前容量已滿，需要計算新容量，
old_capacity = 4，new_capacity = 4 + 4 >> 1 + 16 = 22，得出 [1, 2, 3, 4, 5] 的容量為 22 個位元組，
V8 向作業系統申請一塊連續大小為 22 位元組的記憶體空間，隨后將老資料一一 copy，再新將新增元素寫入，

3.2 縮容

緊接著，我們在 src/objects/elements.cc 中找到 SetLengthImpl 方法中的如下代碼：

// path:src/objects/elements.cc

// line:750
if (2 * length + JSObject::kMinAddedElementsCapacity <= capacity) {
  // If more than half the elements won't be used, trim the array.
  // Do not trim from short arrays to prevent frequent trimming on
  // repeated pop operations.
  // Leave some space to allow for subsequent push operations.
  int elements_to_trim = length + 1 == old_length
                             ? (capacity - length) / 2
                             : capacity - length;
  isolate->heap()->RightTrimFixedArray(*backing_store, elements_to_trim);
  // Fill the non-trimmed elements with holes.
  BackingStore::cast(*backing_store)
      .FillWithHoles(length,
                     std::min(old_length, capacity - elements_to_trim));
} else {
  // Otherwise, fill the unused tail with holes.
  BackingStore::cast(*backing_store).FillWithHoles(length, old_length);
}

當陣列元素減少（如 pop）后，如果陣列容量大于等于 length 的 2 倍，則進行容量調整，使用 RightTrimFixedArray 函式，計算出需要釋放的空間大小，做好標記，等待 GC 回收；如果陣列容量小于 length 的 2 倍，則用 holes 物件填充，

總結：

陣列元素少的時候是線性結構存盤（FixedArray）的，記憶體地址連續，查找速度快，可以動態擴縮容；
陣列元素多的時候轉化為慢陣列，通過創建了一個字典來記錄映射關系，記憶體不連續，通過大名鼎鼎的Object.defineProperty(object, key, descriptor)創建

js的陣列看似不同，其實只是V8 在底層實作上做了一層封裝，使用兩種資料結構實作陣列，并且通過時間和空間2個緯度的取舍，優化了陣列的性能，

參考學習博客

??????

?? 關注我，你會發現一個踏實努力的寶藏前端??，讓我們一起學習，共同成長吧，

?? 喜歡的小伙伴記得點贊關注收藏喲，回看不迷路 ??

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/500845.html

標籤：其他

上一篇：BOM的概述及方法

下一篇：SASS 運算 (Operations)符的基本使用

V8中的快慢陣列（附原始碼、圖文更易理解😃）

1、全填充 or 帶孔

2、快慢陣列

為什么陣列也是物件型別的？

2.1、快陣列何時轉換為慢陣列

(1)、看一下原始碼先??

(2)、分析

2.2、慢陣列何時轉換為快陣列

(1)、看一下原始碼先??

(2)、分析

快慢轉換總結

3、動態擴容與收縮

3.1、擴容

3.2 縮容

總結：