¿Por qué GCC genera código 15-20% más rápido si optimizo para el tamaño en lugar de la velocidad?

Noté por primera vez en 2009 que GCC (al menos en mis proyectos y en mis máquinas) tiene la tendencia a generar código notablemente más rápido si -Os para el tamaño ( -Os ) en lugar de la velocidad ( -O2 o -O2 ), y he estado preguntándose desde entonces por qué.

He logrado crear un código (bastante tonto) que muestra este comportamiento sorprendente y es lo suficientemente pequeño como para publicarlo aquí.

 const int LOOP_BOUND = 200000000; __attribute__((noinline)) static int add(const int& x, const int& y) { return x + y; } __attribute__((noinline)) static int work(int xval, int yval) { int sum(0); for (int i=0; i<LOOP_BOUND; ++i) { int x(xval+sum); int y(yval+sum); int z = add(x, y); sum += z; } return sum; } int main(int , char* argv[]) { int result = work(*argv[1], *argv[2]); return result; } 

Si lo compilo con -Os , se necesita 0.38 s para ejecutar este progtwig, y ​​0.44 s si está comstackdo con -O2 o -O2 . Estos tiempos se obtienen de forma consistente y prácticamente sin ruido (gcc 4.7.2, x86_64 GNU / Linux, Intel Core i5-3320M).

(Actualización: he movido todo el código de ensamblaje a GitHub : hicieron la publicación inflada y aparentemente agregaron muy poco valor a las preguntas ya que las fno-align-* tienen el mismo efecto).

Aquí está el ensamblaje generado con -Os y -O2 .

Desafortunadamente, mi comprensión del ensamblaje es muy limitada, así que no tengo idea de si lo que hice a continuación fue correcto: agarré el ensamblaje para -O2 y -O2 todas sus diferencias en el ensamblaje para -Os excepto las líneas .p2align , como resultado aquí . Este código aún se ejecuta en 0.38s y la única diferencia es el material de .p2align .

Si creo que es correcto, estos son rellenos para la alineación de la stack. De acuerdo con ¿Por qué GCC pad funciona con NOPs? se hace con la esperanza de que el código se ejecute más rápido, pero aparentemente esta optimización resultó contraproducente en mi caso.

¿Es el relleno el culpable en este caso? ¿Porque y como?

El ruido que produce hace que las micro optimizaciones sean imposibles.

¿Cómo puedo asegurarme de que esas alineaciones accidentales afortunadas / desafortunadas no interfieran cuando realizo microoptimizaciones (no relacionadas con la alineación de la stack) en el código fuente C o C ++?


ACTUALIZAR:

Siguiendo la respuesta de Pascal Cuoq, cambié un poco las alineaciones. Al pasar -O2 -fno-align-functions -fno-align-loops a gcc, todos los .p2align se han ido del ensamblado y el ejecutable generado se ejecuta en 0.38s. De acuerdo con la documentación de gcc :

-Os habilita todas las -O2 optimizaciones [pero] -Os desactiva los siguientes indicadores de optimización:

  -falign-functions -falign-jumps -falign-loops 
-falign-labels -freorder-blocks -freorder-blocks-and-partition
-fprefetch-loop-arrays

Por lo tanto, parece un problema de (des) alineación.

Sigo siendo escéptico sobre -march=native como se sugiere en la respuesta de Marat Dukhan . No estoy convencido de que no se trata solo de interferir con este problema de (falta de) alineación; no tiene absolutamente ningún efecto en mi máquina. (Sin embargo, subí su respuesta).


ACTUALIZACIÓN 2:

Podemos sacar -Os de la imagen. Los siguientes tiempos se obtienen al comstackr con

  • -O2 -fno-omit-frame-pointer 0.37s

  • -O2 -fno-align-functions -fno-align-loops 0.37s

  • -S -O2 luego moviendo manualmente el conjunto de add() después del work() 0.37s

  • -O2 0.44s

Me parece que la distancia de add() desde el sitio de llamadas es muy importante. He intentado perf , pero el resultado de la perf stat y el perf report tiene muy poco sentido para mí. Sin embargo, solo pude obtener un resultado consistente de ello:

