¿Cuándo es efectivo el desenrollado de lazo?

Question

Loop unwinding es una forma común de ayudar al compilador a optimizar el rendimiento. Me preguntaba si y en qué medida la ganancia de rendimiento se ve afectado por lo que está en el cuerpo del bucle:

1. número de declaraciones
2. número de llamadas a funciones
3. uso de tipos de datos complejos, métodos virtuales , etc.
4. dinámico (de) la asignación de la memoria

¿Qué reglas (de oro?) que utiliza para decidir si o no para relajarse un bucle de rendimiento crítica? ¿Qué otra optimización considera en estos casos?

Answer 1

En general, desenrollar los bucles a mano no vale la pena el esfuerzo. El compilador sabe mejor cómo funciona la arquitectura de destino y desenrollará el ciclo si es beneficioso.

Existen rutas de código que se benefician cuando se desenrollan para CPU de tipo Pentium-M, pero no se benefician para Core2, por ejemplo. Si desenrollo a mano, el compilador ya no puede tomar una decisión y puedo terminar con un código que no es el óptimo. P.ej. exactamente lo opuesto que traté de lograr.

Existen varios casos en los que desenrollo bucles críticos de rendimiento a mano, pero solo hago esto si sé que el compilador podrá, después del desenrollado manual, utilizar características específicas de arquitectura como instrucciones SSE o MMX. Entonces, y solo entonces lo hago.

Btw: las CPU modernas son muy eficientes en la ejecución de ramas bien predecibles. Esto es exactamente lo que es un bucle. La sobrecarga del ciclo es tan pequeña actualmente que rara vez hace la diferencia. Los efectos de latencia de memoria que pueden ocurrir debido al aumento en el tamaño del código, sin embargo, harán la diferencia.

Answer 2

Esta es una pregunta de optimización, y como tal solo hay una regla general: probar el rendimiento y probar una optimización de desenrollado de bucle solo si las pruebas demuestran que es necesario. Considere las optimizaciones menos disruptivas primero.

Answer 3

En mi experiencia, el desenrollado del bucle, y el trabajo que se necesita es efectiva cuando:

• sólo hay unas pocas declaraciones dentro del bucle.
• las declaraciones implican sólo un pequeño número de diferentes variables y no hay llamadas de funciones a
• Sus operaciones funcionan en la memoria ya asignada (una transformación de la imagen en el lugar, por ejemplo)

desenrollado parcial es a menudo menos trabajo para 80 % de la ganancia. Por lo tanto, en lugar de recorrer todos los píxeles de una imagen N por M (N M iteraciones) donde N es siempre divisible por 8, itere (N M/8) veces sobre cada bloque de ocho píxeles. Esto es especialmente eficiente si está realizando alguna operación que utiliza algunos de los píxeles vecinos.

He obtenido muy buenos resultados optimizando manualmente las operaciones en píxeles en instrucciones MMX o SSE (8 o 16 píxeles a la vez), pero también pasé días optimizando algo solo para descubrir que la versión está optimizada por el compilador corrió diez veces más rápido.

Y, por cierto, para la (hermosa | notable) la mayoría ejemplo de bucle desenrollado echa un vistazo a Duffs device

Answer 4

Una cosa importante a tener en cuenta: En el código de producción en su lugar de trabajo, el futuro legibilidad del código es mucho mayor que los beneficios de desenrollar lazo. El hardware es barato, el tiempo del programador no lo es. Solo me preocuparía el desenrollado del lazo si esa es la ÚNICA forma de resolver un problema de rendimiento comprobado (por ejemplo, en un dispositivo de baja potencia).

Otras reflexiones: Las características de los compiladores varían mucho, y en algunos casos, como Java, la determinación se hace sobre la marcha por el HotspotJVM, por lo que argumentaría en contra de la anulación del ciclo en cualquier caso.

Answer 5

Los bucles de desenrollado manual pueden ser ineficaces en procesadores más nuevos pero pueden ser útiles en GPU y arquitecturas ligeras como ARM, ya que no son tan buenos como los procesadores de CPU actuales en predicción y porque las pruebas y saltos realmente desperdician ciclos en aquellos procesadores.

Dicho esto, solo se debe hacer en bucles muy estrechos y en bloques, porque al desenrollar se está hinchando significativamente el tamaño del código y esto hará que la memoria caché en dispositivos pequeños y terminará con un problema mucho peor en su mano.

Una nota de advertencia, sin embargo, desenrollar un bucle debería ser el último recurso al optimizar. Pervierte su código a un nivel que lo hace inmanejable y alguien que lo lea podría romperse y amenazarlo a usted y a su familia más adelante. Sabiendo eso, haz que valga la pena :)

El uso de macros puede ser de gran ayuda para hacer que el código sea más legible y hará que el desenrollado sea deliberado.

Ejemplo:

for(int i=0; i<256; i++) 
{ 
    a+=(ptr + i) << 8; 
    a-=(ptr + i - k) << 8; 
    // And possibly some more 
} 

Se puede desenrollar a:

#define UNROLL (i) \ 
    a+=(ptr[i]) << 8; \ 
    a-=(ptr[i-k]) << 8; 


for(int i=0; i<32; i++) 
{ 
    UNROLL(i); 
    UNROLL(i+1); 
    UNROLL(i+2); 
    UNROLL(i+3); 
    UNROLL(i+4); 
    UNROLL(i+5); 
    UNROLL(i+6); 
    UNROLL(i+7); 
} 

