¿Por qué los bucles siempre se compilan en el estilo "hacer...mientras" (salto de cola)?

Relacionado: conceptos básicos de bucles asm: bucles While, Do While y For en lenguaje ensamblador (emu8086)

Terminología: Wikipedia dice que " inversión de bucle " es el nombre para convertir a while(x), if(x) do{}while(x)colocando la condición en la parte inferior del bucle donde pertenece.

Menos instrucciones/uops dentro del bucle = mejor . Estructurar el código fuera del bucle para lograr esto suele ser una buena idea.

A veces, esto requiere "rotación del bucle" (pelar parte de la primera iteración para que el cuerpo del bucle real tenga la rama condicional en la parte inferior). Entonces haces parte de la primera iteración y tal vez te saltas el ciclo por completo, luego caes en el ciclo. A veces también necesitas algo de código después del ciclo para finalizar la última iteración.

A veces, la rotación del bucle es muy útil si la última iteración es un caso especial, por ejemplo, una tienda que debes omitir. Esto le permite implementar un while(1) {... ; if(x)break; ...; }bucle como do- while o colocar una de las condiciones de un bucle de múltiples condiciones en la parte inferior.

Algunas de estas optimizaciones están relacionadas con la canalización de software o la habilitan, por ejemplo, cargar algo para la siguiente iteración. (OoO exec en x86 hace que la canalización de SW no sea muy importante en estos días, pero sigue siendo útil para núcleos en orden como muchos ARM. Y el desenrollado con múltiples acumuladores sigue siendo muy valioso para ocultar la latencia de FP transmitida por bucle en un bucle de reducción como un producto punto o suma de una matriz.)

do{}while()es la estructura canónica/idiomática para bucles en asm en todas las arquitecturas, acostúmbrese a ella. IDK si hay un nombre para ello; Yo diría que dicho bucle tiene una "estructura hacer mientras". Si desea nombres, puede llamar a la while()estructura "código de mala calidad no optimizado" o "escrito por un novato". :P La rama de bucle en la parte inferior es universal y ni siquiera vale la pena mencionarla como optimización de bucle . Tu siempre haces eso.

Este patrón se usa tan ampliamente que en las CPU que usan predicción de rama estática para ramas sin una entrada en las cachés del predictor de rama, se predice que las ramas condicionales hacia adelante desconocidas no se tomarán, y se predice que las ramas hacia atrás desconocidas se tomarán (porque probablemente sean ramas de bucle). ). Consulte la predicción de ramas estáticas en los procesadores Intel más nuevos en el blog de Matt Godbolt y el capítulo de predicción de ramas de Agner Fog al comienzo de su microarquitectura 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 que otras implementaciones superescalares/fuera de servicio (como algunas ARM o POWER) también tuvieran un rendimiento limitado de instrucciones de rama, ya sea que se tomen o no. Pero tener menos instrucciones dentro del bucle es casi universal cuando todo lo que tienes es una rama condicional en la parte inferior y ninguna rama incondicional.

Si es posible que el bucle necesite ejecutarse cero veces , los compiladores suelen colocar una prueba y una rama fuera del bucle para omitirlo, en lugar de saltar a la condición del bucle 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 a la transformación while()una if(){ do{}while; }"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 principal en el orden incorrecto, un compilador inteligente podría cambiar for(i) for(j) a[j][i]++;si for(j) for(i) a[j][i]++;puede demostrar que es correcta). Pero supongo que puedes verlo if()como una iteración de cero o uno. bucle. Dato curioso, los desarrolladores de compiladores enseñan a sus compiladores cómo invertir un bucle (para permitir la vectorización automática) para un caso (muy) específico es la razón por la cual el punto de referencia libquantum de SPECint2006 está "roto" . La mayoría de los compiladores no pueden invertir bucles en el caso general, solo aquellos que se parecen casi exactamente al de SPECint2006...

Puede ayudar al compilador a hacer un conjunto más compacto (menos instrucciones fuera del bucle) escribiendo do{}while()bucles en C cuando sepa que la persona que llama no puede pasar size=0o cualquier otra cosa 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 firmado versus sin firmar son un problema de optimización complicado, especialmente si elige un tipo más estrecho que los punteros; verifique la salida del conjunto del compilador para asegurarse de que no extienda el signo de un bucle estrecho contador dentro del bucle muy a menudo si lo usa como un índice de matriz. Pero tenga en cuenta que firmado puede ser realmente útil, porque el compilador puede asumir que i++ <= boundeventualmente se volverá falso, porque el desbordamiento firmado es UB pero sin firmar 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 o sin firmar; size_tSin embargo, suele ser una buena opción para recorrer matrices, 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 convencer al compilador de que no desperdicie ninguna instrucción con cero o signo. extenderse, puede ser complicado.

