JavaScript: How come map.has is so much faster than set.has and array.indexOf?

Question

I came across the following benchmarks: https://jsperf.com/array-includes-and-find-methods-vs-set-has If you'll execute it, you'll see that map.has is by far the most efficient way of finding an item in a collection in the browser.

I also recreated this test in Node using benchmarks.js, and got the following results:

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

Node 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

These results are very surprising for me, does anyone know:

How come map.has is 10 times faster than set.has and almost 6 times faster than array.indexOf?
In Node 6, includes seems to be much slower than indexOf, and arr.find(val => val === 1) is the same as arr.includes(1). Why?
set.has seems to be slower in Node 9 than it used to be in Node 6, why is that?

Because a Set is implemented as a hash set, which doesn't need to do linear search? That's the whole purpose of using it over a list structure. — Bergi
– Bergi, Commented Apr 15, 2018 at 12:41
has of Map and indexOf do two complelty differnt things. indexOf searches for a value (that might exists multible times in an array). And has for an key that has to be unique. — t.niese
– t.niese, Commented Apr 15, 2018 at 12:47
Thanks guys! but still, why Map.has is ten times faster than Set.has? — Eliran Pe'er
– Eliran Pe'er, Commented Apr 15, 2018 at 12:47
None of them should be significantly faster then the other. Because both should use the same way of hashing and lookup. So the results of 6.2.0 for has is what I would expect. At the end of 2017 they closed JS Maps and Sets Performance, but when those changes in v8 are included into node Performance regression in v8.10 and v9.0 for Maps with object keys depends on when node updates v8. — t.niese
– t.niese, Commented Apr 15, 2018 at 16:02

ypresto · Accepted Answer · 2023-01-31 16:57:48Z

UPDATE

Now V8 has ReduceSetPrototypeHas method, so it would be optimized in newer version of Node.js or browsers.

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

TL;DR: V8's TurboFan currently optimize Map.has() call into native method call in C++ world, but not Set.has() call.

No, how come Map.has is way faster than Set.has?

This is also very interesting, because they must use the same internal implementation of hash table.

The answer dives into how TurboFan, JIT compiler of V8, does optimization. It utilizes Sea of nodes concept, you can think it is AST for optimization. V8 does optimization by replacing some subtree in the sea of nodes with faster representation (reduction). Simplest example of reduction is replacing a = 1 + 2 to a = 3.

One of the super power of this would be that it can replace some JS method calls with a call to underlying C++ implementations to remove overhead. See the official slide, especially a few pages from this link to see examples of what it does.

Then, look into the code where actual reduction happens.

In 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 is tied to FindOrderedHashTableEntry family methods which actually looks up the hash table. Look source code from here.)

But there is no ReduceSetPrototypeHas method, so such optimization is not done for Set.has. This is why Set.has() is slower than Map.has().

I confirmed that local-built V8 with replacing to below code makes Set.has and Map.has benchmark result almost the same.

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

I'm not sure whether Set.has should be optimized or not, because V8 should optimize for real-world application, not for micro-benchmark result. (I also don't know what is and how large the drawback for adding new reduction.)

(I have no idea why upgrading Node 6.2.0 -> 9.4.0 make Set.has() 3 times slower.)

See https://v8.dev/docs/turbofan for further resources of TurboFan internals.

Someone please mark this answer as the correct one. The value is insane.

Collectives™ on Stack Overflow

JavaScript: How come map.has is so much faster than set.has and array.indexOf?

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related