JavaScript：为什么map.has比set.has和array.indexOf快这么多？

Question

我遇到了以下基准：https://jsperf.com/array-includes-and-find-methods-vs-set-has \n如果你执行它，你会发现这map.has是迄今为止最在浏览器中查找集合中的项目的有效方法。

\n\n

我还在 Node 中使用重新创建了这个测试benchmarks.js，并得到了以下结果：

\n\n

节点9.4.0：

\n\n

set.has x 6,454,428 ops/sec \xc2\xb11.25% (90 runs sampled)\nmap.has x 64,519,657 ops/sec \xc2\xb10.95% (86 runs sampled)\narr.includes x 11,415,721 ops/sec \xc2\xb11.41% (87 runs sampled)\narr.indexOf x 11,344,587 ops/sec \xc2\xb11.39% (87 runs sampled)\narr.find x 1,579,635 ops/sec \xc2\xb11.09% (92 runs sampled)\nFastest is map.has\n

\n\n

节点6.2.0：

\n\n

set.has x 16,677,473 ops/sec \xc2\xb11.35% (86 runs sampled)\nmap.has x 15,089,503 ops/sec \xc2\xb11.35% (85 runs sampled)\narr.includes x 1,345,019 ops/sec \xc2\xb11.31% (89 runs sampled)\narr.indexOf x 15,943,213 ops/sec \xc2\xb14.40% (80 runs sampled)\narr.find x 1,423,994 ops/sec \xc2\xb12.05% (82 runs sampled)\nFastest is set.has,arr.indexOf\n

\n\n

这些结果对我来说非常令人惊讶，有谁知道：

\n\n

\n

1. 为什么map.has比 快 10 倍set.has和几乎 6 倍array.indexOf？

\n

2. 在 Node 6 中，includes似乎比 慢得多indexOf，并且arr.find(val => val === 1)与 相同arr.includes(1)。为什么？

\n

3. set.hasNode 9 中的速度似乎比 Node 6 中的速度要慢，这是为什么呢？

\n

\n

Answer 1

更新

现在V8有了ReduceSetPrototypeHas方法，所以它会在新版本的Node.js或浏览器中进行优化。

https://github.com/v8/v8/commit/4c81827c8d6ca1d3d9b0cb6a2ef1264eb0f59524

TL;DR：V8 的 TurboFan 目前将 Map.has() 调用优化为 C++ 世界中的本机方法调用，但没有优化 Set.has() 调用。

不，为什么 Map.has 比 Set.has 快得多？

这也很有趣，因为它们必须使用相同的哈希表内部实现。

答案深入到V8 的 JIT 编译器TurboFan如何进行优化。它利用了Sea of​​ Nodes的概念，你可以认为它是用于优化的AST。V8 通过用更快的表示（缩减）替换节点海中的一些子树来进行优化。最简单的减少示例是替换a = 1 + 2为a = 3.

其超强功能之一是它可以用对底层 C++ 实现的调用来替换一些 JS 方法调用，以消除开销。请参阅官方幻灯片，尤其是此链接中的几页，以查看其功能的示例。

然后，查看实际减少发生的代码。

在V8的js-call-reducer.ccJSCall中， ofMap.has将被替换为原生函数调用：

Reduction JSCallReducer::ReduceMapPrototypeHas(Node* node) {
  ...(reading current nodes)...

  Node* table = effect = graph()->NewNode(
      simplified()->LoadField(AccessBuilder::ForJSCollectionTable()), receiver,
      effect, control);

  Node* index = effect = graph()->NewNode(
      simplified()->FindOrderedHashMapEntry(), table, key, effect, control);

  Node* value = graph()->NewNode(simplified()->NumberEqual(), index,
                                 jsgraph()->MinusOneConstant());
  value = graph()->NewNode(simplified()->BooleanNot(), value);

  ReplaceWithValue(node, value, effect, control);
  return Replace(value);
}

（与实际查找哈希表的系列方法FindOrderedHashMapEntry相关。从这里查看源代码。）FindOrderedHashTableEntry

但没有ReduceSetPrototypeHas办法，所以没有做这样的优化Set.has。这就是为什么Set.has()比 慢的原因Map.has()。

我确认本地构建的 V8 替换为以下代码后Set.has与Map.has基准测试结果几乎相同。

Reduction JSCallReducer::ReduceMapPrototypeHas(Node* node) {
  return NoChange();
}

我不确定是否Set.has应该优化，因为 V8 应该针对实际应用程序进行优化，而不是针对微基准测试结果。（我也不知道添加新的减少量的缺点是什么以及有多大。）

（我不知道为什么升级 Node 6.2.0 -> 9.4.0 会Set.has()慢 3 倍。）

有关 TurboFan 内部的更多资源，请参阅https://v8.dev/docs/turbofan 。