关于javascript:精读JS-数组的内部实现

67次阅读

共计 6490 个字符，预计需要花费 17 分钟才能阅读完成。

每个 JS 执行引擎都有本人的实现，咱们这次关注 V8 引擎是如何实现数组的。

本周次要精读的文章是 How JavaScript Array Works Internally?，比拟简略的介绍了 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_ELEMENTS

PACKED_SMI_ELEMENTS 类型是性能最好的模式，存储的类型默认是间断的整型。当咱们插入整型时，V8 会给数组主动扩容，此时类型还是 PACKED_SMI_ELEMENTS：

const arr = [] // PACKED_SMI_ELEMENTS
arr.push(1) // PACKED_SMI_ELEMENTS

或者间接创立有内容的数组，也是这个类型：

const arr = [1, 2, 3] // PACKED_SMI_ELEMENTS

主动降级

当咱们对数组应用骚操作时，V8 会默默的进行类型降级。比方忽然拜访到第 100 项：

const arr = [1, 2, 3] // PACKED_SMI_ELEMENTS
arr[100] = 4 // HOLEY_SMI_ELEMENTS

如果忽然插入一个浮点类型，会降级到 DOUBLE：

const arr = [1, 2, 3] // PACKED_SMI_ELEMENTS
arr.push(4.1) // PACKED_DOUBLE_ELEMENTS

当然如果两个骚操作一联合，HOLEY_DOUBLE_ELEMENTS 就胜利被你造出来了：

const arr = [1, 2, 3] // PACKED_SMI_ELEMENTS
arr[100] = 4.1 // HOLEY_DOUBLE_ELEMENTS

再狠一点，插入个字符串或者函数，那就到了最最兜底类型，HOLEY_ELEMENTS：

const arr = [1, 2, 3] // PACKED_SMI_ELEMENTS
arr[100] = '4' // HOLEY_ELEMENTS

从是否有 Empty 状况来看，PACKED > HOLEY 的性能，Benchmark 测试后果大略快 23%。

从类型来看，SMI > DOUBLE > 空类型。起因是类型决定了数组每项的长度，DOUBLE 类型是指每一项可能为 SMI 也可能为 DOUBLE，而空类型的每一项类型齐全不可确认，在长度确认上会破费额定开销。

因而，HOLEY_ELEMENTS 是性能最差的兜底类型。

降级的不可逆性

文中提到一个重点，示意降级是不可逆的，具体能够看下图：

<img width=500 src=”https://s1.ax1x.com/2022/05/08/O3nzsf.png”>

其实要表白的法则很简略，即 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 提供的 Native API，在一般 js 脚本是不辨认的，因而咱们要在执行时增加参数 --allow-natives-syntax：

~/.jsvu/v8-debug ./test.js --allow-natives-syntax

同时，在 test.js 里应用 %DebugPrint 打印咱们要调试的数组，如：

const arr = []
%DebugPrint(arr)

输入后果为：

DebugPrint: 0x120d000ca0b9: [JSArray]
 - map: 0x120d00283a71 <Map(PACKED_SMI_ELEMENTS)> [FastProperties]

也就是说，arr = [] 创立的数组的外部类型为 PACKED_SMI_ELEMENTS，合乎预期。

验证不可逆转换

不看源码的话，权且置信原文说的类型转换不可逆，那么咱们做一个测试：

const arr = [1, 2, 3]
arr.push(4.1)

console.log(arr);
%DebugPrint(arr)

arr.pop()

console.log(arr);
%DebugPrint(arr)

打印外围后果为：

1,2,3,4.1
DebugPrint: 0xf91000ca195: [JSArray]
 - map: 0x0f9100283b11 <Map(PACKED_DOUBLE_ELEMENTS)> [FastProperties]

1,2,3
DebugPrint: 0xf91000ca195: [JSArray]
 - map: 0x0f9100283b11 <Map(PACKED_DOUBLE_ELEMENTS)> [FastProperties]

能够看到，即使 pop 后将原数组回退到齐全整型的状况，DOUBLE 也不会优化为 SMI。

再看下长度的测试：

const arr = [1, 2, 3]
arr[4] = 4

console.log(arr);
%DebugPrint(arr)

arr.pop()
arr.pop()

console.log(arr);
%DebugPrint(arr)

打印外围后果为：

1,2,3,,4
DebugPrint: 0x338b000ca175: [JSArray]
 - map: 0x338b00283ae9 <Map(HOLEY_SMI_ELEMENTS)> [FastProperties]

