xiaofeihe

译文：Fast for-in in V8

原文链接：https://v8.dev/blog/fast-for-in

Fast for-in in V8

for-in是许多框架中广泛使用的语言特性。尽管它无处不在，从实现的角度来看，它是一种比较模糊的语言结构，V8竭尽全力使它变的更快。在过去的一年中，for-in变得更加符合规范，并且在具体场景中速度提升了3倍。

许多受欢迎的网站广泛使用了for-in，并将会从中受益。例如，在2016年早些时候，Facebook花费了7%的脚本时间在for-in上面，在Wikipedia上面，这个数字更高甚至到了大约8%。通过改善for-in的性能表现，Chrome51显著改善了这两个网站的性能。

由于for-in的各种改进，Wikipedia和Facebook将它们的脚本时间改善了4%。请注意在同一时期，V8的其余部分也变的更快，使的脚本总体性能提高了4%以上。

在博文接下来的内容，我们将解释我们如何设法加快这一核心语言功能，并同时解决长期存在的规范违规问题。

The spec

出于性能原因，for-in迭代语义是模糊的。

当我们在不同的实现中观察for-in的spec-text时，它以一种意想不到的模糊方式编写。让我们看一下使用适当的陷阱迭代Proxy对象的示例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const proxy = new Proxy({ a: 1, b: 1},
  {
    getPrototypeOf(target) {
    console.log('getPrototypeOf');
    return null;
  },
  ownKeys(target) {
    console.log('ownKeys');
    return Reflect.ownKeys(target);
  },
  getOwnPropertyDescriptor(target, prop) {
    console.log('getOwnPropertyDescriptor name=' + prop);
    return Reflect.getOwnPropertyDescriptor(target, prop);
  }
});

在V8/Chrome 56你会得到下面的输出：

1
2
3
4
5
6
ownKeys
getPrototypeOf
getOwnPropertyDescriptor name=a
a
getOwnPropertyDescriptor name=b
b

相反，你在Firefox 51中获得了不同语句顺序基于相同代码段：

1
2
3
4
5
6
ownKeys
getOwnPropertyDescriptor name=a
getOwnPropertyDescriptor name=b
getPrototypeOf
a
b

两种浏览器都遵循规范，但是规范并没有强制执行明确的指令顺序。要正确理解这些循环漏洞，让我们看一下spec文本：

通常规范说明精确地指出了所需的确切步骤。但在这种情况下，它们提到一个简单的散文列表，甚至执行的顺序留给实施者。原因通常是规范的这些部分是在JavaScript引擎已经具有不同实现的事实之后编写的。该规范试图通过提供以下指示来绑定松散的末端：

  1. 迭代器的throw和return方法为null，永远不会被调用。
  2. 迭代器的下一个方法处理对象属性，以确定是否应将属性键作为迭代器值返回。
  3. 返回的属性键不包括符号键。
  4. 枚举期间可以删除目标对象的属性。
  5. 在迭代器的下一个方法处理之前删除的属性将被忽略。如果在枚举期间向目标对象添加了新属性，则不能保证在活动枚举中处理新添加的属性。
  6. 在任何枚举中，迭代器的下一个方法最多返回一次属性名。
  7. 枚举目标对象的属性包括递归地枚举其原型的属性，原型的原型等;但是，如果原型的属性与已经由迭代器的下一个方法处理的属性具有相同的名称，则不会处理该原型的属性。
  8. 在确定原型对象的属性是否已被处理时，不会考虑[可枚举]属性的值。
  9. 原型对象的可枚举属性名称必须通过调用作为参数传递的原型对象属性来获得。
  10. EnamateObjectProperties必须通过调用目标对象的[OwnPropertyKeys]内部方法来获取其自己的属性键。

