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.