.includes() algorithm and speed?

Question

I'm interested to know what algorithm the .includes() method uses? Does it use a modularized hash like rabin karp?

I'm somewhat hesitant to use .includes() without knowing more about its methodology and speed. The documentation I've found doesn't go into specifics when discussing it (e.g. https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/String/includes)

Shandra

I always thought it used indexOf underneath it, but I'm not sure... – Penza

It's most likely just syntactic sugar, and uses the same methods as indexOf under the hood, but how it's actually implemented is up to the vendors. – Illiquid

The implementation is undefined. You're asking for an analysis of the source of every JavaScript engine. Some will perform better and some will perform worse than you expect. – Christlike

check out the polyfill in the link you mention above -- it shows a sample implementation (somewhat naive): developer.mozilla.org/en/docs/Web/JavaScript/Reference/… – Fijian

Answer 1

Given that different engines could implement .includes in different ways, it may be difficult to make blanket statements regarding implementation. However it should be possible to get an idea of it's speed by doing some benchmarking (as testing is likely the only way to be sure).

Using node 7.0 I tried testing three different functions:
1. includes(), passing in a sequential array
2. a basic for loop, passing in a sequential array
3. has(), passing in a precreated set from a sequential array

The results I obtained suggested the length of the array itself didn't seem to matter(as hoped), but how far the desired number was from the start did. For finding numbers at indexes <20 or so, the for loop seems slightly faster (by perhaps ~15%?). For larger indexes includes() over takes the for loop (being ~2-3x times faster by index 500 seemingly). However .has() is vastly faster for finding numbers at later indexes (~25-30x faster by index 800) and the size of the indexes seems to have little impact on its speed (but creating the set takes time).

Admittedly these are somewhat limited tests and many factors could impact them. One interesting result was that if a set was created from the passed in array (and not some other array), even if the set wasn't passed into the functions, it seemed to increase the speed of includes, and decrease the speed of the for loop function slightly. Some type of caching which somehow benefits .includes() I'd assume?

Oops

Answer 2

The Rabin-Karp algorithm is a string searching algorithm, but you've linked the Array includes() algorithm, which, unlike a string search, is not sequence-dependent. The ECMA specification describes its behavior in a way that dictates implementation: it applies SameValueZero to each element in ascending order. Given that description, any normal algorithm will be O(n) time and O(1) memory.

String.indexOf, on the other hand, doesn't have such a picky specification, and V8 uses a Boyer-Moore-Horspool string search implementation.

Nitro