Recursive Function Performance - Static vs This

I recently solved a recursive problem in JavaScript, using a static function instead of adding the function to the prototype of the object I was working on. The pair programmer asked me why I choose to do it that way. After a few minutes discussion, I settled on two reason why I intuitively felt static functions are faster, especially for recursion: less scope lookups and better Just-In-Time compilation (JIT) optimizations. This article describes my hypothesis that static functions are faster and the results which clearly show using this in recursion does not meaningfully affect performance in modern browsers.

There is also a simple demo, so you can try it for yourself.

How do it…

For simplicity, a recursive function that calculates triangular numbers (sum of the current number and all positive integers smaller than it) will be used.

Here is the static triangular recursion function:

function triangular(curr) {
    if (1 === curr) {
        return curr;
    }
    else {
        return curr + triangular(curr - 1);
    }
}

Here is the prototype triangular recursion function:

function MathPrototype(n) {
    this.curr = n;
}
MathPrototype.prototype = {
    curr: 0,
    triangular: function() {
        if (1 === this.curr) {
            return this.curr;
        }
        else {
            return this.curr-- + this.triangular();
        }
    }
};

Here is the triangular recursion function attached to an object, instead of a function prototype:

var mathObject = {
    curr: 0,
    triangular: function() {
        if (1 === this.curr) {
            return this.curr;
        }
        else {
            return this.curr-- + this.triangular();
        }
    }
};

Here is the prototype triangular recursion function that attempts to force prototype scope lookup:

function MathPrototypeAdv(n) {
	this.curr[0] = n;
}
MathPrototypeAdv.prototype = {
	curr: [0],
	triangular: function() {
		if (1 === this.curr[0]) {
			return this.curr[0];
		}
		else {
			return this.curr[0]-- + this.triangular();
		}
	}
};

Try running the test yourself (will print to the console, may take up to 30s):

Recursion tests

How it works…

Below is an explanation of each method and some guesses about how the JIT is optimizing:

The static recursive function calls itself, so each call needs to search one level up the scope chain to find the recursive function as a variable. The rest of the function uses the passed local variable, performs a decr operation and passes the value into the recursive function, performs a simple arithmetic operation, and returns the result. Without knowing exactly what the JIT does, we can assume that it determines curr is an integer and optimizes the closure of triangular.

The prototype recursive function calls itself and keeps track of curr on this, so each call needs to search this for the recursive function and the variable to decriment. The rest of the function modifies the curr variable on this, performs a decr operation, performs an arithmetic operation, and returns the result. Since, we define curr on this in the constructor, we don’t actually need to lookup the variable on prototype. Without knowing exactly what the JIT does, we can assume that it determines curr is an integer and optimizes the references to this.

The object recursive function behaves and performs much like the basic prototype function.

I added an advanced prototype recursive function that uses an array attached to the prototype of the function for storing curr in an attempt to force traversal of the prototype scope chain. There is also a small overhead of accessing the index in the array, but array lookup time is negligible. The expectation is that each function execution requires a lookup first on this to see that curr is not there, and then a lookup on the prototype. In most browsers the JIT probably patches the prototype onto this to avoid the additional scope lookups, but otherwise behaves the same way as the basic prototype function.

The provided test function executes the recursive function 10,000 times using a value of 1,000 to calculate an arbitrary score for comparison. Here are the values I calculated:

MethodChrome v22FireFox v15Safari v6
static8322795189
object8522145432
prototype (this)9321275370
prototype (proto)15722655646

I immediately learned: 1) the JIT, in all browsers, does some sweet magic, because it was difficult to find an operation that could produce meaningful variants between the techniques (and even with variations the differences are measured in fractions of a microsecond), 2) the perfomance difference was negligible, and 3) the performance in FireFox is reverse of expectations. As usual, Chrome was blazing fast, an order of magnitude faster than other browsers. I was happy that Chrome and Safari behaved as expected, but was surprised that FireFox performs worse when using the static function. I attribute the difference in behavior to the JIT used by each browser (please comment if you know exactly how they work in these cases). In FireFox, my guess is that the JIT has special optimizations around accessing this that the other browsers do not use, which makes referencing this less expensive than searching the scope chain (even just one level), or it has poorer optimizations around the referencing variables on the scope chain, so accessing this outperforms scope chain lookups.