-O2 :

  602,312,864 stalled-cycles-frontend # 0.00% frontend cycles idle 3,318 cache-misses 0.432703993 seconds time elapsed [...] 81.23% a.out a.out [.] work(int, int) 18.50% a.out a.out [.] add(int const&, int const&) [clone .isra.0] [...] ¦ __attribute__((noinline)) ¦ static int add(const int& x, const int& y) { ¦ return x + y; 100.00 ¦ lea (%rdi,%rsi,1),%eax ¦ } ¦ ? retq [...] ¦ int z = add(x, y); 1.93 ¦ ? callq add(int const&, int const&) [clone .isra.0] ¦ sum += z; 79.79 ¦ add %eax,%ebx 

Para fno-align-* :

  604,072,552 stalled-cycles-frontend # 0.00% frontend cycles idle 9,508 cache-misses 0.375681928 seconds time elapsed [...] 82.58% a.out a.out [.] work(int, int) 16.83% a.out a.out [.] add(int const&, int const&) [clone .isra.0] [...] ¦ __attribute__((noinline)) ¦ static int add(const int& x, const int& y) { ¦ return x + y; 51.59 ¦ lea (%rdi,%rsi,1),%eax ¦ } [...] ¦ __attribute__((noinline)) ¦ static int work(int xval, int yval) { ¦ int sum(0); ¦ for (int i=0; i<LOOP_BOUND; ++i) { ¦ int x(xval+sum); 8.20 ¦ lea 0x0(%r13,%rbx,1),%edi ¦ int y(yval+sum); ¦ int z = add(x, y); 35.34 ¦ ? callq add(int const&, int const&) [clone .isra.0] ¦ sum += z; 39.48 ¦ add %eax,%ebx ¦ } 

Para -fno-omit-frame-pointer :

  404,625,639 stalled-cycles-frontend # 0.00% frontend cycles idle 10,514 cache-misses 0.375445137 seconds time elapsed [...] 75.35% a.out a.out [.] add(int const&, int const&) [clone .isra.0] ¦ 24.46% a.out a.out [.] work(int, int) [...] ¦ __attribute__((noinline)) ¦ static int add(const int& x, const int& y) { 18.67 ¦ push %rbp ¦ return x + y; 18.49 ¦ lea (%rdi,%rsi,1),%eax ¦ const int LOOP_BOUND = 200000000; ¦ ¦ __attribute__((noinline)) ¦ static int add(const int& x, const int& y) { ¦ mov %rsp,%rbp ¦ return x + y; ¦ } 12.71 ¦ pop %rbp ¦ ? retq [...] ¦ int z = add(x, y); ¦ ? callq add(int const&, int const&) [clone .isra.0] ¦ sum += z; 29.83 ¦ add %eax,%ebx 

Parece que estamos estancados en la llamada para add() en el caso lento.

He examinado todo lo que perf -e puede escupir en mi máquina; no solo las estadísticas que se dan arriba.

Para el mismo ejecutable, la stalled-cycles-frontend muestra una correlación lineal con el tiempo de ejecución; No noté nada más que pudiera correlacionarse tan claramente. (La comparación de stalled-cycles-frontend para diferentes ejecutables no tiene sentido para mí.)

Incluí las faltas de caché, ya que surgió como el primer comentario. Examiné todas las fallas de caché que se pueden medir en mi máquina mediante perf , no solo las que se mencionaron anteriormente. Los errores de caché son muy muy ruidosos y muestran poca o ninguna correlación con los tiempos de ejecución.

Por defecto, los comstackdores optimizan para el procesador “promedio”. Dado que los diferentes procesadores favorecen las diferentes secuencias de instrucciones, las optimizaciones del comstackdor habilitadas por -O2 pueden beneficiar al procesador promedio, pero disminuyen el rendimiento en su procesador particular (y lo mismo se aplica a los ” -Os ). Si prueba el mismo ejemplo en diferentes procesadores, encontrará que en algunos de ellos se beneficia de -O2 mientras que otros son más favorables para -Os optimizaciones.

