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 ...

YUI Port of jQuery TipTip Plugin

This article explains and shares the implementation of the light-weight jQuery plugin TipTip port to YUI. The goal is to clone the plugin behavior, as closely as possible, using YUI.

Getting ready

Read up on the TipTip tooltip plugin. You will find all the documentation for configuring the TipTip widget: TipTip jQuery Plugin. The YUI code is a clone of version 1.3.

How do it…

Download and include the yui.tiptip.plugin in ...

Custom Events for Scrolling Towards Element Margins Plugin

As per Nate's recommendation, I have rewritten the Custom Events for Scrolling Towards Element Margins YUI module to leverage the plugin system of YUI. This way you can add it to any existing widget, instead of running it as a standalone.

Getting ready

Here is the complete source code (ScrollActionerPlugin.js):
YUI.add('scroll_actioner_plugin', function(Y) { var BOUNDING_BOX = 'boundingBox', VIEWPORT_REGION = 'viewportRegion', Lang = Y.Lang; // A plugin class designed to animate Widget's show ...

Custom Events for Scrolling Towards Margins

There is an emerging UI pattern, where additional content is loaded when the user scrolls to the bottom of an element or page. This can be seen on the Facebook newsfeed, or many applications on touch-driven mobile devices. Today's article describes a YUI 3 widget that we use on Votizen.com, which will fire an event when the user scrolls to the border of an element.

Getting ready

Here is the complete source code (ScrollAction.js): ...

Simplified Text Replacement in HTML

JavaScript developers frequently have to replace parts of text on a webpage. Sometimes it is a hassle, as there are multiple small pieces of text that need to be replaced inside of a larger element (such as numbers or madlibs). Today's code snippet finds each var node inside of a parent element and returns an object with a substitute function. This function simplifies replacing the content inside the var elements.

Getting started…

Create HTML markup ...

Sharing Static Data Between YUI 3 Instances

YUI 3 does an excellent job of sandboxing instances so that you cannot accidentally contaminate objects or data. However, sometimes you need to share data between instances, such as if you have a global click handler that dispatches events. Otherwise, each time you include the module, the global data or event is duplicated. Therefore, we need a good way to occasionally share data between instances.

How do it…

As with most problems, there are ...

Template String Replacement Function

Today’s article introduces an efficient method for replacing template values in a JavaScript string. Although, concatenating strings together is the default way that JavaScript programmers insert values into a string, using a replacement function can lead to more readable code. Additionally, the replacement function is fast enough that it rarely affects performance.

Getting ready

In the following example, several values are concatenated into a string:
var http = "https:" == document.location.protocol ? "https" ...

Getting Started With Node-JS

I attended the Node-JS Camp this past week and had a lot of fun talking with the developers, and familiarizing myself with the awesomeness of Node-JS. Node-JS is a powerful version of JavaScript that allows for server-side scripting and running light-weight web servers. The best part is, if you know client-side JavaScript, you know the basics of server-side JavaScript, and only need to learn how to import and use the built in libraries. Todays ...

Legacy Support for HTML 5 Forms

As discussed in the article, HTML 5 Feature Detection Using Modernizr, HTML 5 contains many new input types and attributes. While, most new browsers support them (although often imperfectly), the majority of people still use browsers that do not. However, we can use JavaScript to provided legacy support for the new HTML 5 input attributes and types in browsers that lack support. Toadys article introduces a widget for the YUI 3 gallery, that emulates ...