V8 引擎数组的底层实现

思考

JS 数组为什么可以保存不同类型的值？

JS 数组是如何存储的？

其它语言例如 C，创建时要决定数组的大小，如果数组满了还要重新申请内存空间，而 JS 数组却可以动态增长，JS 数组的动态扩容与减容是怎么做到的？

一、JS 数组保存不同类型值

Chrome v8 对应源码如下：

// 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;
};

可以看到，Chrome V8 源码中 JSArray 继承自 JSObject，这意味着 JS 中数组是一个特殊的对象，内部能以键值对的形式存储数据，所以 JS 中数组可以存放不同类型的值。

二、JS 数组的存储

JSArray 继承于 JSObject，根据上面代码的注释，它有两种存储方式：

• fast：存储结构是 FixedArray，并且数组长度 <= elements.length()，push 或 pop 时可能会伴随着动态扩容或减容；
• slow：存储结构是 HashTable（哈希表），并且数组下标作为 key

fast 模式下数组在源码里面叫 FastElements，而 slow 模式下的叫做 SlowElements

1、快数组（FastElements）

FixedArray 是 V8 实现的一个类似于数组的类，表示一段连续的内存，可以使用索引直接定位。新创建的空数组默认就是快数组。当数组填满时，如果继续 push，JSArray 会进行动态扩容，以存储更多的元素。

2、慢数组（SlowElements）

慢数组以哈希表的形式存储在内存空间里，它不需要开辟连续的存储空间，但需要额外维护一个哈希表，与快数组相比，性能相对较差。

// src/objects/dictionary.h
class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Dictionary
    : public HashTable<Derived, Shape> {
  using DerivedHashTable = HashTable<Derived, Shape>;

  public:
    using Key = typename Shape::Key;
    // Returns the value at entry.
    inline Object ValueAt(InternalIndex entry);
    inline Object ValueAt(const Isolate* isolate, InternalIndex entry);
  
  // ...
};

从源码中可以看出，慢数组的内部就是一个 HashTable。

3、快数组转慢数组

Chrome V8 对应源码如下：

// src/objects/js-objects.h
static const uint32_t kMaxGap = 1024;

// src/objects/dictionary.h
// JSObjects prefer dictionary elements if the dictionary saves this much
// memory compared to a fast elements backing store.
static const uint32_t kPreferFastElementsSizeFactor = 3;

// 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;
  // 快数组新容量是扩容后的容量 3 倍之多时，也会被转成慢数组
  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;
  }
  // 当加入的索引值（例如例 3 中的 2000）比当前容量 capacity ≥ 1024 时，
  // 返回 true，转为慢数组
  if (index - capacity >= JSObject::kMaxGap) return true;
  *new_capacity = JSObject::NewElementsCapacity(index + 1);
  DCHECK_LT(index, *new_capacity);
  // TODO(ulan): Check if it works with young large objects.
  if (*new_capacity <= JSObject::kMaxUncheckedOldFastElementsLength ||
      (*new_capacity <= JSObject::kMaxUncheckedFastElementsLength &&
       ObjectInYoungGeneration(object))) {
    return false;
  }
  return ShouldConvertToSlowElements(object.GetFastElementsUsage(),
                                     *new_capacity);
}

可以看到，快数组会被转为慢数组的情况有：

• 当加入的索引值 index 比当前容量 capacity 差值 ≥ 1024 时（index - capacity >= 1024）
• 快数组新容量是扩容后的容量 3 倍之多时。

例如：向快数组里增加一个大索引同类型值：

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

当往 arr 增加一个 2000 的索引时，arr 被转成慢数组。节省了大量的内存空间（从索引为 2 到索引为 2000）

4、慢数组转快数组

Chrome V8 对应源码如下：

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 = Max(index + 1, *new_capacity);
  uint32_t dictionary_size = static_cast<uint32_t>(dictionary.Capacity()) *
                             NumberDictionary::kEntrySize;
  // Turn fast if the dictionary only saves 50% space.
  return 2 * dictionary_size >= *new_capacity;
}

可以看到，快数组节省仅为 50％ 的空间时，就转为慢数组（Dictionary）

三、JS 数组的动态扩容与减容

默认空数组初始化大小为 4 :

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

1、动态扩容

JS 中数组执行 push 操作时，一旦发现数组内存不足，将进行扩容。

在 Chrome 源码中，push 的操作是用汇编实现的，在 c++ 里嵌入汇编以提高执行效率，并且在汇编的基础上用 c++ 封装了一层，在编译执行时，会将这些 c++ 代码转成汇编代码。

计算新容量的函数：

// js-objects.h
static const uint32_t kMinAddedElementsCapacity = 16;

// code-stub-assembler.cc
Node* CodeStubAssembler::CalculateNewElementsCapacity(Node* old_capacity,
                                                      ParameterMode mode) {
  CSA_SLOW_ASSERT(this, MatchesParameterMode(old_capacity, mode));
  Node* half_old_capacity = WordOrSmiShr(old_capacity, 1, mode);
  Node* new_capacity = IntPtrOrSmiAdd(half_old_capacity, old_capacity, mode);
  Node* padding =
      IntPtrOrSmiConstant(JSObject::kMinAddedElementsCapacity, 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

接着申请一块这么大的内存，把老的数据拷过去，把新元素放在当前 length 位置，然后将数组的 length + 1，并返回 length。

所以，扩容可以分为以下几步：

1. push 操作时，发现数组内存不足；
2. 申请 new_capacity = old_capacity / 2 + old_capacity + 16 长度的内存空间；
3. 将数组拷贝到新内存中；
4. 把新元素放在当前 length 位置；
5. 数组的 length + 1；
6. 返回 length。

整个过程，开发者是无感知的，不像 C 需要开发者手动申请内存空间。

2、动态减容

当数组执行 pop 操作时，会判断 pop 后数组的容量，是否需要进行减容。

不同于数组的 push 使用汇编实现的，pop 是使用 c++ 实现的。

判断是否进行减容如下：

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);
}

当数组 pop 后，如果数组容量 ≥ length 的 2 倍，则进行容量调整，使用 RightTrimFixedArray 函数，计算出要释放的空间大小，做好标记，等待 GC 回收；如果数组容量小于 length 的 2 倍，则用 holes 对象填充。

所以，减容可以分为以下几步：

1. pop 操作时，获取数组 length；
2. 获取 length - 1 上的元素（要删除的元素）
3. 数组 length - 1；
4. 判断数组的总容量是否 ≥ length - 1 的 2 倍；是的话，使用 RightTrimFixedArray 函数计算出要释放的空间大小，并做好标记，等待 GC 回收；不是的话则用 holes 对象填充；
5. 最后返回要删除的元素。

四、总结

V8 引擎源码中，JSArray 继承自 JSObject，这意味着 JS 中数组是一个特殊的对象，内部能以键值对的形式存储数据，所以 JS 中数组可以存放不同类型的值。

JS 数组包括快数组和慢数组两种存储方式，快数组即以空间换时间，申请大块连续内存，以提高效率；而慢数组则以时间换空间，以 HashTable 哈希表的方式存储数据，不必申请连续的空间，虽然节约内存但性能不如快数组。JS 会根据合理使用内存的原则来决定使用哪种数组。

JS 的动态扩容在数组容量不足时进行，先进行内存空间的申请，然后把原数组拷贝到新内存中，在当前 length 的位置开始存放新元素，最后将 length 的值加一；而 JS 的动态减容在数组容量过多时进行，先计算出要释放的空间大小，并做好标记，然后等待垃圾回收机制回收。