c++ - ¿Por qué g++ lleva los cálculos a un bucle caliente?

gcc assembly

Question

Tengo un comportamiento de compilador muy extraño donde G ++ extrae los cálculos en un bucle en caliente, reduciendo severamente el rendimiento del código resultante. ¿Que esta pasando aqui?

Considera esta función:

#include <cstdint>

constexpr bool noLambda = true;

void funnyEval(const uint8_t* columnData, uint64_t dataOffset, uint64_t dictOffset, int32_t iter, int32_t limit, int32_t* writer,const int32_t* dictPtr2){
   // Computation X1
   const int32_t* dictPtr = reinterpret_cast<const int32_t*>(columnData + dictOffset);
   // Computation X2
   const uint16_t* data = (const uint16_t*)(columnData + dataOffset);
   // 1. The less broken solution without lambda
   if (noLambda) {
        for (;iter != limit;++iter){
            int32_t t=dictPtr[data[iter]];
            *writer = t;
            writer++;
        }
   }
   // 2. The totally broken solution with lambda
   else {
        auto loop = [=](auto body) mutable { for (;iter != limit;++iter){ body(iter); } };
        loop([=](unsigned index) mutable {
            int32_t t=dictPtr[data[index]];
            *writer = t;
            writer++;
        });
   }
}

El problema aquí es que G ++ de alguna manera adora llevar los cálculos X1 y X2 al circuito principal caliente, reduciendo el rendimiento. Aquí están los detalles:

La función simplemente itera sobre una matriz de data , busca un valor en un diccionario dictPtr y lo escribe en un writer ubicación de memoria de destino. data y dictPtr se calculan al comienzo de la función. Tiene dos sabores para hacerlo: uno con una lambda y otro sin ella.

(Tenga en cuenta que esta función es solo un ejemplo mínimo de trabajo de código mucho más complicado. Por lo tanto, abstenga de comentar que el lambda no es necesario aquí. Estoy consciente de este hecho y, en el código original, es necesario, por desgracia).

El problema al compilar con el último g ++ (intenté 8.1 y 7.2, el mismo problema con g ++ más antiguos como se puede ver en los enlaces de godbolt provistos) con un alto nivel de optimización ( -O3 -std=c++14 ) es el siguiente :

La solución 2. ( noLambda=false ) genera un código muy malo para el bucle, incluso peor que la solución "ingenua", porque asume que es una buena idea extraer los cómputos X1 y X2, que están fuera del bucle principal súper caliente. , en el circuito principal súper caliente, por lo que es un 25% más lento en mi CPU.

https://godbolt.org/g/MzbxPN

.L3:
        movl    %ecx, %eax          # unnecessary extra work
        addl    $1, %ecx
        addq    $4, %r9             # separate loop counter (pointer increment)
        leaq    (%rdi,%rax,2), %rax # array indexing with an LEA
        movzwl  (%rax,%rsi), %eax   # rax+rsi is Computation X2, pulled into the loop!
        leaq    (%rdi,%rax,4), %rax # rax+rdx is Computation X1, pulled into the loop!
        movl    (%rax,%rdx), %eax   
        movl    %eax, -4(%r9)
        cmpl    %ecx, %r8d
        jne     .L3

Cuando se utiliza un bucle for ( noLambda=true ) habitual, entonces el código es mejor ya que X2 ya no se incorpora al bucle, ¡pero X1 todavía lo es !:

https://godbolt.org/g/eVG75m

.L3:
        movzwl  (%rsi,%rax,2), %ecx
        leaq    (%rdi,%rcx,4), %rcx
        movl    (%rcx,%rdx), %ecx # This is Computation X1, pulled into the loop!
        movl    %ecx, (%r9,%rax,4)
        addq    $1, %rax
        cmpq    %rax, %r8
        jne     .L3

Puedes probar que esto es realmente X1 en el bucle al reemplazar dictPtr (el cálculo X1) en el bucle con dictPtr2 (un parámetro), la instrucción desaparecerá:

