Roger Leung‘s Epcot

vuePress-theme-reco Roger Leung ( z3rog )    2018 - 2021
Roger Leung‘s Epcot

Choose mode

  • dark
  • auto
  • light
Blog
Note
Github (opens new window)
author-avatar

Roger Leung ( z3rog )

18

Article

20

Tag

Blog
Note
Github (opens new window)

V8 中的快慢属性与快慢数组

vuePress-theme-reco Roger Leung ( z3rog )    2018 - 2021

V8 中的快慢属性与快慢数组

Roger Leung ( z3rog ) 2020-05-17 ChromeV8

聊聊 V8 底层如何处理 JavaScript 中的对象与数组

# 对象

我们先来看一个例子。假设我们有这样的代码:

function Foo() {
  this[100] = 'test-100'
  this[1] = 'test-1'
  this["B"] = 'foo-B'
  this[50] = 'test-50'
  this[9] = 'test-9'
  this[8] = 'test-8'
  this[3] = 'test-3'
  this[5] = 'test-5'
  this["A"] = 'foo-A'
  this["C"] = 'foo-C'
}

const foo = new Foo()

for (const key in foo) {
  console.log(`key:${key}, value:${foo[key]}`)
}
// key:1, value:test-1
// key:3, value:test-3
// key:5, value:test-5
// key:8, value:test-8
// key:9, value:test-9
// key:50, value:test-50
// key:100, value:test-100
// key:B, value:foo-B
// key:A, value:foo-A
// key:C, value:foo-C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

我们创建一个 Foo 实例 foo,foo 中有 10 个属性,我们遍历该对象并依次打印,可以发现打印的顺序与设置的顺序并不一致。细心一点观察可以发现,对于整数型的 key 值,会从小到大遍历,对于非整数型的 key 值,会按照设置的先后顺序遍历。在 V8 中,前后者分别被称为 数组索引属性(Array-indexed Properties)和 命名属性(Named Properties),遍历时一般会先遍历前者。前后两者在底层存储在两个单独的数据结构中,分别用 properties 和 elements 两个指针指向它们,如下图:



js-object


之所以存储在两个数据结构中,是为了使不同情况下对属性的增删改查都相对高效。

我们对前面的代码打一个 snapshot 进行观察:

properties-elements

咦?没有 properties 啊?实际上,V8 有一种策略:如果命名属性少于等于 10 个时,命名属性会直接存储到对象本身,而无需先通过 properties 指针查询,再获取对应 key 的值,省去中间的一步,从而提升了查找属性的效率。直接存储到对象本身的属性被称为 对象内属性(In-object Properties)。对象内属性与 properties、elements 处于同一层级。

为了印证这个说法,将代码替换为如下内容,重新打 snapshot。可以看到超出 10 个的部分 property10 和 property11 存储在 properties 中,这部分命名属性称为普通属性:

function Foo(properties, elements) {
  //添加可索引属性
  for (let i = 0; i < elements; i++) {
    this[i] = `element${i}`
  }

  //添加常规属性
  for (let i = 0; i < properties; i++) {
    const prop = `property${i}`
    this[prop] = prop
  }
}
const foo = new Foo(12, 12)
1
2
3
4
5
6
7
8
9
10
11
12
13

properties-elements-2

至此,我们已经对命名属性、数组索引属性与对象内属性有一个基本了解。

# 隐藏类和描述符数组

在 V8 中,每个 JavaScript 对象的第一个字段都指向一个隐藏类(HiddenClass)。隐藏类是用来描述和便于跟踪 JavaScript 对象的「形状」的,里面存储了对象的元信息如:对象的属性数量、对象原型的引用等等。多个具有相同结构(即命名属性和顺序均相同)的对象共享相同的隐藏类。因此,动态地为对象增加属性的过程中隐藏类会被更改。

我们先看看隐藏类的结构:


hidden-class

