Las aplicaciones cada vez demandan mayores recursos a la hora de ejecutarse: mayor velocidad, mas memoria, etc. Y a veces parece que la única solución es la de fabricar máquinas más veloces, sin embargo, ¿podríamos pensar que esto es inevitable?
Cuando los programadores realizan sus programas se centran principalmente en la parte algorítmica de los mismos que, como es normal, es la parte más importante en esta etapa del desarrollo software, ¿qué haríamos nosotros con un programa que no hace lo que queremos?, sin embargo, en este post vamos a preocuparnos menos de esta fase y pasar a transformar nuestros programas, que sabemos que ya funcionan correctamente, para que se ejecuten de una manera mucho más rápida.
La mayoría de nosotros, cuando nos enfrentamos a la resolución de un problema intentamos hacer el algoritmo con el único fin de que funcione correctamente, utilizando multitud de variables auxiliares y montones de comprobaciones innecesarias. Cuando lo probamos y vemos que funciona, una sonrisa de oreja a oreja recorre nuestra cara, ¿ahora qué?, Lo hemos hecho, pero ¿podríamos haberlo hecho mejor y más rápido?.
Aceleremos nuestros programas
El primer paso que debemos dar ante todo al implementar un algoritmo es el de comprender el problema, ¿qué es lo que realmente queremos resolver?, ¿cómo lo vamos a resolver? y ¿cuál es la mejor forma de resolverlo?. De nada nos vale realizar una implementación eficiente de la ordenación utilizando
el método de la burbuja, frente a una implementación mediocre pero correcta del algoritmo de ordenación utilizando el método
QuickSort.
Apenas aumentemos el número de elementos de entrada de nuestro eficiente algoritmo, este se verá delegado a segundo puesto por nuestra lenta implementación del famoso QuickSort.
Sin embargo la cosa cambia frente a dos implementaciones distintas del mismo algoritmo, el más eficiente será el ganador. ¿Y cuales son esos parámetros que hacen que una implementación sea más eficiente? Principalmente el número de instrucciones que deben ejecutarse para resolver una misma tarea, aunque existen otras como el orden de complejidad del algoritmo, (probablemente la más importante, aunque no entraremos en ello), el aprovechamiento de diversas características del microprocesador, acceso eficiente a la memoria caché y otros parámetros que iremos viendo poco a poco.
La idea de este post es la de mostrar pequeñas transformaciones y trucos que podemos aplicar al código de nuestros programas que harán la ejecución de los mismos mucho más rápidos y que pueden ser aplicados tanto por los programadores gurús o avanzados como por los que estéis descubriendo la programación recientemente.
Antes de empezar me gustaría indicar que los conocimientos que se adquieran en estos artículos no solo son válidos para su aplicación en la programación Delphi (que es el lenguaje que vamos a usar en los ejemplos), sino que son igualmente efectivos aplicados a cualquier lenguaje de programación imperativo.
Bueno, después de esta introducción vayamos al lío:
Desenrolle de bucles
Uno des las primeras técnicas que aprendí para acelerar los programas viene como consecuencia de la aparición de las estructuras iterativas en los mismos. Si nos fijamos bien, la mayoría de los algoritmos tienen su cuerpo principal en algún tipo de bucle que se ejecuta interminablemente hasta que se cumple algún tipo de condición y puede deducirse que si aceleramos la ejecución de los bucles, la ejecución del programa completo será mucho más rápida.
Veamos el siguiente ejemplo:
for k := 0 to 10000 do
A[k] := B[k] * C[k]
En este sencillo ejemplo pude verse como estamos multiplicando los elementos de dos vectores y guardando sus resultados en un tercero.
¿En qué consiste el desenrolle de bucles?. Veamos el ejemplo anterior al que se le ha aplicado el desenrolle una sola vez:
for j := 0 to 5000 do // se ha dividido la condición entre numero de desenrolles
begin
A[j*2] := B[j*2] * C[j*2];
A[(j*2)+1] := B[(j*2)+1] * C[(j*2)+1];
end;
El desenrolle de bucles consiste en hacer que el número de veces que se ejecuta el cuerpo del bucle sea menor, modificando este de tal manera que se ejecuten las mismas operaciones, teniendo especial cuidado con los índices que se manejan.
Veamos unas gráficas de rendimiento.
 |