这些步骤听起来很乏味，但是规范包含一个明确且更具可读性的示例实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function* EnumerateObjectProperties(obj) {
  const visited = new Set();
  for (const key of Reflect.ownKeys(obj)) {
    if (typeof key === 'symbol') continue;
    const desc = Reflect.getOwnPropertyDescriptor(obj, key);
    if (desc && !visited.has(key)) {
      visited.add(key);
      if (desc.enumerable) yield key;
    }
  }
  const proto = Reflect.getPrototypeOf(obj);
  if (proto === null) return;
  for (const protoKey of EnumerateObjectProperties(proto)) {
    if (!visited.has(protoKey)) yield protoKey;
  }
}

既然你已经深入到了这里，你可能已经从前面的例子中注意到V8并不完全遵循规范示例实现。首先，for-in示例生成器以递增方式工作，而V8则预先收集所有keys，主要是出于性能原因。这非常好，实际上spec文本没有明确定义操作A-J的顺序。尽管如此，正如您将在本文稍后发现的那样，在2016年之前，V8并未完全遵守规范。

The enum cache

for-in生成器的示例实现遵循收集和产生键的增量模式。在V8中，在第一步中收集属性键，然后仅在迭代阶段使用。对于V8，这使一些事情变得更容易。要了解原因，我们需要查看对象模型。

一个简单的对象，例如{a：’value a’，b：’value b’，c：’value c’}可以在V8中有各种内部表示，我们将在详细的后续文章中展示这一点。这意味着根据我们拥有的属性类型 - 对象中的属性、快的属性或慢的属性-实际的属性名称存储在不同的位置。这使得收集可枚举keys成为一件非常重要的事情。

V8通过隐藏类或所谓的Map来跟踪对象的结构。具有相同Map的对象具有相同的结构。此外，每个Map都有一个共享数据结构，描述符数组，其中包含有关每个属性的详细信息，例如属性存储在对象上的位置，属性名称以及可枚举性等详细信息。

让我们暂时假设我们的JavaScript对象已达到其最终形状，并且不会添加或删除更多属性。在这种情况下，我们可以使用描述符数组作为键的源。如果只有可枚举的属性，则此方法有效。每次V8使用可通过Map的描述符数组访问的单独EnumCache时，为了避免过滤掉不可枚举属性的开销。

鉴于V8期望慢速字典对象经常更改（即通过添加和删除属性），对于具有字典属性的慢对象，没有描述符数组。因此，V8不为慢速属性提供EnumCache。类似的假设适用于索引属性，因此它们也被排除在EnumCache之外。

让我们总结一下重要的事实：

  1. Maps are used to keep track of object shapes.
  2. Descriptor arrays store information about properties (name, configurability, visibility).
  3. Descriptor arrays can be shared between Maps.
  4. Each descriptor array can have an EnumCache listing only the enumerable named keys, not indexed property names.

The mechanics of for-in

现在，您已经部分了解Maps的工作原理以及EnumCache与描述符数组的关系。V8通过Ignition（一个字节码解释器）和TurboFan（优化编译器）执行JavaScript，它们以类似的方式处理for-in。为简单起见，我们将使用伪C++方式来解释内部如何实现for-in：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// For-In Prepare:
FixedArray* keys = nullptr;
Map* original_map = object->map();
if (original_map->HasEnumCache()) {
  if (object->HasNoElements()) {
    keys = original_map->GetCachedEnumKeys();
  } else {
    keys = object->GetCachedEnumKeysWithElements();
  }
} else {
  keys = object->GetEnumKeys();
}

