Chrome JavaScript:为什么map.has比set.has和array.indexOf快这么多?

jpfvwuh4  于 2023-02-01  发布在  Go
关注(0)|答案(1)|浏览(118)

我遇到了以下基准: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.hasset.has快10倍,比array.indexOf快6倍?
1.在节点6中,includes似乎比indexOf慢很多,而arr.find(val => val === 1)arr.includes(1)相同,为什么?

  1. set.has在节点9中似乎比以前在节点6中慢,这是为什么?
weylhg0b

weylhg0b1#

    • 更新**

现在V8有了ReduceSetPrototypeHas方法,所以在Node.js或浏览器的新版本中会对其进行优化。
https://github.com/v8/v8/commit/4c81827c8d6ca1d3d9b0cb6a2ef1264eb0f59524

    • TL; DR**:V8的TurboFan当前优化了Map. has()调用到C++世界中的本地方法调用,但未优化Set. has()调用。

不,为什么Map比设定快?
这也很有趣,因为它们必须使用相同的哈希表内部实现。
答案在于V8的JIT编译器TurboFan是如何进行优化的。它利用了节点之海的概念,你可以认为它是用于优化的AST。V8通过将节点之海中的一些子树替换为更快的表示(约简)来进行优化。最简单的约简示例是将a = 1 + 2替换为a = 3
它的一个超级强大的功能是它可以将一些JS方法调用替换为对底层C++实现的调用,以消除开销。请参见官方幻灯片,特别是此链接中的几页,以查看它的功能示例。
然后,查看代码中发生实际缩减的地方。
在V8的www.example.com中,Map.hasJSCall将替换为本地函数调用:js-call-reducer.cc of V8, JSCall of Map.has will be replaced with native function calls:

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.hasMap.has基准测试结果几乎相同。

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

我不确定是否应该优化Set.has,因为V8应该针对真实世界的应用进行优化,而不是针对微基准测试结果进行优化(我也不知道添加新的reduction的缺点是什么,有多大)。
(我不知道为什么升级节点6.2.0-〉9.4.0会使Set.has()慢3倍。)
有关TurboFan内部构件的更多资源,请参见https://v8.dev/docs/turbofan

相关问题