JavaScript

Optimization: Minimize look-ups in for loops.

In JavaScript, like in many other languages a loop can be defined in many ways. The standard of course is the for-loop, the while loop, or do while loop. They are all natively implemented in JavaScript and benefit from the just in time compiler to be optimized for speed. There is recursion too that can be considered a loop, but let's limit ourselves to the native ones.

When I started learning JavaScript, the simplest way to iterate through sets of values was using a for-loop. Here is a simple example of it being used.

// Select elements by class name. This was in 2009 so bear with me
var allElements = document.getElementsByTagName("*");
var elements = new Array();
var className = "selected";

for(var i = 0; i < allElements.length;i++){
    if (allElements[i].className.indexOf(className) != -1 ) {
        elements.push(allElements[i]);
    }
}

console.log(elements); 
// all elements with selected class name.

This worked pretty well. You can wrap it in a function and call it whenever you need to get an element by its class name. However, there are a few things that are redundant.

For each iteration of the loop, we are access a property of the allElements object.

V8 design docs

Most JavaScript engines use a dictionary-like data structure as storage for object properties - each property access requires a dynamic lookup to resolve the property's location in memory. This approach makes accessing properties in JavaScript typically much slower than accessing instance variables in programming languages like Java and Smalltalk.

If I wrote it like this it would be easier to understand: allElements["length"]. When we run our loop, this object property look up happens as many times as the total number of elements. It would be nice if we can do the look up only once and get over it. Well we can.

for (var i = 0, l = allElements.length; i < l; i++)

Now the value of the length property is saved once in a variable l for length, and the condition only has to compares two literals, which is much faster.

Unfortunately, inside our loop there are also other problems. Inside the if statement we are checking if the class name exists, to do so we are using another look up: allElements[i]. And when we meet our condition, we are doing the same look up again to append it to our array. We can fix this in two steps.

First we can save that element in a variable so we don't have to do the look up multiple times.

for (var i = 0, l = allElements.length; i < l; i++) {
    var currentElement = allElements[i];
    if (currentElement.className.indexOf(className) != -1 ) {
        elements.push(currentElement);
    }
}

This is a great improvement and it makes it easier to read. We could call it a day but there is one little thing that isn't quite right. In JavaScript, creating a new variable in a for-loop doesn't add it to a new scope. Instead, the variable is hoisted up to the top of the current scope. For each iteration we are hoisting up a new variable that overwrites the previous one. To fix this, we can declare the variable outside of the loop.

var allElements = document.getElementsByTagName("*"),
    elements = [],
    className = "selected",
    currentElement = null;

for (var i = 0, l = allElements.length; i < l; i++) {
    currentElement = allElements[i];
    if (currentElement.className.indexOf(className) != -1 ) {
        elements.push(currentElement);
    }
}

Note that I also combined the variable declarations. Only one var is used at the top followed by a comma to separate each assignment. Now comes one questions. Optimization or Readability.

We can optimize it some more by moving the second var out of the for-loop since it is going to get hoisted up anyway.

var allElements = document.getElementsByTagName("*"),
    elements = [],
    className = "selected",
    currentElement = null,
    i = 0,
    l = allElements.length;

for (; i < l; i++) {
    currentElement = allElements[i];
    if (currentElement.className.indexOf(className) != -1 ) {
        elements.push(currentElement);
    }
}

But now we get this funky looking for loop: for (; i < l; i++). Although it works just the same and limits the code to do only what it is supposed to do at a slightly faster speed, it might confuse the next developer that has to maintain your code. At points like this, I always choose readability over optimization.


Now that we optimized our loop the question is, was it worth it? How much more speed are we gaining by doing this. The answer is very little. Especially if you are going to run this function only once at a time, the gain is negligible. But, if you are doing something like game programming, or animations, having this sort of mentality will go a long way.

Games usually work using a main loop: A controlled infinite loop that drives the entire game. So in order to obtain the maximum frames per second it's important to make sure your code is not doing anything unnecessary. Removing some extra look ups may help you meet your goals, and hopefully keep the code readable enough so you can always work on it.


Comments

There are no comments added yet.

Let's hear your thoughts

For my eyes only