Bucle normalizado

En informática , un bucle normalizado (a veces llamado bucle bien comportado) es un bucle en el que la variable del bucle comienza en 0 (o cualquier constante) y se incrementa en uno en cada iteración hasta que se cumple la condición de salida. Los bucles normalizados son muy importantes para la teoría de compiladores y el análisis de dependencias de bucles , ya que simplifican el análisis de dependencias de datos . ^{[ 1 ]}

Bucles bien comportados

Un bucle bien comportado normalmente tiene la forma:

para ( i = 0 ; i < MAX ; i ++ ) a [ i ] = b [ i ] + 5 ;

Debido a que el incremento es unitario y constante, es muy fácil ver que, si tanto a como b son mayores que MAX, este bucle nunca accederá a memoria fuera del rango asignado.

Bucles no normalizados

Un bucle no normalizado puede comenzar en índices diferentes, incrementarse en cantidades no unitarias y tener condiciones de salida difíciles de definir. Estos bucles son difíciles de optimizar, vectorizar e incluso recorrer, especialmente si se ejecutan funciones en cualquier parte de las condiciones del bucle.

Un ejemplo sencillo, donde no empieza desde el principio y aumenta de uno en uno:

// Example 1for(i=7;i<MAX;i+=3)a[i]=b[i]+5;

A more complicated example, with an additional exit condition:

// Example 2for(i=7;i<MAX||i>MIN;i+=3)a[i]=b[i]+5;

Loops can also have non-predictable behavior during compilation time, where the exit condition depends on the contents of the data being modified:

// Example 3for(i=7;i<MAX&&a[i];i+=3)a[i]=b[i]+5;

Or even dynamic calculations by means of function calls:

// Example 4for(i=start();i<max();i+=increment())a[i]=b[i]+5;

Reverse loops are also very simple, and can be easily normalized:

// Example 5for(i=MAX;i>0;i--)a[i]=b[i]+5;

Converting to a normalized loop

If the non-normalized doesn't have dynamic behaviour, it's normally very easy to transform it to a normalized one. For instance, the first example (Example 1) above can easily be converted to:

// Ejemplo 1 -> normalizado para ( i = 0 ; i < ( MAX -7 ) / 3 ; i ++ ) a [ i * 3 + 7 ] = b [ i * 3 + 7 ] + 5 ;

Si bien el tercer ejemplo se puede normalizar parcialmente para permitir cierta paralelización, aún carece de la capacidad de conocer la duración del bucle (cuántas iteraciones habrá), lo que dificulta la vectorización mediante el uso de hardware multimedia.

Comenzar en 7 no supone un gran problema, siempre que el incremento sea regular, preferiblemente uno. Cuando varias instrucciones dentro del bucle utilizan el índice, se pueden crear algunas variables temporales privadas para gestionar los diferentes ritmos de iteración.

El bucle inverso (Ejemplo 5) también es fácil de normalizar:

// Ejemplo 5 -> normalizado para ( i = 0 ; i < MAX ; i ++ ) a [ MAX - i ] = b [ MAX - i ] + 5 ;

Tenga en cuenta que el acceso sigue siendo inverso. En este caso, no tiene sentido dejarlo así (ya que no hay dependencia de datos ), pero cuando existen dependencias, se debe tener cuidado de revertir también el acceso, ya que podría alterar el orden de las asignaciones.

Conversiones imposibles

El ejemplo 4 anterior hace imposible predecir nada de ese bucle. A menos que las funciones sean triviales (constantes), no hay forma de saber dónde comenzará y terminará el bucle ni cuánto se incrementará en cada iteración. Estos bucles no solo son difíciles de paralelizar, sino que además tienen un rendimiento pésimo.

En cada iteración, el bucle evaluará dos funciones ( max() e increment() ). Incluso si se insertan las funciones en línea, la condición se vuelve demasiado compleja como para que valga la pena optimizarla. El programador debe tener especial cuidado de no crear estos bucles a menos que sea estrictamente necesario (si es que alguna vez se crean).

Otro peligro de este tipo de bucles surge cuando la evaluación depende de que los datos se estén modificando. Por ejemplo, un error común al usar iteradores es eliminar elementos de una lista mientras se modifica, o confiar en tamaños (para la condición de salida) que ya no son válidos.