JavaScript Optimization


Introduction

This document is intended to serve a number of purposes. One, it is intended to be a compendium of JavaScript optimization techniques, a place where one can turn to find optimization examples, some well known to JavaScript Programmers, and some not so well known. Two, it is also a source of performance information with regard to how these techniques perform in comparison to each other. Lastly, it is intended to address the issue of which programming optimization techniques work as intended in the interpreted environment in which JavaScript code runs.

There are a few web sites out there that deal with JavaScript optimization, but most only deal with size issues, and if they do deal with other issues, it is in a very general way. I seek to rectify that here. I will also delve into some of the more obscure issues related to programming optimization, and how they might impact on JavaScript. This document is divided into three main sections: Speed, Size and Memory.

I have chosen JavaScript 1.3 as the basis for the tests.

- Jeff Greenberg



Speed


I am starting with this section because it is one of the most neglected aspects of JavaScript optimization. Of course, most of the time it is not needed in everyday JavaScript. There are some things to keep in mind about speed optimization:

1) The best kind of speed optimization is more efficient algorithm design. Before you go nuts trying to squeeze every last ounce of speed out of every statement, take a serious look at the design of your algorithms first. Why? See next point.
2) Speed optimization is usually the last step and the last resort while programming. Code that has been altered explicitly for speed concerns is almost always difficult to read, maintain and overhaul. If you plan on sharing your code with others, this is something you should think about seriously.
3) For most uses of JavaScript, speed optimization is just not necessary. If you are feeling the urge to speed up your code just for the sake of it, don't. It's not worth it. If, however, speed is critical to your project, and you can't seem to get the necessary speed from your design, then your code is a good candidate for speed optimization.

** It should be noted that the power of the techniques in this section comes from combining them.**


IE vs. NS: Results & Stability

There are two things that are clear from these results:

1) IE is, in general, faster than Netscape at just about everything.

2) Optimizing JavaScript code for speed brings the performance of Netscape much closer to that of Internet Explorer, and usually speeds up the IE code as well.

I believe the test results support speed optimization if for nothing else than to make JavaScript code more predictable and stable across different browsers (at least these two, anyway).

About the Tests

Speed tests take the following form, unless otherwise noted.
Run the code through many cycles, and report the total time of execution. Then divide total time by the total number of cycles to get an average execution time per cycle for the code being tested.

This is done to insure that the final value is as accurate as possible.


** Some of the tests can take 30 seconds or so (especially on Netscape), so be patient.




Straight Forward

** There are no tests in this section.

Limit Work Inside Loops

Impact Clarity Ease Of Use
Varies High Easy


This one is pretty self evident. For instance, check out the following example:


Example 1 - Before

with (Math) {

for (var i=0;i<round(staticNum*(PI/12));i++)
    {
    testVar+=(2*log(6)) + (x/2);
    }

}

The calculations inside the loop and in the condition get evaluated every time through the loop, even though they don't change. For loops with high counts, complex calculations can really slow things down. These expressions should be removed and placed in variables:

Example 1 - After

with (Math) {

var tester = round(staticNum*(PI/12));
var valChange = (2*log(6)) + (x/2);

}

for (var i=0;i<tester;i++)
    {
    testVar+=valChange;
    }


Minimize Repeated Expressions

Impact Clarity Ease Of Use
Varies High Easy


This goes hand in hand with the above tip. If you find yourself constantly using an expression in your code, you should place it in a variable so that it only has to be evaluated once:


Example 2

bottomLayerWidth = 5 * ((layerWidth/2)*(.5*layerHeight));
topLayerWidth = 2 * ((layerWidth/2)*(.5*layerHeight));

textLayerWidth = (4 + bottomLayerWidth) * ((layerWidth/2)*(.5*layerHeight));
statusLayerWidth = (2 + topLayerWidth) * ((layerWidth/2)*(.5*layerHeight));


Should be changed to:


var changeVal = ((layerWidth/2)*(.5*layerHeight));

bottomLayerWidth = 5 * changeVal;
topLayerWidth = 2 * changeVal;

textLayerWidth = (4 + bottomLayerWidth) * changeVal;
statusLayerWidth = (2 + topLayerWidth) * changeVal;


The Unnecessary Variable Gotcha