https://godbolt.org/g/nZ7TjJ

.L3:
        movzwl  (%rdi,%rax,2), %ecx
        movl    (%r10,%rcx,4), %ecx
        movl    %ecx, (%r9,%rax,4)
        addq    $1, %rax
        cmpq    %rax, %rdx
        jne     .L3

Este es finalmente el ciclo como quiero tenerlo. Un bucle simple que carga los valores y almacena el resultado sin tener que realizar cálculos aleatorios.

¿Entonces, qué está pasando aquí? Rara vez es una buena idea hacer un cálculo en un bucle caliente, pero G ++ parece pensarlo aquí. Esto me está costando un rendimiento real. La lambda agrava toda la situación; lleva a G ++ a extraer aún más cómputos en el ciclo.

Lo que hace que este problema sea tan severo es que este es un código C ++ realmente trivial sin características sofisticadas. Si no puedo confiar en que mi compilador produzca el código perfecto para un ejemplo tan trivial, tendré que verificar el ensamblaje de todos los bucles activos en mi código para asegurarme de que todo sea lo más rápido posible. Esto también significa que probablemente haya una gran cantidad de programas afectados por esto.

Answer 1

Está utilizando un tipo de 32 bits sin signo para el índice de matriz (en la línea 21). Esto obliga al compilador a considerar en cada paso del ciclo si ha desbordado su rango disponible, en cuyo caso debe volver al comienzo de la matriz. ¡El código adicional que ves está relacionado con este cheque! Hay al menos tres formas de evitar este enfoque excesivamente cauteloso del compilador:

1. Utilice un tipo de 64 bits para el índice en la línea 21. Ahora el compilador sabe que nunca se ajustará a la matriz y generará el mismo código que sin la lambda.
2. Utilice un tipo de 32 bits con signo para el índice en la línea 21. Ahora el compilador ya no se preocupa por el desbordamiento: el desbordamiento firmado se considera UB y, por lo tanto, se ignora. Considero que esto es un error en la interpretación del estándar, pero las opiniones difieren sobre esto.
3. Aclare al compilador que nunca ocurrirá un desbordamiento, agregando una línea ''int32_t iter = 0;'' al comienzo de la función, y eliminar iter de la declaración. Claramente, esto no resuelve su problema, pero ilustra cómo es el análisis de desbordamiento lo que hace que se genere el código adicional.

No se queja del código antes de que comience el ciclo, pero aquí tiene el mismo problema. Simplemente haga iter y limite int64_t, y verá que se vuelve considerablemente más corto ya que el compilador ya no considera la posibilidad de desbordamiento de matriz.

Entonces, para recapitular: no es el cálculo de X1 y X2 lo que se mueve al ciclo que hace que el tamaño se infle, sino el uso de una variable de índice de matriz de tipo incorrecto.

Answer 2

Intenté ejecutar el código y ... sorpresa: las instrucciones que se ejecutan cuando estás en el bucle no son las que ves en el enlace del compilador que publicaste. Mira esto (agregué una función principal) https://godbolt.org/g/PPYtQa Las instrucciones ejecutadas mientras estás en el ciclo son 162-167, es decir,

.L15:
        movzwl  25(%rbx,%rdx), %ecx
        movl    5(%rbx,%rcx,4), %ecx
        movl    %ecx, 0(%rbp,%rdx,2)
        addq    $2, %rdx
        cmpq    $180, %rdx
        jne     .L15

Puede verificar esto compilando en su máquina

g++ test.cpp -std=c++1z -g -O3

y corriendo con gdb

> gdb a.out
(gdb) break funnyEval
(gdb) layout split #shows assebly
(gdb) stepi #steps to the next instruction

