Array.prototype.includes() can slow down your code

#javascript #performance

In this blog post, I explain when you should avoid Array.prototype.includes() and what you can use instead.

🚀 Not rocket science, or is it?

I ran into a performance issue on a recent project. After some debugging, I came across the following: There was an Array with a large amount of data. To check if a certain value is included Array.prototype.includes() was used. All this is not rocket science - or is it?

⏱ Time for performance measurements

Let's start with a simple measurement. An array with a million entries and we check if certain values are included in the array.

const arr = [...Array(1000000).keys()];

arr.includes(1);        // 0.077ms
arr.includes(10):       // 0.004ms
arr.includes(100);      // 0.003ms
arr.includes(1000);     // 0.003ms
arr.includes(10000);    // 0.014ms
arr.includes(100000);   // 0.113ms
arr.includes(1000000);  // 1.066ms

The value 1000000 is not included in the array - the runtime is already 1 second. Optimizing this is probably still considered micro-optimization. If you use Array.prototype.filter() in combination with Array.prototype.includes() for large data sets, the snail will overtake you!

But why?

The reason for this is the time complexity. Array.prototype.includes() and Array.prototype.filter() has a linear complexity (O(n)).

I found the following article that explains the Big O notation well:

Article No Longer Available

🐇 Almost always as fast as a rabbit

Let's take a look at Set.prototype.has() and compare the performance with Array.prototype.includes().

const arr = [...Array(1000000).keys()];
arr.includes(1000000); // 1.336ms

const arr = [...Array(1000000).keys()];
const setObj = new Set(arr)
setObj.has(1000000); // 0.016ms

Two simple examples with very different runtimes - 1.336ms vs. 0.016ms.

But why?

Set.prototype.has() has a constant complexity (O(1)) meanwhile Array.prototype.includes() has a linear complexity (O(N)).

⏱ More performance measurements

It makes no sense to replace Array.prototype.includes() with Set.prototype.has() everywhere, because it is not always faster. It's important to use functions with loops carefully. 😉

I performed a few benchmarks for this purpose, which you can see in the following table:

Value	`Array.prototype.includes()`	`Set.prototype.has()`	Result
1	836859994.45 ops/s ± 1.01%	176325072.58 ops/s ± 1.49%	`Set.prototype.has()` 78.93% slower
10	826996638.6 ops/s ± 0.95%	87438374.47 ops/s ± 6.73%	`Set.prototype.has()` 89.43% slower
100	800038628.18 ops/s ± 0.56%	143287118.03 ops/s ± 0.86%	`Set.prototype.has()` 82.09% slower
1000	590640746.37 ops/s ± 0.63%	171114526.18 ops/s ± 0.7%	`Set.prototype.has()` 71.03% slower
10000	96545.28 ops/s ± 1.06%	133468419.89 ops/s ± 1.69%	`Array.prototype.includes()` 99.93% slower
100000	9380.42 ops/s ± 0.96%	131819933.56 ops/s ± 0.82%	`Array.prototype.includes()` 99.99% slower