接上一篇 V8 中的快慢属性，本篇分析 V8 中的快慢数组，了解数组全填充还是带孔、快慢数组、快慢转化、动态扩缩容等等。其实很多语言底层都采用类似的处理方式，比如：Golang 中切片的 append 操作就涉及扩容处理。
🎁 D8 调试工具使用请来这里
1、全填充 or 带孔
通过一个小李子，看一下什么是全填充数组(Paked-Array)，什么是带孔数组(Holey-Array)
前面还写了稀疏数组，稀疏数组更加具有业务应用性，清洗的是无意义的数据，可以对比带孔数组来分析一下，有兴趣请看👉 稀疏数组——实现五子棋存盘和续上盘功能
const o = ['a', 'b', 'c']console.log(o[1]) // 'b'
delete o[1]console.log(o[1]) // undefinedo.__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 源码中清晰地表明，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.// staticstatic 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)、分析
所以，前面的例子：
const arr = [1, 2, 3];arr[1999] = 1999;%DebugPrint(arr);
复制代码
1999 - 2 > 1024，arr 从快数组转换为哈希形式存储的慢数组。
下面看一下详细运行信息👇
2.2、慢数组何时转换为快数组
(1)、看一下源码先👇
path:v8/src/objects/js-objects.cc
// path:v8/src/objects/js-objects.cc
// line:4932static 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 到 2^32-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.// 空数组预分配的大小为4static 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);
复制代码
具体分析如下：👇
向数组 [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:750if (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 个纬度的取舍，优化了数组的性能。
我是 甜点 cc，个人网站(国外站点): https://blog.i-xiao.space/
回头看，轻舟已过万重山；向前看，前路漫漫亦灿灿。
公众号：【看见另一种可能】
评论