精读《JS数组的内部实现》
2024-09-17 10:54:40
每个JS执行引擎都有自己的实现，我们这次关注V8引擎是如何实现数组的。
本周主要精读的文章是HowJavaScriptArrayWorksInternally?，比较简略的介绍了V8引擎的数组实现机制，笔者也会参考部分其他文章与源码结合进行讲解。
概述JS数组的内部类型有很多模式，如：
PACKED_SMI_ELEMENTS
PACKED_DOUBLE_ELEMENTS
PACKED_ELEMENTS
HOLEY_SMI_ELEMENTS
HOLEY_DOUBLE_ELEMENTS
HOLEY_ELEMENTS
PACKED翻译为打包，实际意思是“连续有值的数组”；HOLEY翻译为孔洞，表示这个数组有很多孔洞一样的无效项，实际意思是“中间有孔洞的数组”，这两个名词是互斥的。
SMI表示数据类型为32位整型，DOUBLE表示浮点类型，而什么类型都不写，表示数组的类型还杂糅了字符串、函数等，这个位置上的描述也是互斥的。
所以可以这么去看数组的内部类型：[PACKED,HOLEY]_[SMI,DOUBLE,'']_ELEMENTS。
最高效的类型PACKED_SMI_ELEMENTS一个最简单的空数组类型默认为PACKED_SMI_ELEMENTS：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSPACKED_SMI_ELEMENTS类型是性能最好的模式，存储的类型默认是连续的整型。当我们插入整型时，V8会给数组自动扩容，此时类型还是PACKED_SMI_ELEMENTS：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS或者直接创建有内容的数组，也是这个类型：
const?arr?=?[1,?2,?3]?//?PACKED_SMI_ELEMENTS自动降级当我们对数组使用骚操作时，V8会默默的进行类型降级。比如突然访问到第100项：
const?arr?=?[1,?2,?3]?//?PACKED_SMI_ELEMENTSarr[100]?=?4?//?HOLEY_SMI_ELEMENTS如果突然插入一个浮点类型，会降级到DOUBLE：
const?arr?=?[1,?2,?3]?//?PACKED_SMI_ELEMENTSarr.push(4.1)?//?PACKED_DOUBLE_ELEMENTS当然如果两个骚操作一结合，HOLEY_DOUBLE_ELEMENTS就成功被你造出来了：
const?arr?=?[1,?2,?3]?//?PACKED_SMI_ELEMENTSarr[100]?=?4.1?//?HOLEY_DOUBLE_ELEMENTS再狠一点，插入个字符串或者函数，那就到了最最兜底类型，HOLEY_ELEMENTS：
const?arr?=?[1,?2,?3]?//?PACKED_SMI_ELEMENTSarr[100]?=?'4'?//?HOLEY_ELEMENTS从是否有Empty情况来看，PACKED>HOLEY的性能，Benchmark测试结果大概快23%。
从类型来看，SMI>DOUBLE>空类型。原因是类型决定了数组每项的长度，DOUBLE类型是指每一项可能为SMI也可能为DOUBLE，而空类型的每一项类型完全不可确认，在长度确认上会花费额外开销。
因此，HOLEY_ELEMENTS是性能最差的兜底类型。
降级的不可逆性文中提到一个重点，表示降级是不可逆的，具体可以看下图：
其实要表达的规律很简单，即PACKED只会变成更糟的HOLEY，SMI只会往更糟的DOUBLE和空类型变，且这两种变化都不可逆。
精读为了验证文章的猜想，笔者使用v8-debug调试了一番。
使用v8-debug调试先介绍一下v8-debug，它是一个v8引擎调试工具，首先执行下面的命令行安装jsvu：
npm?i?-g?jsvu然后执行jsvu，根据引导选择自己的系统类型，第二步选择要安装的js引擎，选择v8和v8-debug：
jsvu//?选择?macos//?选择?v8，v8-debug然后随便创建一个js文件，比如test.js，再通过~/.jsvu/v8-debug./test.js就可以执行调试了。默认是不输出任何调试内容的，我们根据需求添加参数来输出要调试的信息，比如：
~/.jsvu/v8-debug?./test.js?--print-ast这样就会把test.js文件的语法树打印出来。
使用v8-debug调试数组的内部实现为了观察数组的内部实现，使用console.log(arr)显然不行，我们需要用%DebugPrint(arr)以debug模式打印数组，而这个%DebugPrint函数式V8提供的NativeAPI，在普通js脚本是不识别的，因此我们要在执行时添加参数--allow-natives-syntax：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS0同时，在test.js里使用%DebugPrint打印我们要调试的数组，如：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS1输出结果为：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS2也就是说，arr=[]创建的数组的内部类型为PACKED_SMI_ELEMENTS，符合预期。
验证不可逆转换不看源码的话，姑且相信原文说的类型转换不可逆，那么我们做一个测试：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS3打印核心结果为：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS4可以看到，即便pop后将原数组回退到完全整型的情况，DOUBLE也不会优化为SMI。
再看下长度的测试：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS5打印核心结果为：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS6也证明了PACKED到HOLEY的不可逆。
字典模式数组还有一种内部实现是DictionaryElements，它用HashTable作为底层结构模拟数组的操作。
这种模式用于数组长度非常大的时候，不需要连续开辟内存空间，而是用一个个零散的内存空间通过一个HashTable寻址来处理数据的存储，这种模式在数据量大时节省了存储空间，但带来了额外的查询开销。
当对数组的赋值远大于当前数组大小时，V8会考虑将数组转化为DictionaryElements存储以节省存储空间。
做一个测试：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS7主要输出结果为：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS8可以看到，占用了太多空间会导致数组的内部实现切换为DICTIONARY_ELEMENTS模式。
实际上这两种模式是根据固定规则相互转化的，具体查了下V8源码：
字典模式在V8代码里叫SlowElements，反之则叫FastElements，所以要看转化规则，主要就看两个函数：ShouldConvertToSlowElements和ShouldConvertToFastElements。
下面是ShouldConvertToSlowElements代码，即什么时候转化为字典模式：
const?arr?=?[]?//?PACKED_SMI_ELEMENTSarr.push(1)?//?PACKED_SMI_ELEMENTS9ShouldConvertToSlowElements函数被重载了两次，所以有两个判断逻辑。第一处new_capacity>size_threshold则变成字典模式，new_capacity表示新尺寸，而size_threshold是根据3已有尺寸2计算出来的。
第二处index-capacity>=JSObject::kMaxGap时变成字典模式，其中kMaxGap是常量1024，也就是新加入的HOLEY(孔洞)大于1024，则转化为字典模式。
而由字典模式转化为普通模式的函数是ShouldConvertToFastElements：
const?arr?=?[1,?2,?3]?//?PACKED_SMI_ELEMENTS0重点是最后一行return2*dictionary_size>=*new_capacity表示字典模式仅节省了50%空间时，不如切换为普通模式（fastmode）。
具体就不测试了，感兴趣同学可以用上面介绍的方法使用v8-debug测试一下。
总结JS数组使用方法非常灵活，但V8使用C++实现时，必须转化为更底层的类型，所以为了兼顾性能，就做了快慢模式，而快模式又分了SMI、DOUBLE；PACKED、HOLEY模式分别处理来尽可能提升速度。
也就是说，我们在随意创建数组的时候，V8会分析数组的元素构成与长度变化，自动分发到各种不同的子模式处理，以最大化提升性能。
这种模式使JS开发者获得了更好的开发者体验，而实际上执行性能也和C++原生优化相差无几，所以从这个角度来看，JS是一种更高封装层次的语言，极大降低了开发者学习门槛。
当然JS还提供了一些相对原生的语法比如ArrayBuffer，或者WASM让开发者直接操作更底层的特性，这可以使性能控制更精确，但带来了更大的学习和维护成本，需要开发者根据实际情况权衡。
讨论地址是：精读《JS数组的内部实现》·Issue#414·dt-fe/weekly
如果你想参与讨论，请点击这里，每周都有新的主题，周末或周一发布。前端精读-帮你筛选靠谱的内容。
版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）
原文：https://juejin.cn/post/7095543597633634317
热门标签