Something to Watch out For


You need to be careful when applying the above methods, however. Only use them when there are repeated expressions that use the same code.

var newX = (radius * (Math.sin(angle)));
var xDiff = Math.abs(newX - oldX);

If the code in newX is only used once, then all you have done* is waste time creating an extra variable.

*Of course, that's not all you have done. You have also made your code easier to read. Remember that optimizing your code for speed often makes it less clear.


If-Then-Else Structure

Impact Clarity Ease Of Use
Varies High Easy


If you have a series of If-Then-Else statements, you should try your best to organize them from most likely to least likely. This way the program doesn't have to traverse all the unlikely conditions to get to the likely ones, which will be called more often.




Not So Straight Forward


Switch vs If-Then-Else

Impact Clarity Ease Of Use
Varies High Easy


A commonly used tactic to wring whatever overhead might be left out of a large group of simple conditional statements is replacing If-Then-Else's with Switch statements. This is a tough one to qualify. Performance varies widely, although you almost always come out with some kind of improvement, even if it is small. As always, proper code design is much more important.

The following test cycles through a group of If-Then-Else statements and a Switch statement 100,000 times, each containing 20 conditionals.

Status:

IFTE SWITCH
Total: ms Total: ms
Per cycle: ms Per cyclems


My Test Results
Win98 (CEL/366) IFTE SWITCH
NS 4.73 total 1590 ms 220 ms
NS 4.73 per cycle .0159 ms .0022 ms
IE 5.5 total 1320 ms 1090 ms
IE 5.5 per cycle .0132 ms .0109 ms




Switch Structure

Impact Clarity Ease Of Use
Negligible High Easy


A common optimization performed outside of the JavaScript world is keeping the structure of a switch statement "close". This refers to the fact that processors on many computers can perform switch statements whose case variables increase predictably and sequentially faster than they can perform switch statements with case variables that contain unpredictable values and large jumps.

My tests indicate that the impact of a close switch on Javascript code is almost non-existent, and is sometimes actually slightly slower than open.

The following tests a close switch statement with a not-so-close one through a cycle of 100,000.

  Status:

Open Close
Total: ms Total: ms
Per Cycle: ms Per Cycle: ms
My Test Results
Win98 (CEL/366) OPEN CLOSE
NS 4.73 total 2530 ms 2470 ms
NS 4.73 per cycle .0253 ms .0247 ms
IE 5.5 total 1100 ms 1210 ms
IE 5.5 per cycle .0110 ms .0121 ms



Bit Shifting for Math with Powers of 2

Impact Clarity Ease Of Use
DOA Medium Easy
Low


To put it plainly: this doesn't work very well (Most of the time. Every now and then you might see a slight improvement. I use the term slight generously). In fact, it's almost always slower than using JavaScript's built in math functions.

Here is a very simple test that multiplies the number 3 by 2 through 250,000 cycles.

status:

Regular Bit-Shift
Total: ms Total: ms
Per Cycle: ms Per Cycle: ms
My Test Results
Win98 (CEL/366) REGULAR BIT-SHIFT
NS 4.73 total 660 ms 610 ms
NS 4.73 per cycle .0026ms .0024 ms
IE 5.5 total 440 ms 380 ms
IE 5.5 per cycle .0018 ms .0015 ms




Look Up Tables

Impact Clarity Ease Of Use
Varies High Easy


Another tried and true method. By putting a large group of often calculated values in an array and looking them up based on their indices, you can avoid costly calculations (see Minimize Repeated Expressions).

This works ok in JavaScript, but you don't get as much of a gain as you do in other languages and it is heavily dependent on the "cost" of the calculations you are putting into the array.

This is most often used with trigonometric values, for instance:

Example 3

sin = new Array();

for (var i=1;i<=360;i++)
    {
    sin[i]=i*(Math.PI/180);
    }

You could then access the sin of any number like so:

var trigVal = sin[34];

Next is an example that shows a modest gain on most platforms. It compares the time it takes to pull the values for the natural log of numbers 0-99 and assign them to variables. (3500 cycles)


status:

