Fat Agnus

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.

1
2
3
4

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.

1
2
3
4
5

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

Over the years I have been involved in doing both backend and frontend development, but for some reason there seems to be a lack of understanding and maybe even respect for what Frontend Engineers do.

Maybe it is because that some people think that doing Html, Css, Javascript and so forth is easy, but in reality it can be really difficult, at least if you want to have it done right.

Browsers are the most hostile software development environment imaginable.
– Douglas Crockford

Douglas said this when he was talking about browsers on desktop computers, but he later on changed his mind when he saw how much worse it was on mobile.

There are so many things to keep track of when doing frontend development and you don’t have the same benefit as the Backend people do, like compiling your stuff, so you cant really trust what is going on.

In Nate Koechleys’s speech he sums up how many things that a frontend engineer needs to balance out.

A conservative number may be 672 different things we’re trying to balance as we built out these websites. – Nate Koechley

The number doesn’t include things like usability, performance and security.

In my mind, frontend engineers should get lots more credit for the work they do.

Watch Nate Koechley speak

Yet another great video from Douglas Crockford

http://video.yahoo.com/video/play?vid=1382941

And here is a little bonus video

Browser Wars Episode II: Attack of the DOMs