En una nota relacionada, pero todavía algo relacionado, si realmente desea ganar en el lado cómputo de instrucciones, asegúrese de que todas las constantes consiguen unificado en menos inmediatos como sea posible en su código para que no termine con el siguiente ensamblaje:

// Bad 
MOV r1, 4 
// ... 
ADD r2, r2, 1 
// ... 
ADD r2, r2, 4 

En lugar de:

// Better 
ADD r2, r2, 8 

Por lo general, los compiladores graves a protegerse contra este tipo de cosas, pero no todos lo harán. Mantenga los '#define', 'enum' y 'static const' a mano, no todos los compiladores optimizarán las variables 'const' locales.

Answer 6

Básicamente, desenrollar es un costo útil de la estructura de bucle es una parte importante del cuerpo del bucle. La estructura de la mayoría de los bucles (y casi todos los bucles que se pueden desenrollar) consiste en (a) incrementar un número entero, (b) compararlo con otro entero y (c) saltar, dos de los cuales son casi los más rápidos instrucciones para la CPU. Por lo tanto, en casi cualquier ciclo, el cuerpo pesará la estructura, produciendo una ganancia insignificante. Si tiene incluso una llamada de función en su cuerpo, el cuerpo será un orden de magnitud más lento que la estructura; nunca lo notaría.

Casi todo lo que realmente puede beneficiarse del desenrollado es algo como memcpy(), donde el cuerpo del bucle solo se mueve de un punto a otro --- por lo que muchos compiladores de C++ C & han entrado automáticamente y desenrollando memcpy durante la última década.

Answer 7

Estas optimizaciones dependen en gran medida de la CPU en que se ejecuta el código y el compilador debe hacerlo, pero si está escribiendo dicho compilador, puede consultar el documento de Intel Intel(R) 64 and IA-32 Architectures Optimization Reference Manual Sección 3.4.1.7 :

• Desenrolle pequeños bucles hasta que la sobrecarga de las cuentas variables de ramificación y de inducción (en general) por menos de 10% del tiempo de ejecución del bucle.

• Evite desenrollar bucles excesivamente; esto puede dañar la memoria caché de seguimiento o la memoria caché de instrucciones.

• Desenrolle los bucles que se ejecutan con frecuencia y tienen un número predecible de iteraciones para reducir el número de interacciones a 16 o menos. Haga esto a menos que aumente el tamaño del código para que el conjunto de trabajo ya no se ajuste al rastreo o al caché de instrucciones. Si el cuerpo del bucle contiene más de una bifurcación condicional, entonces desenrósquelo para que el número de iteraciones sea 16/(# ramas condicionales).

También puede solicitar una copia impresa gratis here.

Answer 8

El desenrollado de lazo manual es útil en general solo para los bucles más triviales.

Como punto de referencia, la biblioteca de C++ estándar en g ++ desenrolla exactamente dos bucles en toda la fuente, que implementan la función de 'encontrar' con y sin predicado, que se parecen:

while(first != last && !(*first == val)) 
    ++first; 

Miré en estos, y otros, bucles, y decididos solo por bucles, esto fue trivial, valió la pena hacerlo.

¡Por supuesto, la mejor respuesta es solo desenrollar esos bucles donde su perfilador muestra que es útil hacerlo!

Answer 9

Si ha hecho todo lo demás posible, y este es su punto de acceso restante, y no hay casi nada dentro del circuito, entonces desenrollar tiene sentido. Esos son muchos "si". Para verificar si esa es su última opción, try this

Answer 10

Desde mi experiencia, el desenrollado de bucle puede brindar un rendimiento del 20% al 50% sin el uso de SEE en mi CPU intel i7.

Para bucle simple con una sola operación, hay una sobrecarga de un salto condicional y un incremento en el bucle. Puede ser efectivo hacer varias operaciones por salto e incremento. Ejemplo de desenrollado de lazo efectivo es el siguiente código:

En el código siguiente sin desenrollar, hay una sobrecarga de una comparación + un jumb + un incremento por operación de suma única. Además, todas las operaciones deben esperar al resultado de las operaciones previas.

template<class TData,class TSum> 
inline TSum SumV(const TData* pVec, int nCount) 
{ 
    const TData* pEndOfVec = pVec + nCount; 
    TSum nAccum = 0; 

    while(pVec < pEndOfVec) 
    { 
     nAccum += (TSum)(*pVec++); 
    } 
    return nAccum; 
} 

Y en el código unwinded, no es la sobrecarga de uno comparar + un jumb + un incremento por cuatro operación suma. Además, hay una gran cantidad de operaciones que no necesitan esperar el resultado de la operación anterior y que el compilador puede optimizar mejor.

template<class TData,class TSum> 
inline TSum SumV(const TData* pVec, int nCount) 
{ 
    const TData* pEndOfVec = pVec + nCount; 
    TSum nAccum = 0; 

    int nCount4 = nCount - nCount % 4; 
    const TData* pEndOfVec4 = pVec + nCount4; 
    while (pVec < pEndOfVec4) 
    { 
     TSum val1 = (TSum)(pVec[0]); 
     TSum val2 = (TSum)(pVec[1]); 
     TSum val3 = (TSum)(pVec[2]); 
     TSum val4 = (TSum)(pVec[3]); 
     nAccum += val1 + val2 + val3 + val4; 
     pVec += 4; 
    }  

    while(pVec < pEndOfVec) 
    { 
     nAccum += (TSum)(*pVec++); 
    } 
    return nAccum; 
}