Direct Lookup Table
Total: ms Total: ms
Per Cycle: ms Per Cycle: ms
My Test Results
Win98 (CEL/366) DIRECT LOOKUP
NS 4.73 total 18290 ms 16530 ms
NS 4.73 per cycle 5.2257 ms 4.7229 ms
IE 5.5 total 2310 ms 1760 ms
IE 5.5 per cycle 0.6600 ms 0.5029 ms



Loop Unrolling

Impact Clarity Ease Of Use
Medium Medium Easy


To unroll a loop, you have it do more than one of the same step per iteration and increment the counter variable accordingly. This helps a lot because you then decrease the number of times you are checking the condition for the loop overall.

This works pretty well in JavaScript, although, to use this method as is you need to be aware of how many iterations the loop will be going through before hand (see Duff's Device in the Straight as a Pretzel section) Or you may run into trouble by overshooting bounds or creating some unwanted behavior.

The following code should make this clear:

for (var i=0;i<iterations;)
    {
    [do something with i here];i++;
    [do something with i here];i++;
    [do something with i here];i++;
    [do something with i here];i++;
    [do something with i here];i++;
    }

I have chosen to unroll this loop five times. Therefore, the number that gets put into iterations needs to be divisible by five, or you could end up with some hard to track down bugs.

Something to be aware of when using this method: don't unroll too many times! Not only will your file end up much larger, but the code may actually execute more slowly than an ordinary loop.

Here is a test that just executes a regular loop and an unrolled loop (unrolled 5 times) 500,000 times, and takes the average time through one cycle of the loop:
  Status:

Regular Unrolled
Total: ms Total: ms
Per Cycle: ms Per Cycle: ms
My Test Results
Win98 (CEL/366) ROLLED UN-ROLLED
NS 4.73 total 11860 ms 2750 ms
NS 4.73 per cycle .0237 ms .0055 ms
IE 5.5 total 830 ms 330 ms
IE 5.5 per cycle .0017 ms .0007 ms



Reverse Loop Counting

Impact Clarity Ease Of Use
Medium Medium Easy


This is perhaps the most shocking method because it works so well in JavaScript (but it is much more effective in Netscape). All that this requires is that you reverse your loop so that it counts down instead of up. I have also seen in various documents about optimization that comparing a number to zero is much quicker than comparing it to another number, so if you decrement and compare to zero it should be faster. I have been unable to verify this in JavaScript.

Here is what the code looks like:

for (var i=iterations;i>0;i--)
    {
    // do something here
    }

Don't believe me? Try this test (500,000 cycles):

  Status:

Ordinary Reverse
Total: ms Total: ms
Per Cycle: ms Per Cycle: ms
My Test Results
Win98 (CEL/366) FORWARD REVERSE
NS 4.73 total 12360 ms 930 ms
NS 4.73 per cycle .0247 ms .0019 ms
IE 5.5 total 820 ms 550 ms
IE 5.5 per cycle .0016 ms .0011 ms



Loop Flipping

Impact Clarity Ease Of Use
Low Medium Easy
Varies


Loop flipping is the method of taking a loop that has it's condition evaluated at the top and changing it to evaluate at the bottom. Most of the time this seems to be inferior to a top evaluating loop in JavaScript, but there are times, which I haven't been able to predict, when bottom evaluating seems faster.

The only way to tell is to test it yourself.

Regular Loop

for (var i=0;i<fIter;i++)
    {

    }

Flipped Loop

i=0;
do
{
 i++;
} while(i<fIter);

Here is the test (500,000 cycles.):

  Status:

Ordinary Flipped
Total: ms Total: ms
Per Cycle: ms Per Cycle: ms
My Test Results
Win98 (CEL/366) REGULAR FLIPPED
NS 4.73 total 11750ms 44330 ms
NS 4.73 per cycle .0235 ms .0880 ms
IE 5.5 total 880 ms 1380 ms
IE 5.5 per cycle .0018 ms .0028 ms



A word about the Speed of JavaScript Math

In general, the built in math functions will always be faster than anything you can come up with.

For instance, you may get the idea that you can speed up multiplies by changing them to adds with the increment (++) operator. It doesn't work. It is always slower.



Straight as a Pretzel



Duff's Device

Impact Clarity Ease Of Use
High Low Medium
Varies


This is, hands down, one of the most effective and coolest ways to deal with loops. It is both wicked fast and flexibile. It is, however, also not the easiest thing to understand, although its use isn't quite so difficult.

** IE NOTE: Internet Explorer has much better loop optimization built in than Netscape. Using this method, you will probably see an increase in performance in IE, but it will be very minor. It makes all the difference in NS though.

Invented by programmer Tom Duff, Duff's Device is a way to unroll a loop without having to know the iterations before hand. It is a combination of a DO statement and a SWITCH statement. You should also note that it combines loop unrolling, reverse loop counting and loop flipping.

As far as I know, I am the first to port this to JavaScript. Took a little bit of thinking, but enough of that. :-)

