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

问题描述

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

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

节点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比set.has快10倍，比array.indexOf快近6倍？

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

3. set.has在节点9中似乎比以前在节点6中慢，这是为什么？

推荐答案

：V8的turbofan当前优化C++中的本机方法调用Map.has()，但不调用Set.has()。

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

答案深入到turbofan，V8的JIT编译器如何进行优化。它利用节点海概念，您可以认为它是AST for优化。V8通过用更快的表示(约简)替换节点海洋中的一些子树来进行优化。最简单的缩减示例是将a = 1 + 2替换为a = 3。

这样做的一个强大功能是，它可以用对底层C++实现的调用替换某些JS方法调用，以消除开销。请参阅官方幻灯片，特别是this link中的几页，以查看其功能示例。

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

在V8的js-call-reducer.cc中，Map.has的JSCall将替换为本机函数调用：

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中的源代码。)

但是没有ReduceMapPrototypeHas方法，所以Set.has没有这样的优化。这就是Set.has()比Map.has()慢的原因。

我确认了本地构建的V8并替换为下面的代码，使得Set.has和Map.has基准测试结果几乎相同。

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

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

(我不知道为什么升级节点6.2.0->；9.4.0会使Set.has()慢3倍。)

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

这篇关于为什么map.has比set.has和array.indexOf快这么多？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！