Desenroscado de bucles

El Desenroscado de bucles (conocido en inglés como loop unrolling o Loop unwinding) es una técnica de optimización de bucles que intenta mejorar la velocidad de ejecución de un programa a costa de aumentar su tamaño binario (Situación de compromiso espacio-tiempo). Esta transformación puede hacerla manualmente el programador o un Compilador optimizador.

El objetivo del desenroscado de bucles es incrementar la velocidad del programa al reducir (o eliminar) instrucciones que controlan el bucle, como aritmética de punteros o la verificación de final de bucle en cada iteración;​ reduciendo la penalización por ramificación además de “ocultar latencias, en particular, la espera de la lectura de datos de memoria”.​ Para eliminar esta sobrecarga en la computación, los bucles pueden ser reescritos como una repetición de sentencias similares independientes.​

Ventajas

El mayor peso en los bucles pequeños se localiza en las instrucciones que incrementan el puntero o índice al siguiente elemento del array y en los test de “¿ha finalizado el bucle?”. Si un compilador o ensamblador de optimización es capaz de precalcular compensaciones para cada variable de la matriz referenciada individualmente, éstas pueden incorporarse directamente en las instrucciones de código de máquina, por lo que no requieren operaciones aritméticas adicionales en tiempo de ejecución.

• Puede conseguirse una mejora significativa si la reducción de instrucciones a ejecutar compensa por cualquier pérdida de rendimiento causada por el incremento en el tamaño del programa.
• La predicción de saltos se minimiza.​
• Si las instrucciones del bucle son independientes entre sí (es decir: si las instrucciones de un ciclo del bucle no afectan a las instrucciones del ciclo siguiente), éstas pueden ser ejecutadas en paralelo.
• El desenroscado puede realizarse dinámicamente si el número de elementos del array no se conoce en tiempo de compilación (como en el Dispositivo de Duff).

Los compiladores optimizadores pueden desenroscar bucles automáticamente o bajo demanda.

Desventajas

• El tamaño del programa aumenta, este efecto puede no ser deseado, particularmente en aplicaciones embebidas.
• Puede que también cause un incremento en los fallos de caché de instrucción, que afectan negativamente al rendimiento.
• A menos que la transformación sea aplicada de manera transparente por un compilador optimizador, el código resultante es menos legible.
• Si en el cuerpo del bucle se realizan llamadas a función, puede que no sea posible combinar el desenroscado con Inlining, ya que el incremento del tamaño el código podría ser excesivo. Por lo tanto, puede que se deba escoger entre ambas optimizaciones.
• Posible aumento del uso de los registros en una sola iteración para almacenar variables temporales^{[cita requerida]}, lo que puede reducir el rendimiento, aunque dependerá mucho de posibles optimizaciones​
• Con la excepción de códigos muy pequeños y simples, los bucles desenroscados que contienen ramificaciones son más lentos que si se usa recursión.​

Desenroscado de bucles estático o manual

El desenroscado de bucles manual (o estático) requiere que el programador analice el bucle e interprete sus iteraciones como una secuencia de instrucciones que pueden reducir la sobrecarga del bucle. Sería el desenroscado opuesto al desenroscado dinámico, que es realizado por el compilador.

Ejemplo de desenroscado manual en C

Supongamos que debemos optimizar una función que borra exactamente 100 objetos de una colección. Esta operación se haría normalmente con un bucle for que llamaría a la función borrar(indice_de_objeto);. Si la carga de trabajo del bucle es mayor que la requerida por la función de borrado, desenroscar el bucle puede acelerar el proceso.

Bucle normal	Bucle desenroscado
for (int indice = 0; indice < 100; ++indice) { borrar(indice); }	for (int indice = 0; indice < 100; indice += 5) { borrar(indice); borrar(indice + 1); borrar(indice + 2); borrar(indice + 3); borrar(indice + 4); }

Como consecuencia de esta modificación, el nuevo programa debe hacer 20 iteraciones en lugar de 100. Por lo tanto sólo deben hacerse el 20% de los saltos y ramificaciones condicionales, lo cual puede ser un descenso potencialmente significativo de la carga de administración del bucle. Para un óptimo beneficio no deben usarse variables que requieran aritmética de punteros en el código desenroscado.