Here's the code (demonstrating a Duff's Device with the loop unrolled 8 times):


// This is just test stuff to make everything clearer.

testVal=0;

iterations = 5125;

// End test stuff

--------------------------------------------

// Begin actual Duff's Device
// JS Implementation by Jeff Greenberg 2/2001

var n = iterations / 8;
var caseTest = iterations % 8;    

do {

    switch (caseTest)
    {
    case 0:              [Do Something to tesVal here];
    case 7:              [Do Something to tesVal here];
    case 6:              [Do Something to tesVal here];
    case 5:              [Do Something to tesVal here];
    case 4:              [Do Something to tesVal here];
    case 3:              [Do Something to tesVal here];
    case 2:              [Do Something to tesVal here];
    case 1:              [Do Something to tesVal here];
                   
    }
    caseTest=0;

}

while (--n > 0);


Ok, what the heck is this you ask?

This is how you set it up: iterations is, of course, how many times to loop. testVal is just here to show how you might affect a value in the loop. The key here is to realize that the code after each case label is EXACTLY the same.

So, you decide how many times you want to unroll the loop, and put that many case labels in the switch statement, 0 to numberOfTimesUnrolled-1, with 0 first then counting down from numberOfTimesUnrolled-1.

n is set to iterations/numberOfTimesUnrolled.

caseTest is set to iterations modulus numberOfTimesUnrolled.

That's all you need to know to use it, but I explain how it works below.


How it Works

Look at the code closely. caseTest is set to the remainder of iterations/numberOfTimesUnrolled.

n is the number of times you can execute all the unrolled statements without having any remainder.

It's easy to see here that caseTest will be 5, and n will be 640. Here's the cool part: The first time we hit the DO loop, caseTest equals 5. So it skips to that case. Now, the way case statements work, unless you specify BREAK after each statement, every statement is executed after the first statement that gets triggered.

See what happens? There are 5 left over iterations, but by skipping to case 5, we execute exactly that amount. At that point, after the first time through the loop, we set caseTest to 0, so that when we go back to the top of the loop, every case statment is executed. This is exactly what we want, because we only have whole groups of 8 to go through now!

How many groups? Why, n of course! And we convieniently decrement n at the bottom of each loop. But notice, we decrement it using PREFIX notation, which makes sense since it's at the bottom of the loop.


If this still isn't clear, go back and read it again. It isn't too hard, but is a bit confusing.


Now, for the test - Each loop goes through 500,125 iterations, incrementing a test value by 1:

  Status:

Ordinary Duff's
Total: ms Total: ms
Per Cycle: ms Per Cycle: ms
My Test Results
Win98 (CEL/366) REGULAR DUFF'S
NS 4.73 total 22360ms 1260 ms
NS 4.73 per cycle .0447 ms .0025 ms
IE 5.5 total 770 ms 710 ms
IE 5.5 per cycle .0015 ms .0014 ms



Faster Cleaner Modified Duff's Device

Impact Clarity Ease Of Use
High Medium Medium
Varies


This nice bit of programming was sent in to me from someone (can't find your email address!!! If it was you, send me your info again!!!!) who was looking for even more speed out of Duff's Device. This is a very clean, clever way to accomplish the same thing I did with my code, but is much faster. It is a very simple implementation, but is one of those things that I'm sure took a bit of thought.
var n = iterations % 8;
while (n--)
    {
    testVal++;
    }
	
n = parseInt(iterations / 8);
while (n--)
    {
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    }



  Status:

Ordinary Duff's Duff's Fast
Total: ms ms ms
Per Cycle: ms ms ms