Dispositivo Duff en Javascript

18 Mar 2011

Introducción

A la vista de los resultados analizados en el artículo “Rendimiento de los bucles en Javascript frente a otras alternativas” y motivado de nuevo por el comentario de @TarodBOFH, decidí realizar más pruebas buscando la estructura bucle de mayor rendimiento en Javascript.

En el experimento anterior medimos a un modelo ordinario junto a otras soluciones más alternativas como las funciones autoejecutables recursivas o el uso de eval, quedando claro que el for tradicional era mucho más eficiente. Ahora quedaba comprobar cómo se comporta esta solución frente a otros métodos nativos como el bucle while (tradicionalmente más rápido) y su versión extrema representada por el Dispositivo Duff.

Veámos en esta ocasión qué resultados obtenemos y cuáles son las conclusiones que podemos extraer de los mismos.

Entendiendo el Dispositivo Duff

Según la Wikipedia, en el ámbito de las ciencias de la computación, un Dispositivo Duff es una implementación optimizada de una copia secuencial para programas en lenguajes C originalmente concevida a Tom Duff en un ya lejano 1983.

Lo interesante de esta técnica es que funciona con la misma eficacia en otros lenguajes de programación además del original C en el que fue implementado.

La idea base de este método es desdoblar un bucle tradicional del tipo switch intercalando la estructura de una instrucción do/while.

En Javascript, podemos implementar esta idea basándonos en la teoría de que:

var i = 0;
i++;
i++;
i++;
i++;
i++;
i++;
i++;
i++; // i = 8

es más rápido que:

var i = 8,
    j = 0;
 
while( --i ){
  j++;
}

La razón de la optimización es que sólo se realiza una comparación y operación matemática por cada bloque de 8 elementos en lugar de por cada uno.

Esto quiere decir que se puede iterar por una colección de n elementos utilizando el siguiente algoritmo:

var i = 8,
    j = 0,
    l = parseInt( ( i / 8 ), 10 );
 
do{
  j++; // Operation to performe goes here...
  j++; // more operations...
  j++; // and so on...
  j++;
  j++;
  j++;
  j++;
  j++; // j = 8
} while( --l );

En el mundo real, deberíamos comprobar que el conjunto a recorrer tiene un número de elementos múltiplo del tamaño que hemos definido para cada uno.

Un ejemplo funcional de implementación sería el siguiente: (aportado por Trygve Lie):

// Duff's device
function duffsdevice( iterations ) {
  // The value we want to performe an operation on
  var opValue = 0;
  // Calculate "spillovers". Spillovers are the numbers not fitting in when the number
  // of iterations are divided with the number of simultanius operations performed
  // Ex: 66 % 8 = 2
  var i = iterations % 8;
  // Run trough the spillovers
  // i must be greater than 0!!
  if( i > 0 ){
    do {
      opValue++; // Operation we want to performe goes here...
    } while( --i );
  }
  // Run trough the number of iterations divided by the number of simultanious
  // operations we would like to performe.
  i = parseInt( iterations / 8 );
  do {
    opValue++; // Operation we want to performe goes here...
    opValue++; // and here..
    opValue++; // and here..
    opValue++; // and here..
    opValue++; // and here..
    opValue++; // and here..
    opValue++; // and here..
    opValue++; // and here..
  } while ( --i );
}

Métodos tradicionales

Por otro lado, mediremos el rendimiento tanto de un bucle for como de una estructura while común:

// Traditional for loop
function traditionalLoop( iterations ){
  var opValue = 0;
  for(
    var x = 1;
    x < iterations && ( x++ );
  );
}
 
// Old fasion while loop adding up one value
function plain( iterations ){
  var opValue = 0;
  var m = iterations;
  while( --m ) {
    opValue++;
  }
}

Los resultados del test de comparación

Para medir el rendimiento, se ha utilizado de nuevo el servicio online JSPerf con los siguientes resultados:



En esta ocasión las pruebas se han realizado con los navegadores Chrome 10, Firefox 4, Opera 11 e IE9 (que en esta ocasión si ha funcionado correctamente).
Analizando los resultados, podemos extraer los siguientes puntos:

  • El Dispositivo Duff es terriblemente rápido.
  • Los bucles while son, como cabía esperar, más rápidos que los de tipo for en todos los escenarios salvo en Chrome.
  • El motor JavaScript de Opera continúa demostrando un buen rendimiento pero la potencia del Chrome es incuestionable.
  • Internet Explorer 9, que pese a lo que marca la tabla es la versión final, demuestra un rendimiento muy pobre frente a sus competidores.

Conclusión

En esta ocasión hemos comprobado como una idea brillante puede portarse de un lenguaje a otro con ciertas garantías de conservar su esencia original: el Dispositivo Duff ha demostrado ser más rápido que las estructuras convencionales en casi un 60% en el caso más desfavorable.

De nuevo, si se os ocurre alguna solución alternativa, compartirla en los comentarios para que todos podamos analizarla.

Más:

Aún no tenemos debug!
Ningún marciano se ha comunicado.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *