栈和队列(V8数组底层实现)

[chris-paul]

栈

栈是一种先进后出的数据结构,而队列是一种先进先出的数据结构,在JS中数组即是栈又是队列

数组

一种最基础的数据结构，每种编程语言都有，它编号从 0 开始，代表一组连续的储存结构，用来储存同一种类型的数据

它的这种特定的存储结构（连续存储空间存储同一类型数据）决定了:

优点

• 随机访问：可以通过下标随机访问数组中的任意位置上的数据,根据下标随机访问的时间复杂度为 O(1)

缺点

• 对数据的删除和插入不是很友好, 时间复杂度为 O(n)

JavaScript 数组的内存占用

FixedArray的内存占用大小为length * kPointerSize,64位的操作系统上，一个指针为8个字节，所以一个长度是1的数组它的大小将是8个字节

var arr = new Array(1000);
// 不会为1000个元素申请内存空间, 不会输出
arr.forEach((item)=>{console.info(item)});

var arr2 = [undefined, undefined];
// 输入两个undefined
arr2.forEach((item)=>{console.info(item)})

JavaScript 中，数组可以保存不同类型值

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

JSArray 继承于 JSObject ，也就是说JS数组就是一个对象,底层就是个 Map ，key 为0，1，2，3这种索引，value 就是数组的元素,数组的index其实是字符串,从注释上看，它有两种存储方式：

• fast：存储结构是 FixedArray ，并且数组长度 <= elements.length() ，push 或 pop 时可能会伴随着动态扩容或减容

• slow：存储结构是 HashTable（哈希表），并且数组下标作为 key

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

1、压紧的（Packed）

例如 ['a', 'b', 'c'] 这样的数组长度为3，数组索引0、1、2均有值，那么就认为是Packed

** 2、有洞的（Holey）**

对于 ['a',,,'d'] 这样的数组，长度为4，但是索引1、2位置并没有进行初始化赋值，那么就认为是Holey。当数组出现了较大空洞的时候，内存明显是被浪费了。

3、快数组（FastElements)

FixedArray 是 V8 实现的一个类似于数组的类，它表示一段连续的内存，可以使用索引直接定位。新创建的空数组默认就是快数组。当数组满（数组的长度达到数组在内存中申请的内存容量最大值）的时候，继续 push 时， JSArray 会进行动态的扩容，以存储更多的元素

所有的数组初始化的时候默认都是快数组模式

4、慢数组（SlowElements

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

3、什么时候会从 fast 转变为 slow

// 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;
  // NewElementsCapacity就是进行扩容
  *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;
  }
  // GetFastElementsUsage 来获取原来的数组中非空洞的元素数量乘以 kPreferFastElementsSizeFactor(值为3) 与 kEntrySize (值为2),与新的容量长度进行对比，如果小于新的容量长度，那么就转换为慢数组
  return ShouldConvertToSlowElements(object.GetFastElementsUsage(),*new_capacity);
}

所以，当处于以下情况时，快数组在扩容之后会被转变为慢数组：

• 当加入的索引值 index 比当前容量 capacity 差值大于等于 1024 时（index - capacity >= 1024）

• 快数组新容量是扩容后的容量 3 倍之多时

• 扩容之后的非空洞元素数量 * kPreferFastElementsSizeFactor * kEntrySize 小于新容量的大小的时候

// 从上面的代码可以看到，当设置 99998 的时候，索引小于当前容量的时候，返回值为false
const a = new Array(99999);
a[99998] = undefined;
// 当设置 99999 这个索引的值的时候，因为超出了原来的FixedArray容量，那么就会进行扩容,扩容的算法（v8/src/objects/js-objects.h#L540）为容量 + 容量 /2 + 16，那么原来 99999 的容量就会扩容放大到 15万,然后会执行 GetFastElementsUsage 来获取原来的数组中非空洞,乘以 kPreferFastElementsSizeFactor(值为3) 与 kEntrySize (值为2) ，与新的容量长度进行对比，如果小于新的容量长度，那么就转换为慢数组
// 下面的代码非空洞元素数量为0，计算后的乘积也为0，因此小于15万的新数组长度，于是数组转换为了慢数组，使用了Dictionary进行数据的存储，从而节省了大量的内存
const b = new Array(99999);
b[99999] = undefined;

4、什么时候会从 slow 转变为 fast

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();
    // smi在64位平台为 -2^31到2^31 -1,  在32位平台为-2^30到2^30 -1,如果数组长度不在smi之间则不转换
    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;
}

所以，当处于以下情况时，快数组会被转变为慢数组：

• 如果数组长度在smi之间并且慢数组比快数组节省 50% 的空间则进行转换

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

JavaScript 中，数组的动态扩容与减容（FastElements）

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

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

判断是否进行扩容
在 JavaScript 中，当数组执行 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

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

• push 操作时，发现数组内存不足

• 申请 new_capacity = old_capacity /2 + old_capacity + 16 那么长度的内存空间

• 将数组拷贝到新内存中

• 把新元素放在当前 length 位置

• 数组的 length + 1

• 返回 length

判断是否进行减容

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 对象填充

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

• pop 操作时，获取数组 length

• 获取 length - 1 上的元素（要删除的元素）

• 数组 length - 1

• 判断数组的总容量是否大于等于 length - 1 的 2 倍
  是的话，使用 RightTrimFixedArray 函数，计算出需要释放的空间大小，并做好标记，等待 GC 回收
  不是的话，用 holes

参考文章

从V8源码分析一个JS 数组的内存占用问题

从Chrome V8源码看JavaScript