lunes, 26 de septiembre de 2011

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

martes, 20 de septiembre de 2011

PL/SQL Usar arrays o cursores en una select

Las bases de datos de ORACLE tienen muchas ventajas que las convierten en candidatas ideales para su implantación en el mundo empresarial. Son fiables, potentes y tienen una gran cantidad de plugins y posibilidades de escalabilidad que hace que sean ideales para prácticamente cualquier entorno.

Pero aun así, tal vez una de sus características más importantes y exitosas sea la capacidad de programación que éstas tienen gracias al lenguaje que viene integrado en sus productos, PL/SQL (Procedural Language/Structured Query Language), que permite extender la funcionalidad del lenguaje SQL.

Este lenguaje incorpora muchas mejoras sobre el SQL estandar, añadiendo manejo de variables o estructuras de bucles, por citar un par de ejemplos, que lo hacen muy parecido a los lenguajes orientados a objetos como puede ser Java o las tecnologías .NET. Pero todo esto con la ventaja de que, al estar incrustado en el motor de Oracle permite un mayor rendimiento e integración del código que al final se nota en una mejora en los tiempos de ejecución comparativamente con otros lenguajes que puedan funcionar a base de querys extrayendo información de la base de datos y después trabajando con éstos en el propio equipo cliente.

No obstante, no es oro todo lo que reluce, y si bien, éste lenguaje supone una gran mejora con respecto a la programación relacional de bases de datos a la que podemos estar acostumbrados, éste todavía tiene una serie de limitaciones que puede hacer muy frustrante el proceso de desarrollo de algunas funcionalidades que queramos aplicar.

En posteriores entradas intentaré hablar más en profundidad de la estructura de la base de datos y los distintos módulos y elementos de los que dispone para funcionar. Pero ahora mismo querría centrarme más en uno de los problemas que me he ido encontrado mientras desarrollaba con PL/SQL.

Y es que, una de las carencias que nos hemos encontrado ha sido a la hora de trabajar con la escalabilidad y modularidad de las funciones que incorporamos a la base de datos.

Normalmente en el mundo de la programación más moderna(de los noventa hacia aquí) ha sido siempre muy importante el concepto de reutilización de código y el de diseñar los programas para que tengan un mantenimiento lo más sencillo posible. Lo que se traduce en hacer el código tan solo una vez y acceder a éste siempre que lo necesites. Esto hace que sea más sencillo de actualizar ya que solo lo tienes que modificar en un sitio y evitar así el tener que recorrer miles de líneas.

No me considero en absoluto un profesional ni un experto en PL/SQL ni trabajando con bases de datos Oracle, todo lo que hemos realizado ha sido de forma totalmente autodidacta y "a salto de mata" conforme lo necesitábamos para realizar nuestro trabajo; por lo tanto esta es una aproximación a  resolver un problema que puede ser más o menos eficiente que otras, pero es funcional y puede resultar de mucha utilidad para otras personas, ya que no hemos logrado encontrar demasiada documentación sobre el tema, la cual, demasiadas veces, está tan solo disponible en inglés.

Poniéndonos en situación, gran parte del código de PL/SQL con el que estamos trabajando está integrado en una serie de estructuras llamadas paquetes.

Estos paquetes pueden tomarse como una especie de clase de .net o java, por buscar una aproximación, en la que declaramos varias funciones que trabajen con la base de datos.

No obstante, como ya he comentado previamente, el lenguaje tiene ciertas carencias básicas que otros lenguajes OO de uso más extendido tienen, y en este caso sería el trabajar con más facilidad con los conjuntos de datos.

Descripción del problema: lo que queremos hacer es llamar desde una función de uno de nuestros paquetes a otra que nos retornaría un grupo de datos en un array, el cual usaríamos para trabajar en una llamada de SQL de las de toda la vida. Para el ejemplo lo que haremos es empezar con una query base y partirla en dos, la primera la introduciremos en un paquete y la segunda en una función a parte a la que llamaremos desde dentro de ese paquete y trabaremos con los datos que nos retorne.

Esta sería:
SELECT A.CAMPO1, A.CAMPO2
    FROM T_TABLA_A A
    WHERE A.ID_CAMPO3 IN (SELECT CAMPO1, CAMPO2 from T_TABLA where CAMPOID = ID_BUSQUEDA2IN);

Primero, antes de empezar, necesitamos crear un paquete que contenga una serie de datos que necesitaremos más adelante. No voy a explicar ahora qué hace cada parte del código y sólo lo haré de su funcionalidad directa.

