站在V8角度看js-array

起源

前两天激情群聊的时候，群友们聊到了js数组是动态的这个话题，然后越聊越深，问题越来越多。后来我查了资料之后，确实又学到了好多东西，在此做一个汇总。所以今天文章的主题是：V8中js数组的实现和各种机制。

调试环境

• node 16.x
• jsvu（不用拉V8源码进行编译，装上配置好即可调试），使用可以参考这篇文章

基本环境准备好之后，就可以开始调试了

前置概念

我们先从概念入手，简单了解一下为什么js的数组会比较特殊。以下是维基百科对数组的定义：

在计算机科学中，数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。

对于熟悉C语言的同学来说，这个概念并不陌生，因为数据类型相同，系统可以为其分配连续的一段内存空间进行存储，而且长度已知，但是js的数组并不是这样的：

let arr = ["ikun", false, {
    sing: true,
    jump: true,
    basketball: true
}]

这样结构的数组结构在js里面也是允许的。接下来就从V8的角度开始探索js-array吧。

快慢数组

在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 TorqueGeneratedJSArray<JSArray, JSObject> {}

在早一点的版本中，是这样定义的

class JSArray : public JSObject {}

也就是说在JS中，数组是一个特殊的对象，这也就解释了为什么数组可以存放不同的数据类型的元素这个问题了，我们可以用上面的例子试一下：

从图中可以看到，最终的存储结构就是一个map，这里有一个小知识点：在底层存储中，我们所说的index其实是字符串

接下来再看看数组的两种存在形式：存储结构为FixedArray的快数组和底层存储结构为Dictionary(再往底层一点是HashTable)的慢数组，这两种形式的定义会在下文中看到。

再有一点就是： 初始化的一个数组是一个FixedArray，也就是快数组，当数组在扩容/收缩达到一定条件的时候，会发生快慢数组的转换。

快数组

快数组的处理和普通数组基本一样，这里的定义也不过多说明了

来个例子吧：

接下来分析一下上图：

• 数据类型为FixedArray：这一点符合要求，因为没有对其进行能让他达到转换成慢数组的某些操作
• 数据的偏移量：这里可以看到，对于数组里面的三个元素，它们的地址差值（偏移量）是相等的，都为0x38，这也说明了是存在于连续的内存空间中，但是这里我有两个疑问，也请各位大佬指点一下：
  1. 这里的偏移量虽然相等，但是如果我let c = [{a: 1}, {b: 2}, {c: 3}]，偏移量不为0x38，但是偏移量相等，也许是和数据类型/内容有关
  2. 这里打印出来的地址，是否是左边为指向内存中function的指针的地址，右边为真正function所在的地址

Hole

hole译为空洞，指的是当一个数组中某些元素有索引，但是没有对应的值的情况，比如：

可以看到，在a中索引为1的元素就是一个hole，b中所有元素均为hole，而对应的模式是HOLEY_SMI_ELEMENTS(简称holey模式)。

holey模式会给未赋值的索引一个特殊的值，用于访问的时候得到undefined，而holey模式同样是分配连续的内存空间，也就是说：快数组才会存在空洞的情况

扩容

首先看看V8中扩容机制的实现方法：

// v8/src/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);
}

// v8/src/objects/js-objects.h  
// Computes the new capacity when expanding the elements of a JSObject. 
// 计算扩充后的容量，新容量 = 原容量 + 原容量/2 + 16 -> 新容量 = 老容量 * 1.5 + 16
// 这里的16就是16个字节，也就是1位16进制
static uint32_t NewElementsCapacity(uint32_t old_capacity) {
    return old_capacity + (old_capacity >> 1) + kMinAddedElementsCapacity;
}

而扩容（数组push,unshift等操作）的时候，实际上是将原本的数据copy一份，寻找一段新的内存空间进行存放（因为原本连续的空间或许在扩容后的长度之内不能连续）：

