On traversing an array in Javascript

I was told by one of the awesome people I work with that the “standard” form for a for loop in Javascript is actually \( \mathcal{O}(n^2) \), so I became curious. Here’s my thoughts, but first, a Java example.

A Java example

I learned to program on Java (well, actually a Delphi/Pascal derivative, but we can all forget that), so I’m going to write an example of a for loop in Java for y’all. Ready?

It is super imperative that I show you my Java skills
public class ForLoop {
    public static void main(String[] args) {
        int[] arr = new int[]{0, 0, 0, 0, 0};
        for(int i = 0; i < arr.length; i++) {
            System.out.println(i + " out of " + arr.length); 
        }
    }
}

So why did I just waste your time with a Java for loop example? I’m not sure. The point was to show that length is a field and therefore has a constant time-complexity.

Java, as far as I understand, does not do field properties like C#, so there isn’t any secret getter methods we can’t immediately see.

A Javascript example

So here’s how I learned how to do a for loop in Javascript; I’ve understood it to run in \( \mathcal{O}(n) \) time.

I really love to Count.
var arr = [0, 0, 0, 0, 0];
for(var i = 0; i < arr.length; i++) {
    console.log(i + " indicies; ah, ah, ah.");
}
console.log(arr.length + ", " + arr.length + " indices!")

Pretty standard. If length is a property of Array.prototype (which is how it seems), then it should also be accessed in constant time. Even though arr.length is retrieved \( n \) times, the overall time-complexity is \( \mathcal{O}(n) \).

There is also another way to write an array iterator in Javascript.

Cached array length iterator
var arr = [0, 0, 0, 0, 0];
for(var i = 0, l = arr.length; i < l; i++) {
    console.log(i);
}

This grabs the length of the array once, then stores it for later use.

According to a recommendation at Impressive Webs and speed tests by Robert Nyman and jsPerf, arr.length is calculated from the array every time its requested (causing \( \mathcal{O}(n) \) time for just retrieval and \( \mathcal{O}(n^2) \) overall when called \( n \) times in the loop). This could mean that there is a setter and getter associated with Array.prototype.length.

Javascript getters and setters

I learned recently that Javascript supports getter and setter methods on its fields. These can be set and get-ed with the functions: __defineSetter__, __defineGetter__, __lookupSetter__, and __lookupGetter__.

So of course I tried all these things in different browsers:

Array.__lookupGetter__("length"); // undefined
Array.__lookupSetter__("length"); // undefined
Array.prototype.__lookupGetter__("length"); // undefined
Array.prototype.__lookupSetter__("length"); // undefined

Which leads me to believe that there is no getter or setter for the length property, though I could most likely be overlooking something.

Looking at the source code for Array in V8, I can’t find anywhere where length is explicitly calculated, but rather updated incrementally whenever there’s an operation on the array. (It’s worth noting that %GetArrayKeys(array, len) gets called on certain operations and probably doesn’t have constant time-complexity).

Conclusion

I really don’t know what to conclude with. According to the tests done by many people, it is definitely quicker to cache an array’s length before traversing it, but I can’t seem to find the getter function associated with Array.prototype.length or the associated source code.

I’m assuming that it takes longer because of how Javascript implementations store and retrieve things from memory, but I have no clue. I don’t think that the time-complexity is quite \( \mathcal{O}(n^2) \), but I have no authority making such a claim.

Is this useful?

Once you’re at the point in the development of your app where performance optimizations like the improving the time-complexity of a for loop over an array in Javascript have a real, quantifiable value, you can pat yourself on the back in knowing that everything else in your backend is as optimized as it possible could be.

So, is this useful? Probably not. To me, at least. But I maybe learned something today.