Why Is Array.includes An Order Of Magnitude Faster Than Set.has In Javascript?

Well having grown up in C++, I am always conscious about what algorithm would fit what. So when I notice the application started to behave sluggish on mobile phones I immediately s

Solution 1:

I'll start by stating that I'm not an expert on JavaScript engine implementations and performance optimization; but in general, you should not trust these kind of tests to give you a reliable assessment of performance.

Time complexity of the underlying algorithm only becomes a meaningful factor over very (very) large numbers, and as a rule of thumb, 1000 is certainly not such a large number, especially for a simple array of integer values.

Over a small amount of millisecond-timed operations, you are going to have many other things happening in the engine at a similar time scale that will throw your measurements off wildly. Optimizations, unexpected overheads, and so on.

As an example, I edited your tests by simply increasing the size of the array to 100,000. The results on my poor old laptop look like this:

arr.includes(-1); //3,323 Ops/s
arr.includes(0); //6,132 Ops/s
prebuildset.has(-1); //41,923,084 Ops/s
prebuildset.has(0); //39,613,278 Ops/s

Which is, clearly, extremely different from your results. My point is, don't try to measure microperformance for small tasks. Use the data structure that makes the most sense for your project, keep your code clean and reasonable, and if you need to scale, prepare accordingly.