对于隐藏类来说最重要的是第三位字段(bit field 3),记录了命名属性的数量和一个指向描述符数组(Descriptor Array)的指针,描述符数组中存储了命名属性的相关信息,因此当 V8 需要获取命名属性的具体信息时,需要先通过 hiddenClass 指针找到对应的 HiddenClass,获取 HiddenClass 第三位字段中记录的描述符数组指针,然后在数组中查询特定的命名属性(划重点!!)。数组索引属性是不会被记录在该数组的,因为他们不会让 V8 更改隐藏类。


adding-properties


以上图为例,当我们创建一个空对象 o 并依次为其增加 a、b、c 三个命名属性时,object o 中的 hiddenClass 会经历以下阶段:

  • 增加 a 属性,生成过渡 HiddenClass 1
  • 增加 b 属性,生成过渡 HiddenClass 2
  • 增加 c 属性,生成过渡 HiddenClass 3
  • 属性添加完成,此时 object o 的 hiddeClass 指针指向 HiddenClass 3

这三个过渡的 HiddenClasses 会被 V8 连接起来,生成一个叫过渡树(transition tree)的结构,从而让 V8 可以追踪 HiddenClasses 之间的关系,并保证相同结构的对象经过相同顺序的命名属性增加操作后,具有相同的 HiddenClass。

如果相同结构的对象增加不同的命名属性,V8 会为在过渡树中开出新的分支,以标识原本相同的 hiddenClass 增加不同命名属性后派生出的不同 Class:


transition-tree

总结

  • 相同结构(命名属性和顺序均相同)的对象共享相同的 HiddenClass
  • 新属性的添加伴随着新 HiddenClass 的创建
  • 数组索引索性不会改变 HiddenClass

# 对象内属性 or 普通属性

引言部分对对象内属性作了简介,它是指那些直接存存储在对象上的命名属性。根据 V8 官方博客的说法,对象内属性的数量是根据对象初始大小预定义好的,但是我多次测试后发现这个数量上限都是 10,不知道什么情况下会有所不同。望知道的朋友们多多指点。

超出对象内属性数量限制的属性被存放与 properties 指针指向的数据结构中,这部分虽然增加了一层查询,但扩容非常方便。


in-object-properties

# 快属性 or 慢属性

线性数据结构的读取速度更快(读取复杂度为 O(1)),因此将存储在线性结构中的命名属性称为快属性。快属性只通过 properties 中的索引访问,但是如前文所述,为了从属性名访问到实际存储位置,V8 必须参考 HiddenClass 上的 Descriptor Array,因为里面存储了关于命名属性的元信息。


fast-vs-slow-properties


因此,倘若一个对象频繁地增删属性,而 V8 还维持原来的线性结构存储的话,插入和删除的复杂度都为 O(n),同时耗费大量的时间、内存在维护 HiddenClass 和 Descriptor Array 上。

为了减少这部分开销,V8 将这些本来会存储在线性结构中的快属性降级为慢属性。此时原本用于存储属性元信息的 Descriptor Array 被置空,转而将信息存储到 properties 内部维护的一个字典(称为 Properties Dictionary)中,这样对对象的增删属性操作便不需更新 HiddenClass 了。但这也意味着 V8 内部的内联缓存(inline-cache)不会生效,所以这种属性被称为慢属性。

# 数组

# 全填充 or 带孔




 

 





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
1
2
3
4
5
6
7
8
9
10

如果一个数组中所有位置均有值,我们称之为全填充(Packed)数组,若某些位置在初始化时未定义(如 const arr = [1, , 3] 中的 arr[1]),或定义后被删除(delete,如上述例子),称之为带孔(Holey)数组。

该例子在 V8 的访问可以通过下图解释:


hole


一开始数组 o 是 packed 的,所以访问 o[1] 时可以直接获取值,而不需要访问原型。而行 4:delete o[1] 为数组引入了一个孔洞(the_hole),用于标记不存在的属性,同时又行 6 为 o 定义了原型上的 1 属性,当再次获取 o[1] 时会穿孔进而继续往原型链上查询。原型链上的查询是昂贵的,可以根据是否有 the_hole 来降低这部分查询开销。