El compilador genera una versión no en línea diferente de funnyEval (que es la que vio en la salida desensamblada), incluso si la que está realmente utilizada está en línea. No tengo ni idea (todavía) por qué los dos son diferentes, pero supongo que si se ve afectado por una penalización de rendimiento, puede solucionarlo asegurándose de que funnyEval se inline: ya sea definiendo en un archivo de encabezado o compilando y enlazando con optimización de tiempo de enlace (-flto). Lo intentaré para ver qué sucede cuando funnyEval está en otra unidad de traducción ...

Answer 3

Felicidades, encontraste un error de gcc . La solución principal es informarlo en la bugzilla de GCC con la palabra clave "optimización perdida". Sus MCVE ya son excelentes casos de prueba para el error, por lo que no debería tomar demasiado tiempo para escribir uno. Copie / pegue el código y alguna descripción. Un enlace a esta Q & A, y un enlace al código en http://godbolt.org/ , sería bueno también.

A veces hay razones sutiles de microarquitectura para usar instrucciones "extra", como xor -zeroing el destino de popcnt / lzcnt o bsf para evitar una dependencia falsa en las CPU de Intel , pero ese no es el caso aquí. Esto es simplemente malo; el movl %ecx, %eax dentro del ciclo podría ser el resultado de usar un tipo sin signo más angosto que un puntero, pero incluso eso podría hacerse de manera más eficiente; es una optimización perdida, también.

No he visto los volcados GIMPLE o RTL de GCC (representaciones internas) para conocer más detalles. El único uso de los valores calculados está dentro del ciclo, por lo que puedo imaginar que la representación interna del compilador de la lógica del programa puede perder la diferencia entre el interior y el exterior del ciclo cuando se transforma. Normalmente, las cosas que no necesitan estar en el circuito se izan o se salen del circuito.

Pero lamentablemente no es raro que gcc deje una instrucción mov extra dentro de un bucle para configurar el código fuera del bucle. Especialmente cuando puede tomar múltiples instrucciones fuera del ciclo para obtener el mismo efecto. Esta suele ser una mala compensación cuando se optimiza el rendimiento en lugar del tamaño del código. No he analizado la salida de ASM de Optimización guiada por perfil tanto como me gustaría, para ver el código donde gcc sabe qué bucles están realmente calientes y los desenrolla. Pero la mayoría del código se construye sin PGO, lamentablemente, por lo que code-gen sin -fprofile-use sigue siendo muy importante.

Sin embargo, el núcleo de esta pregunta no es cómo obtener este ejemplo en particular lo más rápido posible. En cambio, me siento más atónito de cómo el compilador puede producir tales desoptimizaciones en un fragmento de código tan simple. Mi principal problema ahora es: de alguna manera he perdido la fe en mi compilador, así que quiero entender cómo puede suceder esto para poder recuperarlo.

¡No tengas fe en gcc! Es una pieza de maquinaria muy compleja que a menudo produce buenos resultados, pero rara vez produce resultados óptimos.

Este caso es una de las elecciones incorrectas más obvias y simples que he visto hacer su optimizador (y es bastante decepcionante), sin embargo. Por lo general, las optimizaciones perdidas son algo más sutiles (y dependen de detalles microarquitectónicos como las opciones del modo de direccionamiento y los puertos de ejecución / uops), o al menos no tan obviamente triviales como para evitar. (Alce esa instrucción sin cambiar ninguna asignación de registro para todo el ciclo).

Pero muchos bucles estrangulan la memoria, no el rendimiento de uop. Las CPUs modernas están diseñadas para masticar las instrucciones desperdiciadas que generan los compiladores, especialmente los compiladores JIT. Esta es la razón por la cual las optimizaciones perdidas como esta generalmente no tienen un gran impacto a escala macro, y por qué los casos donde sí importan (por ejemplo, codificadores de video o multiplicaciones de matrices) a menudo todavía usan bloques de asm escritos a mano.