Por otro lado, este desenroscado manual hace crecer el código de 4 a 8 líneas, pudiendo provocar durante la ejecución que se usen más registros para almacenar las variables de cada iteración^{[cita requerida]}. Además, las variables de control del bucle y la cantidad de operaciones en la estructura desenroscada deben ser escogidas cuidadosamente para asegurar que el comportamiento es el mismo que en el código original. Por ejemplo, debemos considerar la posibilidad de que la cantidad de iteraciones no fuese divisible por 5. Los cambios requeridos también se complican si las condiciones de finalización del bucle son variables.

Complejidad prematura

En este simple caso, el control del bucle es tan solo un trabajo extra que organiza las instrucciones. El bucle en sí mismo no contribuye a obtener el resultado deseado, tan sólo ahorra al programador del tedio de replicar el código varias veces, esta tarea podría haber sido delegada al preprocesador o a las herramientas de los editores de texto. De manera parecida, las instrucciones if y otras estructuras de control del flujo de programa pueden ser sustituidas por código replicado, con la salvedad de que inflan el código. Es trivial para un programa realizar las combinaciones, pero un programador puede encontrar la repetición aburrida y cometer errores.

Bucle normal	Bucle desenroscado
for (indice = 1; indice <= 8; indice++){ if (indice % 2 == 0) cosas_pares(indice); else cosas_impares(indice); }	cosas_impares(1); cosas_pares(2); cosas_impares(3); cosas_pares(4); cosas_impares(5); cosas_pares(6); cosas_impares(7); cosas_pares(8);

El siguiente ejemplo incluye la variable de índice en el cómputo:

Bucle normal	Bucle desenroscado
x(1) = 1; for (indice = 2; indice <= 9; indice++){ x(indice) = x(indice - 1) * indice; printf("%d %d",indice,x(indice)); }	x(1) = 1; x(2) = x(1) * 2; printf("2%d",x(2)); x(3) = x(2) * 3; printf("3%d",x(3)); x(4) = x(3) * 4; printf("4%d",x(4)); ...etc.

que al ser compilado, producirá gran cantidad de código (se podrán ver muchas instrucciones print) pero es posible aplicar más optimizaciones. En el ejemplo anterior sólo se hace referencia a x(indice) y x(indice - 1) en el bucle, por lo tanto: al no haber más referencias a la colección x sus usos pueden ser reemplazados por una variable. Pero hacer dicho cambio puede evitar que el compilador se de cuenta de que los valores del array son constantes, cada uno de ellos derivado de una constante previa y que por lo tanto podría resumir el código para que quedase:

  printf ("2,2");
  printf ("3,6");
  printf ("4,24");
  ...etc.

En general, el contenido de un bucle puede ser grande, implicando complejas indexaciones de array. Probablemente estos casos sean los mejores para dejar que un compilador optimizador desenrosque el bucle. Al replicar los bucles más internos puede permitir varias optimizaciones aunque la ganancia sea pequeña a no ser que el índice del bucle sea grande.

Desenroscando bucles WHILE

Un bucle WHILE similar al siguiente (expresado en pseudocódigo)

Bucle normal	Bucle desenroscado	Bucle desenroscado y retocado
WHILE (condición) DO acción ENDWHILE ...	WHILE (condición) DO acción IF NOT(condición) THEN GOTO salir acción IF NOT(condición) THEN GOTO salir acción ENDWHILE LABEL salir: .	IF (condición) THEN REPEAT { acción IF NOT(condición) THEN GOTO salir acción IF NOT(condición) THEN GOTO salir acción } WHILE (condición) LABEL salir:

Este desenroscado acelera el bucle ya que la instrucción ENDWHILE (que se compilará como un salto al inicio del bucle) se ejecutará tan sólo una tercera parte de las veces.

Es incluso mejor el ejemplo de pseudocódigo retocado, en que algunos compiladores optimizadores eliminarán por completo los saltos incondicionales.

Desenroscado dinámico

Dado que los beneficios del desenroscado de bucles suelen depender del tamaño del array (del que habitualmente no se sabe el tamaño hasta que se ejecuta el código) los compiladores en tiempo de ejecución pueden decidir si ejecutar un bucle normal o generar una secuencia (relativamente corta) de instrucciones individuales para cada elemento. Esta flexibilidad es una de las ventajas de las técnicas de compilación en tiempo de ejecución frente a la compilación estática o la optimización manual en el contexto del desenroscado de bucles. En esta situación, incluso con valores de índice la mejora es útil al requerir poco (o ningún) incremento del tamaño del programa.

Los programadores de lenguaje ensamblador (incluyendo los desarrolladores de compiladores optimizadores) también pueden beneficiarse del desenroscado dinámico de bucles, usando un método similar al que se usa para las tablas de saltos eficientes. En este caso, el mejor rendimiento se da cuando el índice máximo de cualquier campo referenciado en un array es menor al desplazamiento máximo que puede ser especificado en una instrucción en código máquina (que será marcado por el compilador si se sobrepasa).

El siguiente ejemplo es para los ensambladores de IBM S/360 o Z/Architecture y asume que un campo de 100 bytes será copiado desde un array llamado FROM a uno llamado TO (ambos con elementos de 256 bytes con 50 entradas).

Ejemplo en ensamblador (IBM/360 o Z/Architecture)

