performance loops assembly optimization micro-optimization

performance - ¿Por qué los bucles siempre se compilan en el estilo "do... while"(salto de cola)?



loops assembly (1)

Menos instrucciones / uops dentro del bucle = mejor. Estructurar el código fuera del bucle para lograr esto es a menudo una buena idea, ya sea que se trate de ramas para permitir una mejor estructura de bucle, o pelar parcialmente la primera iteración para que pueda caer en el bucle en un punto conveniente y tal vez guardar una instrucción mov o lo que sea que contenga (no estoy seguro si hay un nombre para eso; "canalización de software" es algo específico).

do{}while() es la estructura canónica / idiomática para bucles en asm en todas las arquitecturas, acostúmbrate a ella. IDK si hay un nombre para ello; Yo diría que tal ciclo tiene una "estructura do while". Si desea nombres, puede llamar a la estructura while() "código no optimizado" o "escrito por un novato". : P Loop-branch en la parte inferior es universal, y ni siquiera vale la pena mencionarlo como Loop Optimization . Siempre haces eso.

Este patrón es tan ampliamente utilizado que en las CPU que usan predicción de rama estática para ramas sin una entrada en los cachés de predicción de rama, se predicen ramas condicionales hacia adelante desconocidas, no tomadas, se predicen ramas hacia atrás desconocidas (porque probablemente son ramas de bucle ) Vea la predicción de rama estática en los nuevos procesadores Intel en el blog de Matt Godbolt y el capítulo de predicción de rama de Agner Fog al comienzo de su microarchivo PDF.

Esta respuesta terminó usando ejemplos x86 para todo, pero gran parte de esto se aplica en todos los ámbitos para todas las arquitecturas. No me sorprendería si otras implementaciones superescalares / fuera de orden (como algunos ARM o POWER) también tienen un rendimiento limitado de instrucción de rama, ya sea que se tomen o no. Pero menos instrucciones dentro del bucle son casi universales cuando todo lo que tiene es una rama condicional en la parte inferior y ninguna rama incondicional.

Si el ciclo puede necesitar ejecutarse cero veces , los compiladores suelen poner una prueba y una rama fuera del ciclo para omitirlo, en lugar de saltar a la condición de ciclo en la parte inferior. (es decir, si el compilador no puede probar que la condición del bucle siempre es verdadera en la primera iteración).

Por cierto, este documento llama transformar while() a if(){ do{}while; } if(){ do{}while; } una "inversión", pero la inversión de bucle generalmente significa invertir un bucle anidado. (por ejemplo, si la fuente recorre una matriz multidimensional de fila mayor en el orden incorrecto, un compilador inteligente podría cambiar for(i) for(j) a[j][i]++; en for(j) for(i) a[j][i]++; si puede probar que es correcto.) Pero supongo que puede mirar if() como un ciclo de iteración cero o uno. Dato curioso, los desarrolladores de compiladores que enseñan a sus compiladores cómo invertir un bucle (para permitir la auto-vectorización) para un caso (muy) específico es la razón por la cual el benchmark libquantum de SPECint2006 está "roto" . La mayoría de los compiladores no pueden invertir bucles en el caso general, solo los que se ven casi exactamente como el de SPECint2006 ...

Puede ayudar al compilador a hacer un asm más compacto (menos instrucciones fuera del bucle) escribiendo do{}while() bucles en C cuando sabe que la persona que llama no puede pasar size=0 o lo que sea que garantice que un bucle se ejecute al menos una vez.

(En realidad, 0 o negativo para los límites de bucle con signo. Los contadores de bucle con signo y sin signo es un problema de optimización complicado, especialmente si elige un tipo más estrecho que los punteros; verifique la salida asm de su compilador para asegurarse de que no esté extendiendo un bucle estrecho contrarresta el tiempo dentro del bucle si lo usa como un índice de matriz, pero tenga en cuenta que firmar realmente puede ser útil, porque el compilador puede suponer que i++ <= bound eventualmente se convertirá en falso, porque el desbordamiento firmado es UB pero no firmado no lo es. Entonces, con unsigned, while(i++ <= bound) es infinito si bound = UINT_MAX .) No tengo una recomendación general sobre cuándo usar firmado versus no firmado; size_t embargo, size_t suele ser una buena opción para recorrer los arreglos, pero si desea evitar los prefijos REX x86-64 en la sobrecarga del bucle (para un ahorro trivial en el tamaño del código), pero convenza al compilador de que no desperdicie ninguna instrucción cero o firme -extender, puede ser complicado.

No puedo ver un gran aumento de rendimiento

Aquí hay un ejemplo en el que esa optimización dará una velocidad de 2x en las CPU Intel antes de Haswell, porque P6 y SnB / IvB solo pueden ejecutar ramas en el puerto 5, incluidas las ramas condicionales no tomadas.

Conocimientos previos requeridos para este análisis de rendimiento estático: la guía de microarquitectura de Agner Fog (lea la sección Sandybridge). Lea también su guía Optimizing Assembly, es excelente. (Sin embargo, en ocasiones están desactualizados en algunos lugares). Consulte también otros enlaces de rendimiento x86 en el wiki de etiquetas x86 . Ver también ¿Puede el MOV de x86 ser realmente "gratis"? ¿Por qué no puedo reproducir esto en absoluto? para algunos análisis estáticos respaldados por experimentos con contadores de rendimiento, y alguna explicación de uops de dominio fusionado versus no fusionado.

También puede utilizar el software IACA de Intel (Intel Architecture Code Analyzer) para realizar análisis estáticos en estos bucles.

; sum(int []) using SSE2 PADDD (dword elements) ; edi = pointer, esi = end_pointer. ; scalar cleanup / unaligned handling / horizontal sum of XMM0 not shown. ; NASM syntax ALIGN 16 ; not required for max performance for tiny loops on most CPUs .looptop: ; while (edi<end_pointer) { cmp edi, esi ; 32-bit code so this can macro-fuse on Core2 jae .done ; 1 uop, port5 only (macro-fused with cmp) paddd xmm0, [edi] ; 1 micro-fused uop, p1/p5 + a load port add edi, 16 ; 1 uop, p015 jmp .looptop ; 1 uop, p5 only ; Sandybridge/Ivybridge ports each uop can use .done: ; }

Esto es 4 uops de dominio fusionado total ( con macro fusión de cmp/jae ), por lo que puede emitir desde el front-end al núcleo fuera de orden en una iteración por reloj. Pero en el dominio no fusionado hay 4 UOP ALU e Intel pre-Haswell solo tiene 3 puertos ALU.

Más importante aún, la presión del puerto 5 es el cuello de botella: este bucle puede ejecutarse en solo una iteración por 2 ciclos porque cmp / jae y jmp deben ejecutarse en el puerto 5. Otros uops que roban el puerto 5 podrían reducir el rendimiento práctico algo por debajo de eso.

Escribiendo el ciclo idiomáticamente para asm , obtenemos:

ALIGN 16 .looptop: ; do { paddd xmm0, [edi] ; 1 micro-fused uop, p1/p5 + a load port add edi, 16 ; 1 uop, p015 cmp edi, esi ; 1 uop, port5 only (macro-fused with cmp) jb .looptop ; } while(edi < end_pointer);

Observe de inmediato, independientemente de todo lo demás, que esta es una instrucción menos en el ciclo. Esta estructura de bucle es al menos un poco mejor en todo, desde el 8086 simple no canalizado hasta el RISC clásico (como los primeros MIPS), especialmente para los bucles de larga duración (suponiendo que no obstaculicen el ancho de banda de la memoria).

Core2 y versiones posteriores deberían ejecutar esto a una iteración por reloj , dos veces más rápido que el ciclo estructurado while while(){} , si la memoria no es un cuello de botella (es decir, suponiendo que L1D impacta, o al menos L2 en realidad; esto es solo SSE2 16 -bytes por reloj).

Esto es solo 3 uops de dominio fusionado, por lo que puede emitir mejor que uno por reloj en cualquier cosa desde Core2, o solo uno por reloj si los grupos de problemas siempre terminan con una rama tomada.

Pero la parte importante es que la presión del puerto 5 se reduce enormemente: solo cmp/jb necesita. Los otros uops probablemente estarán programados para port5 parte del tiempo y robarán ciclos del rendimiento de la rama de bucle, pero esto será un pequeño% en lugar de un factor de 2. Vea ¿Cómo se programan exactamente los uops x86? .

La mayoría de las CPU que normalmente tienen un rendimiento de ramificación tomada de uno por 2 ciclos aún pueden ejecutar pequeños bucles a 1 por reloj. Sin embargo, hay algunas excepciones. (Olvidé qué CPU no pueden ejecutar bucles cerrados a 1 por reloj; ¿quizás la familia Bulldozer? O tal vez solo algunas CPU de baja potencia como VIA Nano). Sandybridge y Core2 definitivamente pueden ejecutar bucles ajustados a uno por reloj. Incluso tienen buffers de bucle; Core2 tiene un búfer de bucle después de la decodificación de longitud de instrucción pero antes de la decodificación regular. Nehalem y luego reciclan uops en la cola que alimenta la etapa de emisión / cambio de nombre. (Excepto en Skylake con actualizaciones de microcódigo; Intel tuvo que deshabilitar el búfer de bucle debido a un error de fusión de registro parcial).

Sin embargo, hay una cadena de dependencia en xmm0 en xmm0 : las CPU Intel tienen un ciclo de latencia de 1 ciclo, por lo que también estamos frente a ese cuello de botella. add esi, 16 es también 1 ciclo de latencia. En la familia Bulldozer, incluso las operaciones de vectores enteros tienen una latencia de 2c, por lo que se reduciría el ciclo a 2c por iteración. (AMD desde K8 e Intel desde SnB pueden ejecutar dos cargas por reloj, por lo que debemos desenrollar de todos modos para obtener un rendimiento máximo). Con coma flotante, definitivamente desea desenrollar con múltiples acumuladores. ¿Por qué mulss solo toma 3 ciclos en Haswell, diferente de las tablas de instrucciones de Agner? .

Si hubiera usado un modo de direccionamiento indexado, como paddd xmm0, [edi + eax] , podría haber usado sub eax, 16 / jnc en la condición de bucle. SUB / JNC puede fusionarse macro en la familia Sandybridge, pero la carga indexada se deslaminaría en SnB / IvB (pero permanecería fusionada en Haswell y más adelante, a menos que use el formulario AVX).

; index relative to the end of the array, with an index counting up towards zero add rdi, rsi ; edi = end_pointer xor eax, eax sub eax, esi ; eax = -length, so [rdi+rax] = first element .looptop: ; do { paddd xmm0, [rdi + rax] add eax, 16 jl .looptop ; } while(idx+=16 < 0); // or JNC still works

(Por lo general, es mejor desenrollar algunos para ocultar la sobrecarga de los incrementos de puntero en lugar de usar modos de direccionamiento indexados, especialmente para tiendas, en parte porque las tiendas indexadas no pueden usar la AGU de la tienda port7 en Haswell +).

En Core2 / Nehalem add/jl no macro fusible, por lo que se trata de 3 uops de dominio fusionado incluso en modo de 64 bits, sin depender de macro fusión. Lo mismo para AMD K8 / K10 / Bulldozer-family / Ryzen: no hay fusión de la condición del bucle, pero PADDD con un operando de memoria es 1 m-op / uop.

En SnB, paddd los laminados de la carga, pero agregue / jl macro-fusible, así que nuevamente 3 uops de dominio fusionado. (Pero en el dominio no fusionado, solo 2 ALU uops + 1 carga, por lo que probablemente haya menos conflictos de recursos que reduzcan el rendimiento del bucle).

En HSW y versiones posteriores, se trata de 2 uops de dominio fusionado porque una carga indexada puede permanecer micro fusionada con PADDD y add/jl macro-fusibles. (Las sucursales pronosticadas se ejecutan en el puerto 6, por lo que nunca hay conflictos de recursos).

Por supuesto, los bucles solo pueden ejecutarse en el mejor de los casos 1 iteración por reloj debido a los límites de rendimiento de la rama tomados incluso para pequeños bucles. Este truco de indexación es potencialmente útil si también tenía algo más que hacer dentro del ciclo.

Pero todos estos bucles no se desenrollaron

Sí, eso exagera el efecto de la sobrecarga del bucle. Pero gcc no se desenrolla de manera predeterminada, incluso en -O3 (a menos que decida desenrollar completamente ). Solo se desenrolla con la optimización guiada por perfil para hacerle saber qué bucles están activos. ( -fprofile-use ). Puede habilitar -funroll-all-loops , pero solo recomendaría hacerlo por archivo para una unidad de compilación que sepa que tiene uno de sus hot loops que lo necesita. O tal vez incluso por función con un __attribute__ , si hay uno para opciones de optimización como esa.

Esto es muy relevante para el código generado por el compilador. (Pero el clang defecto es desenrollar bucles pequeños en 4, o bucles pequeños en 2, y extremadamente importante, usar múltiples acumuladores para ocultar la latencia).

