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

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

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

节点9.4.0：

set.has x 6,454,428 ops/sec ±1.25% (90 runs sampled)
map.has x 64,519,657 ops/sec ±0.95% (86 runs sampled)
arr.includes x 11,415,721 ops/sec ±1.41% (87 runs sampled)
arr.indexOf x 11,344,587 ops/sec ±1.39% (87 runs sampled)
arr.find x 1,579,635 ops/sec ±1.09% (92 runs sampled)
Fastest is map.has

节点6.2.0：

set.has x 16,677,473 ops/sec ±1.35% (86 runs sampled)
map.has x 15,089,503 ops/sec ±1.35% (85 runs sampled)
arr.includes x 1,345,019 ops/sec ±1.31% (89 runs sampled)
arr.indexOf x 15,943,213 ops/sec ±4.40% (80 runs sampled)
arr.find x 1,423,994 ops/sec ±2.05% (82 runs sampled)
Fastest is set.has,arr.indexOf

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

1. 怎么会map.has比 快 10 倍set.has几乎快 6 倍array.indexOf?

2. 在节点 6 中，includes似乎比慢得多indexOf, and arr.find(val => val === 1)是相同的arr.includes(1). Why?

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

UPDATE

现在V8有ReduceSetPrototypeHas方法，因此它将在较新版本的 Node.js 或浏览器中进行优化。

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

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

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

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

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

其超强功能之一是它可以用对底层 C++ 实现的调用来替换一些 JS 方法调用，以消除开销。请参阅官方幻灯片，尤其是其中的几页这个链接 https://docs.google.com/presentation/d/1sOEF4MlF7LeO7uq-uThJSulJlTh--wgLeaVibsbb3tc/edit#slide=id.g5499b9c42_089查看其功能的示例。

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

In js-call-reducer.cc https://github.com/v8/v8/blob/65d9c441dfad3d06d5a2cf2857a71e2388e10d6f/src/compiler/js-call-reducer.cc#L7223 of V8, JSCall of Map.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实际上查找哈希表的系列方法。查看源代码来自here http://%20https://github.com/v8/v8/blob/65d9c441dfad3d06d5a2cf2857a71e2388e10d6f/src/builtins/builtins-collections-gen.cc#L2403.)

But 没有ReduceSetPrototypeHas method，所以没有进行这样的优化Set.has。这就是为什么Set.has()慢于Map.has().

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

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

我不确定是否Set.has是否应该优化，因为 V8 应该优化现实世界的应用，不适用于微基准测试结果。 （我也不知道添加新的减少量的缺点是什么以及有多大。）

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

See https://v8.dev/docs/turbofan https://v8.dev/docs/turbofan了解 TurboFan 内部结构的更多资源。