1,2,3
DebugPrint: 0x338b000ca175: [JSArray]
 - map: 0x338b00283ae9 <Map(HOLEY_SMI_ELEMENTS)> [FastProperties]

也证实了 PACKED 到 HOLEY 的不可逆。

字典模式

数组还有一种外部实现是 Dictionary Elements，它用 HashTable 作为底层构造模仿数组的操作。

这种模式用于数组长度十分大的时候，不须要间断开拓内存空间，而是用一个个零散的内存空间通过一个 HashTable 寻址来解决数据的存储，这种模式在数据量大时节俭了存储空间，但带来了额定的查问开销。

当对数组的赋值远大于以后数组大小时，V8 会思考将数组转化为 Dictionary Elements 存储以节俭存储空间。

做一个测试：

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

arr[3000] = 4;
%DebugPrint(arr);

次要输入后果为：

DebugPrint: 0x209d000ca115: [JSArray]
 - map: 0x209d00283a71 <Map(PACKED_SMI_ELEMENTS)> [FastProperties]

DebugPrint: 0x209d000ca115: [JSArray]
 - map: 0x209d00287d29 <Map(DICTIONARY_ELEMENTS)> [FastProperties]

能够看到，占用了太多空间会导致数组的外部实现切换为 DICTIONARY_ELEMENTS 模式。

实际上这两种模式是依据固定规定互相转化的，具体查了下 V8 源码：

字典模式在 V8 代码里叫 SlowElements，反之则叫 FastElements，所以要看转化规定，次要就看两个函数：ShouldConvertToSlowElements 和 ShouldConvertToFastElements。

上面是 ShouldConvertToSlowElements 代码，即什么时候转化为字典模式：

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

ShouldConvertToSlowElements 函数被重载了两次，所以有两个判断逻辑。第一处 new_capacity > size_threshold 则变成字典模式，new_capacity 示意新尺寸，而 size_threshold 是依据 3 已有尺寸 2 计算出来的。

第二处 index - capacity >= JSObject::kMaxGap 时变成字典模式，其中 kMaxGap 是常量 1024，也就是新退出的 HOLEY(孔洞) 大于 1024，则转化为字典模式。

而由字典模式转化为一般模式的函数是 ShouldConvertToFastElements：

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;

  // Turn fast if the dictionary only saves 50% space.
  return 2 * dictionary_size >= *new_capacity;
}

重点是最初一行 return 2 * dictionary_size >= *new_capacity 示意字典模式仅节俭了 50% 空间时，不如切换为一般模式（fast mode）。

具体就不测试了，感兴趣同学能够用下面介绍的办法应用 v8-debug 测试一下。

总结

JS 数组应用办法非常灵活，但 V8 应用 C++ 实现时，必须转化为更底层的类型，所以为了兼顾性能，就做了快慢模式，而快模式又分了 SMI、DOUBLE；PACKED、HOLEY 模式别离解决来尽可能晋升速度。

也就是说，咱们在随便创立数组的时候，V8 会剖析数组的元素形成与长度变动，主动散发到各种不同的子模式解决，以最大化晋升性能。

这种模式使 JS 开发者取得了更好的开发者体验，而实际上执行性能也和 C++ 原生优化相差无几，所以从这个角度来看，JS 是一种更高封装档次的语言，极大升高了开发者学习门槛。

当然 JS 还提供了一些绝对原生的语法比方 ArrayBuffer，或者 WASM 让开发者间接操作更底层的个性，这能够使性能管制更准确，但带来了更大的学习和保护老本，须要开发者依据理论状况衡量。

探讨地址是：精读《JS 数组的外部实现》· Issue #414 · dt-fe/weekly

如果你想参加探讨，请 点击这里，每周都有新的主题，周末或周一公布。前端精读 – 帮你筛选靠谱的内容。

关注 前端精读微信公众号

<img width=200 src=”https://img.alicdn.com/tfs/TB165W0MCzqK1RjSZFLXXcn2XXa-258-258.jpg”>

版权申明：自在转载 - 非商用 - 非衍生 - 放弃署名（创意共享 3.0 许可证）

正文完
javascript
发表至： javascript
2022-05-09
 0
常用的ES6新特性–解构赋值
关于javascript:精读设计模式-Interpreter-解释器模式
关于javascript:鸿蒙系统中的-JS-开发框架
关于javascript:js-实现复制文本到剪贴板