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

performance assembly (6)

Noté por primera vez en 2009 que GCC (al menos en mis proyectos y en mis máquinas) tiene la tendencia de 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 sido 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 necesitan 0.38 s para ejecutar este programa, y 0.44 s si se compila con -O2 o -O2 . Estos tiempos se obtienen de manera 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 ensamblado generado con -Os y -O2 .

Desafortunadamente, mi comprensión del ensamblaje es muy limitada, por lo 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 , el resultado here . Este código aún se ejecuta en 0.38s y la única diferencia es el material .p2align .

Si adivino correctamente, estos son rellenos para la alineación de la pila. Según ¿Por qué el GCC pad funciona con los NOP? Se hace con la esperanza de que el código se ejecute más rápido, pero al parecer esta optimización fracasó en mi caso.

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

El ruido que hace prácticamente imposibilita las micro optimizaciones de temporización.

¿Cómo puedo asegurarme de que tales alineaciones fortuito / desafortunadas accidentales no interfieran cuando hago microoptimizaciones (no relacionadas con la alineación de la pila) en el código fuente de C o C ++?

ACTUALIZAR:

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

-Os habilita todas las optimizaciones -O2 [pero] -Os deshabilita los siguientes indicadores de optimización:
-falign-functions -falign-jumps -falign-loops <br/> -falign-labels -freorder-blocks -freorder-blocks-and-partition <br/> -fprefetch-loop-arrays <br/>

Por lo tanto, casi parece un problema de alineación (errónea).

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

ACTUALIZACIÓN 2:

Podemos sacar -Os fuera de la imagen. Los siguientes tiempos se obtienen compilando 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

A mí me parece que la distancia de add() desde el sitio de llamadas importa mucho. He intentado perf , pero la salida de perf stat y 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 nos estancamos en la llamada a add() en el caso lento.

He examinado todo lo que se 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 se correlacionara tan claramente. (La comparación stalled-cycles-frontend de los stalled-cycles-frontend para diferentes ejecutables no tiene sentido para mí).

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

Creo que puedes obtener el mismo resultado que hiciste:

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

... utilizando -O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1 . He estado compilando todo con estas opciones, que fueron más rápidas que el -O2 simple cada vez que me -O2 en medir, durante 15 años.

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

Si adivino correctamente, estos son rellenos para la alineación de la pila.

No, esto no tiene nada que ver con la pila, los NOP que se generan de forma predeterminada y las opciones -falign - * = 1 prevent son para la alineación del código.

Según ¿Por qué el GCC pad funciona con los NOP? Se hace con la esperanza de que el código se ejecute más rápido, pero aparentemente esta optimización fracasó 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 normalmente se obtiene 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 del procesador). Alinear una función, un bucle o una etiqueta en un límite de 16 bytes significa que las posibilidades aumentan estadísticamente de que se necesitará una línea menos 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 eficiencia del caché. En el caso de los bucles y la etiqueta, los NOP pueden incluso necesitar ejecutarse una vez (cuando la ejecución llega al bucle / etiqueta normalmente, a diferencia de un salto).

Estoy agregando esta aceptación posterior para señalar que se han estudiado los efectos de la alineación en el rendimiento general de los programas, incluidos los grandes. Por ejemplo, este artículo (y creo que una versión de este también apareció en CACM) muestra cómo los cambios en el orden de los enlaces y el tamaño del entorno del sistema operativo por sí solos fueron suficientes para cambiar significativamente el rendimiento. Ellos atribuyen esto a la alineación de "hot loops".

Este artículo, titulado "¡Producir datos incorrectos sin hacer nada obviamente malo!" dice que un sesgo experimental inadvertido debido a diferencias casi incontrolables en los entornos de ejecución de programas probablemente hace que muchos resultados de referencia no tengan sentido.

Creo que te encuentras con un ángulo diferente en la misma observación.

Para el código de rendimiento crítico, este es un argumento bastante bueno para los sistemas que evalúan el entorno en el momento de la instalación o la ejecución y eligen el mejor local entre las versiones optimizadas de manera diferente de las rutinas clave.