create or replace
Package Dummy As
  Type Cursor_Out Is Ref Cursor;
end Dummy;
Con este paquete que hemos creado llamado Dummy tenemos el cursor que usaremos más adelante para retornar los datos de la función.

Después tendremos que declarar un tipo para Oracle. Esto es una especie de variables u objetos personalizados que podemos crear en la base de datos. Su creación es muy sencilla, en este caso haremos un array de números:

create or replace
TYPE NUMBER_ARRAY IS TABLE OF number;
Los usaremos para trabajar con este en las querys como si de una tabla normal y corriente se tratase.

Una vez hecho esto ya tenemos la estructura básica para trabajar con la query.

Primero declararemos la función que retornará los datos:

create or replace
FUNCTION  funcion_retorna_datos(ID_BUSQUEDA2IN IN T_TABLA.CAMPOID%TYPE) RETURN DUMMY.cursor_out IS

cursor_ret  dummy.cursor_out;

BEGIN


 open cursor_ret for
        SELECT CAMPO1, CAMPO2 from T_TABLA where CAMPOID = ID_BUSQUEDA2IN;

  RETURN cursor_ret;
 
END funcion_retorna_datos;

Este es símplemente el código de una función típica de PL/SQL en Oracle. Tiene la declaración del nombre, la entrada de datos, el retorno, una declaración de variables y el código de en medio que símplemente es la query que había entre los paréntesis. En resumen, símplemente introduce el retorno en un cursor del tipo que hemos creado en el paquete Dummy y lo retorna.

Ahora vamos a la parte con miga, que es crear un procedimiento que, en este caso estaría, dentro de un paquete, que llamará a funcion_retorna_datos y usa el resultado de esa llamada dentro de la select que alberga.

 PROCEDURE QUERY_SENCILLA_CON_LLAMADA(ID_BUSQUEDA1IN IN NUMBER, ID_BUSQUEDA2IN IN T_TABLA.CAMPOID%TYPE,
                     CUROUT OUT TCURSOR) IS  
       cur_array NUMBER_ARRAY; 
       cursor_intermedio  tcursor;
      
       MICURSOR  tcursor;      
  BEGIN
   
      cursor_intermedio  := funcion_retorna_datos(ID_BUSQUEDA2IN);

      loop
      FETCH cursor_intermedio BULK COLLECT INTO cur_array;
      EXIT WHEN cursor_intermedio%NOTFOUND;
      end loop;
     
     
    OPEN MICURSOR FOR
    SELECT A.CAMPO1, A.CAMPO2
    FROM T_TABLA_A A
    WHERE A.ID_CAMPO3 IN (select column_value from table(cur_array));
   
    CUROUT := MICURSOR;
  END QUERY_SENCILLA_CON_LLAMADA;

En este caso tenemos un procedimiento con dos variables de entrada de datos, la primera un número y la segunda una del tipo que tenga la columna CAMPOID de la tabla T_TABLA, y como retorno un cursor llamado TCURSOR que se declararía en la cabecera del paquete(como he dicho antes, ya me explayaré más adelante con las explicaciones sobre PL/SQL y Oracle).

Una vez dentro del código, declararemos un array del tipo que hemos creado antes, en este caso uno de números, y también un cursor para albergar el resultado de la función funcion_retorna_datos, como vemos ni siquiera es del mismo tipo que el que retorna originalmente la función. No es necesario mientras sean compatibles, y en este caso lo son ya que ambos son cursores.

Entonces símplemente llamaremos a la función asignándole el valor de respuesta a la variable que lo albergará:
cursor_intermedio  := funcion_retorna_datos(ID_BUSQUEDA2IN);
E introduciremos los valores en el array, ya que no podemos hacer diréctamente una query de un cursor. Lo tendremos que hacer con un bucle que irá introduciendo los datos uno a uno hasta que el cursor llegue al final.
      loop
      FETCH cursor_intermedio BULK COLLECT INTO cur_array;
      EXIT WHEN cursor_intermedio%NOTFOUND;
      end loop;
Entonces ya tendremos el array de número llamado cur_array inicializado con los datos que nos ha envíado la función anteriormente. Ahora todo lo que tendremos que hacer es usarla en la query como si se tratara de una tabla cualquiera.

SELECT A.CAMPO1, A.CAMPO2
    FROM T_TABLA_A A
    WHERE A.ID_CAMPO3 IN (select column_value from table(cur_array));
Como vemos, estamos usando un array como fuente de una consulta SQL pasándola como parametro a table().