深入V8-JS数组在内存中如何存储

问题的来源

在刷算法题的过程中，常常用到数组，数组的定义为：

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

我们知道C++中的数组在内存中是连续存储的，且数组元素类型相同，这与上述数组的定义是一致的。但对于JS中的数组而言也是如此吗？

JS的数组元素可以是任何类型的，且长度可以任意更改

const a = [1,'str',true,{}];
console.log(a.length);   // 4

a.push(2);
console.log(a.length);   // 5 

那么问题来了

1. JS的数组元素大小不一，能够都放在大小一致的内存单元中吗？如果各个元素占用的内存单元不一致，那也就无法通过索引来计算出元素所处的内存地址了
2. JS的数组长度可任意更改，对于已分配好连续内存空间的数组来说，任意往数组里添加元素，那么如何保证后面添加的元素能分配到这块内存中呢？

似乎JS的数组在内存中是连续存储的这个命题并不是很科学

从V8看数组

引出了以上几个问题，我们就要认识下JS中的数组了

V8中的快慢属性

function Foo() {
  this[100] = 'test-100'
  this[1] = 'test-1'
  this["B"] = 'foo-B'
  this[50] = 'test-50'
  this[9] = 'test-9'
  this[8] = 'test-8'
  this[3] = 'test-3'
  this[5] = 'test-5'
  this["A"] = 'foo-A'
  this["C"] = 'foo-C'
}

const foo = new Foo()

for (const key in foo) {
  console.log(`key:${key}, value:${foo[key]}`)
}
// key:1, value:test-1
// key:3, value:test-3
// key:5, value:test-5
// key:8, value:test-8
// key:9, value:test-9
// key:50, value:test-50
// key:100, value:test-100
// key:B, value:foo-B
// key:A, value:foo-A
// key:C, value:foo-C

我们创建一个Foo的实例foo，然后遍历该实例的键，可以发现遍历的顺序与我设置的顺序并不一致，数字属性在前，非数组属性在后。且数字类型的键按其大小顺序遍历，非数字类型的键按其设置顺序遍历。

在V8中，前者被称索引属性，后者被称为命名属性，在遍历时会先遍历前者。两者在内存中分别存储在不同的地方，由对象中的两个指针指向它们，分别是elements 和 properties，如下图：

之所以要存储在两个数据结构中，是为了在不同情况下都能做到更高效的增删改查操作。

观察内存快照，发现对象中并没有properties，这是因为V8中的策略，当命名属性小于等于10 个时，命名属性保存为对象内属性，即与elements 和 properties处在同一层级，这样做的好处是可以直接访问这些命名属性不要再去访问properties对象，从而提升了属性查找的效率。

为了验证这个说法，执行以下代码，并打出内存快照，共12个命名属性，多出来的两个存储在了properties中。

function Foo(elements, properties) {
  for (let i = 0; i < properties; i++) {
    this[`property${i}`] = `property${i}`;
  }
  for (let i = 0; i < elements; i++) {
    this[i] = `element${i}`;
  }
}

const foo = new Foo(12, 12);

快数组与慢数组

const arr = new Array(100); // 快数组
arr[arr.length + 1026] = 1; // 快数组转为慢数组

在这个例子中，第1行定义了一个长度100的空数组，第二行在arr.length+1026处的值改为1，如果V8将连续内存扩容到arr.length+1026，那么这个操作让arr成为一个稀疏数组，这样会使数组占用大量且无效的内存空间，造成内存的浪费！

为了避免这种情况，V8将该数组转化为慢数组：创建一个字典来保存每个属性的键、值、描述符的三元组，这个过程是通过Object.defineProperty()来实现的，而使用该api在V8中创建的正是慢属性，对应到数组中就是慢数组。

那么什么情况下V8会将快数组转为慢数组？转换的规则是什么？

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

// 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> {
public:
// [length]: The length property.
DECL_ACCESSORS(length, Tagged<Object>)
DECL_RELAXED_GETTER(length, Tagged<Object>)
// ...
}

在V8源码中可以看到，JS数组有两种模式：

1. Fast模式的存储结构为 FixedArray，并且长度小于等于elements.length，pop和push操作可以用来扩容和收缩数组。
2. Slow模式的存储结构为 HashTable 也就是哈希表，这个HashTable的键为数字类型。

快数组 FixedArray

1. FixedArray是V8实现的一个类似数组的类，在内存中开辟一块连续的内存空间，可以实现随机访问，新创建的空数组默认是快数组。
2. 快数组的长度是可变的，可以通过动态删除和添加元素来调整内存大小，内部通过扩容和收缩机制实现。

扩容机制

// v8/src/objects/js-array.h
// Number of element slots to pre-allocate for an empty array.
// 声明一个新的空数组时，会预分配长度为4的内存空间
static const int kPreallocatedArrayElements = 4;