Estos son los resultados del time ./test 0 0 en varios procesadores (tiempo del usuario informado):

 Processor (System-on-Chip) Compiler Time (-O2) Time (-Os) Fastest AMD Opteron 8350 gcc-4.8.1 0.704s 0.896s -O2 AMD FX-6300 gcc-4.8.1 0.392s 0.340s -Os AMD E2-1800 gcc-4.7.2 0.740s 0.832s -O2 Intel Xeon E5405 gcc-4.8.1 0.603s 0.804s -O2 Intel Xeon E5-2603 gcc-4.4.7 1.121s 1.122s - Intel Core i3-3217U gcc-4.6.4 0.709s 0.709s - Intel Core i3-3217U gcc-4.7.3 0.708s 0.822s -O2 Intel Core i3-3217U gcc-4.8.1 0.708s 0.944s -O2 Intel Core i7-4770K gcc-4.8.1 0.296s 0.288s -Os Intel Atom 330 gcc-4.8.1 2.003s 2.007s -O2 ARM 1176JZF-S (Broadcom BCM2835) gcc-4.6.3 3.470s 3.480s -O2 ARM Cortex-A8 (TI OMAP DM3730) gcc-4.6.3 2.727s 2.727s - ARM Cortex-A9 (TI OMAP 4460) gcc-4.6.3 1.648s 1.648s - ARM Cortex-A9 (Samsung Exynos 4412) gcc-4.6.3 1.250s 1.250s - ARM Cortex-A15 (Samsung Exynos 5250) gcc-4.7.2 0.700s 0.700s - Qualcomm Snapdragon APQ8060A gcc-4.8 1.53s 1.52s -Os 

En algunos casos, puede aliviar el efecto de las optimizaciones desventajosas pidiendo a gcc que optimice para su procesador en particular (usando las opciones -mtune=native o -march=native ):

 Processor Compiler Time (-O2 -mtune=native) Time (-Os -mtune=native) AMD FX-6300 gcc-4.8.1 0.340s 0.340s AMD E2-1800 gcc-4.7.2 0.740s 0.832s Intel Xeon E5405 gcc-4.8.1 0.603s 0.803s Intel Core i7-4770K gcc-4.8.1 0.296s 0.288s 

Actualización: en Core i3 basado en Ivy Bridge, tres versiones de gcc ( 4.6.4 , 4.7.3 y 4.8.1 ) producen binarios con un rendimiento significativamente diferente, pero el código de ensamblaje solo tiene variaciones sutiles. Hasta el momento, no tengo ninguna explicación de este hecho.

Ensamblaje desde gcc-4.6.4 -Os (se ejecuta en 0.709 segundos):

 00000000004004d2 <_ZL3addRKiS0_.isra.0>: 4004d2: 8d 04 37 lea eax,[rdi+rsi*1] 4004d5: c3 ret 00000000004004d6 <_zl4workii>: 4004d6: 41 55 push r13 4004d8: 41 89 fd mov r13d,edi 4004db: 41 54 push r12 4004dd: 41 89 f4 mov r12d,esi 4004e0: 55 push rbp 4004e1: bd 00 c2 eb 0b mov ebp,0xbebc200 4004e6: 53 push rbx 4004e7: 31 db xor ebx,ebx 4004e9: 41 8d 34 1c lea esi,[r12+rbx*1] 4004ed: 41 8d 7c 1d 00 lea edi,[r13+rbx*1+0x0] 4004f2: e8 db ff ff ff call 4004d2 <_ZL3addRKiS0_.isra.0> 4004f7: 01 c3 add ebx,eax 4004f9: ff cd dec ebp 4004fb: 75 ec jne 4004e9 <_ZL4workii+0x13> 4004fd: 89 d8 mov eax,ebx 4004ff: 5b pop rbx 400500: 5d pop rbp 400501: 41 5c pop r12 400503: 41 5d pop r13 400505: c3 ret 

