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.


Answers

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

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.


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.


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é.


Ya hay algunas buenas respuestas a esta pregunta, pero para completar, quisiera señalar que la sección aplicable del estándar C es 5.1.2.2.3 / 15 (que es la misma que la sección 1.9 / 9 en el Estándar de C ++ 11). Esta sección establece que los operadores solo pueden reagruparse si son realmente asociativos o conmutativos.





c++ c performance gcc assembly