Adding Time Complexity Annotation Where Applicable

[torressam333]

It would be cool if the MDN docs included performance and efficiency data within the documentation.
For example when looking at concat() vs push() methods for combing arrays, knowing the Big O time and space complexity of the methods would be useful.

Just an idea, what do you all think?

[ghost]

The ECMAScript specification does give algorithms that engines should follow, and we can analyse their Big-O notation complexities, but engines are only required to act "as if" following such algorithms, therefore are open to implementations that, for example, completely elude memory usage for a particular algorithm, or possibly (although unlikely) perform more internal work therefore this doesn't seem possible to accurately describe what performance characteristics can be expected.

Take Array#unshift: this could be amortized to an O(log(n)) operation in engine implementations that keep a base pointer in their array data structure and allocate memory on both ends when deemed necessary, yet other engines may decide to implement the operation in such a manner requiring a full copy, thus O(n), while another engine may decide to implement their arrays and strings both using ropes, so their shifting operations act more like that of a linked-list, that is, exhibiting O(1) for appending.

Another example is from the the specification for WeakSet, WeakMap, Set, and Map:

WeakSets must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structure used in this specification is only intended to describe the required observable semantics of WeakSets. It is not intended to be a viable implementation model.

[Josh-Cena]

To follow-up: engines often have a "fast path" and a "slow path". If it decides that the underlying behavior is not observable, it can take a very optimized path; otherwise (especially with Proxies), it needs to follow the spec-defined procedure step-by-step (possibly invoking a lot of custom JS code), which often makes it slower by orders of magnitude.

[torressam333]

@Josh-Cena this is great info? Can you provide a link to a relevant source so I can read up more on this particular topic (js engine paths/decisions)?

[Josh-Cena]

Oh—I have to admit it's mostly hearsay and don't quote me on this. Engine implementers talk about it often, and it leads to proposals like https://github.com/tc39/proposal-rm-builtin-subclassing

[ghost]

So, I didn't use the idea of "fast paths," because engines don't really change the time complexity of the code - that is, it still scales the same, but with less variables involved. This allows specialization, resulting in potentially significant performance gain.

Here's an example of a specific V8 "fast path": https://v8.dev/blog/spread-elements.
They start to elude operations under some conditions, yet the Big-O time complexity remains the same: there are still n element copies, whereas before it was n element copies and n iterator .next() calls. That could be represented as O(n + n), which coalesces to O(n), thus both are O(n). (Although, technically, as the normal spreading required array reallocations, we might consider it to be O(n * log(n)))

There are also plenty of "fast paths" that primarily revolve around compilation of JavaScript to superior assembly code generation, which still falls under the same umbrella.

Now, consider if you have a loop of n iterations performing no operations in the body, or only consisting of dead code? This is O(n), but can be removed and therefore be O(1).

An example of the concept in general: https://compileroptimizations.com/category/dead_code_elimination.htm

[Josh-Cena]

Yes—most optimizations should still be constant-level. O(n) to O(log(n)) or even O(1) sounds very aggressive😄 However, at the normal scale of JS apps, it could still be a 100x improvement.

[torressam333]

@phosra I see your point and it is very valid. The ECMA standard is explicit but the time/space complexity is too dependent on the particular JS engine. Great response, thanks!