Mi colega me ayudó a encontrar una respuesta plausible a mi pregunta. Notó la importancia del límite de 256 bytes. No está registrado aquí y me alentó 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 las banderas -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 intentamos alinearlos con 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 (troncal) con -O3 hace la alineación apropiada y el código generado no muestra este comportamiento extraño.

Por supuesto, si se realiza una alineación inadecuada, empeora las cosas. Una alineación innecesaria / incorrecta solo consume bytes sin razón y potencialmente aumenta las fallas de caché, etc.

El ruido que hace prácticamente imposibilita las micro optimizaciones de temporización.
¿Cómo puedo asegurarme de que tales alineaciones fortuito / desafortunadas accidentales no interfieran cuando realizo microoptimizaciones (no relacionadas con la alineación de la pila) en los 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 XX cortes de límite de byte add() en el medio ( XX depende de la máquina).
si la llamada a add() tiene que saltar sobre un límite de XX byte y el objetivo no está alineado.
si add() no está alineado.
si el bucle no está alineado

Los primeros 2 son maravillosamente visibles en los códigos y resultados que Marat Dukhan publicó amablemente . 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 corte de límite de 256 bytes add() justo en el medio y ni add() ni el bucle está alineado. Sorpresa, sorpresa, este es el caso más lento!

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

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>

No hay nada 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 no haya nada alineado, la llamada a add() no tiene que saltar por encima del límite de 256 bytes y el objetivo se encuentra 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, lo dejaré para que él lo descubra. No tengo tal procesador.

Ahora, en mi máquina no obtengo este efecto de límite de 256 bytes. Sólo la función y la alineación del bucle se activan en mi máquina. Si paso g++ -O2 -falign-functions=16 -falign-loops=16 entonces todo vuelve a la normalidad: siempre obtengo el caso más rápido y el tiempo ya no es sensible a la -fno-omit-frame-pointer . Puedo pasar g++ -O2 -falign-functions=32 -falign-loops=32 o cualquier múltiplo 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) tiene la tendencia de 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 explicación probable es que tenía puntos calientes que eran sensibles a la alineación, como el de este ejemplo. Al meterse con las banderas (pasando -Os lugar de -O2 ), esos hotspots se alinearon de manera afortunada por accidente y el código se hizo más rápido. No tuvo nada que ver con la optimización del tamaño: fueron por pura casualidad que los hotspots se alinearon mejor. A partir de ahora, comprobaré los efectos de la alineación en mis proyectos.

Ah, y una cosa más. ¿Cómo pueden surgir tales puntos de acceso, como el que se muestra en el ejemplo? ¿Cómo puede fallar la add() 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<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; }

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

gcc no add() línea add() !

Eso es todo, es tan fácil crear involuntariamente zonas interactivas como la del OP. Por supuesto, en parte es mi culpa: gcc es un excelente compilador. Si compila lo anterior como: g++ -O2 -flto add.cpp main.cpp , es decir, si realizo la optimización del tiempo de enlace, ¡el código se ejecuta en 0.19s!

(La inclusión se inhabilita artificialmente en el OP, por lo tanto, el código en el OP fue 2 veces más lento).

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

El escenario que viene a la mente es pequeños bucles. Cuando la rama iba hacia atrás y la distancia no estaba demasiado lejos, la predicción de la rama se estaba optimizando para este caso, ya que todos los pequeños bucles 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 ambos cambia ligeramente.

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

Por defecto, los compiladores optimizan el procesador "promedio". Dado que los diferentes procesadores favorecen las diferentes secuencias de instrucciones, las optimizaciones del compilador habilitadas por -O2 podrían beneficiar al procesador promedio, pero disminuir el rendimiento de su procesador particular (y lo mismo se aplica a -Os ). Si prueba el mismo ejemplo en diferentes procesadores, encontrará que algunos de ellos se benefician del -O2 mientras que otros son más favorables a -Os optimizaciones de -Os .

Aquí están los resultados para time ./test 0 0 en varios procesadores (tiempo de usuario reportado):

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 optimizaciones desventajosas pidiéndole 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 ahora, no tengo 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

Ensamblado 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

Si su programa está limitado por el caché del CÓDIGO L1, entonces la optimización para el tamaño de repente comienza a pagar.

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

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