Para un ejemplo en x86 ver Enlaces externos. * initialize all the registers to point to arrays etc (R14 is return address) LM R15,R2,INIT load R15= '16', R0=number in array, R1--> 'FROM array', R2--> 'TO array' LOOP EQU * SR R15,R0 get 16 minus the number in the array BNP ALL if n > 16 need to do all of the sequence, then repeat * (if # entries = zero, R15 will now still be 16, so all the MVC's will be bypassed) * calculate an offset (from start of MVC sequence) for unconditional branch to 'unwound' MVC loop MH R15,=AL2(ILEN) multiply by length of (MVC..) instruction (=6 in this example) B ALL(R15) indexed branch instruction (to MVC with drop through) * Assignment (move) table - (first entry has maximum allowable offset with single register = X'F00' in this example) ALL MVC 15*256(100,R2),15*256(R1) * move 100 bytes of 16th entry from array 1 to array 2 (with drop through) ILEN EQU *-ALL length of (MVC...) instruction sequence; in this case =6 MVC 14*256(100,R2),14*256(R1) * MVC 13*256(100,R2),13*256(R1) * MVC 12*256(100,R2),12*256(R1) * All 16 of these 'move character' instructions use base plus offset addressing MVC 11*256(100,R2),11*256(R1) * and each to/from offset decreases by the length of one array element (256). MVC 10*256(100,R2),10*256(R1) * This avoids pointer arithmetic being required for each element up to a MVC 09*256(100,R2),09*256(R1) * maximum permissible offset within the instruction of X'FFF'. The instructions MVC 08*256(100,R2),08*256(R1) * are in order of decreasing offset, so the first element in the set is moved MVC 07*256(100,R2),07*256(R1) * last. MVC 06*256(100,R2),06*256(R1) * MVC 05*256(100,R2),05*256(R1) * MVC 04*256(100,R2),04*256(R1) * MVC 03*256(100,R2),03*256(R1) * MVC 02*256(100,R2),02*256(R1) * MVC 01*256(100,R2),01*256(R1) move 100 bytes of 2nd entry MVC 00*256(100,R2),00*256(R1) move 100 bytes of 1st entry * S R0,MAXM1 reduce Count = remaining entries to process BNPR R14 ... no more, so return to address in R14 AH R1,=AL2(16*256) increment 'FROM' register pointer beyond first set AH R2,=AL2(16*256) increment 'TO' register pointer beyond first set L R15,MAXM1 re-load (maximum MVC's) in R15 (destroyed by calculation earlier) B LOOP go and execute loop again * * ----- Define static Constants and variables (These could be passed as parameters) --------------------------------- * INIT DS 0A 4 addresses (pointers) to be pre-loaded with a 'LM' instruction MAXM1 DC A(16) maximum MVC's N DC A(50) number of actual entries in array (a variable, set elsewhere) DC A(FROM) address of start of array 1 ("pointer") DC A(TO) address of start of array 2 ("pointer") * ----- Define static Arrays (These could be dynamically acquired) -------------------------------------------------- * FROM DS 50CL256 array of (max) 50 entries of 256 bytes each TO DS 50CL256 array of (max) 50 entries of 256 bytes each

En este ejemplo, se necesitarán aproximadamente 202 instrucciones para un bucle 'conventional' (50 iteraciones) mientras que en el código dinámico anterior necesita sólo unas 89 instrucciones (un ahorro del 56% aproximadamente). Si el array consistiera de tan sólo 2 entradas, aún se ejecutaría en aproximadamente el mismo tiempo que el bucle sin desenroscar. El incremento del código es de tan sólo unos 108 bytes (incluso con miles de entradas en el array). Pueden usarse técnicas similares cuando intervienen múltiples instrucciones, siempre y cuando la longitud del conjunto de instrucciones se ajuste. Por ejemplo, en este ejemplo, si se necesita borrar el resto del array (asignando un valor nulo) después de haber copiado los 100 bytes, se puede añadir una instrucción de borrado XC xx*256+100(156,R1),xx*256+100(R2) inmediatamente después de cada MVC en la secuencia (entendiendo que xx coincide con el valor anterior en el MVC). También es perfectamente posible generar el código anterior 'en línea' usando una macro de ensamblador, especificando 4 o 5 operadores (u otra alternativa, crear una subrutina, que se accedería con una simple llamada, pasando una lista de parámetros), haciendo que la optimización quede accesible a programadores poco experimentados.

Ejemplo en C

El siguiente ejemplo muestra un desenroscado dinámico de bucle para un programa escrito en C. A diferencia del ejemplo anterior en ensamblador, la aritmética de punteros se genera por el compilador porque la variable indice se usa para indexar los elementos del array. La optimización más completa sólo es posible cuando se usan índices absolutos.

#include<stdio.h>

#define BLOQUE (8)

int main()
{ 
  int indice = 0; 
  int elementos = 50;                     // Numero a procesar.
  int iteraciones = (elementos / BLOQUE); // Cantidad de iteraciones.
  int resto = (elementos % BLOQUE);       // Resto (a procesar posteriormente).

  /* Si la cantidad de elementos no es divisible por BLOQUE
     calcula los elementos restantes a procesar */

  // Desenrosca el bucle en 'bloques' de 8 elementos
  while (iteraciones-- > 0) 
  { 
    printf("procesando(%d)\n", indice    );
    printf("procesando(%d)\n", indice + 1); 
    printf("procesando(%d)\n", indice + 2); 
    printf("procesando(%d)\n", indice + 3); 
    printf("procesando(%d)\n", indice + 4); 
    printf("procesando(%d)\n", indice + 5); 
    printf("procesando(%d)\n", indice + 6); 
    printf("procesando(%d)\n", indice + 7);

    // Actualiza el indice con los elementos procesados en la iteracion.
    indice += BLOQUE; 
  }

  /* Se usa una instruccion switch para procesar el resto no divisible por BLOQUE
     saltando a la etiqueta case que procesara en cascada el resto de casos para
     completar la operacion (Dispositivo de Duff). */
  switch (resto) 
  {
    case 7 : printf("process(%d)\n", indice + 6);
    case 6 : printf("process(%d)\n", indice + 5);
    case 5 : printf("process(%d)\n", indice + 4);
    case 4 : printf("process(%d)\n", indice + 3);
    case 3 : printf("process(%d)\n", indice + 2);
    case 2 : printf("process(%d)\n", indice + 1);
    case 1 : printf("process(%d)\n", indice    );
    case 0 :                                    ;
  }
  return 0;
}

Véase también

• Compilación en tiempo de ejecución.
• Loop splitting.
• Loop fusion.
• Dispositivo de Duff.
• Instruction-level parallelism.
• Computación paralela.

Lectura adicional

• Kennedy, Ken; Allen, Randy (2001). Optimizando los compiladores para arquitecturas modernas: Una aproximación basada en dependencias. Morgan Kaufmann. ISBN 1-55860-286-0. 

Enlaces externos

• Chapter 7, pages 8 to 10, of Michael Abrash's Graphics Programming Black Book es momento de desenroscar bucles, con un ejemplo en ensamblador x86.
• Desenroscado genérico de bucles.
• Optimizando subrutinas en lenguaje ensamblador.

• Datos: Q1869750