Have you encountered a case where you are suspicious about the performance issue in some part of the application and your concern was dismissed? Imagine a typical comment like:
Don’t worry. That function runs really fast.
While in many cases this is a valid assertion, in other cases being fast is not enough. Future web apps won’t be judged by how the individual pieces are evaluated, rather by the way they run together in an orchestra.
A simple function like this:
Array.prototype.swap = function (i, j) {
var k = this[i]; this[i] = this[j]; this[j] = k;
}
is rather innocent. There is not much you can do to optimize it. Yet, when it is being invoked from an implementation of a very inefficient sorting algorithm, the overall outcome would be disastrous.
Page optimization
So far, typical discussions and best practices on web page optimizations (WPO) are geared towards two things: transport and interface responsiveness optimizations. The former is about leveraging the available bandwidth to its potential, obviously very useful since nobody likes to stare at the blank page while it is loading. The latter is to ensure that the user is happy with the user interface, often involving tricks from minimizing DOM operations to using hardware acceleration.
As web applications become bigger and more complex, soon there will be one huge issue which needs a lot of attention: scalability. For many traditional developers who jump to the web, either from the desktop background (C++/Java) or RIA development (Flex) or server-side scripting (Ruby/ASP), this is especially important. They are going to build web apps of a different class. The apps won’t be just web pages sprinkled with some interactivity to add the richness of the user interface.
Many future applications will be architected and designed from the ground-up to be seriously large-scale. In those cases, the transport and responsiveness will be still relevant, yet they can be dwarfed by the application complexity. Imagine a stereotyped business logic application which deals with customer data, the central problem is less about CSS minification or JavaScript scope access. The bottleneck lies somewhere else.
Orders of growth
Let’s take a simplified example of client-side data sorting. If this is about a simple phonebook on a mobile device, then the performance is not as critical as a corporate address book, mainly because of the amount of entries to be sorted is different. Using bubble sort, with its quadratic growth average complexity, would not be a smart choice if the application must scale to a large number of contacts. The determining factor that becomes very important is the upper bound of the amount of computation as the application needs to tackle larger volume of data.
Note that it does not even have something to do with traditional data manipulation. If you are writing a parser, does it scale when the input which it consumes is getting bigger? If you create a layout system, does it behaves nicely as the application stacks and nests the layout beyond your wild imagination? If your regular expression extracts an important piece from the user, does it choke when he feeds an slightly longer string than the typical? If you deal with graph-based dependency analysis, does everything still not fall apart when new nodes pop up like there is no tomorrow? If you develop a query engine, does it run forever when the document has a gazillion elements?
The scalability strategy is very important for framework or library author. There is no way to completely predict beforehand how people are going to use (or rather, abuse) the framework. Customers totally understand that as their data grows, they can expect a performance degradation in the processing. What many customers want to know (and often they do not describe exactly like this) is the quantitative explanation. If my address book doubles its entries, how much slowdown I can expect from this grid component? Is it also 2x? Is it 4x? Is it 100x?
Empirical run-time analysis
For things like sorting and searching, theoretical analysis of the algorithm complexity is widely available. However, real-world application analysis, even for many operations inside jQuery, is often not available or prohibitively expensive to be carried out formally. The fallback solution is to perform the run-time analysis, i.e. monitoring the behavior of the application as the input data grows.
If we go back to the Array.prototype.swap example, we just have to monitor how many times this function is being called during the sorting process. Essentially we are adding instrumentation to our code. Change the size of the data to be sorted, monitor the growth in the function invocation. Voila! We have a report which demonstrates its run-time behavior.
In this simplified example, it’s rather easy to carry out the above analysis. A slightly more complicated cases, anything from a selector engine to code quality tool will need a different approach. What about automatic instrumentation?
This is where Esprima kicks in. In case you’re not familiar with it, Esprima is a JavaScript parser designed from the very beginning to be extremely fast. The newest demo that comes with Esprima is the so-called function entrance tracing. In fact, the live demo at esprima.org/demo/functiontrace.html exactly demonstrates the sorting example given before. Go ahead, try it out, and come back again later (I’ll wait, I promise). Bonus exercise: change the sort function to something else, e.g. a binary sort.
Before the demo executes your code, it inserts an additional statement before every function block. For example, the swap function can become something like:
Array.prototype.swap = function (i, j) {
Log({ name: 'Array.prototype.swap', lineNumber: 1, range: [23, 94] });
var k = this[i]; this[i] = this[j]; this[j] = k;
}
The function Log is the name of the tracer (easily customized, see below). It will receive an object which has the information about the function name, its location (line number) as well as the index-based range of the function in the source. Armed with this instrumentation, you can do whatever you want in the implementation of your Log function.
The demo actually does a little bit more in order to be able to show the number of calls for every function. The tracer is TRACE.enterFunction, where TRACE is a simple object with its implementation is fully shown below:
window.TRACE = {
hits: {},
enterFunction: function (info) {
var key = info.name + ' at line ' + info.lineNumber;
if (this.hits.hasOwnProperty(key)) {
this.hits[key] = this.hits[key] + 1;
} else {
this.hits[key] = 1;
}
},
getHistogram: function () {
var entry,
sorted = [];
for (entry in this.hits) {
if (this.hits.hasOwnProperty(entry)) {
sorted.push({ name: entry, count: this.hits[entry]});
}
}
sorted.sort(function (a, b) {
return b.count - a.count;
});
return sorted;
}
};
Rather simple, isn’t it? Yet, it produces a powerful outcome: the record of every function call in the code.
Backstage: automatic instrumentation
Adding the above automatic instrumentation is possible via Esprima new source modification feature. There is still little information about the modify API but hopefully this will be expanded further. Basically, what you have to do is:
esprima.modify(code, esprima.Trace.FunctionEntrance('LOG'));
That’s all! esprima.modify will pass your source string to esprima.Trace.FunctionEntrance which parses your code, figure out where the functions are, then insert the instrumentation by calling the supplied tracer function.
Because of the dynamic nature of JavaScript, Esprima will do a best-effort guess for the function name (or mark it as an anonymous one), in case it’s not obvious. The unit tests demonstrate clearly that all the following constructs present no problem whatsoever, the correct function reference is still obtained properly:
function hello() {}
hello = function() {}
var hello = function() {}
var hello = function say() {}
(function(){})()
[14, 3].forEach(function(x) { alert(x) })
var x = { y: function(z) {} }
If adding a prolog with a tracer function call is not sufficient for you, flexible customization is further possible by supplying a function (instead of a string) to esprima.Tracer.FunctionEntrace, e.g.:
esprima.modify(code, esprima.Tracer.FunctionEntrance(function (info) {
return '// Executing function ' + info.name +
' at line ' + info.lineNumber + 'n';
}));
The modified code will look something like:
Array.prototype.swap = function (i, j) {
// Executing function Array.prototype.swap at line 1
var k = this[i]; this[i] = this[j]; this[j] = k;
}
It is rather useless because what being inserted is just a line comment. For your real-world instrumentation, you might want to build a more sophisticated customized instrumentation.
Instrumentation and testing workflow
Of course the instrumented version of your code is useless without actually testing it. There are several possible approach. The easiest is to a create a separate build for the instrumented version to be used in various scalability tests. For example, the performance test suite of a phone book will watch the function call analysis as it slowly increases the amount of contacts or switches to a variety of different test fixture.
In many cases, run-time analysis of application complexity does not depend very much on the actual environment. To facilitate fast smoke test, the use of headless WebKit such as PhantomJS can be very beneficial. Executing the complexity tests headlessly still allows the collection of various performance data without the need to launch any real browsers. Should you use a continuous integration system, this fits nicely into the workflow. As a bonus, PhantomJS is also supported by Travis CI, making it really easy to stress-test your open source applications and libraries.
Happy testing!
P.S.: In the next installment I will discuss Esprima for startup performance analysis. Update: it’s available, read more about automatic JavaScript execution tracking.