Duff’s Device: loop unrolling for interpreted languages

Technology

In 1983, Tom Duff invented a really strange way to use the C language’s switch and case statements for the in code “unrolling” optimization of large loops. As an example, he described a simple loop that copies an array to an output register:

	send(to, from, count)
	register short *to, *from;
	register count;
	{
		do
			*to = *from++;
		while(--count>0);
	}

On every iteration of the loop, in addition to the copy that is being performed, the count variable is decremented and a comparison is done against 0. Duff’s Device allows you to achieve the same result, but with only an 8th of the overhead:

	send(to, from, count)
	register short *to, *from;
	register count;
	{
		register n=(count+7)/8;
		switch(count%8){
		case 0:	do{	*to = *from++;
		case 7:		*to = *from++;
		case 6:		*to = *from++;
		case 5:		*to = *from++;
		case 4:		*to = *from++;
		case 3:		*to = *from++;
		case 2:		*to = *from++;
		case 1:		*to = *from++;
			}while(--n>0);
		}
	}

What happens is that the loop is unrolled 8 times, so each iteration of the loop runs the internal code 8 times over without the comparison. The genius of Duff’s Device is that it takes advantage of the way the C switch/case structure works. The first time through, if the iterations don’t divide evenly by 8, the loop code is executed enough times to equal the remainder of iterations/8. It’s a little bizarre, because the “do” statement occurs within the switch, but there are “case” statements within the “do”. Nevertheless, it’s valid C.

Before someone cries foul, remember that this is only really suitable for speeding up the performance of inner loops when no suitable, better algorithm is available. If you code C, most modern compilers are smart enough to automatically optimize your code and unroll loops for you.

For interpreted languages like PHP or Javascript, however, you sometimes need to do a little optimization on your own if you want to squeeze out some extra performance. Luckily, both languages have a c-style switch statement.

Andy King wrote about a slightly altered version of this loop unrolling algorithm which ditches the switch statement and breaks the normal Duff’s Device into two separate loops, one for the remainder and one for the unrolling. In Javascript, it performs a simple addition loop in only a third of the time of a normal for loop (testVal++ is the normal loop’s interior):

function duffFasterLoop8(iterations) {
  var testVal=0;	
  var n = iterations % 8;
  if (n>0) {
    do 
    {
      testVal++;
    }
    while (--n); // n must be greater than 0 here
  }
    
  n = parseInt(iterations / 8);
  do 
  {
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
  }
  while (--n);
}

It’s not as syntactically clever as Duff’s Device, but it’s a good way to manually unroll an inner loop and get the best performance for your extra effort.

Duff’s Device
Andy King’s Optimizing JavaScript For Execution Speed

What will the next generation of Make: look like? We’re inviting you to shape the future by investing in Make:. By becoming an investor, you help decide what’s next. The future of Make: is in your hands. Learn More.

Tagged
Discuss this article with the rest of the community on our Discord server!

ADVERTISEMENT

Escape to an island of imagination + innovation as Maker Faire Bay Area returns for its 16th iteration!

Prices Increase in....

Days
Hours
Minutes
Seconds
FEEDBACK