Ensamblaje desde gcc-4.7.3 -Os (se ejecuta en 0.822 segundos):

 00000000004004fa <_ZL3addRKiS0_.isra.0>: 4004fa: 8d 04 37 lea eax,[rdi+rsi*1] 4004fd: c3 ret 00000000004004fe <_zl4workii>: 4004fe: 41 55 push r13 400500: 41 89 f5 mov r13d,esi 400503: 41 54 push r12 400505: 41 89 fc mov r12d,edi 400508: 55 push rbp 400509: bd 00 c2 eb 0b mov ebp,0xbebc200 40050e: 53 push rbx 40050f: 31 db xor ebx,ebx 400511: 41 8d 74 1d 00 lea esi,[r13+rbx*1+0x0] 400516: 41 8d 3c 1c lea edi,[r12+rbx*1] 40051a: e8 db ff ff ff call 4004fa <_ZL3addRKiS0_.isra.0> 40051f: 01 c3 add ebx,eax 400521: ff cd dec ebp 400523: 75 ec jne 400511 <_ZL4workii+0x13> 400525: 89 d8 mov eax,ebx 400527: 5b pop rbx 400528: 5d pop rbp 400529: 41 5c pop r12 40052b: 41 5d pop r13 40052d: c3 ret 

Ensamblaje desde gcc-4.8.1 -Os (se ejecuta en 0.994 segundos):

 00000000004004fd <_ZL3addRKiS0_.isra.0>: 4004fd: 8d 04 37 lea eax,[rdi+rsi*1] 400500: c3 ret 0000000000400501 <_zl4workii>: 400501: 41 55 push r13 400503: 41 89 f5 mov r13d,esi 400506: 41 54 push r12 400508: 41 89 fc mov r12d,edi 40050b: 55 push rbp 40050c: bd 00 c2 eb 0b mov ebp,0xbebc200 400511: 53 push rbx 400512: 31 db xor ebx,ebx 400514: 41 8d 74 1d 00 lea esi,[r13+rbx*1+0x0] 400519: 41 8d 3c 1c lea edi,[r12+rbx*1] 40051d: e8 db ff ff ff call 4004fd <_ZL3addRKiS0_.isra.0> 400522: 01 c3 add ebx,eax 400524: ff cd dec ebp 400526: 75 ec jne 400514 <_ZL4workii+0x13> 400528: 89 d8 mov eax,ebx 40052a: 5b pop rbx 40052b: 5d pop rbp 40052c: 41 5c pop r12 40052e: 41 5d pop r13 400530: c3 ret 

Mi colega me ayudó a encontrar una respuesta plausible a mi pregunta. Él notó la importancia del límite de 256 bytes. Él no está registrado aquí y me animó a publicar la respuesta yo mismo (y tomar toda la fama).


Respuesta corta:

¿Es el relleno el culpable en este caso? ¿Porque y como?

Todo se reduce a la alineación. Las alineaciones pueden tener un impacto significativo en el rendimiento, es por eso que tenemos los -falign-* en primer lugar.

He enviado un informe de error (falso?) A los desarrolladores de gcc . Resulta que el comportamiento predeterminado es “alineamos los bucles a 8 bytes por defecto, pero tratamos de alinearlo a 16 bytes si no necesitamos completar más de 10 bytes”. Aparentemente, este valor predeterminado no es la mejor opción en este caso particular y en mi máquina. Clang 3.4 (tronco) con -O3 hace la alineación apropiada y el código generado no muestra este comportamiento extraño.

Por supuesto, si se hace una alineación inapropiada, empeora las cosas. Una alineación innecesaria / incorrecta solo consume bytes sin ninguna razón y potencialmente aumenta la falta de memoria caché, etc.

El ruido que produce hace que las micro optimizaciones sean imposibles.

¿Cómo puedo asegurarme de que esas alineaciones accidentales afortunadas / desafortunadas no interfieran cuando realizo microoptimizaciones (no relacionadas con la alineación de la stack) en códigos fuente C o C ++?

Simplemente diciéndole a gcc que haga la alineación correcta:

g++ -O2 -falign-functions=16 -falign-loops=16


Respuesta larga:

El código se ejecutará más lento si:

  • un límite de XX bytes corta add() en el medio ( XX depende de la máquina).

  • si la llamada a add() tiene que saltar un límite de XX byte y el objective no está alineado.

  • si add() no está alineado.

  • si el lazo no está alineado.