No veo un gran aumento en el rendimiento

Aquí hay un ejemplo en el que esa optimización brindará una aceleración del doble en CPU Intel anteriores a Haswell, porque P6 y SnB/IvB solo pueden ejecutar ramas en el puerto 5, incluidas ramas condicionales no tomadas.

Conocimientos previos necesarios para este análisis de rendimiento estático: guía de microarcos de Agner Fog (lea la sección de Sandybridge). Lea también su guía de optimización del ensamblaje, es excelente. (Sin embargo, ocasionalmente está desactualizado en algunos lugares). Consulte también otros enlaces de rendimiento x86 en elx86etiqueta wiki. Consulte también ¿Puede el MOV de x86 ser realmente "gratuito"? ¿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 los uops de dominios fusionados y no fusionados.

También puede utilizar el software IACA (Intel Architecture Code Analyzer) de Intel 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:                    ; }

Se trata de 4 uops de dominio fusionado en total ( con macrofusión decmp/jae ), por lo que puede emitir desde el front-end al núcleo fuera de servicio en una iteración por reloj. Pero en el dominio no fusionado hay 4 ALU uops 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 se puede ejecutar en solo una iteración cada 2 ciclos porque cmp/jae y jmp necesitan ejecutarse en el puerto 5. Otros uops que roban el puerto 5 podrían reducir el rendimiento práctico un poco por debajo de eso.

Al escribir el bucle 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 ligeramente mejor en todo, desde el simple 8086 no canalizado hasta el RISC clásico (como los primeros MIPS), especialmente para bucles de larga duración (suponiendo que no produzcan cuellos de botella en el ancho de banda de la memoria).

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

Estos son solo 3 uops de dominio fusionado, por lo que pueden emitirse a más de 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 lo importante es que la presión del puerto 5 se reduce enormemente: sólo cmp/jblo necesita. Los otros uops probablemente estarán programados para portar 5 algunas veces y robar ciclos del rendimiento de la rama de bucle, pero esto será un pequeño porcentaje en lugar de un factor de 2. Consulte ¿ Cómo se programan exactamente los uops x86? .

La mayoría de las CPU que normalmente tienen un rendimiento de rama tomada de uno cada 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; ¿tal vez la familia Bulldozer? O tal vez solo algunas CPU de bajo consumo como VIA Nano). Sandybridge y Core2 definitivamente pueden ejecutar bucles cerrados a uno por reloj. Incluso tienen buffers de bucle; Core2 tiene un búfer de bucle después de la decodificación de la longitud de la instrucción pero antes de la decodificación normal. Nehalem y posteriormente 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 desactivar el búfer de bucle debido a un error de fusión de registros parciales).

Sin embargo, existe una cadena de dependencia en bucle en xmm0: Las CPU Intel tienen una latencia de 1 ciclo paddd, por lo que también nos enfrentamos a ese cuello de botella. add esi, 16También hay una latencia de 1 ciclo. En la familia Bulldozer, incluso las operaciones vectoriales enteras tienen una latencia de 2c, por lo que eso provocaría un cuello de botella en el bucle de 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 el máximo rendimiento). Con punto flotante, definitivamente desea desenrollar con múltiples acumuladores. ¿Por qué Mulss requiere solo 3 ciclos en Haswell, a diferencia de las tablas de instrucciones de Agner? (Desenrollando bucles FP con múltiples acumuladores) .

Si hubiera usado un modo de direccionamiento indexado, como paddd xmm0, [edi + eax], podría haber usado sub eax, 16/ jncen 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 versiones posteriores, 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 del puntero en lugar de usar modos de direccionamiento indexados, especialmente para tiendas, en parte porque las tiendas indexadas no pueden usar la AGU de tienda del puerto 7 en Haswell+).

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