Beneficios con un recuento de iteraciones muy bajo:

Considere lo que sucede cuando el cuerpo del bucle debe correr una o dos veces: hay muchos más saltos con cualquier otra cosa que do{}while .

  • Para do{}while , la ejecución es una línea recta sin ramas tomadas y una rama no tomada en la parte inferior. Esto es excelente.

  • Por un if() { do{}while; } if() { do{}while; } que podría ejecutar el ciclo cero veces, son dos ramas no tomadas. Eso sigue siendo muy bueno. (No tomado es un poco más barato para el front-end que tomado cuando ambos se predicen correctamente).

  • Para un jmp hasta el fondo jmp; do{}while() jmp; do{}while() , es una rama incondicional tomada, una condición de bucle tomada, y luego la rama de bucle no se toma. Esto es un poco torpe, pero los predictores de rama modernos son muy buenos ...

  • Para una estructura while(){} , esta es una salida de bucle no tomada, una jmp tomada en la parte inferior, luego una rama de salida de bucle tomada en la parte superior.

Con más iteraciones, cada estructura de bucle hace una rama más tomada. while(){} también hace una rama más no tomada por iteración, por lo que rápidamente empeora obviamente.

Las últimas dos estructuras de bucle tienen más saltos para pequeños recuentos de viajes.

Saltar al fondo también tiene la desventaja de los bucles no pequeños de que el fondo del bucle podría estar frío en el caché L1I si no se ha ejecutado durante un tiempo. La búsqueda / captación previa de código es buena para llevar el código al front-end en línea recta, pero si la predicción no predijo la rama lo suficientemente temprano, es posible que se pierda un código para el salto hacia abajo. Además, la decodificación paralela probablemente habrá (o podría haber) decodificado parte de la parte superior del bucle mientras decodifica el jmp en la parte inferior.

Saltar condicionalmente sobre un bucle do{}while while evita todo eso: solo saltas hacia adelante al código que aún no se ha ejecutado en los casos en que el código sobre el que estás saltando no debería ejecutarse en absoluto. A menudo predice muy bien porque una gran cantidad de código nunca realiza 0 viajes a través del ciclo. (es decir, podría haber sido una do{}while el compilador simplemente no pudo probarlo).

Saltar al fondo también significa que el núcleo no puede comenzar a trabajar en el cuerpo del bucle real hasta después de que el front-end persiga dos ramas tomadas.

Hay casos con condiciones de bucle complicadas donde es más fácil escribirlo de esta manera, y el impacto en el rendimiento es pequeño, pero los compiladores a menudo lo evitan.

Bucles con múltiples condiciones de salida:

Considere un bucle memchr o un bucle strchr : tienen que detenerse al final del búfer (basado en un recuento) o al final de una cadena de longitud implícita (0 bytes). Pero también tienen que salir del círculo si encuentran una coincidencia antes del final.

Así que a menudo verás una estructura como

do { if () break; blah blah; } while(condition);

O solo dos condiciones cerca del fondo. Idealmente, puede probar varias condiciones lógicas con la misma instrucción real (por ejemplo, 5 < x && x < 25 usando sub eax, 5 / cmp eax, 20 / ja .outside_range , truco de comparación sin signo para la verificación de rango, o combinar eso con un OR para verifique los caracteres alfabéticos de cualquier caso en 4 instrucciones ), pero a veces no puede y solo necesita usar una rama de salida de bucle de estilo de if()break , así como una rama normal tomada hacia atrás.

Otras lecturas:

Algo fuera de tema:

Cuando intento comprender el ensamblaje (con la optimización del compilador activada), veo este comportamiento:

Un bucle muy básico como este

outside_loop; while (condition) { statements; }

A menudo se compila en (pseudocódigo)

; outside_loop jmp loop_condition ; unconditional loop_start: loop_statements loop_condition: condition_check jmp_if_true loop_start ; outside_loop

Sin embargo, si la optimización no está activada, se compila en un código normalmente comprensible:

loop_condition: condition_check jmp_if_false loop_end loop_statements jmp loop_condition ; unconditional loop_end:

Según tengo entendido, el código compilado se parece mejor a esto:

goto condition; do { statements; condition: } while (condition_check);

No puedo ver un gran aumento del rendimiento o un aumento de la legibilidad del código, entonces, ¿por qué suele ser así? ¿Hay un nombre para este estilo de bucle, por ejemplo "verificación de condición final"?