# 快数组 or 慢数组

const arr = [1, 2, 3]
arr[1999] = 1999
// arr 会如何存储?
1
2
3

这个例子中,在行 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,当对象或数组很庞大时,不可避免地导致访问速度下降,这是底层原理决定的。

# 深入

# 为什么 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)
  // ...
}
1
2
3
4
5
6
7
8
9
10
11

在 V8 源码中清晰地表明,JSArray 继承自 JSObject,即数组是一个特殊的对象,而 JS 中所有非原始类型都是对象的实例,所以 JS 中数组可以存储多种类型的值。

我们在看看注释。注释中说,JS 中的数组会有快慢两种模式:

  • 快模式:数组实现的是 V8 里一个叫 FixedArray 的类,它在内存中是连续的空间,直接通过索引读写值,非常快。如果有 push 或 pop 操作,它会动态地扩容或收缩。
  • 慢模式:如前文所介绍,V8 创建了一个字典(HashTable)来记录映射关系,其中索引的整数值即是字典的键。

# 快数组何时转换为慢数组


























 












 












// 摘自:`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;

// ...
class NumberDictionaryShape : public NumberDictionaryBaseShape {
 public:
  static const int kPrefixSize = 1;
  static const int kEntrySize = 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;
  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);
  // TODO(ulan): Check if it works with young large objects.
  if (*new_capacity <= JSObject::kMaxUncheckedOldFastElementsLength ||
      (*new_capacity <= JSObject::kMaxUncheckedFastElementsLength &&
       ObjectInYoungGeneration(object))) {
    return false;
  }
  return ShouldConvertToSlowElements(object.GetFastElementsUsage(),
                                     *new_capacity);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

注意 26、39 两行高亮的代码,它们表达的意思分别是:

  • 如果快数组扩容后的容量是原来的 3 倍以上,意味着它比 HashTable 形式存储占用更大的内存,快数组会转换为慢数组
  • 如果快数组新增的索引与原来最大索引的差值大于 1024,快数组会被转换会慢数组

所以,前面的例子:

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

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

# 慢数组何时转换为快数组


























 
 


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 = 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

27 行之前是一些容错,比如行 7,如果有过强制使用慢数组的标识(如某个 key 是整型且数值很大,直接标识为只能使用慢数组),那就不可以再转换为快数组,直接返回 false。

26、27 行表明,当慢数组转换成快数组能节省不少于 50% 的空间时,才会将其转换。

# 动态扩容与收缩

// 摘自 `src/objects/js-array.h`
// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;
1
2
3

上面代码表明,当声明一个空数组时,已预分配好 4 个字节的存储空间,所以 [] 与 [1, 2, 3, 4] 占用一样多的内存。 前面说过,JSArray 继承自 JSObject,我们可以在 js-objects.h 中找到如下代码:

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
  return old_capacity + (old_capacity >> 1) + kMinAddedElementsCapacity;
}
1
2
3
4
5
6

这是对 JSObject elements 扩容和对 JSArray 扩容的通用方法。扩容后容量的计算逻辑是:在原占用空间 old_capacity 的基础上增加一半(old_capacity >> 1 右移 1 位表示除 2,再相加得原空间 1.5 倍),再加上 16。

举例:向数组 [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,再新将新增元素写入。

紧接着,我们在 src/objects/elements.cc 中找到 SetLengthImpl 方法中的如下代码:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

当数组元素减少(如 pop)后,如果数组容量大于等于 length 的 2 倍,则进行容量调整,使用 RightTrimFixedArray 函数,计算出需要释放的空间大小,做好标记,等待 GC 回收;如果数组容量小于 length 的 2 倍,则用 holes 对象填充。

# References

  • https://v8.dev/blog/fast-properties (opens new window)