Los primeros 2 son muy visibles en los códigos y resultados que amablemente publicó Marat Dukhan . En este caso, gcc-4.8.1 -Os (se ejecuta en 0.994 segundos):

 00000000004004fd <_ZL3addRKiS0_.isra.0>: 4004fd: 8d 04 37 lea eax,[rdi+rsi*1] 400500: c3 

un límite de 256 bytes corta add() justo en el medio y ni add() ni el bucle están alineados. Sorpresa, sorpresa, ¡este es el caso más lento!

En caso de que gcc-4.7.3 -Os (se ejecute en 0.822 segundos), el límite de 256 bytes solo corta en una sección fría (pero ni el bucle ni add() se cortan):

 00000000004004fa <_ZL3addRKiS0_.isra.0>: 4004fa: 8d 04 37 lea eax,[rdi+rsi*1] 4004fd: c3 ret [...] 40051a: e8 db ff ff ff call 4004fa <_ZL3addRKiS0_.isra.0> 

Nada está alineado, y la llamada a add() tiene que saltar sobre el límite de 256 bytes. Este código es el segundo más lento.

En caso de que gcc-4.6.4 -Os (se ejecute en 0.709 segundos), aunque nada está alineado, la llamada a add() no tiene que saltar sobre el límite de 256 bytes y el objective está exactamente a 32 bytes de distancia:

  4004f2: e8 db ff ff ff call 4004d2 <_ZL3addRKiS0_.isra.0> 4004f7: 01 c3 add ebx,eax 4004f9: ff cd dec ebp 4004fb: 75 ec jne 4004e9 <_ZL4workii+0x13> 

Este es el más rápido de los tres. Por qué el límite de 256 bytes es especial en su máquina, dejaré que él lo resuelva. No tengo ese procesador.

Ahora, en mi máquina no obtengo este efecto de frontera de 256 bytes. Solo la función y la alineación de bucle se activan en mi máquina. Si paso g++ -O2 -falign-functions=16 -falign-loops=16 , todo vuelve a la normalidad: siempre obtengo el caso más rápido y el tiempo ya no es sensible al -fno-omit-frame-pointer . Puedo pasar g++ -O2 -falign-functions=32 -falign-loops=32 o múltiplos de 16, el código tampoco es sensible a eso.

Noté por primera vez en 2009 que gcc (al menos en mis proyectos y en mis máquinas) tienen la tendencia a generar código notablemente más rápido si optimizo para el tamaño (-Os) en lugar de la velocidad (-O2 o -O3) y me he estado preguntando desde entonces por qué.

Una posible explicación es que tenía puntos de acceso que eran sensibles a la alineación, al igual que el de este ejemplo. Al jugar con las banderas (pasando -Os lugar de -O2 ), esos puntos de acceso se alinearon por casualidad y el código se hizo más rápido. No tuvo nada que ver con optimizar el tamaño: fueron por puro accidente que los puntos de acceso se alinearon mejor. A partir de ahora, verificaré los efectos de la alineación en mis proyectos.

Ah, y una cosa más. ¿Cómo pueden surgir esos puntos conflictivos, como el que se muestra en el ejemplo? ¿Cómo puede fallar la creación de una función tan pequeña como add() ?

Considera esto:

 // add.cpp int add(const int& x, const int& y) { return x + y; } 

y en un archivo separado:

 // main.cpp int add(const int& x, const int& y); const int LOOP_BOUND = 200000000; __attribute__((noinline)) static int work(int xval, int yval) { int sum(0); for (int i=0; i 

y comstackdo como: g++ -O2 add.cpp main.cpp .

¡gcc no add() !

Eso es todo, es tan fácil crear puntos de acceso no intencionados como el que está en el OP. Por supuesto, es en parte culpa mía: gcc es un excelente comstackdor. Si comstack lo anterior como: g++ -O2 -flto add.cpp main.cpp , es decir, si realizo la optimización de tiempo de enlace, ¡el código se ejecuta en 0.19s!

