Mistake Explanation

If you omit a line like x = test() || x from your benchmarking code, the compiler is able to skip doing the work that you think it's doing. My original test that gave fast results looked like:

for (let i = 0; i < 10_000; i++) {
  testArray.includes(randomKeys[i]);
}

I'm still not sure what Node.js is doing there. The real test should look like:

let magic = true;
for (let i = 0; i < 10_000; i++) {
  magic = testArray.includes(randomKeys[i]) || magic;
}

This shows Array.includes starts being slower than keyed Object access at around 10 items & is about 10x slower than object access at ~100 items. Here's a gist if you want to repro.

Node.js Array.includes is faster than you'd expect [INCORRECT BELOW THIS POINT]

This is incorrect! My benchmark was written in a way that allowed the compiler to skip doing work I thought it was doing.

I've done a few Advent of Code problems, and one thing that's occasionally tripped me up has been my erroneous assumption that accessing the key of an object is fast. It's a fast constant time operation, but whatever hashing node is doing internally to find a key can sometimes be a performance hot-spot. There's a massive difference in speed between Array[index] and Object[key], and that made me start to wonder whether Object[key] was slow enough that there were situations where it'd make more sense to use Array.includes instead.

When I benchmarked it, I was pretty astounded to see that on a sorted array, Array.includes is faster on arrays of 10,000 strings than Object[key]. Internally, I'm guessing Array.includes is using binary-search when it knows that the array is sorted, which is a cool optimization! Here's the gist if you want to test it out. (I'm running these tests on Node 14 on a Mac Mini)

What about unsorted arrays?

When the array is unsorted, Object[key] look-ups start beating Array.includes pretty quickly: once we have ~20 documents, we'd expect to see faster look-ups from keyed object access. This is much more in line with what I expected when setting up this test.

What about Set.has?

Set.has is consistently slower than Object[key]. It can handle more cases than Object[key] can, but from a speed perspective, it's not in the running. I still often use it over Object[key] because I think it does a better job of expressing the intent to someone who's reading the code, and it's still a fast-enough constant time look-up.

What does this all mean?

Absolutely nothing! I still use Set.has for the majority of situations where I need to check membership in a list. For most of the code I write, expressing clear intent is far more important than optimizing performance, and I have yet to profile non-Advent-of-Code performance and find Object[key] or Set.has being a hotspot.

Benchmark Results

         10 object access x 25,715,807 ops/sec ±0.70% (94 runs sampled)
         10 set x 18,422,013 ops/sec ±0.85% (96 runs sampled)
         10 array x 28,105,533 ops/sec ±0.88% (89 runs sampled)
Fastest for ordered 10 is array
         40 object access x 20,175,473 ops/sec ±0.90% (92 runs sampled)
         40 set x 19,632,409 ops/sec ±0.73% (92 runs sampled)
         40 array x 27,999,865 ops/sec ±1.09% (94 runs sampled)
Fastest for ordered 40 is array
         100 object access x 21,842,706 ops/sec ±0.70% (95 runs sampled)
         100 set x 18,283,045 ops/sec ±0.78% (95 runs sampled)
         100 array x 27,860,691 ops/sec ±1.03% (94 runs sampled)
Fastest for ordered 100 is array
         1000 object access x 20,026,184 ops/sec ±0.82% (92 runs sampled)
         1000 set x 14,656,626 ops/sec ±1.37% (89 runs sampled)
         1000 array x 23,392,774 ops/sec ±1.31% (90 runs sampled)
Fastest for ordered 1000 is array
         10000 object access x 14,367,754 ops/sec ±0.58% (93 runs sampled)
         10000 set x 12,213,161 ops/sec ±0.51% (95 runs sampled)
         10000 array x 28,067,504 ops/sec ±0.94% (92 runs sampled)
Fastest for ordered 10000 is array
         100000 object access x 9,106,145 ops/sec ±1.55% (93 runs sampled)
         100000 set x 7,918,164 ops/sec ±0.92% (91 runs sampled)
         100000 array x 78,374 ops/sec ±58.42% (86 runs sampled)
Fastest for ordered 100000 is object access
         1000000 object access x 3,296,346 ops/sec ±1.05% (93 runs sampled)
         1000000 set x 2,076,943 ops/sec ±1.24% (91 runs sampled)
         1000000 array x 490 ops/sec ±3.50% (40 runs sampled)
Fastest for ordered 1000000 is object access
         10 object access x 24,869,178 ops/sec ±0.80% (91 runs sampled)
         10 set x 19,181,356 ops/sec ±0.98% (92 runs sampled)
         10 array x 27,691,570 ops/sec ±0.99% (90 runs sampled)
Fastest for random 10 is array
         40 object access x 27,450,529 ops/sec ±1.30% (86 runs sampled)
         40 set x 12,483,804 ops/sec ±1.30% (91 runs sampled)
         40 array x 16,590,091 ops/sec ±0.92% (92 runs sampled)
Fastest for random 40 is object access
         100 object access x 31,040,999 ops/sec ±1.24% (87 runs sampled)
         100 set x 12,386,070 ops/sec ±1.14% (91 runs sampled)
         100 array x 16,389,384 ops/sec ±1.22% (91 runs sampled)
Fastest for random 100 is object access
         1000 object access x 25,365,248 ops/sec ±1.52% (88 runs sampled)
         1000 set x 11,275,049 ops/sec ±1.51% (91 runs sampled)
         1000 array x 16,294,268 ops/sec ±1.23% (88 runs sampled)
Fastest for random 1000 is object access
         10000 object access x 16,907,288 ops/sec ±1.47% (89 runs sampled)
         10000 set x 8,905,038 ops/sec ±1.47% (91 runs sampled)
         10000 array x 14,777,156 ops/sec ±1.19% (91 runs sampled)
Fastest for random 10000 is object access
...