Dispositivo de DUFF

A muchos nos sonará la palabra DUFF como algo más cercano al mundo de la televisión gracias a los Simpon o a la propia cerveza que ya se vende en algunos lados(que tampoco está muy buena, sobre todo siendo un subproducto de la Primus, que nunca ha sido santo de mi devoción) que a un programador. No obstante Tom Duff ha trabajado en Lucasarts y en Pixar, además de crear este extrañísimo y muy eficiente algoritmo, así que opino de que debe ser reivindicado. Además, de por su… único aspecto personal, tal y como podemos ver en su entrada de la wikipedia.
En resumen, el algoritmo lo que hace es acelerar el funcionamiento de cualquier bucle repetitivo estilo foreach, while o recursivo. Echadle un ojo a su versión en php o a su entrada en la wikipedia para la de C.
Como nota personal, he probado este sistema en un par de bucles especialmente pesados de mi página web logrando un 400% de mejora en tiempos. Así que funcionar, lo que se dice funcionar, funciona.
Aquí tengo las cifras:
Resultado 1 = 9000000 en 1.0531
Resultado 2 = 9000000 en 0.2776
El resultado 1 es un bucle for que entra 9 millones de veces a sumar un +1 a un número que empieza siendo un cero. El segundo hace lo mismo pero usando el dispositivo de duff.
Como vemos tiene más de un 400% de mejora de velocidad. También hice una prueba cambiando el bucle do..while por un while a secas, pero empeoraba una décima de segundo de media con respecto al dispositivo de duff original.

Duff’s Device: loop unrolling for interpreted languages

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
VIA MAKE