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:

1. How come map.has is 10 times faster than set.has and almost 6 times faster than array.indexOf?

2. 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?

3. set.has seems to be slower in Node 9 than it used to be in Node 6, why is that?

Answer 1

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.