| Rendimiento de la rutina desenrollada frente a la original |
Como puede verse, si tomamos como referencia lo que tarda en ejecutarse el bucle original, el bucle desenrollado una sola vez, produce un incremento de velocidad de un 224,7 % más. De esta manera hemos hecho que la gestión del bucle for sea menor por un coste adicional de mayor código en el cuerpo del mismo.
La implementación interna del bucle for consiste en comprobar si se ha llegado al limite del mismo, y si no, incrementar el contador. Reduciendo el número de veces que se realizan estas comprobaciones hacemos que nuestro algoritmo se ejecute más rápido y además al colocar un cuerpo del bucle más grande hemos dado la posibilidad al microprocesador de planificar mejor las instrucciones para su reordenación y hemos hecho que los cauces de ejecución del mismo estén ocupados durante más tiempo.
Desenrollemos ahora el bucle en 4:
for j := 0 to 2500 do
begin
A[j*4] := B[j*4] * C[j*4];
A[(j*4)+1] := B[(j*4)+1] * C[(j*4)+1];
A[(j*4)+2] := B[(j*4)+2] * C[(j*4)+2];
A[(j*4)+3] := B[(j*4)+3] * C[(j*4)+3];
end;
Ahora la condición de finalización e incremento del bucle for se reduce en un cuarto al bucle original, por lo que el tiempo de ejecución de este algoritmo se espera mucho menor.
 |
| Tiempo y rendimiento del bucle desenrollado 4 veces |
Como podemos observar, los tiempos de ejecución de este algoritmo son mucho menores consiguiéndose un incremento de velocidad del 345%.
Vamos por último a desenrollar el bucle 8 veces.
for j := 0 to 1250 do
begin
A[j*8] := B[j*8] * C[j*8];
A[(j*8)+1] := B[(j*8)+1] * C[(j*8)+1];
A[(j*8)+2] := B[(j*8)+2] * C[(j*8)+2];
A[(j*8)+3] := B[(j*8)+3] * C[(j*8)+3];
A[(j*8)+4] := B[(j*8)+4] * C[(j*8)+4];
A[(j*8)+5] := B[(j*8)+5] * C[(j*8)+5];
A[(j*8)+6] := B[(j*8)+6] * C[(j*8)+6];
A[(j*8)+7] := B[(j*8)+7] * C[(j*8)+7];
end;
 |
| Tiempo del bucle desenrollado 8 veces |
 |
| Rendimiento del bucle desenrollado 8 veces |
Desenrollando 8 veces el bucle interno del algoritmo original hemos llegado a conseguir un método que realiza lo mismo que el primero pero 4,2 veces más rápido.
Fijaros en que la condición del bucle se ha dividido por 8 y los índices hacen la función de desplazamiento dentro del bucle, haciendo que el espacio de trabajo dentro de los arrays sea el correcto.
Optimización del índice del bucle
Para optimizar el bucle for debemos estudiar que parámetros entran en juego en su ejecución. El bucle for está formado por el contador, la condición de terminación y el cuerpo del bucle. Hasta ahora hemos realizado operaciones sobre el cuerpo del bucle sin embargo también tenemos que tener en cuenta el índice y la condición. Respecto a la condición, esta deberá ser lo más sencilla posible ya que se evalúa en cada iteración del bucle. Respecto al contador, en los ejemplos anteriores hemos utilizado una variable global, sin embargo, ¿que pasaría si utilizamos una variable local al procedimiento donde se ejecuta el bucle for?.
 |
| Tiempo de utilizar una variable local al procedimiento frente a los anteriores métodos |
 |