// v8/src/code-stub-assembler.cc
Node* new_elements = AllocateFixedArray(to_kind, new_capacity, mode);
// Copy the elements from the old elements store to the new.
// The size-check above guarantees that the |new_elements| is allocated
// in new space so we can skip the write barrier.
CopyFixedArrayElements(from_kind, elements, to_kind, new_elements, capacity,
                     new_capacity, SKIP_WRITE_BARRIER, mode);
StoreObjectField(object, JSObject::kElementsOffset, new_elements);

以下是结合自己理解画的一个拷贝扩容的图：

收缩

收缩的实现如下：

// v8/src/elements.cc  783
// 如果容量大于等于 length * 2 + 16，则进行收缩容量调整
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.
    
    //收缩后的大小由现在的length + 1与原本的length判断得出是全部收缩还是只需要收缩1/2
    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.
    // 收缩之后的空白位置用hole填充
    BackingStore::cast(*backing_store)->FillWithHoles(length, old_length);
}

慢数组

老规矩，直接看定义：

这里慢数组没有什么好说的，就是一个以HashTable为基础的Dictionary，也正是因为HashTable，慢数组不会开辟大量的连续空间，但是查询效率会相对较低，这也是一种时间换空间的行为。

快慢数组的转换

讲完了快慢数组和扩容、收缩机制，接下来看看快慢数组之间是如何转换的吧。 首先在源码里js-objects和dictionary里面可以看到这样的两个常量定义：

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

// src/objects/dictionary.h
static const uint32_t kPreferFastElementsSizeFactor = 3;

翻译一下可以知道：kMaxGap表示一个最大的差值，kPreferFastElementsSizeFactor则表示选择快数组的一个范围，也可以理解为一个倍数，这两个常量会被应用到接下来的转换中。

快数组->慢数组

接下来结合源码进行一波分析：

static inline bool ShouldConvertToSlowElements(uint32_t used_elements,
                                               uint32_t new_capacity) {
  uint32_t size_threshold = NumberDictionary::kPreferFastElementsSizeFactor *
                            NumberDictionary::ComputeCapacity(used_elements) *
                            NumberDictionary::kEntrySize;//kEntrySize == 3
                            //3 * 扩容后的容量 * 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;
  }
  if (index - capacity >= JSObject::kMaxGap) return true;// 新增的索引与之前的最大索引值的差值大于1024
  *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);
}

可以看到扩容有两种条件：

1. 当3 * 原本的容量 * 3 >= 扩容后的容量，会转换为慢数组，因为慢数组的存储空间上是有优势的。
2. 当新增的索引与之前的最大索引值的差值大于1024时，意味着有至少1024个hole，这个时候也需要转换为慢数组

接下来看看具体的验证吧

第一种情况因为一直计算，不好截图结果，大家可以自己试一试

我们着重看看第二种情况的验证：

我们可以看到，初始化数组的length为2，但是当在1030位置放了一个值之后，数组的索引差值为1027，这个值是大于kMaxGap的，于是这个时候快数组已经转换成了慢数组。

慢数组->快数组

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->IsJSSloppyArgumentsObject()) {
    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;
}

// v8/src/objects/smi.h  
static constexpr int kMaxValue = kSmiMaxValue;

// v8/include/v8-internal.h  
static constexpr intptr_t kSmiMaxValue = -(kSmiMinValue + 1);

慢数组的条件只有代码里注释重点的地方，如果新的容量 <= 原本容量的1/2，那么这个时候会转换成快数组，源码里也写了原因：当前慢数组相对于快数组如果只节省了少于50%的内存容量，那么转换成快数组

还是基于上一个例子，给其填上一些hole，看看结果：

可以看到，给a填上了100个空洞之后，elements kind已经变成了HOLEY_SMI_ELEMENTS，这说明之前转成慢数组的a已经转回了快数组

总结

今天讲了快慢数组的概念和相互之间的转换，还有hole机制以及扩容/收缩机制。 希望有大佬回答一下我在快慢数组中提到的关于偏移量的问题。 如有错误，欢迎指正，感谢阅读。

参考资料

zhuanlan.zhihu.com/p/371236424

v8.dev/blog/fast-p…

github.com/v8/v8/blob/…