En SnB, paddddeslamina de la carga, pero agrega/jl macro-fuse, por lo que nuevamente 3 uops de dominio fusionado. (Pero en el dominio no fusionado, solo se cargan 2 ALU uops + 1, 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 microfusionada con PADDD y add/jlmacrofusibles. (Las ramas previstas 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 rama adoptados, incluso para bucles pequeños. Este truco de indexación es potencialmente útil si también tienes algo más que hacer dentro del bucle.

Pero todos estos bucles no se desenrollaron

Sí, eso exagera el efecto de la sobrecarga del bucle. Pero gcc no se desenrolla de forma predeterminada ni siquiera en -O3(a menos que decida desenrollarse por completo ). Solo se desenrolla con 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 bucles activos que lo necesita. O tal vez incluso por función con un __attribute__, si hay uno para opciones de optimización como esa.

Entonces esto es muy relevante para el código generado por el compilador. (Pero clangpor defecto desenrolla bucles pequeños de 4 en 4, o bucles pequeños de 2 en 2 y, lo que es muy importante, utiliza 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 ejecutarse una o dos veces: hay muchos más saltos con cualquier otra cosa que no sea 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.

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

• Para un jmp-to-the-bottom jmp; do{}while(), es una rama incondicional tomada, una condición de bucle tomada y luego la rama del bucle no se toma. Esto es un poco complicado, pero los predictores de ramas modernos son muy buenos...

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

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

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

Saltar al final también tiene una desventaja para los bucles no pequeños: la parte inferior del bucle puede estar fría en la caché L1I si no se ha ejecutado por un tiempo. La recuperación/precarga 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 con suficiente antelación, es posible que se pierda el código para el salto al final. Además, la decodificación paralela probablemente habrá decodificado (o podría haber) parte de la parte superior del bucle mientras decodifica la jmpparte inferior.

Saltar condicionalmente un do{}whilebucle 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 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 bucle. (es decir, podría haber sido un do{}while, el compilador simplemente no logró probarlo).

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

Hay casos con condiciones de bucle complicadas en los que 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 memchrbucle, o un strchrbucle: tienen que detenerse al final del búfer (según un recuento) o al final de una cadena de longitud implícita (0 bytes). Pero también tienen que breaksalir 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 simplemente dos condiciones cerca del fondo. Idealmente, puede probar múltiples condiciones lógicas con la misma instrucción real (por ejemplo, usando 5 < x && x < 25// sub eax, 5, un truco de comparación sin signo para verificar el rango, o combinarlo con un para verificar caracteres alfabéticos de cualquier caso en 4 instrucciones ), pero a veces no puede y simplemente Es necesario utilizar una rama de salida de bucle de estilo, así como una rama normal tomada hacia atrás.cmp eax, 20ja .outside_rangeORif()break

Otras lecturas:

• Charla de Matt Godbolt en CppCon2017: “¿Qué ha hecho mi compilador por mí últimamente? Unbolting the Compiler's Lid” para conocer buenas formas de ver la salida del compilador (por ejemplo, qué tipo de entradas dan una salida interesante y una introducción a la lectura de x86 asm para principiantes). relacionado: ¿Cómo eliminar el "ruido" de la salida del ensamblaje GCC/clang?

• Microprocesadores modernos ¡Una guía de 90 minutos! . Los detalles analizan las CPU canalizadas superescalares, en su mayoría de arquitectura neutral. Muy bien. Explica el paralelismo a nivel de instrucción y cosas así.

• Guía de optimización x86 de Agner Fog y microarco pdf. Esto le permitirá pasar de poder escribir (o comprender) un ensamblaje x86 correcto a poder escribir un ensamblaje eficiente (o ver lo que debería haber hecho el compilador).

• otros enlaces en elx86tag wiki, incluidos los manuales de optimización de Intel. Además, varias de mis respuestas (vinculadas en la etiqueta wiki) tienen cosas que Agner pasó por alto en sus pruebas en microarquitecturas más recientes (como la deslaminación de modos de direccionamiento indexados microfusionados en SnB y elementos de registro parcial en Haswell+).

• ¿Por qué Mulss requiere solo 3 ciclos en Haswell, a diferencia de las tablas de instrucciones de Agner? (Desenrollando bucles FP con múltiples acumuladores) : cómo usar múltiples acumuladores para ocultar la latencia de un bucle de reducción (como un producto escalar FP).

• Conferencia 7: Transformaciones de bucle (también en archive.org ). Muchas cosas interesantes que los compiladores hacen con los bucles, usando la sintaxis C para describir el conjunto.

• https://en.wikipedia.org/wiki/Loop_optimization

Algo fuera de tema:

• El ancho de banda de la memoria casi siempre es importante, pero no es ampliamente conocido que un solo núcleo en la mayoría de las CPU x86 modernas no puede saturar la DRAM, y ni siquiera se acerca a los Xeons de muchos núcleos, donde el ancho de banda de un solo subproceso es peor que en un quad-core con Controladores de memoria de doble canal .

• ¿Cuánto de 'Lo que todo programador debería saber sobre la memoria' sigue siendo válido? (mi respuesta tiene comentarios sobre lo que ha cambiado y lo que sigue siendo relevante en el conocido excelente artículo de Ulrich Drepper).

Dec 13 '2017 10:12 Peter Cordes