// v8/src/objects/js-objects.h
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
    // 扩容公式：old_capacity*1.5 + 16
    return old_capacity + (old_capacity >> 1) + kMinAddedElementsCapacity;
}

声明的空数组预分配大小为4的内存空间，当执行添加元素的操作时，若数组内存不够则将对数组内存进行扩容，扩容公式为：new_capacity = old_capacity * 1.5 +16，即原容量的1.5倍加16。然后将数组内容拷贝到新分配的连续内存空间，然后length+1。

例如当前长度为4的数组，其扩容后所占用的内存单元应为4*1.5+16=22个，我们可以试一试：

function A() {
  this.arr = new Array(4).fill(1);
}
const a = new A();

先声明一个长度为4，用1填充的数组，然后打一个内存快照，可以看到该数组占用24字节的内存空间：4*4+8=224

数组的elements的大小=元素个数*元素大小 +8。对于整型数组来说，其大小为4字节

在JS中非浮点数的数据类型占4字节，浮点数数据类型占8字节

然后对数组进行添加元素的操作：

function A() {
  this.arr = new Array(4).fill(1);
}
const a = new A();
a.arr.push(1);

此时由于原数组已满，添加元素会导致数组扩容，打个内存快照，可以看到这时数组占用100字节的内存空间，让我们来计算一下：扩容后的数组所占内存单元为4*1.5+16=22个，字节数为22*4+8=96。

快照中字节数为100，说明数组实际上扩容到了23个内存单元！但按照v8源码的公式计算应是22个内存单元，这里不太清楚原因。

收缩机制

// v8/src/objects/elements.cc

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.
    uint32_t new_capacity =
    length + 1 == old_length ? (capacity + length) / 2 : length;
    DCHECK_LT(new_capacity, capacity);
    isolate->heap()->RightTrimArray(BackingStore::cast(*backing_store),
        new_capacity, capacity);
    // Fill the non-trimmed elements with holes.
    BackingStore::cast(*backing_store)
        ->FillWithHoles(length, std::min(old_length, new_capacity));
} 

当对数组执行pop操作后，如果数组的length*2+16小于等于内存单元个数capacity，那么会对数组占用的内存进行减容，减容机制是根据length+1和old_length来判断是减容一半还是全部减容。

慢数组 HashTable

const arr = [1, 2, 3]
arr[1999] = 1999
// arr 会如何存储？

在这个例子中，arr由快数组转为慢数组，其底层的存储结构也由FixedArray变为HashTable。

快数组转化为慢数组

那么快数组什么情况下会被转化为慢数组？

// v8/src/objects/dictionary.h

static const uint32_t kPreferFastElementsSizeFactor = 3;

class NameDictionaryShape : public BaseNameDictionaryShape {
 public:
  static const int kPrefixSize = 3;
  static const int kEntrySize = 3;
  static const bool kMatchNeedsHoleCheck = false;
};

// 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(Tagged<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);
}

快数组向慢数组的转换往往发生在数组扩容的时候：

1. 扩容后的非孔洞元素数量的9倍小于等于扩容后数组占用的内存的时候，快数组转为慢数组
2. 新加入元素的索引与当前数组占用的内存单元个数之差大于等于1024时

总之，快数组是否要转化为慢数组的底层逻辑是根据分配给数组的内存空间有多少被浪费来决定的。

慢数组转化为快数组

• 当慢数组占用的内存空间大于等于快数组占用的内存空间的**50%**时，慢数组转化为快数组。

let a = [1,2];
// 在 1030 的位置上面添加一个值，会造成多于1024个孔洞，数组会使用为Slow模式来实现
a[1030] = 1;
// 往 200-1029 这些位置上赋值填补空洞，此时快数组占用空间1030 * 4, 慢数组占用空间 829 * 4,
// 慢数组不再比快数组节省 50% 的空间,此时转换为快数组
for (let i = 200; i < 1030; i++) {
    a[i] = i;
}

总结

在V8的源码可以很清楚的看到，js-Array类是继承自js-Object类的，这印证了js数组就是个对象，js数组的数字索引说白了也是对象的一种键，被称为快属性；而慢属性也就是命名属性，比如Object.defineProperty()所定义的就是慢属性。

现在就可以回答文章开头的问题了，JS的数组分为Fast模式和Slow模式，且两者可以根据需要动态地相互转换。

• Fast模式也称为快数组，快数组的存储结构是连续的内存块（可以扩容和收缩），可实现随机访问，效率较高。
• Slow模式也称为慢数组，慢数组的存储结构是HashTable，慢数组存在的意义是能够实现数组元素不同类，且解决快数组在孔洞较多时造成的内存浪费问题。由于需要计算Hash值并维护HashTable，慢数组的访问效率自然比不上快数组。