| Ganancia de rendimiento al utilizar una variable local al procedimiento frente a los anteriores métodos |
Si nos fijamos en las dos últimas columnas de las figuras anteriores, podemos ver los tiempos de ejecución del bucle desenrollado 8 veces, pero en el último se ha utilizado una variable local al procedimiento donde se encontraba el bucle for como contador del mismo.
Procedure Rutina
var
j : integer;
begin
for j := 0 to 1250 do
begin
A[j*8] := B[j*8] * C[j*8];
A[(j*8)+1] := B[(j*8)+1] * C[(j*8)+1];
A[(j*8)+2] := B[(j*8)+2] * C[(j*8)+2];
A[(j*8)+3] := B[(j*8)+3] * C[(j*8)+3];
A[(j*8)+4] := B[(j*8)+4] * C[(j*8)+4];
A[(j*8)+5] := B[(j*8)+5] * C[(j*8)+5];
A[(j*8)+6] := B[(j*8)+6] * C[(j*8)+6];
A[(j*8)+7] := B[(j*8)+7] * C[(j*8)+7];
end;
end;
Para explicar lo que ha ocurrido tenemos que pensar como realiza un compilador la etapa de optimización. Cuando se entra en un procedimiento se almacenan en la pila los registros del microprocesador. Esto implica que se queden libres, para utilizarlos, albergando en ellos variables que se utilizarán dentro del procedimiento, donde en este caso, el índice del bucle for es un candidato en potencia. Ya que el índice se ha colocado dentro de uno de los registros del microprocesador, su manipulación es muchísimo más rápida a la hora de, por ejemplo, multiplicarlo, como vemos en el código anterior. De ahí el incremento de velocidad en la ejecución de este procedimiento en un 625%.
¿Y esto es todo?
¡Os parece poco! Bueno, intentaremos mejorarlo. Hemos aprendido a desenrollar los bucles for teniendo especial cuidado con el contador. Sin embargo, el desenrolle de bucles muestra toda su potencia con otra de las estructuras iterativas de la programación imperativa: el bucle while.
Internamente, el for no está diseñado de manera óptima lo que lleva a que el bucle while sea más eficiente para la mayoría de las tareas. Veamos como se construye un bucle for internamente.
for i:=n to m do
A[i] := B[i] * C[i]
se transforma en:
PA:=@A[m];
PB:=@B[m];
PC:=@C[m];
contador := m-n+1;
if contador > 0 then
repeat
PA^:=PB^ * PC^;
inc(PA);
inc(PB);
inc(PC);
dec(contador);
until contador = 0;
y el problema es que la variable i no aparece por ningún lado dentro de la implementación del bucle, lo que lleva a que en cada iteración tenemos, en este caso, que incrementar los tres punteros de las variables que necesitan el índice del bucle. Podemos ver además, en el ejemplo anterior, la sobrecarga de código que es necesario introducir a la hora de inicializar el bucle for.
El código anterior en formato while sería el siguiente:
i:=n;
while i <= m do
A[i] := B[i] * C[I];
Por lo tanto, nuestra rutina podría transformase en:
Procedure Rutina
var
j : integer;
begin
while j < 10000 do
begin
A[j] := B[j] * C[j];
A[j+1] := B[j+1] * C[j+1];
A[j+2] := B[j+2] * C[j+2];
A[j+3] := B[j+3] * C[j+3];
A[j+4] := B[j+4] * C[j+4];
A[j+5] := B[j+5] * C[j+5];
A[j+6] := B[j+6] * C[j+6];
A[j+7] := B[j+7] * C[j+7];
j := j + 8;
end;
end;
 |
| Comparativa de tiempos de todas los métodos implementados |
 |
| Ganancia de tiempo de todos los métodos |
Como puede verse en las figuras anteriores, la implementación con la estructura while es un 50% más rápida que la misma implementada con el for debido principalmente a que desaparece la multiplicación del índice dentro del cuerpo del bucle y de la transformación más eficiente de la misma a código máquina, siendo finalmente 6,7 veces más rápida que la rutina inicial.
Debemos recordar que el índice debe ser divisible por el número de veces que queremos desenrollar el cuerpo del bucle.
Conclusiones
Después de ver estos resultados seguramente tendréis una pregunta en vuestra mente, ¿podríamos desenrollar hasta cualquier nivel?. La respuesta es sí; de esta manera aumentará el rendimiento del programa pero también su tamaño aumentará considerablemente y si el cuerpo del bucle es muy complejo habrá que desenrollarlo y modificarlo con cuidado de no equivocarnos (cosa que es muy común que ocurra) y el código pasará a ser menos legible. Es por tanto que deberemos llegar a una situación de compromiso entre espacio, legibilidad y velocidad prestando atención también al contenido y tipo del cuerpo del bucle. Valores comunes de desenrolle son 1,2,4 y 8. Además hay que tener en cuenta que la condición de salida sea múltiple del nivel de desenrolle que queremos aplicar, sino es así deberíamos comprobar con que indice se ha salido y si falta alguna otra iteración implementarla fuera del bucle.
Otro factor a tener en cuenta es el de intentar utilizar siempre, en cualquier estructura iterativa, una variable local como índice para que pueda ser planificada y así ser gestionada para ubicarla en un registro del microprocesador.
También debemos destacar la utilización de la estructura while frente a la for a menos que manejemos arrays de más de una dimensión ya que sino tendremos que pagar por el hecho de utilizar multiplicaciones a la hora de desplazar los punteros de las matrices.
Para los más avezados podéis intentar aplicar las técnicas que hemos aprendido en esta ocasión al siguiente fragmento de código, desenrollando el bucle en un factor de 2 (fijaos que no conocemos a priori el valor de k por lo que tendremos que añadir código para controlar esa situación).
Randomize;
k := random(1000);
for j:=0 to k do
A[j] := B[j] * C[j];
En esta entrega hemos aprendido una de las técnicas más utilizadas entre los programadores y compiladores para acelerar la ejecución de los programas, que consiste en duplicar el código dentro de una estructura iterativa para disminuir el número de veces que se ejecuta el cuerpo de control del bucle, a lo que se denomina desenrolle de bucles.