(La alineación está inhabilitada artificialmente en el OP, por lo tanto, el código en el PO fue 2 veces más lento).

Estoy agregando esta post-aceptación para señalar que se han estudiado los efectos de la alineación en el rendimiento general de los progtwigs, incluidos los grandes. Por ejemplo, este artículo (y creo que una versión de esto también apareció en CACM) muestra cómo el orden de enlace y los cambios en el tamaño del entorno de SO por sí solos fueron suficientes para cambiar el rendimiento de manera significativa. Lo atribuyen a la alineación de “bucles calientes”.

Este documento, titulado “Producir datos incorrectos sin hacer nada obviamente mal!” dice que el sesgo experimental inadvertido debido a las diferencias casi incontrolables en los entornos de ejecución del progtwig probablemente hace que muchos resultados de referencia carezcan de significado.

Creo que estás encontrando un ángulo diferente en la misma observación.

Para el código de rendimiento crítico, este es un buen argumento para los sistemas que evalúan el entorno durante la instalación o el tiempo de ejecución y eligen la mejor opción local entre las versiones optimizadas de las rutinas clave.

Creo que puedes obtener el mismo resultado que lo que hiciste:

Agarré el ensamblaje para -O2 y uní todas sus diferencias en el ensamblaje para -Os excepto las líneas .p2align:

… usando -O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1 . He estado comstackndo todo con estas opciones, que eran más rápidas que simple -O2 cada vez que me molestaba en medir, durante 15 años.

Además, para un contexto completamente diferente (incluido un comstackdor diferente), noté que la situación es similar : la opción que se supone que “optimiza el tamaño del código en lugar de la velocidad” se optimiza para el tamaño y la velocidad del código.

Si creo que es correcto, estos son rellenos para la alineación de la stack.

No, esto no tiene nada que ver con la stack, los NOP que se generan de manera predeterminada y que las opciones -falign – * = 1 previenen la alineación del código.

De acuerdo con ¿Por qué GCC pad funciona con NOPs? se hace con la esperanza de que el código se ejecute más rápido, pero aparentemente esta optimización resultó contraproducente en mi caso.

¿Es el relleno el culpable en este caso? ¿Porque y como?

Es muy probable que el relleno sea el culpable. La razón por la que se considera que el relleno es necesario y es útil en algunos casos es que el código generalmente se capta en líneas de 16 bytes (consulte los recursos de optimización de Agner Fog para conocer los detalles, que varían según el modelo de procesador). Alinear una función, bucle o etiqueta en un límite de 16 bytes significa que aumentan estadísticamente las posibilidades de que se necesiten menos líneas para contener la función o el bucle. Obviamente, es contraproducente porque estos NOP reducen la densidad del código y, por lo tanto, la eficacia de la caché. En el caso de bucles y tags, los NOP incluso pueden necesitar ejecutarse una vez (cuando la ejecución llega normalmente al bucle / etiqueta, en lugar de a un salto).

Si su progtwig está limitado por el caché CODE L1, la optimización del tamaño comienza a pagarse de repente.

La última vez que revisé, el comstackdor no es lo suficientemente inteligente como para resolver esto en todos los casos.

En su caso, -O3 probablemente genere el código suficiente para dos líneas de caché, pero -Os cabe en una línea de caché.

De ninguna manera soy un experto en esta área, pero parece recordar que los procesadores modernos son bastante sensibles cuando se trata de predicción de twigs . Los algoritmos utilizados para predecir las twigs son (o al menos volvieron en los días en que escribí el código de ensamblador) en función de varias propiedades del código, incluida la distancia de un objective y la dirección.

El escenario que viene a la mente es pequeños bucles. Cuando la bifurcación retrocedía y la distancia no era demasiado larga, la predicción de bifurcación se estaba optimizando para este caso, ya que todos los bucles pequeños se hacen de esta manera. Las mismas reglas pueden entrar en juego cuando intercambias la ubicación de add y work en el código generado o cuando la posición de ambas cambia ligeramente.

Dicho esto, no tengo idea de cómo verificar eso y solo quería que supieras que esto podría ser algo que quieras investigar.