接上一篇掘金 V8 中的快慢属性
  
  
  
  
  
  
  ，本篇分析V8 中的快慢数组  
  
  
  
  
  
  
，了解数组全填充还是带孔
  
  
  
  
  
  
  、快慢数组  
  
  
  
  
  
  
、快慢转化
 


 


 


 


 


 


 

、动态扩缩容等等              。其实很多语言底层都采用类似的处理方式
 


 


 


 


 


 


 

，比如：Golang中切片的append操作就涉及扩容处理
  
 
  
 
  
 
  
 
  
 
  
 
  
 。

? D8调试工具使用请来掘金 D8调试工具——jsvu的使用细则

1
 
 
 
 
 
 
 、全填充 or 带孔

通过一个小李子
 
 
 
 
 
 
 ，看一下什么是全填充数组(Paked-Array)   
   
   
   
   
   
   
，什么是带孔数组(Holey-Array)

前面还写了稀疏数组
 

 

 

 

 

 

 
，稀疏数组更加具有业务应用性

 

 

 

 

 

 

 ，清洗的是无意义的数据              ，可以对比带孔数组来分析一下
 
 

 
 

 
 

 
 

 
 

 
 

 
 
，有兴趣请看掘金? 稀疏数组——实现五子棋存盘和续上盘功能

const o = [a, b, c] console.log(o[1]) // b delete o[1] console.log(o[1]) // undefined o.__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 里一个叫FixedArray的类













，它在内存中是连续的空间
  
  
  
  
  
  
  ，直接通过索引读写值  
  
  
  
  
  
  
，非常快              。如果有 push 或 pop 操作
 


 


 


 


 


 


 

，它会动态地扩容或收缩

 
 

 
 

 
 

 
 

 
 

 
 

 
 。

慢模式：如前文所介绍
 
 
 
 
 
 
 ，V8 创建了一个字典（HashTable）来记录映射关系   
   
   
   
   
   
   
，其中索引的整数值即是字典的键













。

为什么数组也是对象类型的？

在 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. // 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(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)              、分析

如果快数组扩容后的容量是原来的3 倍以上













，意味着它比HashTable形式存储占用更大的内存                     ，快数组会转换为慢数组

如果快数组新增的索引与原来最大索引的差值大于 1024 
 
 
 
 
 
 
 
 
 
 
 
 
 
，快数组会被转换会慢数组

所以




















，前面的例子：

const arr = [1, 2, 3]; arr[1999] = 1999; %DebugPrint(arr);

1999 - 2 > 1024              ，arr 从快数组转换为哈希形式存储的慢数组
 
 
 
 
 
 
 
 
 
 
 
 
 
 。

下面看一下详细运行信息?

修改arr之前:

修改arr之后：

2.2  
 
  
 
  
 
  
 
  
 
  
 
  
 
、慢数组何时转换为快数组

(1)













、看一下源码先?

path:v8/src/objects/js-objects.cc // path:v8/src/objects/js-objects.cc // line:4932 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 = 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位-231到232-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. // 空数组预分配的大小为4 static 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);

arr.push 之前：

arr.push 后：

具体分析如下： ?

向数组 [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:750 if (2 * length + JSObject::kMinAddedElementsCapacity <= capacity) { // If more than half the elements wont 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个纬度的取舍
 

 

 

 

 

 

 
，优化了数组的性能 

 

 

 

 

 

 

。

参考学习博客

???

? 关注我

 

 

 

 

 

 

 ，你会发现一个踏实努力的宝藏前端?              ，让我们一起学习
 
 

 
 

 
 

 
 

 
 

 
 

 
 
，共同成长吧              。

? 喜欢的小伙伴记得点赞关注收藏哟













，回看不迷路 ?