Unrolling your loop for better performance in Javascript

Posted

Loop unrolling, is a loop transformation technique that attempts to optimize a program’s execution speed at the expense of its size. – Wikipedia

What this means is that we are trying to limit the number of iterations to mitigate the overhead in a loop.

Consider this.

var i=values.length;
while(i--){
	processData(values[i]);
}

If we say that there are only 5 items in the array that will make it easier for us to unroll it.

processData(values[0]);
processData(values[1]);
processData(values[2]);
processData(values[3]);
processData(values[4]);

It isn’t pretty and it would probably be annoying to maintain such an approach if the size of the array grow or shrinks. The performance gain for this example wont make the downside worth it, but if the array was quite large then it would be useful, but still even more annoying to maintain.

Tom Duff to the rescue

Tom came up with a brilliant solution/pattern for unrolling loops in C, which got the name Duff’s Device and was later on converted to Javascript by Jeff Greenberg.

Here is the javascript version

var iterations = Math.ceil(values.length / 8);
var startAt = values.length % 8;
var i = 0;

do {
	switch(startAt){
		case 0: process(values[i++]);
		case 7: process(values[i++]);
		case 6: process(values[i++]);
		case 5: process(values[i++]);
		case 4: process(values[i++]);
		case 3: process(values[i++]);
		case 2: process(values[i++]);
		case 1: process(values[i++]);
	}
	startAt = 0;
} while (--iterations > 0);

The idea with this pattern is that each trip through the loop does the work of 1-8 iterations of a normal loop and Tom also figured out that 8 was the optimal number to use. A very important aspect of this pattern is the use of modulus, because not all arrays will be divisible by 8.

This technique might look a bit strange but it will actually run faster then a normal loop. How ever, we can make it run even faster, if we remove the switch statement from the loop, because conditionals have a performance overhead.

This example was introduced in Speed Up Your Site by Andrew B. King.

var iterations = Math.floor(values.length / 8);
var leftover = values.length % 8;
var i = 0;

if (leftover > 0){
	do {
		process(values[i++]);
	} while (--leftover > 0);
}

do {
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
} while (--iterations > 0);

This optimized Duff’s Device is 39 percent faster than the original and 67 percent faster than a normal for loop. – Speed Up Your Site, Andrew B. King

Finale word

Before you go and change all of your loops, you should consider if you really need to use this pattern. For small arrays the performance gain is to small to have any greater impact, so you should only applied this technique when you find a bottleneck that is related to a loop.

Further Reading

Even Faster Web Sites: Performance Best Practices for Web Developers

Share on FacebookTweet about this on TwitterShare on LinkedInShare on Google+Share on RedditBuffer this pageEmail this to someone

6 thoughts on “Unrolling your loop for better performance in Javascript

  1. zproxy wrote:

    I guess this optimization is actually what the javascript JIT compiler should be doing…

  2. Mark Jensen wrote:

    Sure, but that is the funny thing about compilers :)

    They are not always as good as people think they are..

  3. pstradomski wrote:

    Shouldn’t the last example use while instead of do/while?

    Assuming values.length is between 0 and 8 we’d have iterations=0, leftover = values.length. The leftover part will process all the elements and the next do/while block will iterate past the end of the array.

  4. Jeff Greenberg wrote:

    Just a side note: The second, faster example of a Javascript Duff’s device cited in Andy King’s book is actually based on a submission to me from someone who saw my code when I first put it up and knew that he could do better. If you follow the link above to that old, old, old page of mine and scroll down, you will see the example.

    The person who sent me that code did indeed send me his name as well, but shortly thereafter I had a computer meltdown and lost his info before being able to properly attribute the code to him.

    Strange how the Javascript Optimization page keeps popping up in blog posts every few years. :-)

    -JG

  5. l.m.orchard wrote:

    But the other funny thing is, sometimes you out-smart yourself: For what it’s worth, I believe TraceMonkey in Firefox specifically optimizes code branches run in loops. So, you might be circumventing the JIT this way.

  6. Pingback: Javascript performance | Werx Limited

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Current day month ye@r *