To get an idea of how negligible the recursion calls are on operation time, take the numbers from the test function and divide by the number of recursive calls (1,000) multipled by the number of iterations (10,000) or X/10,000,000, where X is the result, and subtract the variation values from each other. My hypethesis is true (except in FireFox), but the performance boost is negligible, and therefore it does not matter which recursion technique is used, instead use whichever you prefer.

Evaluating JavaScript Iteration Techniques

It has been a while since we looked at the performance of various iteration techniques in JavaScript. Since most developers use a JavaScript framework nowadays, you may not even be aware of the trade-offs being made each time you call $.each or your library’s equivalent iteration function. This article describes the four most common iteration techniques and how well they perform on several browsers, and compares it to the native browser Array.prototype.forEach.

Article updated on ...

Optmizing String Comparisons

This article will discuss a simple optimization to save you a few characters and a little performance when evaluating equality. In JavaScript, there are two types of equality: structural equality (==) where the content of two references are the same, and physical equality (===) where two object point to the same reference or are structurally equal and have the same object type. For the most part I use physical equality when comparing values, to ensure ...

Video on High Performance JavaScript

The guys at Plaxo have developed a large and powerful web application to help you keep in touch and up-to-date. In this video "Joseph Smart" discusses what they learned while developing their JavaScript driven application. There are some really great take aways and this is a must watch:

http://us.i1.yimg.com/cosmos.bcst.yahoo.com/player/media/swf/FLVVideoSolo.swf flashvars=id=3881103&emailUrl=http%3A%2F%2Fvideo.yahoo.com%2Futil%2Fmail%3Fei%3DUTF-8%26vid%3D1041101&imUrl=http%253A%252F%252Fvideo.yahoo.com%252Fvideo%252Fplay%253Fei%253DUTF-8%2526vid%253D1041101&imTitle=Joseph%2BSmarr%253A%2B%2526quot%253BHigh-performance%2BJavaScript%253A%2BWhy%2BEverything%2BYou%2526%252339%253Bve%2BBeen%2BTaught%2BIs%2BWrong%2526quot%253B&searchUrl=http://video.yahoo.com/search/video?p=&profileUrl=http://video.yahoo.com/video/profile?yid=&creatorValue=ZXJpY21pcmFnbGlh&vid=1041101 type=application/x-shockwave-flash width=425 height=350>

How To Improve YUI Dom hasClass

On my project, Mint, I have reached a point, where the code is mostly stable and decided to start looking for ways to improve the performance. I checked out various JavaScript profiling techniques, deciding that the Firebug profiler was probably the most accurate. I then started profiling the different pages and realized (to my surprise) that a lot of time spent in the YAHOO.util.Dom.hasClass method. I use getElementsByClass method a lot, so this ...

Faster Loops in JavaScript

I was writing an event handler function and realized that I was coding loops in a way that is not usually possible in other languages. Lets discuss this technique, which can help improve the run-time of certain iterative for loops. Suppose you have an event callback function with multiple triggers and a collection of something that you need to iterate through each time the callback function is made (like rows in a table or list ...

JavaScript Memory Leaks

On one of my projects, Mint.com, I recently noticed severe performance degradation in IE6 when the browser remains open. As it turns out a lot of the techniques used by various JavaScript Frameworks, and even my own JavaScript architecture, causes memory leaks. This is especially prominent in IE6, because its memory manager has poor heuristics for detecting JavaScript leaks. Its not as important in better browsers like, FireFox, but I do notice that Firefox ...