A menudo es posible mantener GCC a mano para crear un buen asm implementando su fuente de una manera que esté estructurada como la asma que desea. (Como este caso: ¿Cuál es la forma más eficiente de contar bits establecidos en una posición o menos? Y ver ¿Por qué este código C ++ es más rápido que mi ensamblaje escrito a mano para probar la conjetura de Collatz?, Para obtener una respuesta más general sobre cómo ayudar compilador vs. batir al compilador con asm escrito a mano).

Pero cuando tu compilador sufre una muerte cerebral como esta, no hay nada que puedas hacer. Bueno, excepto buscar soluciones temporales, o cosas como evitar enteros unsigned más estrecho que punteros que otras respuestas han señalado como importantes.

Curiosamente, el peor de los casos (2 instrucciones LEA adicionales en el ciclo, más el uso de contadores de bucle adicionales) solo ocurre con su if (noLambda) .

Si realiza 2 versiones separadas de la función y elimina el if , la versión nolambda un bucle limpio (pero pierde la auto-vectorización del compilar, lo que sería una ganancia cuando se compila con -march=skylake )

Puse tu código en el explorador del compilador Godbolt . (También es interesante usar -funroll-loops para ver qué partes se -funroll-loops a hacer cada iteración de bucle desenrollado, y que están simplemente dentro del bucle una vez).

# gcc7.2:  the nolamba side of the if, with no actual if()
.L3:
    movzwl  (%rsi,%rax,2), %ecx
    movl    (%rdx,%rcx,4), %ecx
    movl    %ecx, (%r9,%rax,4)   # indexed store: no port 7
    addq    $1, %rax             # gcc8 -O3 -march=skylake uses inc to save a code byte here.
    cmpq    %rax, %r8
    jne     .L3

En Intel Sandybridge-family, esto decodifica a 5 uops. (La macro-fusión del cmp / jcc convierte ese par en 1 uop. Las otras instrucciones son todas simples, movzwl es una carga pura y no necesita un puerto ALU).

La tienda se deshilacha en SnB / IvB (cuesta un uop extra para la etapa de emisión de 4 amplios, uno de los cuellos de botella principales del front-end), pero puede permanecer fundido en HSW / SKL. Sin embargo, no puede usar el puerto 7 (porque está indexado), lo que significa que HSW / SKL estaría limitado a 2 operaciones de memoria por reloj, no a 3.

Cuellos de botella

• Anchura de banda de emisión de front-end de 4 uops de dominio fusionado por reloj. El ciclo es de 5 uops y puede emitirse a casi 1 iteración por 1.25. (Los bucles que no son múltiplos de 4 no son perfectos, pero 5 uops se manejan bien en Haswell / Skylake al menos . Posiblemente no en Sandybridge).

• cargar / almacenar puertos de ejecución: Haswell y más adelante pueden ejecutar 2 cargas + 1 tienda por reloj, pero solo cuando la tienda evita un modo de direccionamiento indexado para que la dirección de tienda uop pueda ejecutarse en el puerto 7.

la versión lambda obtiene un segundo contador de bucle (incremento de puntero) y un tonto movl %ecx, %eax , pero las instrucciones LEA permanecen fuera del ciclo.

Pero no es el cálculo extra per se, es el rendimiento total uop que probablemente está dañando su ciclo. Si el diccionario permanece mayormente caliente en caché, una CPU Haswell o posterior

Iba a escribir más, pero no terminé. Publicando ahora porque la parte inicial / media genérica aparentemente es de lo que se trata la pregunta. No confíes ciegamente en gcc.

Y no espere que el código sea óptimo la mayor parte del tiempo. A menudo puede ganar 10 o 20% simplemente modificando la fuente C (y algunas veces más). A veces, gcc simplemente no parece tener una pista, como usar lea extra sin razón aparente al desenrollar, en lugar de usar un desplazamiento en un modo de direccionamiento. Creo que su modelo de costo de modo de direccionamiento no debe ser preciso, al menos para -march=haswell / -march=skylake .