// For-In Body:
for (size_t i = 0; i < keys->length(); i++) {
  // For-In Next:
  String* key = keys[i];
  if (!object->HasProperty(key) continue;
  EVALUATE_FOR_IN_BODY();
}

For-in可以分为三个主要步骤：

  1. 准备要迭代的keys
  2. 获取下一个key
  3. 评估整体for-in

“准备”步骤是这三个中最复杂的步骤，也是EnumCache发挥作用的地方。在上面的示例中，您可以看到，如果存在并且对象(及其原型)上没有元素(整数索引属性)，则V8直接使用EnumCache。对于存在索引属性名称的情况，V8跳转到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
FixedArray* JSObject::GetCachedEnumKeysWithElements() {
  FixedArray* keys = object->map()->GetCachedEnumKeys();
  return object->GetElementsAccessor()->PrependElementIndices(object, keys);
}

FixedArray* Map::GetCachedEnumKeys() {
  // Get the enumerable property keys from a possibly shared enum cache
  FixedArray* keys_cache = descriptors()->enum_cache()->keys_cache();
  if (enum_length() == keys_cache->length()) return keys_cache;
  return keys_cache->CopyUpTo(enum_length());
}

FixedArray* FastElementsAccessor::PrependElementIndices(
      JSObject* object, FixedArray* property_keys) {
  Assert(object->HasFastElements());
  FixedArray* elements = object->elements();
  int nof_indices = CountElements(elements)
  FixedArray* result = FixedArray::Allocate(property_keys->length() + nof_indices);
  int insertion_index = 0;
  for (int i = 0; i < elements->length(); i++) {
    if (!HasElement(elements, i)) continue;
    result[insertion_index++] = String::FromInt(i);
  }
  // Insert property keys at the end.
  property_keys->CopyTo(result, nof_indices - 1);
  return result;
}

在没有找到现有EnumCache的情况下，我们再次跳转到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
29
30
31
32
33
34
35
36
37
FixedArray* JSObject::GetEnumKeys() {
  // Get the receiver’s enum keys.
  FixedArray* keys = this->GetOwnEnumKeys();
  // Walk up the prototype chain.
  for (JSObject* object : GetPrototypeIterator()) {
     // Append non-duplicate keys to the list.
     keys = keys->UnionOfKeys(object->GetOwnEnumKeys());
  }
  return keys;
}

FixedArray* JSObject::GetOwnEnumKeys() {
  FixedArray* keys;
  if (this->HasEnumCache()) {
    keys = this->map()->GetCachedEnumKeys();
  } else {
    keys = this->GetEnumPropertyKeys();
  }
  if (this->HasFastProperties()) this->map()->FillEnumCache(keys);
  return object->GetElementsAccessor()->PrependElementIndices(object, keys);
}

FixedArray* FixedArray::UnionOfKeys(FixedArray* other) {
  int length = this->length();
  FixedArray* result = FixedArray::Allocate(length + other->length());
  this->CopyTo(result, 0);
  int insertion_index = length;
  for (int i = 0; i < other->length(); i++) {
    String* key = other->get(i);
    if (other->IndexOf(key) == -1) {
      result->set(insertion_index, key);
      insertion_index++;
    }
  }
  result->Shrink(insertion_index);
  return result;
}

这个简化的C++代码对应于V8中的实现，直到2016年初我们开始研究UnionOfKeys方法。如果仔细观察，您会注意到我们使用了一个简单的算法来排除列表中的重复项，如果原型链上有许多键，则可能会产生较差性能。这就是我们决定在下一节中进行优化的方式。

Problems with for-in

正如我们在上一节中已经指出的那样，UnionOfKeys方法具有糟糕的最坏情况性能。它基于这样一个有效的假设：即大多数对象具有快速属性，因此将受益于EnumCache。第二个假设是原型链上只有很少的可枚举属性，限制了查找重复项所花费的时间。但是，如果对象具有缓慢字典属性和原型链上的许多键，则UnionOfKeys将成为瓶颈，因为每次输入for-in时我们都必须收集可枚举的属性名称。

除了性能问题之外，现有算法还存在另一个问题，即它不符合规范。V8多年来错误地使用了以下示例：

1
2
3
4
5
6
7
var o = {
  __proto__ : {b: 3},
  a: 1
};
Object.defineProperty(o, 'b', {});

for (var k in o) console.log(k);

输出：

1
2
a
b

也许违反直觉，这应该只打印出a，而不是a和b。如果你回想一下本文开头的规范文本，那么步骤G和J意味着原型链上接收器跟踪属性上的非可枚举属性。

为了使事情变得更复杂，ES6引入了代理对象，这打破了很多V8代码的假设。要以符合规范的方式实现for-in，我们必须在总共13个不同代理陷阱中触发以下5个。

Internal method Handler method
[[GetPrototypeOf]] getPrototypeOf
[[GetOwnProperty]] getOwnPropertyDescriptor
[[HasProperty]] has
[[Get]] get
[[OwnPropertyKeys]] ownKeys

这需要原始GetEnumKeys代码的重复版本，该代码试图更紧密地遵循规范示例实现。ES6代理和缺少处理跟踪属性是我们重构如何提取所有keys在2016年初的核心动机。

The KeyAccumulator

我们引入一个单独的辅助类KeyAccumulator，它处理收集的for-in键的复杂性。随着ES6规范的发展，像Object.keys或Reflect.ownKeys这样的新特性需要它们自己的略微修改收集keys。通过使用单一的可配置位置，我们可以提高for-in的性能并避免重复代码。KeyAccumulator由一个快速部分组成，它只支持一组有限的操作，但能够非常有效地完成这些操作。慢累加器支持所有复杂的情况，如ES6代理。

为了正确过滤跟踪属性，我们必须维护一个单独的非可枚举属性列表，这些属性是我们到目前为止所看到的不可枚举的属性。出于性能原因，我们只有在弄清楚对象的原型链上有可枚举的属性之后才这样做。

Performance improvements

有了KeyAccumulator，一些模式就变得可行了。第一步是避免原始UnionOfKeys方法的嵌套循环，这种循环会导致缓慢的角点情况。在第二步中，我们执行了更详细的预检查，以利用现有的EnumCaches并避免不必要的复制步骤。

为了说明符合规范的实现更快，让我们看看以下四个不同的对象：

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
var fastProperties = {
  __proto__ : null,
  'property 1': 1,
  …
  'property 10': n
};

var fastPropertiesWithPrototype = {
  'property 1': 1,
  …
  'property 10': n
};

var slowProperties = {
  __proto__ : null,
  'dummy': null,
  'property 1': 1,
  …
  'property 10': n
};
delete slowProperties['dummy']

var elements = {
  __proto__: null,
  '1': 1,
  …
  '10': n
}

下图比较了在没有优化编译器的情况下，在紧密循环中运行for-in循环一百万次的原始性能。

正如我们介绍的那样，这些改进在维基百科和Facebook上变得非常明显。

除了Chrome 51中的初步改进之外，第二次性能调整还带来了另一项重大改进。下图显示了我们在Facebook页面启动期间花在脚本上的总时间的跟踪数据。V8的37937版本的选定范围相当于额外4％的性能提升！

avatar

为了强调改进for-in的重要性，我们依赖于我们在2016年建立的工具中的数据，这些数据允许我们在一组网站上提取V8测量值。下表显示了Chrome 49在大约25个代表性真实网站上的V8 C++入口点（运行时函数和内置函数）所花费的相对时间。

Position Name Total Time
1 CreateObjectLiteral 1.10%
2 NewObject 0.90%
3 KeyedGetProperty 0.70%
4 GetProperty 0.60%
5 ForInEnumerate 0.60%
6 SetProperty 0.50%
7 StringReplaceGlobalRegExpWithString 0.30%
8 HandleApiCallConstruct 0.30%
9 RegExpExec 0.30%
10 ObjectProtoToString 0.30%
11 ArrayPush 0.20%
12 NewClosure 0.20%
13 NewClosure_Tenured 0.20%
14 ObjectDefineProperty 0.20%
15 HasProperty 0.20%
16 StringSplit 0.20%
17 ForInFilter 0.10%

对for-in最重要的帮助在第5和第17位，平均占网站脚本总时间的0.7％。在Chrome 57中，ForInEnumerate已降至总时间的0.2％，ForInFilter由于汇编程序写入的快速路径而低于测量阈值。

如果对你有帮助，可以请我喝杯咖啡

avatar